Counting Gilbreath Permutations + Ultimate Principle — Magical Mathematics

Gilbreath Principle in Action

THEOREM. The Ultimate Gilbreath Principle. For a permutation $π$ of ${1, 2, 3, \dots, N}$ , the following four properties are equivalent:

$π$ is a Gilbreath permutation.

For each $j$ , the top $j$ cards ${π (1), π (2), π (3), \dots, π (j)}$ are distinct modulo $j$ .

For each $j$ and $k$ with $k j \leq N$ , the $j$ cards $(π ((k - 1) j + 1)$ , $π ((k - 1) j + 2), \dots, π (k j)}$ are distinct modulo $j$ .

For each $j$ , the top $j$ cards are consecutive in $1, 2, 3, \dots, N$ .

The Gilbreath Principle is a fascinating mathematical property that works with sequences of numbers.

Deal off any number of cards from a deck arranged 1, 2, …, N and riffle shuffle the two piles: the Gilbreath Principle states that after the riffle shuffle, adjacent pairs of cards will always contain one card from each of the original piles.

Session notes

Chapter 5 of Magical Mathematics ends with counting Gilbreath permutations and the Ultimate Gilbreath Principle, their complete characterisation.

0:36 No new effects. The book’s Gilbreath effects are the lie detector and the poker hands; “A little bit of magic” is a de Bruijn variation, left open-ended rather than a concrete trick. YouTube has many more Gilbreath effects, often with sleight of hand, which we will not cover.

3:42 A Gilbreath permutation: start from $1, 2, \dots, n$ (left is top), deal off $j$ cards reversing them, then riffle preserving internal order. How many exist, and how to recognise one?

5:48 The book states $2^{n - 1}$ . My binary-labelling attempt failed: not every bit string is a valid riffle. Pratik: with 8 dealt from 20, there are $(8 20)$ riffles.

10:32 Saraswati: there are $(k n)$ Gilbreath permutations with $k$ cards dealt (positions chosen, order forced). Summing over $k$ gives $2^{n}$ , twice the book’s count.

12:44 The extreme cases, identity and full reversal, are distinct and not the culprit, and there is no obvious $n /2$ symmetry.

15:51 Checking $n = 3$ by hand: dealing off one card gives 123, 213, 231; dealing off two gives 213, 231, 321 and repeats. Four permutations, not eight; each appears exactly twice.

21:25 The card at the cut can be the last of the dealt pile or the first of the rest; the outcome is the same either way. A Gilbreath permutation decomposes into a decreasing run and an increasing run sharing exactly one element at the junction (Saraswati). The true count is $\frac{1}{2} \sum_{k} (k n) = 2^{n - 1}$ .

24:44 The book’s bijection: choose $S = {s_{1} < \dots < s_{j}} \subseteq {2, \dots, n}$ ; place $j, \dots, 1$ at positions $s_{1}, \dots, s_{j}$ and fill the rest with $j + 1, \dots, n$ in order. For $n = 5$ , $S = {3, 5}$ : positions 3 and 5 receive 2 and 1; the remaining positions receive 3, 4, 5. With $S = {2, 3, 4, 5}$ one gets 5 4 3 2 1, the full reversal, which is why dealing off all $n$ cards needs no separate case.

29:27 Any Gilbreath permutation’s dealt-card positions recover an $S$ that regenerates it, and every $S$ describes a valid riffle. Excluding position 1 from $S$ forces the junction card into the undealt pile and resolves the double-count. Hence $2^{n - 1}$ .

37:19 Example: $543627189$ arises from dealing off five cards and from dealing off four; the maximal decreasing run from the top and the maximal increasing run share one element (Pratik: like a longest-subsequence decomposition). The convention disambiguates.

43:35 Pratik: the overcount argument and the book’s subset argument are morally the same proof.

44:37 Roughly $1/ n$ of Gilbreath permutations are cyclic; cyclic ones correspond to zeros of a recursively defined polynomial family, which is where the Mandelbrot set enters the chapter title. This is stated with references, not proved.

45:38 The Ultimate Gilbreath Principle (statement above): we covered properties 2, 3, and 4. Property 4, which I found cutest: the top $j$ cards form a consecutive set of integers for every $j$ .

47:05 Example, $n = 9$ : a Gilbreath outcome whose top five are 5 4 6 7 8, as a set ${4, \dots, 8}$ , so the sixth card must be 3 or 9. It was 3, so the seventh must be 2 or 9.

49:42 Property 4 holds because you can replay the riffle backwards. The top run of the outcome comes from one pile, and the top of the other pile continues exactly where that run left off, because the dealt pile was reversed. Each drop from the dealt pile extends the top- $j$ set downward; each drop from the other pile extends it upward. Saraswati: induction on the drops; Pratik agreed it is always consecutive.

52:52 Property 4 implies property 2 immediately ( $j$ consecutive integers have distinct residues mod $j$ ); property 3 follows for sliding blocks.

54:58 For the converse, a participant argued via maximal consecutive chunks $A_{1}, A_{2}, \dots$ from the dealt pile and $B_{1}, B_{2}, \dots$ from the rest: the first elements of $A_{1}$ and $B_{1}$ are adjacent integers (as in 6 5 4 followed by 7), which lets you reverse-engineer the riffle. Fine print left open.

1:01:07 Not covered: applications citing Knuth (disk storage) and Penrose (aperiodic tilings); de Bruijn’s variant with two equal halves (say spades and diamonds alternating against clubs and hearts alternating) where a free cut after the riffle still guarantees one of two properties; two-dimensional analogues, noted as wide open.

1:04:19 Up next: chapter 6, perfect shuffles and other shuffles, with JavaScript standing in for dexterity.

To think about

List the four Gilbreath permutations of ${1, 2, 3}$ and the eight of ${1, 2, 3, 4}$ ; verify the count.
Write out the bijection with subsets of ${2, \dots, n}$ carefully.
Prove property 4 by induction on the drops of the riffle.
Prove that property 4 implies the permutation is Gilbreath.
Count cyclic Gilbreath permutations for small $n$ ; compare with $2^{n - 1} / n$ .

An interactive demo from the original page is parked while the card-interactives library is built; the text above stands on its own.