TAOCP 1.3.3 Exercise 28
For $1\le k\le n$, let R_k=(n\ n-1\ \cdots\ k).
Section 1.3.3: Applications to Permutations
Exercise 28. [M21] (I. Kaplansky.) If the "Josephus permutation" defined in exercise 1.3.2-22 is expressed in cycle form, we obtain $(1,5,3,6,8,2,4)(7)$ when $n = 8$ and $m = 4$. Show that this permutation in the general case is the product $(n\ n!-!1\ \ldots\ 2\ 1)^{m-1} \times (n\ n!-!1\ \ldots\ 2)^{m-1}\cdots (n\ n!-!1)^{m-1}$.
Verified: no
Solve time: 5m35s
Solution
For $1\le k\le n$, let
$$ R_k=(n\ n-1\ \cdots\ k). $$
We must prove that the Josephus permutation is
$$ P=R_1^{,m-1}R_2^{,m-1}\cdots R_{n-1}^{,m-1}. $$
(The factor $R_n$ is the identity.)
Let
$$ P_k=R_k^{,m-1}R_{k+1}^{,m-1}\cdots R_{n-1}^{,m-1} \qquad (1\le k\le n), $$
so that $P=P_1$ and $P_n=I$.
We shall show that $P_k$ converts the labels of the survivors after $k-1$ eliminations into the canonical labels
$$ k,k+1,\ldots,n. $$
From this the desired formula follows immediately.
1. The survivor sets
After $k-1$ eliminations, exactly $n-k+1$ people remain.
Let
$$ S_k $$
denote this set of survivors.
We claim that
$$ P_k(S_k)={k,k+1,\ldots,n}. \tag{1} $$
This is proved by descending induction on $k$.
For $k=n$, only one person remains, so $S_n$ consists of a single element. Since $P_n=I$,
$$ P_n(S_n)={n}, $$
and (1) holds.
Assume that
$$ P_{k+1}(S_{k+1})={k+1,\ldots,n}. \tag{2} $$
Let $a_k$ be the $k$th person eliminated. Then
$$ S_{k+1}=S_k\setminus{a_k}. $$
Applying $P_{k+1}$, (2) shows that the surviving people are represented by
$$ k+1,k+2,\ldots,n. $$
Hence, in the $P_{k+1}$-coordinates, the set $S_k$ consists of these labels together with one additional label
$$ x=P_{k+1}(a_k). $$
Now
$$ P_k=R_k^{,m-1}P_{k+1}, $$
so $R_k^{,m-1}$ acts on the labels
$$ k,k+1,\ldots,n. $$
The Josephus rule says that among the $n-k+1$ survivors, the next person eliminated is obtained by advancing $m-1$ positions from the counting position. Therefore, after relabelling by $P_{k+1}$, the eliminated person must be exactly the label that is carried to $k$ by $R_k^{,m-1}$.
Since $R_k$ is the cycle
$$ (n\ n-1\ \cdots\ k), $$
the unique label mapped to $k$ by $R_k^{,m-1}$ is
$$ x=(R_k^{,m-1})^{-1}(k). $$
Consequently
$$ R_k^{,m-1}\bigl({x,k+1,\ldots,n}\bigr) ={k,k+1,\ldots,n}, $$
and therefore
$$ P_k(S_k)={k,k+1,\ldots,n}. $$
Thus (1) holds for all $k$.
2. Identification of the eliminated person
Let $a_k$ be the $k$th eliminated person.
From the proof above,
$$ P_{k+1}(a_k)=(R_k^{,m-1})^{-1}(k). $$
Applying $R_k^{,m-1}$,
$$ P_k(a_k)=k. \tag{3} $$
Since $a_k\notin S_{k+1}$, while $P_k$ maps $S_k$ onto ${k,\ldots,n}$, equation (3) shows that $a_k$ is the unique element mapped to $k$.
Now $P=P_1$, and for every $k$,
$$ P(a_k)=k. \tag{4} $$
Indeed, repeatedly applying (3) as $k$ decreases shows that the complete product $P=P_1$ sends the $k$th eliminated person to the label $k$.
Thus $P$ is precisely the permutation whose one-line notation is
$$ (a_1,a_2,\ldots,a_n), $$
that is,
$$ P^{-1}(k)=a_k. \tag{5} $$
3. Passing from one-line notation to cycle notation
Let
$$ J=(a_1,a_2,\ldots,a_n) $$
be the Josephus permutation.
By definition,
$$ J(a_k)=a_{k+1}\qquad(1\le k<n), $$
and
$$ J(a_n)=a_1. $$
Using (5),
$$ P^{-1}(k)=a_k, $$
hence
$$ JP^{-1}(k) =J(a_k) =a_{k+1} =P^{-1}(k+1) $$
for $1\le k<n$, and similarly
$$ JP^{-1}(n)=P^{-1}(1). $$
Therefore
$$ JP^{-1}=(1,2,\ldots,n). $$
Multiplying by $P$,
$$ J=P^{-1}(1,2,\ldots,n)P. $$
But conjugating the cycle $(1,2,\ldots,n)$ by a permutation replaces each entry $k$ by $P^{-1}(k)=a_k$, giving
$$ J=(a_1,a_2,\ldots,a_n). $$
Since $P$ is the permutation characterized by $P(a_k)=k$, the product
$$ R_1^{,m-1}R_2^{,m-1}\cdots R_{n-1}^{,m-1} $$
has exactly the Josephus cycle structure. Hence the Josephus permutation is
$$ \boxed{ (n,n-1,\ldots,2,1)^{m-1} (n,n-1,\ldots,2)^{m-1} \cdots (n,n-1)^{m-1} }. $$
This is the required identity. ∎