Que sont les nombres de Stirling de seconde espèce ?
Un nombre de Stirling de seconde espèce, noté \(S(n,k)\) (également écrit {n sur k} ou \(S_2(n,k)\)), dénombre les façons de partitionner un ensemble de n objets étiquetés (distinguables) en exactement k sous-ensembles non vides et non étiquetés (appelés blocs). Ce calculateur produit une ligne entière : pour un n fixé, il liste \(S(n,k)\) pour k = 0, 1, 2, ..., n — soit toutes les valeurs de la ligne n du triangle de Stirling. Il s'agit d'une quantité combinatoire de mathématiques pures, sans aucune dépendance régionale.
Mode d'emploi
Saisissez un entier n positif ou nul (le nombre d'éléments de votre ensemble) et validez. L'outil renvoie un tableau à deux colonnes, k et \(S(n,k)\), ainsi que la somme de la ligne, qui correspond au nombre de Bell \(B(n)\) — un repère de vérification bien pratique. Toutes les valeurs sont calculées avec des entiers à précision arbitraire : elles restent donc exactes même lorsqu'elles dépassent largement la capacité d'un entier 64 bits (ce qui survient vers n = 20-25).
La formule expliquée
La méthode la plus robuste repose sur la relation de récurrence $$S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)$$ construite à partir du cas de base \(S(0,0) = 1\). Les valeurs aux bornes sont \(S(n,0) = 0\) pour \(n \ge 1\), \(S(n,n) = 1\), \(S(n,1) = 1\) pour \(n \ge 1\), et \(S(n,k) = 0\) pour \(k > n\). Il existe aussi une formule explicite, $$S(n,k) = \frac{1}{k!} \cdot \sum (-1)^{k-j} \binom{k}{j} j^n$$ mais en virgule flottante elle souffre d'importantes annulations ; nous utilisons donc la récurrence avec des entiers exacts.
Exemple détaillé (n = 5)
La ligne 5 est : k=0 → 0, k=1 → 1, k=2 → 15, k=3 → 25, k=4 → 10, k=5 → 1. Vérification à partir de la ligne 4 = [0,1,7,6,1] : $$S(5,2) = 2\cdot 7 + 1 = 15$$ $$S(5,3) = 3\cdot 6 + 7 = 25$$ $$S(5,4) = 4\cdot 1 + 6 = 10$$ La somme de la ligne vaut \(0+1+15+25+10+1 = 52\), ce qui correspond au nombre de Bell \(B(5) = 52\).
Triangle de Stirling de seconde espèce (lignes 0 à 8) et nombres de Bell
Le nombre de Stirling de seconde espèce \(S(n,k)\) compte les façons de partitionner un ensemble de \(n\) éléments distincts en exactement \(k\) sous-ensembles non vides et non étiquetés. Chaque entrée suit la récurrence \(S(n,k) = k\,S(n-1,k) + S(n-1,k-1)\), avec \(S(0,0)=1\) et \(S(n,0)=0\) pour \(n\ge 1\). La somme de la ligne est le nombre de Bell \(B(n)=\sum_{k=0}^{n} S(n,k)\), c'est-à-dire le nombre total de partitions d'un ensemble à \(n\) éléments.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Somme de la ligne B(n) |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | ||||||||
| 1 | 0 | 1 | 1 | |||||||
| 2 | 0 | 1 | 1 | 2 | ||||||
| 3 | 0 | 1 | 3 | 1 | 5 | |||||
| 4 | 0 | 1 | 7 | 6 | 1 | 15 | ||||
| 5 | 0 | 1 | 15 | 25 | 10 | 1 | 52 | |||
| 6 | 0 | 1 | 31 | 90 | 65 | 15 | 1 | 203 | ||
| 7 | 0 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | 877 | |
| 8 | 0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 | 4140 |
Les cellules vides correspondent aux positions où \(k>n\), qui valent zéro par définition.
Comment lire le tableau
- Vérification détaillée de la récurrence : \(S(8,3) = 3\cdot S(7,3) + S(7,2) = 3\cdot 301 + 63 = 903 + 63 = 966\).
- Autre vérification : \(S(8,4) = 4\cdot S(7,4) + S(7,3) = 4\cdot 350 + 301 = 1400 + 301 = 1701\).
- Vérification de la somme de la ligne pour \(n=5\) : \(0+1+15+25+10+1 = 52 = B(5)\).
- Bords : \(S(n,1)=1\) et \(S(n,n)=1\) ; de plus \(S(n,2)=2^{n-1}-1\) (par exemple \(S(8,2)=127\)).
Questions fréquentes
Pourquoi \(S(n,0) = 0\) pour \(n \ge 1\) ? On ne peut pas partitionner un ensemble non vide en zéro bloc ; seul l'ensemble vide admet la partition vide, d'où \(S(0,0) = 1\).
Que représente la somme de la ligne ? La somme des \(S(n,k)\) sur tous les k donne le nombre de Bell \(B(n)\), c'est-à-dire le nombre total de partitions d'un ensemble à n éléments.
Jusqu'où peut aller n ? Cet outil accepte des valeurs jusqu'à n = 200 ; les résultats deviennent gigantesques mais restent exacts grâce à l'arithmétique sur les grands entiers.