Nombre de Stirling

Voici une table donnant quelques valeurs des s(n, k) (suites  A008275 et  A008276 de l'OEIS), que l'on peut calculer ligne par ligne grâce à la relation de récurrence du § suivant, de même que le triangle de Pascal :

En partant de la relation ${\displaystyle (X-1)(X-2)..(X-n)=\sum _{k=0}^{n}s(n+1,k+1)X^{k}}$, et en utilisant les relations entre coefficients et racines, on obtient [4] :

${\displaystyle \sigma _{k}(1,2,\cdots ,n)=\sum _{1\leqslant i_{1}<i_{2}<..<i_{k}\leqslant n}i_{1}..i_{k}=(-1)^{k}s(n+1,n+1-k)}$, pour ${\displaystyle n\geqslant k\geqslant 1}$.

Exemple

Pour tout entier n supérieur ou égal à 1 :

${\displaystyle s(n+1,n-1)=\sum _{1\leqslant i<j\leqslant n}ij={\frac {(n-1)n(n+1)(3n+2)}{24}}}$, voir la suite A000914 de l'OEIS.

Les nombres de Stirling de première espèce signés vérifient la relation de récurrence

${\displaystyle \forall k\geqslant 1\quad s(n+1,k)=s(n,k-1)-ns(n,k)}$

avec les conditions initiales

${\displaystyle s(0,0)=1\quad {\rm {et}}\quad \forall n\geqslant 1\quad s(n,0)=s(0,n)=0}$.

Leurs valeurs absolues vérifient (avec mêmes conditions initiales) la relation de récurrence

${\displaystyle \forall k\geqslant 1\quad |s(n+1,k)|=|s(n,k-1)|+n|s(n,k)|}$.

Chacune des deux relations de récurrence peut se déduire de l'autre. De plus, la première découle de la relation de récurrence des factorielles décroissantes :

${\displaystyle (x)_{n+1}=x(x)_{n}-n(x)_{n}}$

et la seconde, d'un raisonnement combinatoire ou de la relation de récurrence des factorielles croissantes :

${\displaystyle (x)^{n+1}=x(x)^{n}+n(x)^{n}}$.

Remarquons que

${\displaystyle \forall k>n\quad s(n,k)=0}$,

${\displaystyle s(n,n)=1,\quad s(n,1)=(-1)^{n-1}(n-1)!,\quad s(n,n-1)=-{n \choose 2}}$,

${\displaystyle s(n,n-2)={\frac {3n-1}{4}}{n \choose 3},\quad s(n,n-3)=-{n \choose 2}{n \choose 4}}$.

Il existe d'autres identités, comme

${\displaystyle s(n,2)=(-1)^{n}(n-1)!\;H_{n-1}}$

où H_n est un nombre harmonique et

${\displaystyle s(n,3)=(-1)^{n-1}{\frac {(n-1)!}{2}}\left[(H_{n-1})^{2}-H_{n-1}^{(2)}\right]}$

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

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.

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

${\displaystyle s(n,m)=\sum _{k=0}^{n-m}(-1)^{k}{\binom {n-1+k}{n-m+k}}{\binom {2n-m}{n-m-k}}S(n-m+k,k)}$

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

${\displaystyle s(n,m)=\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 :

${\displaystyle s(n,m)={\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)!}}}$.

On peut démontrer plusieurs identités en manipulant la fonction génératrice :

${\displaystyle (1+t)^{x}=\sum _{n=0}^{\infty }{x \choose n}t^{n}=\sum _{n=0}^{\infty }{\frac {t^{n}}{n!}}\sum _{k=0}^{n}s(n,k)x^{k}=\sum _{k=0}^{\infty }x^{k}\sum _{n=k}^{\infty }{\frac {t^{n}}{n!}}s(n,k)=\operatorname {e} ^{x\ln(1+t)}}$.

En particulier, on peut inverser l'ordre de la sommation et prendre des dérivées, puis fixer t ou x.

Si on prend x = -1, qu'on développe ${\displaystyle (1+t)^{-1}}$ et qu'on identifie les puissances de t dans les deux développements, on obtient :

${\displaystyle \sum _{k=0}^{n}(-1)^{k}s(n,k)=(-1)^{n}n!}$

Si on développe l'exponentielle ${\displaystyle e^{x\ln(1+t)}}$ et qu'on identifie les puissances de x dans les deux développements, on obtient :

${\displaystyle \sum _{n=k}^{\infty }s(n,k){\frac {t^{n}}{n!}}={\frac {\left(\ln(1+t)\right)^{k}}{k!}}}$,

valide pour ${\displaystyle |t|<1}$.

La valeur absolue du nombre de Stirling de première espèce compte le nombre de permutations de n objets composés d'exactement k cycles disjoints. Par exemple, ${\displaystyle s(4,2)=11}$ correspond au fait que le groupe symétrique ${\displaystyle S_{4}}$ possède trois permutations de la forme

${\displaystyle (**)(**)}$ — 2 cycles de longueur 2

et huit permutations de la forme

${\displaystyle (***)}$ — 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 fonction du 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 Knuth, The Art of Computer Programming.

Les nombres de Stirling de seconde espèce S(n, k) sont définis combinatoirement de trois façons équivalentes :

• S(n, k) est le nombre de relations d'équivalence ayant k classes d'équivalence définies sur un ensemble de n éléments ;
• S(n, k) est le nombre de partitions d'un ensemble à n éléments en k sous-ensembles ;
• k! × S(n, k) est le nombre de surjections d'un ensemble à n éléments sur un ensemble à k éléments. Attention, ce dernier nombre est lui aussi souvent noté S(n, k) ou s(n, k).

Les nombres de Stirling de seconde espèce sont donnés par la formule explicite

${\displaystyle S(n,k)={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{n}}$,

laquelle s'obtient par exemple[6] - [7] en remarquant que le nombre de surjections (d'un ensemble à n éléments vers un ensemble à k éléments) peut se compter par la formule d'inclusion-exclusion : on compte toutes les applications moins celles n'atteignant pas un certain élément, plus celles n'atteignant pas deux éléments, moins...

À partir de la définition combinatoire, on peut également démontrer[8] - [7] que ces nombres vérifient la relation de récurrence

${\displaystyle \forall n,k\geqslant 1\quad S(n,k)=S(n-1,k-1)+kS(n-1,k)}$

avec les conditions initiales

${\displaystyle S(0,0)=1\quad {\rm {et}}\quad \forall n\geqslant 1\quad S(n,0)=S(0,n)=0}$.

On déduit de la relation de récurrence ci-dessus[9] - [7] que

${\displaystyle \sum _{k=0}^{n}S(n,k)(X)_{k}=X^{n}}$,

où ${\displaystyle (X)_{k}=X(X-1)...(X-k+1)}$ (symbole de Pochhammer),

ce qui fournit une définition algébrique des nombres de Stirling de deuxième espèce, équivalente à la définition combinatoire initiale.

Cette formule est utilisée par exemple dans l'expression des sommes ${\displaystyle \sum _{k=1}^{n}k^{p}}$.

Voici quelques valeurs des nombres de Stirling de seconde espèce (suites  A008277 et  A008278 de l'OEIS) :

On a par exemple S(n, n) = 1,

${\displaystyle S(n,n-1)={\binom {n}{2}}}$

et

${\displaystyle S(n,2)=2^{n-1}-1}$.

Le nombre total de partitions d'un ensemble à n éléments,

${\displaystyle B_{n}=\sum _{k=1}^{n}S(n,k)}$,

est le n-ième nombre de Bell.

Si X est une variable aléatoire suivant une distribution de Poisson avec une moyenne λ, alors son n-ième moment est

${\displaystyle E(X^{n})=\sum _{k=1}^{n}S(n,k)\lambda ^{k}}$.

En particulier, le n-ième moment d'une distribution de Poisson de moyenne 1 est précisément le nombre de partitions d'un ensemble de taille n, qui est le n-ième nombre de Bell (formule de Dobinski).

• (en) Milton Abramowitz et Irene Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables [détail de l’édition] (lire en ligne), « Stirling Numbers », § 24.1.3-4, p. 824-825
• (en) Louis Comtet, Advanced Combinatorics : The Art of Finite and Infinite Expansions, D. Reidel, 1974, 343 p. (ISBN 978-90-277-0441-2, lire en ligne)
• (en) Victor Adamchik, « On Stirling Numbers and Euler Sums », Journal of Computational and Applied Mathematics, vol. 79,‎ 1997, p. 119-130 (lire en ligne)
• (en) Arthur T. Benjamin, Gregory O. Preston et Jennifer J. Quinn, « A Stirling Encounter with Harmonic Numbers », Mathematics Magazine, vol. 75, n^o 2,‎ 2002, p. 95-103 (lire en ligne)
• (en) J. M. Sixdeniers, K. A. Penson et A. I. Solomon, « Extended Bell and Stirling Numbers From Hypergeometric Exponentiation », Journal of Integer Sequences, vol. 4, n^o 01.1.4,‎ 2001 (lire en ligne)
• (en) Hsien-Kuei Hwang, « Asymptotic Expansions for the Stirling numbers of the first kind », Journal of Combinatorial Theory, a, vol. 71, n^o 2,‎ 1995, p. 343-351 (DOI 10.1016/0097-3165(95)90010-1, lire en ligne)

• Code de Lehmer
• Correspondance fondamentale de Foata
• Cycles et points fixes
• Nombre eulérien
• Nombre de Lah
• Polynôme de Bell
• Polynôme de Touchard
• Suite de polynômes
• Nombres de Stirling et fonctions génératrices exponentielles en combinatoire symbolique (en)
• Transformée de Stirling (en)

• (en) Eric W. Weisstein, « Stirling Number of the First Kind », sur MathWorld
• (en) E. Weisstein, « Stirling Number of the Second Kind », sur MathWorld
• (en) rmilson (146), « Stirling numbers of the first kind », sur PlanetMath
• (en) rmilson (146), « Stirling numbers of the second kind », sur PlanetMath