Calculateur des nombres de Stirling de seconde espèce S(n,k)

Calculateur des nombres de Stirling de seconde espèce S(n,k)

En croissance AI Skill PRO

Entrez le calcul

Formule

S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)nS\!\left(\text{n},\,\text{k}\right) = \frac{1}{\text{k}!}\sum_{j=0}^{\text{k}} (-1)^{j}\binom{\text{k}}{j}\left(\text{k}-j\right)^{\text{n}}
Statistiques d'utilisation

Publicité

Résultats

Nombre de Stirling de seconde espèce S(5, 2)
15
façons de répartir des éléments distincts en sous-ensembles non vides (Éléments: 5 · Sous-ensembles: 2)
n (taille de l'ensemble) 5
k (sous-ensembles) 2
Notation S(n, k)

Signaler une erreur sur cette page

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.

Quatre boules étiquetées réparties dans deux boîtes non étiquetées illustrant une partition d'ensemble
\(S(n,k)\) compte les façons de répartir n éléments étiquetés en k groupes non vides et non étiquetés.

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\).

Publicité

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.

Grille triangulaire de petits nombres de Stirling disposés comme le triangle de Pascal
Un triangle de valeurs \(S(n,k)\), chacune formée à partir des deux valeurs au-dessus.

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\).

Publicité

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.

Dernière mise à jour:

Les plus populaires dans Mathématiques et statistiques

Voir toutes les calculatrices de Mathématiques et statistiques