Loading AI tools
De Wikipédia, l'encyclopédie libre
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.
Diverses notations sont utilisées pour les nombres de Stirling, parmi lesquelles[1] :
La notation avec crochets, analogue à celle utilisée pour les coefficients binomiaux, est due à Jovan Karamata, 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 (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.
Les nombres de Stirling de première espèce signés s(n, k) ,pour n, k entiers naturels, sont les coefficients du développement de la factorielle décroissante (x)n, c'est-à-dire que
((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
Ils ont aussi une définition combinatoire : cf. § #Interprétation combinatoire ci-dessous.
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 |
En partant de la relation , et en utilisant les relations entre coefficients et racines, on obtient [4] :
Pour tout entier n supérieur ou égal à 1 :
Les nombres de Stirling de première espèce signés vérifient la relation de récurrence
avec les conditions initiales
Leurs valeurs absolues vérifient (avec mêmes conditions initiales) la relation de récurrence
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 :
et la seconde, d'un raisonnement combinatoire ou de la relation de récurrence des factorielles croissantes :
Remarquons que
Il existe d'autres identités, comme
où Hn est un nombre harmonique et
où 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.
On peut montrer[5] la relation suivante entre nombres de Stirling de première et seconde espèce :
d'où, utilisant la formule pour ces derniers qui sera donnée plus bas :
ou encore, après simplifications :
On peut démontrer plusieurs identités en manipulant la fonction génératrice :
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 et qu'on identifie les puissances de t dans les deux développements, on obtient :
Si on développe l'exponentielle et qu'on identifie les puissances de x dans les deux développements, on obtient :
valide pour .
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, correspond au fait que le groupe symétrique possède trois permutations de la forme
et huit permutations de la forme
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 :
Les nombres de Stirling de seconde espèce sont donnés par la formule explicite
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
avec les conditions initiales
On déduit de la relation de récurrence ci-dessus[9],[7] que
où (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 .
Voici quelques valeurs des nombres de Stirling de seconde espèce (suites A008277 et A008278 de l'OEIS) :
n \ k | 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 |
On a par exemple S(n, n) = 1,
et
Le nombre total de partitions d'un ensemble à n éléments,
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
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).
D'après leur caractérisation algébrique, les nombres de Stirling de première et seconde espèce, disposés, comme dans les tables de valeurs ci-dessus, en deux matrices triangulaires infinies, constituent les deux matrices de passage (dans un sens et dans l'autre) entre deux bases de l'espace des polynômes[10] : la base canonique des monômes Xk et la base des symboles de Pochhammer X(X – 1)(X – 2)…(X – k + 1). Le fait que ces deux matrices sont inverses l'une de l'autre se traduit par[11] :
où est le symbole de Kronecker.
Une généralisation de la définition des nombres de Stirling fait intervenir un troisième paramètre entier , de sorte que[12]:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.