Nombre de Stirling

En mathématiques, les nombres de Stirling apparaissent dans plusieurs problèmes combinatoires. Ils tirent leur nom de James Stirling, qui les a introduits au XVIII^e siècle. Il en existe deux sortes, nommés les nombres de Stirling de première espèce et les nombres de Stirling de seconde espèce.

Notations

Diverses notations sont utilisées pour les nombres de Stirling, mais celles que l'on rencontre le plus souvent sont

$\left[\begin{matrix} n \\ k \end{matrix}\right]$ , pour les nombres de Stirling de première espèce, et

$\left\{\begin{matrix} n \\ k \end{matrix}\right\}$ , pour les nombres de Stirling de seconde espèce.

Cette notation, analogue à celle utilisée pour les coefficients binomiaux, est due à Jovan Karamata (en), qui l'a proposée en 1935, et dont l'usage a été encouragé par Donald Knuth^[1] ; on l'appelle la notation de Karamata.

Nombres de Stirling de première espèce

En combinatoire, les nombres de Stirling de première espèce non signés comptent le nombre de permutations de n éléments se décomposant en k cycles disjoints. De manière plus générale, ces nombres sont les valeurs absolues des nombres de Stirling de première espèce (signés), qui sont les coefficients du développement de

$(x)_n=\sum_{k=1}^n \left[\begin{matrix} n \\ k \end{matrix}\right]x^k$

où (x)_n est la factorielle décroissante

$(x)_n=x(x-1)(x-2)\cdots(x-n+1).$

On peut inverser la définition afin d'exprimer $x n$ comme une suite de factorielles croissantes :

$x^n = \sum_{k=0}^n \left[\begin{matrix} n \\ k \end{matrix}\right] (x)_k$

Des relations similaires lient les nombres de Stirling de première espèce aux polynômes de Bernoulli. Un grand nombre de relations liées aux nombres de Stirling cachent des relations similaires liées aux coefficients binomiaux. L'étude des relations entre ces deux nombres est le calcul ombral et est un domaine important de la théorie des suites de Sheffer (en).

Table de valeurs

Voici une table donnant quelques valeurs des nombres de Stirling de première espèce (suite A008275 et suite A008276 de l’OEIS), de la même forme que le triangle de Pascal :

n \ k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	-1	1
3	0	2	-3	1
4	0	-6	11	-6	1
5	0	24	-50	35	-10	1
6	0	-120	274	-225	85	-15	1
7	0	720	-1764	1624	-735	175	-21	1
8	0	-5040	13068	-13132	6769	-1960	322	-28	1
9	0	40320	-109584	118124	-67284	22449	-4536	546	-36	1

Relation de récurrence

Les nombres de Stirling de première espèce satisfont la relation de récurrence

$\left[\begin{matrix} n+1 \\ k \end{matrix}\right] = \left[\begin{matrix} n \\ k-1 \end{matrix}\right] -n \left[\begin{matrix} n \\ k \end{matrix}\right]$

pour $1\leq k\leq n-1$ , avec les conditions initiales

$\left[\begin{matrix} n \\ 0 \end{matrix}\right]=0 \quad \mbox { et } \quad \left[\begin{matrix} 1 \\ 1 \end{matrix}\right] = 1$

Ceci découle de la relation de récurrence des factorielles décroissantes :

$(x)_{n+1} = x(x)_n - n(x)_n\,$ .

Identités simples

Remarquons que

$\left[\begin{matrix} n \\ 1 \end{matrix}\right] = (-1)^{n-1} (n-1)!$

$\left[\begin{matrix} n \\ n \end{matrix}\right] = 1$

$\left[\begin{matrix} n \\ n-1 \end{matrix}\right] = (-1)^n {n \choose 2}$

Il en existe d'autres, comme

$\left[\begin{matrix} n \\ 2 \end{matrix}\right] = (-1)^n (n-1)!\; H_{n-1}$

où $H n$ est un nombre harmonique et

$\left[\begin{matrix} n \\ 3 \end{matrix}\right] = \frac {1}{2} (-1)^{n-1} (n-1)! \left[ (H_{n-1})^2 - H_{n-1}^{(2)} \right]$

où $H_n^{(m)}$ est un nombre harmonique généralisé.

Formules explicites

On peut montrer^[2] la relation suivante entre nombres de Stirling de première et seconde espèce :

$\left[\begin{matrix} n \\ m \end{matrix} \right]=\sum_{k=0}^{n-m}(-1)^k\binom{n-1+k}{n-m+k}\binom{2n-m}{n-m-k}\left\{\begin{matrix} n-m+k \\ k \end{matrix} \right\},$

d'où, utilisant la formule explicite pour ces derniers qui sera donnée plus bas :

$\left[\begin{matrix} n \\ m \end{matrix} \right]=\sum_{k=0}^{n-m}\sum_{j=0}^{k}\frac{(-1)^{2k-j}}{k!}\binom{n-1+k}{n-m+k}\binom{2n-m}{n-m-k}{k \choose j} j^{n-m+k},$

ou encore, après simplifications :

$\left[\begin{matrix} n \\ m \end{matrix} \right]=\frac{(2n-m)!}{(m-1)!}\sum_{k=0}^{n-m}\frac{1}{(n+k)(n-m-k)!(n-m+k)!}\sum_{j=0}^{k}\frac{(-1)^{j} j^{n-m+k} }{j!(k-j)!}.$

Fonction génératrice

Plusieurs identités peuvent être obtenues en manipulant la fonction génératrice

$(1+t)^x = \sum_{n=0}^\infty {x \choose n} t^n = \sum_{n=0}^\infty \frac {t^n}{n!} \sum_{k=0}^n \left[\begin{matrix} n \\ k \end{matrix}\right] x^k = \sum_{k=0}^\infty x^k \sum_{n=k}^\infty \frac {t^n}{n!} \left[\begin{matrix} n \\ k \end{matrix}\right] = e^{x\ln(1+t)}$

En particulier, l'ordre de la sommation peut être inversé; on peut également prendre des dérivées, ou encore fixer t ou x,

Sommes finies

$\sum_{k=0}^n (-1)^k \left[\begin{matrix} n \\ k \end{matrix}\right] = (-1)^n n!$

Sommes infinies

$\sum_{n=m}^\infty \left[\begin{matrix} n \\ k \end{matrix}\right] \frac{x^n}{n!} = \frac {\left(\ln (1+x)\right)^m}{k!}$

qui est valide pour $x < 1$ .

Interprétation énumérative

La valeur absolue du nombre de Stirling de première espèce compte le nombre de permutations de $n$ objets ayant exactement $k$ cycles. Par exemple, $\left[\begin{matrix} 4 \\ 2 \end{matrix}\right]=11$ correspond au fait que le groupe symétrique $S 4$ possède trois permutations de la forme

( * * )( * * )

— 2 cycles de longueur 2

et huit permutations de la forme

( * * * )

— 1 cycle de longueur 3 et 1 cycle de longueur 1.

La valeur absolue du nombre de Stirling de première espèce compte aussi le nombre de permutations de $n$ objets ayant exactement $k$ records. Cette identité entre records et cycles résulte de la correspondance fondamentale de Foata. La forme produit de la série génératrice des nombres de Stirling de première espèce résulte de l'indépendance des termes du code de Lehmer d'une permutation, code très lié aux records d'une permutation. L'interprétation des nombres de Stirling en termes de nombre de records explique l'apparition des nombres de Stirling dans l'analyse de l'algorithme de recherche du maximum, qui est la première analyse d'algorithme traitée dans le livre fondateur de Donald Knuth, The art of computer programming.

Nombres de Stirling de seconde espèce

Les nombres de Stirling de seconde espèce $\left\{\begin{matrix} n \\ k \end{matrix}\right\}$ comptent le nombre de relations d'équivalence ayant k classes d'équivalence définies sur un ensemble de n éléments, c'est-à-dire aussi le nombre de partitions en k sous-ensembles d'un ensemble de n objets. La somme

$B_n=\sum_{k=1}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\}$

est le n^ème nombre de Bell. Si nous posons

$(x)_n=x(x-1)(x-2)\cdots(x-n+1)$

(en particulier, (x)₀ = 1 car il s'agit d'un produit vide) pour la factorielle décroissante, nous pouvons caractériser les nombres de Stirling de seconde espèce par

$\sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\}(x)_k=x^n.$