A permutation identity supporting the Green–Liebeck code conjecture

The identity holds for ALL admissible $k,m,n$ and every $1\le i\le k$.

Write $(u)_j=u(u-1)\cdots(u-j+1)$, let

$$\ell=k-i,\qquad M=n-k-m,$$

and note that the hypotheses imply $m\ge2k>k$ and $M\ge k$. In falling-factorial notation, the proposed identity is

$$(k)_\ell\bigl((M+m)_i-(M)_i\bigr) = m\sum_{r=1}^{i}\sum_{s=0}^{\ell} \binom{i}{r}\binom{\ell}{s} (m-r-s-1)_{r-1}(r+s-1)_s (M+r+s)_{i-r}(k-r-s)_{\ell-s}. \tag{1}$$

Set $j=r+s$. Dividing (1) by $i!\ell!$ and canceling factorials gives the equivalent identity

$$\binom{k}{i} \left[ \binom{M+m}{i}-\binom{M}{i} \right] = \sum_{j=1}^{k}\sum_{r=1}^{i} A_{m,j,r} \binom{k-j}{i-r} \binom{M+j}{i-r}, \tag{2}$$

where

$$A_{m,j,r} = \frac{m}{j}\binom{j}{r}\binom{m-j-1}{r-1} = \frac{m}{r}\binom{j-1}{r-1}\binom{m-j-1}{r-1}. \tag{3}$$

The quantity $A_{m,j,r}$ counts $j$-element subsets of a labeled $m$-cycle having exactly $r$ nonempty cyclic runs: choose the positive occupied-run lengths, the positive complementary-gap lengths, and a distinguished vertex, then divide by the $r$ possible distinguished runs.

Introduce formal variables $t,z$, and put

$$B=(1+z)^k(1+t/z)^M,\qquad w=\frac{1+t/z}{1+z}.$$

Let $\operatorname{CT}_{\infty}$ denote the constant term in the Laurent expansion at $z=\infty$. For $j\le k$,

$$\operatorname{CT}_{\infty}(Bw^jt^r) = t^r \sum_{a\ge0} \binom{k-j}{a}\binom{M+j}{a}t^a. \tag{4}$$

For $j>k$, this constant term is zero: the Laurent series has maximal $z$-degree $k-j<0$.

The transfer matrix for binary cyclic words, recording occupied vertices by $w$ and occupied runs by $t$, is

$$T= \begin{pmatrix} 1&wt\\ 1&w \end{pmatrix}.$$

Its closed walks yield

$$\operatorname{tr}(T^m) = 1+w^m+ \sum_{j=1}^{m-1}\sum_{r\ge1}A_{m,j,r}w^jt^r. \tag{5}$$

Here the first two terms correspond to the all-zero and all-one words. The characteristic roots of $T$ are

$$\lambda_1=1+t/z, \qquad \lambda_2=\frac{1-t}{1+z},$$

as their sum is $1+w$ and their product is $w(1-t)$. Hence

$$\operatorname{tr}(T^m)=\lambda_1^m+\lambda_2^m.$$

Since $m>k$, both

$$B\lambda_2^m =(1-t)^m(1+z)^{k-m}(1+t/z)^M$$

and

$$Bw^m =(1+z)^{k-m}(1+t/z)^{M+m}$$

have strictly negative maximal $z$-degree and therefore have zero constant term at infinity.

Multiplying (5) by $B$ and taking constant terms consequently gives

$$\operatorname{CT}_{\infty} \left( B\sum_{j=1}^{m-1}\sum_{r\ge1} A_{m,j,r}w^jt^r \right) = \operatorname{CT}_{\infty} \left( (1+z)^k \bigl[(1+t/z)^{M+m}-(1+t/z)^M\bigr] \right).$$

Extract the coefficient of $t^i$. By (4), the left side is precisely the right side of (2); the right side is

$$\binom{k}{i} \left[ \binom{M+m}{i}-\binom{M}{i} \right].$$

This proves (2), and therefore the original permutation identity (1), for every $1\le i\le k$.