A beautiful identity between polynomials

Notations

Pour $n\geqslant 1$, posons
$$P_n(X)=\sum_{k=1}^{n}a_{n,k}X^{k},$$où $a_{n,k}$ compte les permutations de $\mathfrak{S}_n$ dont la décomposition en cycles à supports disjoints comporte exactement $k$ cycles, points fixes compris (un point fixe est un cycle de longueur $1$). Ces entiers sont les nombres de Stirling de première espèce non signés, souvent notés $\left[{n\atop k}\right]$. Il s’agit de montrer
$$P_n(X)=X(X+1)\cdots(X+n-1)=\prod_{i=0}^{n-1}(X+i).$$

Étape 1 : la relation de récurrence

Lemme. Pour $n\geqslant 2$ et $1\leqslant k\leqslant n$,
$$a_{n,k}=a_{n-1,k-1}+(n-1)\,a_{n-1,k},$$avec les conventions $a_{n,0}=0$ pour $n\geqslant 1$ et $a_{n,k}=0$ pour $k>n$.

Démonstration. Partitionnons l’ensemble des permutations de $\mathfrak{S}_n$ à $k$ cycles selon la nature du cycle contenant $n$.

Cas 1 : $n$ est un point fixe. La restriction de $\sigma$ à $\{1,\dots,n-1\}$ est alors une permutation de $\mathfrak{S}_{n-1}$, et ses cycles sont ceux de $\sigma$ privés du cycle $(n)$ : elle en a donc $k-1$. Réciproquement, toute $\tau\in\mathfrak{S}_{n-1}$ à $k-1$ cycles se prolonge d’une unique façon en fixant $n$. Ce cas contribue pour $a_{n-1,k-1}$.

Cas 2 : le cycle de $n$ est de longueur $\geqslant 2$. Notons $\tau$ la permutation de $\mathfrak{S}_{n-1}$ obtenue en effaçant $n$ de son cycle, c’est-à-dire en remplaçant le motif $\cdots\to \sigma^{-1}(n)\to n\to\sigma(n)\to\cdots$ par $\cdots\to\sigma^{-1}(n)\to\sigma(n)\to\cdots$. Le cycle raccourci reste de longueur $\geqslant 1$, donc $\tau$ possède encore $k$ cycles. Réciproquement, se donner $\sigma$ revient à se donner $\tau\in\mathfrak{S}_{n-1}$ à $k$ cycles, puis à insérer $n$ immédiatement après l’un des $n-1$ éléments de $\{1,\dots,n-1\}$ dans son cycle. Ces $n-1$ insertions donnent des permutations deux à deux distinctes, car l’antécédent $\sigma^{-1}(n)$ les distingue. Ce cas contribue pour $(n-1)\,a_{n-1,k}$.

Les deux cas étant exclusifs et exhaustifs, le lemme est établi. $\square$

Étape 2 : traduction polynomiale et récurrence

En multipliant la relation du lemme par $X^{k}$ et en sommant sur $k$ de $1$ à $n$, il vient
$$P_n(X)=\sum_{k}a_{n-1,k-1}X^{k}+(n-1)\sum_{k}a_{n-1,k}X^{k}=X\,P_{n-1}(X)+(n-1)P_{n-1}(X),$$le premier décalage d’indice étant licite grâce aux conventions ci-dessus. Autrement dit,
$$P_n(X)=(X+n-1)\,P_{n-1}(X).$$

Initialisation. $\mathfrak{S}_1$ est réduit à l’identité, qui a un cycle : $a_{1,1}=1$ et $P_1(X)=X$, ce qui est bien le produit vide multiplié par $X$.

Hérédité. Si $P_{n-1}(X)=\prod_{i=0}^{n-2}(X+i)$, alors $P_n(X)=(X+n-1)\prod_{i=0}^{n-2}(X+i)=\prod_{i=0}^{n-1}(X+i)$.

Par récurrence, $P_n(X)=X(X+1)\cdots(X+n-1)$ pour tout $n\geqslant 1$. $\blacksquare$

Variante : preuve bijective directe

Le développement du produit $\prod_{i=0}^{n-1}(X+i)$ consiste à choisir, pour chaque $i\in\{0,\dots,n-1\}$, soit le terme $X$, soit le terme $i$. Ce choix se lit exactement comme le procédé de construction incrémentale d’une permutation : on insère successivement les éléments $1,2,\dots,n$, et à l’étape $i+1$ on décide soit d’ouvrir un nouveau cycle (facteur $X$, une seule manière), soit d’insérer $i+1$ après l’un des $i$ éléments déjà placés (facteur $i$). Toute permutation s’obtient ainsi de façon unique, et son nombre de cycles est le nombre de fois où l’on a choisi $X$. Le coefficient de $X^{k}$ dans le produit est donc $a_{n,k}$.

Remarques

• Nombre moyen de cycles. En dérivant en $X=1$ la relation $P_n(X)=\prod_{i}(X+i)$, l’espérance du nombre de cycles d’une permutation uniforme de $\mathfrak{S}_n$ vaut $\sum_{i=0}^{n-1}\frac{1}{1+i}=H_n\sim\ln n$. La variance vaut $H_n-H_n^{(2)}$, et un théorème de Goncharov donne la normalité asymptotique.
• Version signée. En posant $s(n,k)=(-1)^{n-k}a_{n,k}$, on obtient $\sum_k s(n,k)X^{k}=X(X-1)\cdots(X-n+1)$ : les nombres de Stirling signés sont les coefficients de la factorielle décroissante, tandis que les non signés sont ceux de la factorielle croissante.

Exemples

1. $n=3$ : $P_3(X)=X(X+1)(X+2)=X^{3}+3X^{2}+2X$. On lit $a_{3,3}=1$ (l’identité), $a_{3,2}=3$ (les trois transpositions, chacune formée d’un $2$-cycle et d’un point fixe) et $a_{3,1}=2$ (les deux $3$-cycles). Total : $6=3!$.
2. $n=4$ : $P_4(X)=X^{4}+6X^{3}+11X^{2}+6X$, soit $a_{4,1}=6$ ($4$-cycles), $a_{4,2}=11$ ($3$-cycles avec point fixe, au nombre de $8$, plus les $3$ doubles transpositions), $a_{4,3}=6$ (transpositions), $a_{4,4}=1$. Total : $24$.
3. Cas extrêmes. $a_{n,n}=1$ (seule l’identité n’a que des points fixes) et $a_{n,1}=(n-1)!$ (nombre de $n$-cycles), ce qui correspond aux coefficients dominant et constant du produit.

https://www.youtube.com/watch?v=XrQdz9m7Q3w