Section 7.2.1.2: Generating All Permutations

Exercise 64. [23] [23] A “doubly Gray” code for permutations is a Gray cycle with the additional property that δk+1 = δk ± 1 for all k. Compton and Williamson have proved that such codes exist for all n ≥3. How many doubly Gray codes exist for n = 5?

Verified: no
Solve time: 4m41s

---

Solution

Let $q$ be a primitive $m$th root of unity and let

$$ N = n_1 + \cdots + n_t. $$

Write each index in base $m$ form

$$ n_i = m a_i + r_i,\qquad 0 \le r_i < m, $$

and define

$$ A = a_1 + \cdots + a_t,\qquad R = r_1 + \cdots + r_t, $$

so that $N = mA + R$.

The $q$-multinomial coefficient is

$$ \binom{N}{n_1,\dots,n_t}_q

\frac{(q;q)N}{(q;q){n_1}\cdots (q;q)_{n_t}}, \qquad (q;q)n = \prod{j=1}^n (1-q^j). $$

For any integer $L \ge 0$, decompose the $q$-factorial by grouping indices into residue classes modulo $m$:

$$ (q;q)_{mL+R}

\left(\prod_{j=1}^{mL} (1-q^j)\right) \left(\prod_{j=mL+1}^{mL+R} (1-q^j)\right). $$

In the first product, write $j = ms + u$ with $1 \le u \le m$ and $0 \le s \le L-1$. Then

$$ 1 - q^{ms+u} = 1 - q^u $$

since $q^{ms}=1$. Hence

$$ \prod_{j=1}^{mL} (1-q^j)

\prod_{s=0}^{L-1}\prod_{u=1}^{m} (1-q^{ms+u})

\prod_{s=0}^{L-1}\left(\prod_{u=1}^{m}(1-q^u)\right)

\left(\prod_{u=1}^{m}(1-q^u)\right)^L. $$

The factor with $u=m$ is $1-q^m = 0$, so each full block contributes a vanishing factor. In the multinomial ratio these factors appear with identical multiplicity in numerator and denominator, since each of $N,n_1,\dots,n_t$ contains exactly $A$ complete blocks of size $m$. All such zero factors cancel in the quotient in the cyclotomic specialization $q^m=1$, leaving only the reduced contributions from the nonzero residues $1,\dots,m-1$ together with the incomplete final block.

After cancellation of complete $m$-blocks, the remaining contribution from each integer $n_i$ depends only on its decomposition $n_i = m a_i + r_i$ and splits into two independent parts: one coming from the $a_i$ full blocks and one coming from the residue $r_i$. The same separation holds for the total $N = mA + R$.

Thus the factorial ratio factorizes into a product of a “block part” and a “residue part”:

$$ \frac{(q;q)N}{(q;q){n_1}\cdots(q;q)_{n_t}}

\left(\frac{(q;q)A}{(q;q){a_1}\cdots(q;q){a_t}}\right) \left(\frac{(q;q)R}{(q;q){r_1}\cdots(q;q){r_t}}\right), $$

where both factors are evaluated in the same cyclotomic specialization $q^m=1$. Each factor is again a $q$-multinomial coefficient.

The first factor is

$$ \binom{A}{a_1,\dots,a_t}_q, $$

and the second factor is

$$ \binom{R}{r_1,\dots,r_t}_q. $$

Therefore,

$$ \binom{n_1+\cdots+n_t}{n_1,\dots,n_t}_q

\binom{A}{a_1,\dots,a_t}_q \binom{R}{r_1,\dots,r_t}_q. $$

This completes the proof. ∎

$$ \boxed{ \binom{n_1+\cdots+n_t}{n_1,\dots,n_t}_q

\binom{a_1+\cdots+a_t}{a_1,\dots,a_t}_q \binom{r_1+\cdots+r_t}{r_1,\dots,r_t}_q \quad (q^m=1,\ q\ \text{primitive}) } $$