Nombre de Stirling

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 XVIIIe siècle. Il en existe trois sortes, nommés les nombres de Stirling de première espèce signés et non signés, et les nombres de Stirling de seconde espèce.

Notations[modifier | modifier le code]

Diverses notations sont utilisées pour les nombres de Stirling, parmi lesquelles[1] :

  • nombres de Stirling de première espèce « signés » :s(n,k),
  • nombres de Stirling de première espèce « non signés » :|s(n,k)|=c(n,k)=\left[{n\atop k}\right],
  • nombres de Stirling de deuxième espèce :S(n,k)=S_n^{(k)}=\left\{{n\atop k}\right\}.

La notation avec crochets, analogue à celle utilisée pour les coefficients binomiaux, est due à Jovan Karamata (en), qui l'a proposée en 1935. Son usage a été encouragé par Donald Knuth[2] mais, outre son ergonomie discutable[3], elle comporte un risque de confusion avec les coefficients binomiaux de Gauss (en) (présentés dans l'article « q-analogue »). Nous nous limiterons donc, pour chacun des trois types de nombres, à la première notation correspondante ci-dessus.

Nombre de Stirling de première espèce[modifier | modifier le code]

Les nombres de Stirling de première espèce signés s(n, k) sont les coefficients du développement de la factorielle décroissante (x)n, c'est-à-dire que

(x)_n=x(x-1)(x-2)\ldots(x-n+1)=\sum_{k=1}^ns(n,k)x^k.

((x)0 = 1 car il s'agit d'un produit vide.)

Le nombre s(n, k) a même signe que (–1)n – k.

Les nombres de Stirling de première espèce non signés |s(n, k)| (valeurs absolues des précédents) sont les coefficients du développement de la factorielle croissante (x)n, c'est-à-dire que

(x)^n=x(x+1)(x+2)\ldots(x+n-1)=\sum_{k=1}^n|s(n,k)|x^k.

Ils ont aussi une définition combinatoire : cf. § « Interprétation énumérative » ci-dessous.

Table de valeurs[modifier | modifier le code]

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 :

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[modifier | modifier le code]

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

\forall k>0,\quad s(n+1,k)=s(n,k-1)-ns(n,k),

avec les conditions initiales

s(0,0)=1\quad{\rm et}\quad\forall n>0,s(n,0)=s(0,n)=0

et leurs valeurs absolues satisfont (avec mêmes conditions initiales) la relation de récurrence

\forall k>0,\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 :

(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 :

(x)^{n+1}=x(x)^n+n(x)^n.

Identités simples[modifier | modifier le code]

Remarquons que

\forall k>n,s(n,k)=0,
s(n,n)=1,\quad s(n,1)=(-1)^{n-1}(n-1)!,\quad s(n,n-1)=-{n\choose2},
s(n,n-2)=\frac{3n-1}4{n\choose3},\quad s(n,n-3)=-{n\choose2}{n\choose4}.

Il existe d'autres identités, comme

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

Hn est un nombre harmonique et

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

Hn(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.

Formules explicites[modifier | modifier le code]

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

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 :

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 :

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)!}.

Fonction génératrice[modifier | modifier le code]

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 
s(n,k)=x^k = 
\sum_{k=0}^\infty x^k
\sum_{n=k}^\infty \frac {t^n}{n!}
s(n,k)= 
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[modifier | modifier le code]

\sum_{k=0}^n (-1)^k s(n,k)=(-1)^n n!

Sommes infinies[modifier | modifier le code]

\sum_{n=m}^\infty s(n,m)\frac{x^n}{n!}=\frac {\left(\ln (1+x)\right)^m}{m!}

qui est valide pour x<1.

Interprétation énumérative[modifier | modifier le code]

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, s(4,2)=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 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.

Nombre de Stirling de seconde espèce[modifier | modifier le code]

Les nombres de Stirling de seconde espèce S(n, k) sont caractérisés par

\sum_{k=0}^nS(n,k)(x)_k=x^n.

Le nombre S(n, k) est 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}^nS(n,k)

est le ne nombre de Bell.

Table de valeurs[modifier | modifier le code]

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

n \ k 0 1 2 3 4 5 6 7 8 9
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
9 0 1 255 3025 7770 6951 2646 462 36 1

Relation de récurrence[modifier | modifier le code]

Ces nombres satisfont la relation de récurrence

\forall k>0,\quad S(n,k)=S(n-1,k-1)+kS(n-1,k),

avec les conditions initiales

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

Identités simples[modifier | modifier le code]

On a par exemple

S(n,n-1)={n \choose 2}

et

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

Formule explicite[modifier | modifier le code]

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

S(n,k)=\frac1{k!}\sum_{j=1}^{k}(-1)^{k-j}{k\choose j}j^n,

laquelle s'obtient[5] en remarquant que le nombre de surjections (d'un ensemble de n éléments vers un ensemble de 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...

Rapport avec la distribution de Poisson[modifier | modifier le code]

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

E(X^n)=\sum_{k=1}^nS(n,k)\lambda^k.

En particulier, le ne 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)).

Relation de réciprocité[modifier | modifier le code]

Les nombres de Stirling de première et seconde espèce peuvent être considérés comme deux systèmes inverses l'un de l'autre, en ce sens que, pour tout nombre naturel n, la matrice formée par les éléments des n premières lignes et des n premières colonnes de la table des nombres de Stirling de première espèce est l'inverse de la matrice correspondante extraite de la table des nombres de Stirling de seconde espèce :

\sum_{n=0}^{\max\{j,k\}}s(n,j)S(k,n)=\delta_{jk}

et

\sum_{n=0}^{\max\{j,k\}}S(n,j)s(k,n)=\delta_{jk}

\delta_{jk} est le symbole de Kronecker.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Stirling number » (voir la liste des auteurs).

  1. D'autres encore sont utilisées par Abramowitz Stegun.
  2. (en) D. E. Knuth, Two notes on notation (source TeX).
  3. Louis Comtet, Analyse combinatoire élémentaire, Techniques Ingénieur, coll. « Mathématiques concrètes » (ISBN 9782841809813, lire en ligne), p. 24.
  4. Pour une démonstration, voir par exemple Louis Comtet, Analyse combinatoire, t. 2, P.U.F., 1970, p. 51.
  5. Voir par exemple L. Comtet, Analyse combinatoire, t. 2, P.U.F., 1970, p. 38.

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]