Permutation-Based Labeled Chip-Firing

Let me begin with labeled chip-firing on an infinite directed binary tree, where the root is at the top. Place 2n chips, labeled from 0 to 2n − 1, at the root. A move consists of choosing any two chips at the same vertex and firing them: the smaller chip goes to the left child, and the larger chip goes to the right child. For k ≥ 2, the k-ary version is exactly what you would guess. Start with kn chips, labeled from 0 to kn − 1, at the root. When a vertex fires, choose k chips and send them, from smallest to largest, to its k children from left to right. The process eventually stops. At that point, there is exactly one chip at every vertex n edges below the root. If we erase the labels, the final configuration is always the same. With the labels, however, our choices matter. Reading the chips on the final layer from left to right gives a permutation of the numbers from 0 to kn − 1. Let us play with eight chips, labeled 0 through 7, on a binary tree. Here is one particularly orderly…