nombre de Stirling

Prenons quatre objets nommés a, b, c et d, puis rangeons-les dans exactement deux groupes non vides. L'ordre des groupes ne compte pas : {a, b} avec {c, d} décrit le même partage que {c, d} avec {a, b}. Il existe sept partages différents. Le nombre de Stirling de seconde espèce qui correspond à cette situation vaut donc 7.

L'autre espèce vient d'un calcul différent : on développe une suite de facteurs x, x − 1, x − 2, etc., puis on lit ses coefficients. Les deux familles portent le même nom, mais ne comptent pas le même type d'organisation.

Pour deux entiers naturels n et k, les nombres de Stirling forment deux familles. Le nombre de première espèce signé, noté s(n, k), est le coefficient de x^k dans le produit de n facteurs x(x − 1)(x − 2)⋯(x − n + 1). Le nombre de première espèce non signé est la valeur absolue de s(n, k). Cette première famille intervient dans l'étude des permutations.

Le nombre de seconde espèce, noté S(n, k), compte les partitions d'un ensemble de n objets en exactement k sous-ensembles non vides. Une partition répartit chaque objet dans un seul bloc, et l'ordre des blocs n'en crée pas une nouvelle. Pour n = 4 et k = 2, on obtient ainsi S(4, 2) = 7.

Pour n ≥ 1 et k ≥ 1, la seconde espèce vérifie la récurrence suivante : $S(n,k)=S(n-1,k-1)+kS(n-1,k)S(n,k)=S(n-1,k-1)+kS(n-1,k)$. Elle s'initialise par S(0, 0) = 1, S(n, 0) = 0 lorsque n ≥ 1, et S(0, k) = 0 lorsque k ≥ 1. Ces conditions impliquent aussi S(n, k) = 0 lorsque k > n.

On cherche le nombre de partitions de l'ensemble {a, b, c, d} en deux blocs non vides. Les données sont n = 4 objets et k = 2 blocs.

1. On applique la récurrence : S(4, 2) = S(3, 1) + 2 × S(3, 2).
2. Les trois objets a, b et c n'ont qu'une partition en un bloc, donc S(3, 1) = 1.
3. Leurs partitions en deux blocs sont {a}|{b, c}, {b}|{a, c} et {c}|{a, b}, donc S(3, 2) = 3.
4. On calcule S(4, 2) = 1 + 2 × 3 = 7.

Le résultat est donc sept partitions. Le terme S(3, 1) décrit le cas où d forme seul le second bloc. Le terme 2 × S(3, 2) décrit les six cas où d rejoint l'un des deux blocs d'une partition de {a, b, c}. Pour contrôler, on énumère quatre partitions de tailles 1 et 3, puis trois partitions de tailles 2 et 2 : 4 + 3 = 7.

Pour compter des répartitions en groupes non vides, la seconde espèce convient lorsque les groupes n'ont pas d'étiquette. On fixe n, le nombre d'objets, et k, le nombre de blocs, puis on calcule S(n, k). Si les groupes portent des noms distincts, ce décompte ne s'applique pas directement.

Pour construire une table de valeurs, la récurrence évite d'énumérer toutes les partitions. On remplit d'abord les bords S(0, 0) = 1 et les zéros, puis chaque case utilise les deux valeurs de la ligne précédente.

Dans un développement polynomial, la première espèce sert au geste inverse : on repère le coefficient de x^k dans le produit descendant. On conserve son signe pour s(n, k), ou seulement sa valeur absolue pour la version non signée.

Les nombres de Stirling ne sont pas la formule de Stirling. Un test simple les sépare : les premiers portent deux indices n et k et décrivent des coefficients ou des partitions, tandis que la formule de Stirling donne une approximation de la factorielle d'un seul entier. Une question sur le nombre de partitions de quatre objets en deux blocs appelle S(4, 2), pas une approximation de 4!.

Si k > n, aucun partage de n objets en k blocs non vides n'existe : le symptôme est qu'au moins un bloc devrait rester vide, et il faut écrire S(n, k) = 0. À l'autre bord, l'ensemble vide possède une partition en zéro bloc, donc S(0, 0) = 1 ; cette convention est nécessaire pour initialiser la récurrence.

Permuter l'ordre des blocs ne produit pas une nouvelle partition. Compter {a, b}|{c, d} puis {c, d}|{a, b} deux fois signale que l'on traite à tort les blocs comme des groupes étiquetés. Il faut identifier ces deux écritures.

Le signe ne se supprime que pour la première espèce non signée. Le remplacer par une valeur absolue dans s(n, k) change le coefficient du polynôme ; inversement, la seconde espèce S(n, k) compte des partitions et reste non négative. Il faut donc toujours lire la lettre et la convention annoncée.

La fiche partition d'un ensemble précise la structure des blocs que S(n, k) dénombre.

L'article analyse combinatoire replace ces dénombrements parmi les méthodes consacrées aux configurations finies.