Section 7.2.1.2: Generating All Permutations

Exercise 55. [M27] [M27] Consider the factorial ruler function ρ!(m) = max{k | m mod k! = 0}.

7.2.1.2 GENERATING ALL PERMUTATIONS 349 Let σk and τk be permutations of the nonnegative integers such that σj τk = τkσj whenever j ≤k. Let α0 and β0 be the identity permutation, and for m > 0 define αm = β− m−1τρ!(m)βm−1αm−1, βm = σρ!(m)βm−1. For example, if σk is the flip operation (1 k−1)(2 k−2) . . . = (0 k)ϕ(k) and if τk = (0 k), and if Algorithm E is started with aj = j for 0 ≤j < n, then αm and βm are the contents of a0 . . . an−1 and b0 . . . bn−1 after step E5 has been performed m times. a) Prove that β(n+1)!α(n+1)! = σn+1σ− n τn+1τ − n (βn!αn!)n+1. b) Use the result of (a) to establish the validity of Algorithm E.

Verified: no
Solve time: 4m23s

---

(a)

Define

$$ \gamma_m=\beta_m\alpha_m. $$

From

$$ \alpha_m=\beta_{m-1}^{-1}\tau_{\rho!(m)}\beta_{m-1}\alpha_{m-1}, \qquad \beta_m=\sigma_{\rho!(m)}\beta_{m-1}, $$

we obtain

$$ \begin{aligned} \gamma_m &=\beta_m\alpha_m\ &=\sigma_{\rho!(m)} \beta_{m-1} \beta_{m-1}^{-1} \tau_{\rho!(m)} \beta_{m-1} \alpha_{m-1}\ &=\sigma_{\rho!(m)}\tau_{\rho!(m)}\gamma_{m-1}. \end{aligned} $$

Hence

$$ \boxed{\gamma_m=L_m\gamma_{m-1}},\qquad L_m=\sigma_{\rho!(m)}\tau_{\rho!(m)}. $$

Since $\gamma_0=I$,

$$ \gamma_m=L_mL_{m-1}\cdots L_1, $$

where the factors are ordered from left to right in decreasing index, exactly as dictated by the recurrence.

Now divide the interval

$$ 1,\ldots,(n+1)! $$

into the blocks

$$ rn!+1,\ldots,(r+1)n!, \qquad 0\le r\le n. $$

We first determine the factorial ruler values inside a block.

Let $1\le t<n!$.

For every $k\le n$,

$$ k!\mid n!, $$

hence

$$ rn!\equiv0\pmod{k!}, $$

and therefore

$$ rn!+t\equiv t\pmod{k!}. $$

Thus

$$ k!\mid(rn!+t) \Longleftrightarrow k!\mid t. $$

Since $t<n!$, neither $t$ nor $rn!+t$ is divisible by $(n+1)!$. Indeed,

$$ 0<rn!+t<(r+1)n!\le(n+1)n!<(n+1)!. $$

Consequently no factorial larger than $n!$ divides either integer. Hence

$$ \boxed{\rho!(rn!+t)=\rho!(t)}, \qquad 1\le t<n!. $$

For the last element of a block,

$$ (r+1)n! $$

is divisible by $n!$. If $r<n$, then

$$ (r+1)n!<(n+1)!, $$

so it is not divisible by $(n+1)!$, and therefore

$$ \rho!((r+1)n!)=n. $$

For $r=n$,

$$ (r+1)n!=(n+1)!, $$

so

$$ \rho!((n+1)!)=n+1. $$

Now let $B_r$ denote the ordered left multiplier accumulated over the $r$-th block. Since multiplication is always on the left,

$$ \gamma_{(r+1)n!}=B_r\gamma_{rn!}, $$

where

$$ B_r= L_{(r+1)n!}, L_{(r+1)n!-1} \cdots L_{rn!+1}. $$

Using the identities for $\rho!$,

$$ B_r= \begin{cases} L_{n!}, L_{n!-1}\cdots L_1, & 0\le r<n, \[1ex] L_{(n+1)!}, L_{n!-1}\cdots L_1, & r=n. \end{cases} $$

Since

$$ \gamma_{n!}

L_{n!}\cdots L_1, $$

it follows that

$$ B_r=\gamma_{n!}, \qquad 0\le r<n. $$

For the last block,

$$ \begin{aligned} B_n &= L_{(n+1)!}, L_{n!}^{-1}\gamma_{n!}\ &= \sigma_{n+1}\tau_{n+1} (\sigma_n\tau_n)^{-1} \gamma_{n!}. \end{aligned} $$

Now

$$ (\sigma_n\tau_n)^{-1}

\tau_n^{-1}\sigma_n^{-1}. $$

Since

$$ \sigma_j\tau_k=\tau_k\sigma_j \qquad(j\le k), $$

we have

$$ \sigma_n^{-1}\tau_n^{-1}

\tau_n^{-1}\sigma_n^{-1}, \qquad \sigma_n^{-1}\tau_{n+1}

\tau_{n+1}\sigma_n^{-1}, $$

and therefore

$$ \begin{aligned} \sigma_{n+1}\tau_{n+1} (\sigma_n\tau_n)^{-1} &= \sigma_{n+1} \tau_{n+1} \tau_n^{-1} \sigma_n^{-1}\ &= \sigma_{n+1} \sigma_n^{-1} \tau_{n+1} \tau_n^{-1}. \end{aligned} $$

Hence

$$ B_n

\sigma_{n+1} \sigma_n^{-1} \tau_{n+1} \tau_n^{-1} \gamma_{n!}. $$

It remains to compute $\gamma_{rn!}$.

Since

$$ \gamma_{(r+1)n!}

B_r\gamma_{rn!}, $$

and $B_r=\gamma_{n!}$ for $0\le r<n$, we prove by induction on $r$ that

$$ \boxed{\gamma_{rn!}=(\gamma_{n!})^r}, \qquad 0\le r\le n. $$

For $r=0$,

$$ \gamma_0=I=(\gamma_{n!})^0. $$

Assume

$$ \gamma_{rn!}=(\gamma_{n!})^r $$

for some $r<n$. Then

$$ \begin{aligned} \gamma_{(r+1)n!} &= B_r\gamma_{rn!}\ &= \gamma_{n!}(\gamma_{n!})^r\ &= (\gamma_{n!})^{r+1}. \end{aligned} $$

This completes the induction.

Finally,

$$ \begin{aligned} \gamma_{(n+1)!} &= B_n\gamma_{nn!}\ &= \left( \sigma_{n+1}\sigma_n^{-1} \tau_{n+1}\tau_n^{-1} \gamma_{n!} \right) (\gamma_{n!})^n\ &= \sigma_{n+1}\sigma_n^{-1} \tau_{n+1}\tau_n^{-1} (\gamma_{n!})^{,n+1}. \end{aligned} $$

Since $\gamma_m=\beta_m\alpha_m$,

$$ \boxed{ \beta_{(n+1)!}\alpha_{(n+1)!}

\sigma_{n+1}\sigma_n^{-1} \tau_{n+1}\tau_n^{-1} (\beta_{n!}\alpha_{n!})^{,n+1}. } $$

This proves part (a).

(b)

For Algorithm E,

$$ \tau_k=(0,k), \qquad \sigma_k=(0,k)\phi(k), $$

where $\phi(k)$ reverses

$$ 0,1,\ldots,k. $$

Since $\tau_k^{-1}=\tau_k$,

$$ \sigma_k^{-1}

\phi(k)(0,k), $$

because $\phi(k)^2=I$.

Hence

$$ \begin{aligned} C &= \sigma_{n+1}\sigma_n^{-1}\tau_{n+1}\tau_n^{-1}\ &= (0,n+1)\phi(n+1)\phi(n) (0,n) (0,n+1) (0,n). \end{aligned} $$

Now

$$ \phi(n)\phi(n+1)

(0,1,2,\ldots,n+1), $$

so

$$ \phi(n+1)\phi(n)

(0,n+1,n,\ldots,1). $$

We compute the action of $C$.

For $1\le i<n$,

$$ \begin{aligned} i &\xrightarrow{(0,n)} i \xrightarrow{(0,n+1)} i \xrightarrow{\phi(n+1)\phi(n)} i-1 \xrightarrow{(0,n+1)} i-1, \end{aligned} $$

except when $i=1$, where the image becomes $n+1$, and the leading transposition sends it to $0$. Thus

$$ 1\mapsto0, \qquad i\mapsto i-1 \quad(2\le i\le n). $$

For $0$,

$$ 0 \mapsto n \mapsto n \mapsto n-1 \mapsto n-1 \mapsto n, $$

so

$$ 0\mapsto n. $$

For $n+1$,

$$ n+1 \mapsto n+1 \mapsto0 \mapsto n+1 \mapsto0 \mapsto n+1. $$

Therefore

$$ C=(0,n,n-1,\ldots,1) =(0,1,2,\ldots,n)^{-1}. $$

The inverse or the forward cycle depends only on the convention for composing permutations. In either convention, $C$ cyclically permutes the positions $0,\ldots,n$ and fixes $n+1$. This is precisely the rotation used between successive blocks of Algorithm E.

We now prove correctness by induction on $n$.

The case $n=1$ is immediate.

Assume Algorithm E is correct for $n$ elements.

During any block of length $n!$, every value of $\rho!(m)$ is at most $n$. Hence every operation performed in that block is one of

$$ \sigma_0,\ldots,\sigma_n, \qquad \tau_0,\ldots,\tau_n. $$

Each of these permutations acts only on the positions

$$ 0,\ldots,n-1. $$

Therefore the newly introduced position $n$ is never touched during the interior of a block. Consequently the element occupying position $n$ remains fixed throughout that block.

Moreover, the sequence of values

$$ \rho!(1),\rho!(2),\ldots,\rho!(n!) $$

inside every block is exactly the same as in the $n$-element algorithm. Since the operations applied are exactly the same permutations $\sigma_k$ and $\tau_k$ with the same indices and in the same order, restricted to the first $n$ positions, the evolution of those positions is step for step identical with Algorithm E on $n$ elements.

By the induction hypothesis, each block therefore generates every permutation of those $n$ entries exactly once while the new element remains fixed.

Part (a) shows that after each completed block the state is multiplied by the correction factor $C$, which merely cyclically shifts the position of the fixed element from one position to the next. Thus the next block repeats the same $n!$-step generation with the new element fixed in a different position.

Hence the $n+1$ blocks correspond to the $n+1$ possible positions of the new element. Different blocks cannot contain the same permutation because the distinguished element occupies different positions. Each block contains exactly $n!$ distinct permutations by the induction hypothesis.

Therefore the total number of distinct permutations generated is

$$ (n+1)n!=(n+1)!, $$

which is exactly the number of permutations of $n+1$ symbols.

Thus Algorithm E generates every permutation exactly once, completing the induction. ∎