Nombres de Stirling de seconde espèce

Les nombres de Stirling de seconde espèce répondent à une question de dénombrement fondamentale en mathématiques discrètes : étant donné n objets distincts, de combien de façons pouvez-vous les partitionner en exactement k groupes non vides non étiquetés ? La réponse s'écrit S(n,k) ou parfois {n choose k} avec des accolades. Ces nombres apparaissent dès que vous regroupez des personnes en équipes sans nommer les équipes, répartissez un ensemble de clés dans des seaux non étiquetés, comptez les fonctions surjectives à un facteur factoriel près, construisez les nombres de Bell comme somme sur k, ou notez des devoirs qui demandent des partitions d'ensembles plutôt que des permutations. Cette capacité accepte des entiers non négatifs n (nombre d'éléments) et k (nombre de sous-ensembles non vides) et renvoie le S(n,k) exact sous forme de chaîne décimale calculée par programmation dynamique BigInt, de sorte que des valeurs bien au-delà des limites d'entiers sûrs ordinaires restent correctes chiffre par chiffre. Les entrées avec un k négatif ou un k supérieur à n sont rejetées avec une erreur de validation claire au lieu d'un zéro silencieux ou d'une mauvaise réponse.

Comment se définissent les nombres de Stirling de seconde espèce

Un nombre de Stirling de seconde espèce S(n,k) compte les partitions d'un ensemble à n éléments en exactement k sous-ensembles non vides non étiquetés. L'ordre à l'intérieur d'un sous-ensemble n'importe pas, et les sous-ensembles eux-mêmes ne sont pas ordonnés : la partition {{1,2},{3}} est la même que {{3},{1,2}}. La récurrence standard est S(n,k) = k · S(n−1,k) + S(n−1,k−1).

Intuitivement, lorsque vous ajoutez le plus récent élément n, soit il forme un singleton à lui seul (alors les n−1 éléments restants forment k−1 sous-ensembles, comptés par S(n−1,k−1)), soit il rejoint l'un des k sous-ensembles existants dans une partition des n−1 premiers éléments en k blocs (k choix, fois S(n−1,k)). Les cas de base qui ferment la table sont S(0,0) = 1, S(n,0) = 0 pour n > 0, S(0,k) = 0 pour k > 0, S(n,1) = 1 et S(n,n) = 1.

Vérifications classiques de manuel : S(3,2) = 3, S(4,2) = 7, S(5,2) = 15 et S(5,3) = 25. Le nombre de Bell B_n, total des partitions d'un n-ensemble avec n'importe quel nombre de blocs, est la somme de S(n,k) sur k de zéro à n. Objets liés mais différents : nombres de Stirling de première espèce (qui suivent les permutations par nombre de cycles) et coefficients binomiaux (qui choisissent des éléments sans partitionner le reste).

Cette implémentation n'utilise jamais d'approximation flottante, d'échantillonnage Monte Carlo ni de tables externes : elle remplit une ligne de programmation dynamique avec une arithmétique BigInt exacte pour que chaque chiffre soit correct. Le chemin est entièrement déterministe — sans graines aléatoires, horloges, réseau ni dérive de modèle — de sorte que les mêmes n et k produisent toujours la même chaîne.

Où les dénombrements de Stirling de seconde espèce apparaissent dans le travail réel

Les cours de combinatoire et les concours de programmation demandent constamment de combien de façons scinder n personnes étiquetées en k équipes non étiquetées, combien de relations d'équivalence sur n éléments ont exactement k classes, ou de combien de façons distribuer n cadeaux distincts dans k boîtes identiques non vides — tout cela égale S(n,k).

Les concepteurs d'algorithmes utilisent des tables de Stirling de seconde espèce pour analyser des structures de données de partition d'ensembles, des croquis de clustering à nombre fixe de clusters, ou compter les façons dont un processus récursif peut regrouper des résultats intermédiaires. Les cours de probabilité et de statistique relient S(n,k) au nombre de façons d'assigner n résultats distincts à k seaux non vides non étiquetés et à la forme fermée du nombre de surjections d'un n-ensemble sur un k-ensemble, qui est k!

· S(n,k). Éducateurs et préparation aux entretiens montrent souvent un court triangle de petites valeurs S(n,k) ; calculer une seule entrée en un appel maintient les démos interactives alignées sur manuels et corrigés sans entretenir à la main de grandes tables. Si vous avez ensuite besoin des nombres de Stirling de première espèce, des nombres de Bell seuls, des dénombrements de surjection avec le facteur k!

déjà appliqué, ou d'une liste explicite de partitions plutôt que du compte, traitez-les comme des intentions de recherche distinctes plutôt que de surcharger cette page.