Qu'est-ce que le nombre de Stirling de seconde espèce ?
Le nombre de Stirling de seconde espèce, noté \(S(n,k)\), compte le nombre de façons de partitionner un ensemble de n éléments distincts (étiquetés) en exactement k sous-ensembles non vides et non étiquetés. C'est une grandeur fondamentale en combinatoire, qui intervient dans les problèmes de partitions d'ensembles, de surjections et de nombres de Bell. Il s'agit d'un outil de mathématiques pures, valable de la même manière partout dans le monde.
Comment utiliser ce calculateur
Saisissez la taille de l'ensemble n et le nombre de sous-ensembles k. Les deux valeurs doivent être des entiers naturels. Cliquez sur « Calculer » pour obtenir \(S(n,k)\), le nombre exact de partitions. Si k est supérieur à n, le résultat vaut 0 : on ne peut pas remplir plus de sous-ensembles non vides qu'il n'y a d'éléments.
La formule expliquée
La forme explicite est $$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} j^{n}$$ où \(C(k,j)\) désigne le coefficient binomial. Une approche équivalente et plus sûre numériquement repose sur la relation de récurrence $$S(n,k) = k\,S(n-1,k) + S(n-1,k-1)$$ avec les cas de base \(S(0,0)=1\), \(S(n,0)=0\) pour \(n>0\) et \(S(0,k)=0\) pour \(k>0\). Ce calculateur utilise la récurrence afin d'éviter les pertes de précision liées aux nombres à virgule flottante. Quelques cas particuliers utiles : \(S(n,1)=1\), \(S(n,n)=1\) et \(S(n,2)=2^{n-1}-1\).
Exemple détaillé
Pour \(n=5\) et \(k=2\) : en utilisant le cas particulier $$S(5,2)=2^{5-1}-1=16-1=15.$$ La récurrence le confirme : $$S(5,2)=2\cdot S(4,2)+S(4,1)=2\cdot 7+1=15.$$ Il existe donc 15 façons de répartir un ensemble de 5 éléments en deux groupes non vides.
Table des nombres de Stirling de deuxième espèce S(n,k) pour n = 0 à 10
Chaque entrée est le nombre de façons de partitionner un ensemble de n éléments étiquetés en exactement k blocs non vides et non étiquetés. Le tableau est construit à partir de la récurrence \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\), avec \(S(0,0)=1\) et \(S(n,0)=S(0,n)=0\) pour \(n\ge 1\). Les cellules vides correspondent à \(k>n\), où S(n,k)=0. La dernière colonne est la somme de la ligne, qui correspond au nombre de Bell B(n). Par exemple, S(10,4) = 34105.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 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 | ||
| 9 | 0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 | 21147 | |
| 10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 | 115975 |
Vérification d'une entrée avec la récurrence : \(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\). On a toujours \(S(n,1)=1\), \(S(n,2)=2^{n-1}-1\), \(S(n,n-1)=\binom{n}{2}\) et \(S(n,n)=1\).
Termes clés et notation
- Partition d'un ensemble
- Une façon de répartir un ensemble en sous-ensembles non vides, deux à deux disjoints (blocs), dont la réunion est l'ensemble entier. L'ordre des blocs et l'ordre des éléments au sein d'un bloc n'ont pas d'importance.
- Étiquetés ou non étiquetés
- Les n éléments sont étiquetés (distinguables, par ex. 1, 2, …, n). Les k sous-ensembles ne sont pas étiquetés : échanger deux blocs donne la même partition. Si les blocs étaient étiquetés, le nombre serait k!·S(n,k) à la place.
- Bloc non vide
- Chacun des k sous-ensembles doit contenir au moins un élément. C'est pourquoi S(n,0)=0 pour n ≥ 1 et S(n,k)=0 lorsque k > n.
- Notation S(n,k)
- Le nombre de Stirling de deuxième espèce, également noté \(\left\{ n \atop k \right\}\). Il se calcule par \(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\).
- Nombre de Bell B(n)
- Le nombre total de partitions d'un ensemble à n éléments en un nombre quelconque de blocs : \(B(n)=\sum_{k=0}^{n}S(n,k)\). Les premières valeurs sont 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975.
- Coefficient binomial
- \(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\), le nombre de façons de choisir j éléments parmi k. Il apparaît dans la formule d'inclusion–exclusion ci-dessus.
- Surjection
- Une fonction d'un ensemble à n éléments sur un ensemble à k éléments dans laquelle chaque élément de l'ensemble à k éléments est atteint au moins une fois. Le nombre de telles fonctions est \(k!\cdot S(n,k)\) : on partitionne le domaine en k blocs, puis on affecte les blocs aux k cibles de k! façons.
Deuxième espèce et première espèce. Les nombres de Stirling de deuxième espèce comptent les partitions d'un ensemble en k blocs. Les nombres de Stirling de première espèce, notés \(c(n,k)\) ou \(\left[ n \atop k \right]\) (non signés), comptent les permutations de n éléments ayant exactement k cycles. Ils obéissent à une récurrence différente, \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\), et sont liés à ceux de deuxième espèce en étant des matrices inverses l'une de l'autre (au signe près).
FAQ
Pourquoi \(S(0,0)=1\) ? Par convention, l'ensemble vide admet exactement une partition en zéro parties : la partition vide.
Que se passe-t-il lorsque \(k > n\) ? Le résultat est 0, car chaque sous-ensemble doit être non vide et le nombre d'éléments est insuffisant.
Quel est le lien avec les nombres de Bell ? En additionnant \(S(n,k)\) pour tous les k allant de 0 à n, on obtient le nombre de Bell \(B(n)\), c'est-à-dire le nombre total de partitions d'un ensemble de n éléments.