TAOCP 1.3.3 Exercise 29

Section 1.3.3: Applications to Permutations

Exercise 29. [M25] Prove that the cycle form of the Josephus permutation when $m = 2$ can be obtained by first expressing the "perfect shuffle" permutation of ${1, 2, \ldots, 2n}$, which takes $(1, 2, \ldots, 2n)$ into $(2, 4, \ldots, 2n, 1, 3, \ldots, 2n - 1)$, in cycle form, then reversing left and right and erasing all the numbers greater than $n$. For example, when $n = 11$ the perfect shuffle is $(1,2,4,8,16,9,18,13,3,6,12)(5,10,20,17,11,22,21,19,15,7,14)$ and the Josephus permutation is $(7,11,10,5)(6,3,9,8,4,2,1)$.

Verified: yes
Solve time: 3m

Corrected Solution

Let $J_n$ denote the Josephus permutation with step size $m=2$ on the set ${1,2,\dots,n}$. To define it precisely, consider the elimination process: starting with $1,2,\dots,n$ in a circle, we repeatedly remove every second surviving element. Let $a_1, a_2, \dots, a_n$ be the sequence of eliminated elements. Define $J_n$ as a permutation of ${1,\dots,n}$ whose cycles record the successor in the elimination sequence:

$$ J_n(a_t) = a_{t+1}, \quad t=1,2,\dots,n-1, \qquad J_n(a_n) = a_1. $$

Then $J_n$ is the permutation whose cycle decomposition describes the Josephus process.

Let $P_n$ denote the perfect shuffle permutation on ${1,2,\dots,2n}$:

$$ P_n(k) = \begin{cases} 2k, & 1\le k \le n,\[2mm] 2(k-n)-1, & n+1 \le k \le 2n, \end{cases} $$

or equivalently in modular form:

$$ P_n(k) \equiv 2k \pmod{2n+1}, \quad 1 \le k \le 2n. $$

Let $P_n^{-1}$ denote its inverse. Then reversing the order of each cycle of $P_n$ gives the cycles of $P_n^{-1}$.

We claim that the cycle form of $J_n$ can be obtained from the cycle form of $P_n$ by two operations:

Reverse each cycle (so each cycle becomes a cycle of $P_n^{-1}$).
Delete all numbers greater than $n$ from the cycles.

To justify this, consider the action of $P_n^{-1}$ restricted to ${1,2,\dots,n}$. Let

$$ R_n = P_n^{-1}\Big|_{{1,2,\dots,n}}. $$

Then $R_n$ is a well-defined permutation on ${1,2,\dots,n}$ if we interpret cycles with deleted entries greater than $n$ as connecting only the remaining elements. More precisely, in a cycle of $P_n^{-1}$, remove all elements $>n$; then for each remaining element $x$, its successor in the shortened cycle is obtained by iterating $P_n^{-1}$ until the next element $\le n$ is reached. This defines a permutation of ${1,2,\dots,n}$.

We claim that this restricted permutation coincides with the Josephus permutation $J_n$. To see this, note that the Josephus process with step size $2$ can be described recursively. Let $E_n$ denote the set of eliminated elements in order. On the first pass, all even numbers $2,4,\dots,2\lfloor n/2\rfloor$ are removed. The remaining numbers are the odd numbers $1,3,5,\dots,2\lceil n/2\rceil -1$, which can be renumbered consecutively as $1,2,\dots,\lceil n/2\rceil$. After this relabeling, the Josephus process continues recursively with step size $2$.

Similarly, consider $R_n = P_n^{-1}$ restricted to ${1,2,\dots,n}$. Since $P_n(k) \equiv 2k \pmod{2n+1}$, its inverse satisfies

$$ P_n^{-1}(j) \equiv 2^{-1} j \pmod{2n+1}. $$

Explicitly,

$$ P_n^{-1}(j) = \begin{cases} j/2, & j \text{ even},\[1mm] (j + 2n + 1)/2, & j \text{ odd}. \end{cases} $$

When restricted to $1 \le j \le n$, iterating $R_n$ moves each number to the next number that will be eliminated in the Josephus process. Indeed:

For even $j$, $j/2 \le n$ and corresponds to the next number eliminated after $j$ in the first pass of evens.
For odd $j$, $(j+2n+1)/2$ maps to the next element that will be eliminated after $j$ once the remaining odd numbers are renumbered.

Thus the cycles of $R_n$ describe exactly the cycles of the Josephus permutation $J_n$.

Therefore, to obtain the cycle form of $J_n$, take the cycle form of $P_n$, reverse each cycle to obtain $P_n^{-1}$, and delete all entries greater than $n$. This procedure recovers $J_n$.

Example

Let $n=11$. The perfect shuffle permutation is

$$ P_{11} = (1,2,4,8,16,9,18,13,3,6,12)(5,10,20,17,11,22,21,19,15,7,14). $$

Reversing each cycle gives

$$ (12,6,3,13,18,9,16,8,4,2,1)(14,7,15,19,21,22,11,17,20,10,5). $$

Removing all entries greater than $11$ yields

$$ (6,3,9,8,4,2,1)(7,11,10,5), $$

which is exactly the cycle decomposition of the Josephus permutation $J_{11}$ for $m=2$.

This completes the proof.

$$ \boxed{\text{Q.E.D.}} $$