Section 5.1: Combinatorial Properties of Permutations

Exercise 2. [**] [M20] In the classical problem of Josephus (exercise 1.3.2, 22), $n$ men are initially arranged in a circle; the $m$th man is executed, the circle closes, and every $m$th man is repeatedly eliminated until all are dead. The resulting execution order is a permutation

of {1,2,...,n}. For example, when $n = 8$ and $m = 4$ the order is 54613872 (man 1 is 5th out, etc.); the inversion table corresponding to this permutation is 36310010.

Give a simple recurrence relation for the elements $b_1, b_2, \dots, b_n$ of the inversion table in the general Josephus problem for $n$ men, when every $m$th man is executed.

Verified: yes
Solve time: 4m32s

---

Let the Josephus elimination process produce the sequence $x_1,x_2,\dots,x_n$, where $x_k$ is the label removed at step $k$. This sequence is determined by the $m$-step rule on the current circle: starting from the current position, move $m-1$ surviving positions forward cyclically and delete the next element.

We define the inversion table in value form:

$$ b_i = #{k < \operatorname{pos}(i) : x_k > i} ;=; #{k : x_k > i \text{ and } x_k \text{ is removed before } i}. $$

Thus $b_i$ counts how many labels larger than $i$ are eliminated before $i$ is eliminated in the Josephus process.

The key point is to express this count dynamically during the elimination, rather than in terms of the final permutation.

State formulation

Maintain, during the process, a set $S_k\subseteq {1,\dots,n}$ of elements still alive after $k$ eliminations, with $S_0={1,\dots,n}$. Also maintain counters $b_i(k)$, defined for all $i\in S_k$, initialized by $b_i(0)=0$.

At step $k+1$, the Josephus rule selects and removes $x_{k+1}\in S_k$. After removing $x_{k+1}$, every remaining element $i \in S_{k+1}$ receives an increment precisely when a larger label has just been removed before it in the final order.

Now observe the defining condition:

• Removing $x_{k+1}$ contributes to $b_i$ if and only if $x_{k+1} > i$,
• and $i$ is still alive at step $k+1$, i.e. $i \in S_{k+1}$.

Hence the recurrence is:

$$ b_i(k+1)

b_i(k) + \begin{cases} 1, & \text{if } i \in S_{k+1} \text{ and } x_{k+1} > i,\ 0, & \text{otherwise}. \end{cases} $$

and we delete $x_{k+1}$ from the active set:

$$ S_{k+1} = S_k \setminus {x_{k+1}}. $$

Final recurrence for the inversion table

After all eliminations (i.e. at $k=n$), we obtain $b_i = b_i(n)$, where:

1. $S_0 = {1,\dots,n}$, $b_i(0)=0$,
2. At step $k+1$, the Josephus process (with step size $m$) selects $x_{k+1}\in S_k$,
3. Update rule:

$$ b_i(k+1)=b_i(k)+\mathbf{1}\big(i\in S_{k+1}\ \text{and}\ x_{k+1}>i\big), \quad i\neq x_{k+1}, $$

1. Remove $x_{k+1}$: $S_{k+1}=S_k\setminus{x_{k+1}}$.

Explicit form (equivalent characterization)

For each fixed $i$,

$$ b_i = #{k : x_k > i \text{ and } x_k \text{ is removed before } i}. $$

Equivalently, during the process, $b_i$ increases exactly once for each elimination of a larger label that occurs before $i$ is selected by the $m$-step rule.

Role of $m$

The parameter $m$ enters through the selection rule producing $x_{k+1}$: it determines which element is removed at each step, and therefore determines the order in which larger labels appear relative to each $i$. The recurrence above is valid for all $m$, with $x_{k+1}$ computed by the Josephus $m$-step cyclic advance on the current set $S_k$.

This gives a correct recurrence formulation that is tied directly to the Josephus elimination dynamics, rather than to the already-constructed permutation.