Permutation groups, applied: shuffles, box designs and a check digit that catches typos
A permutation is a rearrangement of n things. A permutation group is a set of rearrangements closed under doing one after another and under undoing. That is the whole definition from Gilbert's Modern Algebra with Applications, and it looks like pure bookkeeping until you ask three practical questions: how many times do I have to shuffle before the deck comes back, how many of these box designs are actually different, and how do I number my orders so a typo announces itself? Each one is a permutation group doing work. Every number below is computed on this page and brute-forced in Python.
1 · Orders: when does the deck come back?
Write a permutation as where each position goes. A perfect out-shuffle of 52 cards (cut in half, interleave exactly, top card stays on top) sends position 1 to 1, 2 to 3, 3 to 5, …, 27 to 2, 28 to 4. Follow each card until it returns to its seat and you get the permutation's cycles. The number of shuffles that restores the whole deck is the order of the permutation: the least common multiple of its cycle lengths, because every cycle has to come around at once.
Eight out-shuffles of a 52-card deck is the identity. The in-shuffle (top card moves down one) has a single 52-cycle and order 52. Same cards, same motion up to one card's width, and one of them is a party trick while the other is a mixing process. Nothing about the order is visible from the shuffle; you have to compute the cycles. The same arithmetic tells you the period of a crew rotation or a roll-stand sequence: write it as a permutation, take the cycles, take the lcm.
2 · Burnside: how many designs are really different?
An RSC has four side panels in a ring. Print each panel one of k colors. There are k⁴ colorings, but a box rotated a quarter turn is the same box, so the real count is the number of orbits under the rotation group C₄ (four rotations). If the box can also be flipped upside down (which reverses the ring), the group is the dihedral group D₄ with eight elements. Counting orbits by hand means listing and crossing out. Burnside's lemma does it with one sum:
number of orbits = (1/|G|) · Σ over g in G of (number of colorings g leaves unchanged)
= (1/|G|) · Σ over g in G of k^(number of cycles of g)A coloring is unchanged by g exactly when every cycle of g is one color, so each g contributes k to the power of its cycle count. For C₄ with two colors: the identity has 4 cycles (16), the quarter turns have 1 (2 each), the half turn has 2 (4). (16 + 2 + 4 + 2)/4 = 6. Here are all 16 colorings sorted into those six orbits, and the same for the other groups and for three colors.
Two colors: 6 designs whether or not you may flip. Three colors: 24 if you may only rotate, 21 if you may also flip, because three of the rotation-orbits are mirror images of each other. That is chirality showing up in a box plant, and it matters when the print has an orientation, which it always does. The second preset is the layout question: six die positions on a 2×3 sheet, each one a blank or waste; the sheet's symmetries are the Klein four-group (identity, a half turn, two flips), and 64 layouts collapse to 24 you would actually have to evaluate. On a real 6×10 layout the raw count is 2⁶⁰ and the lemma is the only way anyone counts.
3 · D₅: the check digit that catches transpositions
Order numbers get typed, read over the phone, and keyed from a label, and the two mistakes humans make are a wrong digit and two adjacent digits swapped. A check digit is a last digit computed from the rest so that both mistakes break it. The simplest scheme, make the digits sum to 0 mod 10, catches every wrong digit and no transpositions at all, because addition commutes: 3 + 7 = 7 + 3. Luhn's algorithm (credit cards) doubles every other digit and catches most transpositions, but not 09 ↔ 90. Jacobus Verhoeff's 1969 scheme catches all of both, and the trick is to replace addition with the multiplication of a non-commutative group of order 10: the dihedral group D₅, the symmetries of a pentagon. Five rotations, five reflections, and a reflection followed by a rotation is not a rotation followed by a reflection, which is exactly the property a transposition needs to trip over.
The scheme walks the digits from the right, applies a fixed permutation p (and its powers p², p³, …) to each digit by position, and multiplies the results together in D₅. A wrong digit changes one factor, and in a group that always changes the product. A swap of neighbors changes x·p(y) into y·p(x), and p was chosen so those are never equal when x ≠ y. There is nothing to tune and nothing probabilistic; the 100% in the table is a theorem, and the Python asserts it over three hundred random numbers and every error you can make in each of them.
4 · Cayley, in one paragraph
D₅ was defined geometrically, but on this page it is a 10 × 10 table, and each row of that table is a permutation of ten symbols. That is Cayley's theorem in miniature: every finite group is a group of permutations, acting on itself by multiplication. The rotation group of the box, the symmetry group of the sheet, the check-digit group, and the shuffle are all the same kind of object, which is why one eighty-line Python file handles all of them with one compose function.
The Python
perms.py: permutations as tuples, closure of generators, cycles and orders, Burnside against brute-force orbit enumeration, and the Verhoeff, Luhn and digit-sum schemes with the error catalog that scores them.
def compose(p, q): # (p * q)(i) = p[q[i]]: do q, then p
return tuple(p[q[i]] for i in range(len(p)))
def cycles(p):
seen, out = set(), []
for i in range(len(p)):
if i in seen: continue
c, j = [], i
while j not in seen:
seen.add(j); c.append(j); j = p[j]
out.append(tuple(c))
return out
def order(p): # lcm of the cycle lengths
return reduce(lambda a, b: a * b // gcd(a, b), (len(c) for c in cycles(p)), 1)
def generate(gens): # the group generated: close under composition
group, frontier = {identity(len(gens[0]))}, [identity(len(gens[0]))]
while frontier:
frontier = [x for g in frontier for h in gens for x in (compose(g, h), compose(h, g))
if x not in group and not group.add(x)]
return sorted(group)
def burnside(group, k): # orbits of k-colorings = average number of fixed colorings
return sum(k ** len(cycles(g)) for g in group) // len(group)
def verhoeff_check(digits): # multiply p^i(d_i) together in D5, from the right; return the inverse
c = 0
for i, d in enumerate(reversed(digits)):
c = D5[c][P[(i + 1) % 8][int(d)]]
return INV[c]