Nombres de Stirling et nombres de Bell
Les nombres de Stirling et les nombres de Bell sont des suites fondamentales de la combinatoire. Ils interviennent principalement dans les problèmes de partitionnement, de permutation, de regroupement et de répartition d'objets distincts.
Les nombres de Stirling existent sous deux formes principales. Les nombres de Stirling de première espèce comptent les permutations selon leur nombre de cycles, tandis que les nombres de Stirling de seconde espèce comptent les partitions d'un ensemble en un nombre fixé de sous-ensembles non vides.
Les nombres de Bell généralisent les nombres de Stirling de seconde espèce. Ils comptent toutes les partitions possibles d'un ensemble, sans imposer le nombre de groupes. En programmation, ces suites apparaissent dans la classification de données, le regroupement d'objets, les structures d'équivalence, les graphes, les bases de données, la génération combinatoire, les algorithmes récursifs et l'analyse de certains espaces de solutions.
Partition d'un ensemble
Une partition d'un ensemble est une collection de sous-ensembles non vides, appelés blocs, qui respectent les conditions suivantes :
- chaque élément appartient à exactement un bloc ;
- les blocs sont deux à deux disjoints ;
- l'union de tous les blocs reconstitue l'ensemble initial.
Considérons :
| E = {a,b,c} |
Une partition possible est :
| {{a,b},{c}} |
Une autre partition est :
| {{a},{b},{c}} |
Partitions de trois éléments
L'ensemble :
| {a,b,c} |
possède les cinq partitions suivantes :
| {{a,b,c}} |
| {{a},{b,c}} |
| {{b},{a,c}} |
| {{c},{a,b}} |
| {{a},{b},{c}} |
Le nombre total de partitions est donc :
| 5 |
Cette valeur correspond au troisième nombre de Bell :
| B3 = 5 |
Nombres de Stirling de première espèce
Les nombres de Stirling de première espèce comptent les permutations de n éléments comportant exactement k cycles.
Ils sont généralement notés :
| s(n,k) |
pour la version signée, et :
| c(n,k) |
ou :
| [n k] |
pour la version non signée.
La version non signée sera principalement utilisée ici.
Cycles d'une permutation
Une permutation peut être décomposée en cycles disjoints.
Par exemple, la permutation :
|
1 → 2 2 → 1 3 → 4 4 → 3 |
s'écrit :
| (1 2)(3 4) |
Elle comporte donc :
| 2 cycles |
Exemple avec trois éléments
Les permutations de :
| {1,2,3} |
peuvent être classées selon leur nombre de cycles.
Permutation possédant trois cycles :
| (1)(2)(3) |
Permutations possédant deux cycles :
|
(1 2)(3) (1 3)(2) (2 3)(1) |
Permutations possédant un cycle :
|
(1 2 3) (1 3 2) |
On obtient donc :
| c(3,1) = 2 |
| c(3,2) = 3 |
| c(3,3) = 1 |
Relation de récurrence de première espèce
Les nombres de Stirling non signés de première espèce vérifient :
|
c(n,k) = c(n-1,k-1) + (n-1)c(n-1,k) |
avec les conditions initiales :
| c(0,0) = 1 |
| c(n,0) = 0 |
pour :
| n > 0 |
et :
| c(0,k) = 0 |
pour :
| k > 0 |
Interprétation de la récurrence
Pour construire une permutation de n éléments comportant k cycles, on considère l'ajout du nouvel élément n à une permutation de n-1 éléments.
Deux possibilités existent.
Première possibilité :
| n |
forme un nouveau cycle seul.
Il faut alors partir d'une permutation de :
| n-1 |
éléments possédant :
| k-1 |
cycles.
Le nombre de possibilités est :
| c(n-1,k-1) |
Insertion dans un cycle existant
Deuxième possibilité : l'élément n est inséré dans l'un des cycles existants.
Une permutation de n-1 éléments comportant k cycles possède :
| n-1 |
positions d'insertion possibles dans sa représentation cyclique.
Le nombre de possibilités est donc :
| (n-1)c(n-1,k) |
En additionnant les deux cas :
|
c(n,k) = c(n-1,k-1) + (n-1)c(n-1,k) |
Premières valeurs de première espèce
Les premières valeurs non signées sont :
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 | 0 |
| 3 | 0 | 2 | 3 | 1 | 0 | 0 |
| 4 | 0 | 6 | 11 | 6 | 1 | 0 |
| 5 | 0 | 24 | 50 | 35 | 10 | 1 |
Cas particuliers de première espèce
Plusieurs valeurs particulières sont faciles à déterminer.
Pour :
| n ≥ 1 |
on a :
| c(n,1) = (n-1)! |
En effet, le nombre de permutations de n éléments formant un seul cycle est :
| (n-1)! |
On a aussi :
| c(n,n) = 1 |
car seule la permutation identité possède n cycles distincts.
Somme des nombres de première espèce
Toutes les permutations de n éléments peuvent être classées selon leur nombre de cycles.
Par conséquent :
| ∑k=0n c(n,k) = n! |
Par exemple, pour :
| n = 4 |
on obtient :
| 6 + 11 + 6 + 1 = 24 |
et :
| 4! = 24 |
Version signée
Les nombres de Stirling signés de première espèce sont définis par :
|
s(n,k) = (-1)n-kc(n,k) |
Ils apparaissent notamment dans les développements algébriques, les changements de base polynomiale et les relations entre puissances ordinaires et factorielles descendantes.
Factorielle descendante
La factorielle descendante est définie par :
|
xn_ = x(x-1)(x-2)...(x-n+1) |
Les nombres de Stirling signés de première espèce permettent d'écrire :
|
xn_ = ∑k=0n s(n,k)xk |
Ils convertissent donc une factorielle descendante en une combinaison de puissances ordinaires.
Exemple algébrique
Pour :
| n = 3 |
on a :
|
x3_ = x(x-1)(x-2) |
En développant :
|
x3_ = x3 - 3x2 + 2x |
Les coefficients :
| 1, -3, 2 |
sont les nombres de Stirling signés de première espèce correspondants.
Nombres de Stirling de seconde espèce
Les nombres de Stirling de seconde espèce comptent le nombre de façons de partitionner un ensemble de n éléments distincts en exactement k blocs non vides.
Ils sont généralement notés :
| S(n,k) |
ou :
| {n k} |
Les blocs ne sont pas ordonnés.
Exemple avec trois éléments
Considérons l'ensemble :
| {a,b,c} |
Partitions en un seul bloc :
| {{a,b,c}} |
Donc :
| S(3,1) = 1 |
Partitions en deux blocs :
|
{{a},{b,c}} {{b},{a,c}} {{c},{a,b}} |
Donc :
| S(3,2) = 3 |
Partition en trois blocs :
| {{a},{b},{c}} |
Donc :
| S(3,3) = 1 |
Relation de récurrence de seconde espèce
Les nombres de Stirling de seconde espèce vérifient :
|
S(n,k) = S(n-1,k-1) + kS(n-1,k) |
avec :
| S(0,0) = 1 |
| S(n,0) = 0 |
pour :
| n > 0 |
et :
| S(0,k) = 0 |
pour :
| k > 0 |
Interprétation de la récurrence de seconde espèce
Pour partitionner n éléments en k blocs, on observe le nouvel élément n.
Deux possibilités existent.
Première possibilité : l'élément n forme un bloc seul.
Les :
| n-1 |
autres éléments doivent alors être répartis en :
| k-1 |
blocs.
Le nombre de possibilités est :
| S(n-1,k-1) |
Ajout à un bloc existant
Deuxième possibilité : l'élément n est placé dans un bloc déjà existant.
Les :
| n-1 |
éléments précédents sont répartis en :
| k |
blocs.
L'élément n peut être ajouté à l'un quelconque des k blocs.
Le nombre de possibilités est donc :
| kS(n-1,k) |
En additionnant :
|
S(n,k) = S(n-1,k-1) + kS(n-1,k) |
Premières valeurs de seconde espèce
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 | 0 |
| 3 | 0 | 1 | 3 | 1 | 0 | 0 |
| 4 | 0 | 1 | 7 | 6 | 1 | 0 |
| 5 | 0 | 1 | 15 | 25 | 10 | 1 |
Cas particuliers de seconde espèce
Pour :
| n ≥ 1 |
on a :
| S(n,1) = 1 |
car tous les éléments sont placés dans un seul bloc.
On a également :
| S(n,n) = 1 |
car chaque élément forme son propre bloc.
Partitions en n-1 blocs
Pour partitionner n éléments en :
| n-1 |
blocs, exactement deux éléments doivent être placés ensemble.
Tous les autres restent seuls.
Le nombre de façons de choisir ces deux éléments est :
| C(n,2) |
Donc :
|
S(n,n-1) = C(n,2) |
Partitions en deux blocs
Pour :
| n ≥ 1 |
le nombre de partitions en deux blocs non vides est :
|
S(n,2) = 2n-1 - 1 |
En effet, on peut sélectionner un sous-ensemble non vide et non total, mais chaque partition serait comptée deux fois si l'on distinguait les deux blocs.
Formule explicite
Les nombres de Stirling de seconde espèce peuvent être calculés par inclusion-exclusion :
|
S(n,k) = 1/k! ∑i=0k (-1)k-i C(k,i) in |
Une autre écriture est :
|
S(n,k) = 1/k! ∑i=0k (-1)i C(k,i) (k-i)n |
Interprétation par fonctions surjectives
Considérons un ensemble de n éléments et k catégories distinctes.
Le nombre de fonctions surjectives vers ces catégories est :
| k!S(n,k) |
En effet :
- `S(n,k)` partitionne les éléments en `k blocs non vides` ;
- `k!` affecte chacun des blocs à une catégorie distincte.
Inclusion-exclusion et surjections
Le nombre total de fonctions d'un ensemble de n éléments vers un ensemble de k éléments est :
| kn |
Pour compter les fonctions surjectives, on retire celles qui omettent au moins une valeur du codomaine.
Le principe d'inclusion-exclusion donne :
|
k!S(n,k) = ∑i=0k (-1)i C(k,i) (k-i)n |
En divisant par :
| k! |
on retrouve la formule explicite de :
| S(n,k) |
Puissances ordinaires et factorielles descendantes
Les nombres de Stirling de seconde espèce permettent d'écrire une puissance ordinaire comme une combinaison de factorielles descendantes :
|
xn = ∑k=0n S(n,k)xk_ |
Cette relation est l'inverse de celle utilisant les nombres de Stirling de première espèce.
Exemple algébrique de seconde espèce
Pour :
| n = 3 |
on a :
|
x3 = S(3,1)x1_ + S(3,2)x2_ + S(3,3)x3_ |
Comme :
|
S(3,1)=1 S(3,2)=3 S(3,3)=1 |
on obtient :
|
x3 = x + 3x(x-1) + x(x-1)(x-2) |
Nombres de Stirling comme matrices inverses
Les matrices triangulaires formées par :
| s(n,k) |
et :
| S(n,k) |
sont inverses l'une de l'autre.
Cela signifie notamment que :
|
∑k s(n,k)S(k,m) = δnm |
où :
| δnm |
est le symbole de Kronecker.
Il vaut 1 lorsque :
| n = m |
et 0 autrement.
Nombres de Bell
Le nombre de Bell d'indice n, noté :
| Bn |
compte le nombre total de partitions d'un ensemble de n éléments distincts, sans imposer le nombre de blocs.
Il s'obtient en additionnant tous les nombres de Stirling de seconde espèce d'une même ligne :
|
Bn = ∑k=0n S(n,k) |
Premiers nombres de Bell
Les premières valeurs sont :
|
B0 = 1 B1 = 1 B2 = 2 B3 = 5 B4 = 15 B5 = 52 B6 = 203 B7 = 877 B8 = 4140 B9 = 21147 B10 = 115975 |
La suite commence donc par :
| 1, 1, 2, 5, 15, 52, 203, 877, 4140, ... |
Exemple avec quatre éléments
Pour un ensemble de quatre éléments :
| E = {a,b,c,d} |
on obtient :
| S(4,1) = 1 |
| S(4,2) = 7 |
| S(4,3) = 6 |
| S(4,4) = 1 |
Donc :
|
B4 = 1 + 7 + 6 + 1 = 15 |
Interprétation des nombres de Bell
Les nombres de Bell comptent toutes les façons de regrouper des objets distincts lorsque :
- chaque objet appartient à un seul groupe ;
- aucun groupe n'est vide ;
- l'ordre des groupes n'est pas pris en compte ;
- le nombre de groupes n'est pas fixé.
Ils comptent donc les partitions en 1 bloc, 2 blocs, 3 blocs, et ainsi de suite.
Relation de récurrence des nombres de Bell
Les nombres de Bell vérifient :
|
Bn+1 = ∑k=0n C(n,k)Bk |
avec :
| B0 = 1 |
Interprétation de la récurrence de Bell
Considérons un ensemble de :
| n+1 |
éléments et choisissons un élément particulier.
Supposons que son bloc contient :
| n-k |
autres éléments.
Ces éléments peuvent être choisis de :
| C(n,n-k) |
façons.
Les k éléments restants peuvent être partitionnés de :
| Bk |
façons.
En sommant toutes les valeurs possibles de k, on obtient la récurrence.
Triangle de Bell
Le triangle de Bell, aussi appelé triangle d'Aitken, permet de calculer les nombres de Bell par additions successives.
On commence par :
| 1 |
Puis chaque nouvelle ligne commence par le dernier élément de la ligne précédente.
Chaque élément suivant est la somme :
- de l'élément situé à gauche ;
- de l'élément situé en haut à gauche.
Exemple de triangle de Bell
|
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 |
Les premiers éléments des lignes donnent :
| 1, 1, 2, 5, 15, ... |
et les derniers éléments fournissent également les nombres de Bell suivants.
Construction du triangle de Bell
Pour une ligne donnée :
|
ligne[i][0] = ligne[i-1][i-1] |
Puis :
|
ligne[i][j] = ligne[i][j-1] + ligne[i-1][j-1] |
pour :
| j ≥ 1 |
Cette méthode permet un calcul simple sans utiliser directement les nombres de Stirling.
Formule de Dobinski
Les nombres de Bell possèdent une formule remarquable appelée formule de Dobinski :
|
Bn = 1/e ∑k=0∞ kn/k! |
Cette formule contient une somme infinie, mais elle converge.
Elle relie les nombres de Bell à l'exponentielle et aux moments de la loi de Poisson.
Interprétation probabiliste
Si une variable aléatoire :
| X |
suit une loi de Poisson de paramètre 1, alors :
|
Bn = E[Xn] |
Les nombres de Bell sont donc les moments ordinaires d'une variable de Poisson de moyenne 1.
Fonction génératrice exponentielle des nombres de Bell
La fonction génératrice exponentielle des nombres de Bell est :
|
∑n=0∞ Bn xn/n! = e^(ex-1) |
Cette formule reflète le fait qu'une partition est un ensemble de blocs non vides.
Fonction génératrice de Stirling de seconde espèce
Pour un entier k fixé, la fonction génératrice exponentielle est :
|
∑n=k∞ S(n,k)xn/n! = (ex-1)k/k! |
Le terme :
| ex-1 |
représente un bloc non vide.
La puissance k représente les k blocs, et la division par :
| k! |
retire l'ordre artificiel entre ces blocs.
Polynômes de Bell
Les polynômes de Bell, également appelés polynômes de Touchard dans certaines formes, sont définis par :
|
Bn(x) = ∑k=0n S(n,k)xk |
En évaluant :
| x = 1 |
on retrouve :
| Bn(1) = Bn |
Polynômes de Touchard
Les polynômes de Touchard vérifient :
|
Tn(x) = ∑k=0n S(n,k)xk |
Ils généralisent les nombres de Bell.
Pour :
| x = 1 |
on obtient le nombre total de partitions.
Pour une autre valeur de x, chaque partition reçoit un poids dépendant de son nombre de blocs.
Exemple de polynôme de Touchard
Pour :
| n = 3 |
on a :
| S(3,1)=1 |
| S(3,2)=3 |
| S(3,3)=1 |
Donc :
|
T3(x) = x + 3x2 + x3 |
En évaluant :
|
T3(1) = 1+3+1 = 5 |
on retrouve :
| B3 = 5 |
Partitions et relations d'équivalence
Chaque partition d'un ensemble correspond à une relation d'équivalence.
Deux éléments sont considérés comme équivalents lorsqu'ils appartiennent au même bloc.
Les nombres de Bell comptent donc également le nombre de relations d'équivalence possibles sur un ensemble de n éléments.
Exemple de relation d'équivalence
Pour l'ensemble :
| {a,b,c} |
la partition :
| {{a,b},{c}} |
correspond à la relation où :
| a ~ b |
tandis que :
| c |
forme sa propre classe d'équivalence.
Le nombre total de relations d'équivalence sur trois éléments est donc :
| B3 = 5 |
Répartition dans des groupes non nommés
Les nombres de Stirling de seconde espèce comptent la répartition de n objets distincts dans exactement k groupes non nommés et non vides.
Si les groupes sont nommés, il faut multiplier par :
| k! |
On obtient alors le nombre de surjections :
| k!S(n,k) |
Groupes nommés avec cases vides autorisées
Si les k groupes sont nommés et que certains groupes peuvent être vides, chaque objet possède :
| k |
choix indépendants.
Le nombre de répartitions est donc :
| kn |
Il faut donc distinguer :
| Type de groupes | Cases vides | Nombre |
|---|---|---|
| Non nommés | Non | S(n,k) |
| Nommés | Non | k!S(n,k) |
| Nommés | Oui | kn |
Partitions ordonnées
Si l'ordre des blocs est important, on parle parfois de partitions ordonnées.
Le nombre de partitions ordonnées de n éléments en exactement k blocs est :
| k!S(n,k) |
Le nombre total de partitions ordonnées est donné par les nombres de Fubini, aussi appelés nombres de Bell ordonnés.
Comparaison avec les nombres de Catalan
Les nombres de Catalan et les nombres de Bell comptent tous deux des structures combinatoires, mais leurs contraintes diffèrent.
Les nombres de Catalan comptent généralement des structures :
- récursives ;
- ordonnées ;
- planaires ;
- non croisées.
Les nombres de Bell comptent toutes les partitions d'un ensemble sans ordre entre les blocs.
Exemple comparatif
Pour :
| n = 4 |
on a :
| C4 = 14 |
et :
| B4 = 15 |
Ces valeurs sont proches par hasard pour ce petit indice, mais les suites comptent des objets très différents et leur croissance diverge rapidement.
Comparaison avec les coefficients binomiaux
Un coefficient binomial :
| C(n,k) |
compte les sous-ensembles de taille k.
Un nombre de Stirling :
| S(n,k) |
compte les partitions en k blocs non vides.
Un nombre de Bell :
| Bn |
compte toutes les partitions, quelle que soit leur quantité de blocs.
Dénombrement des classifications
Supposons que n documents distincts doivent être regroupés en exactement k catégories, sans nommer les catégories et sans laisser de catégorie vide.
Le nombre de regroupements possibles est :
| S(n,k) |
Si le nombre de catégories n'est pas fixé, le nombre total de regroupements est :
| Bn |
Exemple de classification
Pour quatre documents :
| D1,D2,D3,D4 |
le nombre de façons de les répartir dans exactement deux groupes non vides est :
| S(4,2) = 7 |
Le nombre total de regroupements possibles est :
| B4 = 15 |
Applications dans les bases de données
Les nombres de Bell peuvent représenter le nombre de regroupements possibles d'un ensemble de colonnes, d'enregistrements ou de critères.
Ils interviennent notamment dans :
- la recherche de partitions de schémas ;
- la classification de lignes ;
- l'analyse de dépendances ;
- le regroupement de requêtes ;
- la génération de stratégies d'exécution.
Le nombre de possibilités peut croître très rapidement.
Applications en apprentissage automatique
Dans certains problèmes de regroupement non supervisé, on cherche à diviser n observations en groupes.
Si le nombre de groupes est fixé à k, l'espace théorique contient :
| S(n,k) |
partitions possibles.
Si le nombre de groupes est inconnu, l'espace complet contient :
| Bn |
partitions.
Cette croissance explique pourquoi l'exploration exhaustive est rapidement impossible.
Applications en graphes
Les partitions d'un ensemble de sommets apparaissent dans :
- le regroupement de sommets ;
- la décomposition de graphes ;
- les problèmes de coloration ;
- les contractions ;
- la recherche de communautés ;
- les coupes et partitions de réseau.
Les nombres de Stirling et de Bell permettent d'estimer le nombre théorique de configurations.
Coloration avec toutes les couleurs utilisées
Le nombre de façons d'attribuer k couleurs distinctes à n objets, en utilisant toutes les couleurs, est :
| k!S(n,k) |
Il s'agit du nombre de fonctions surjectives d'un ensemble de n objets vers un ensemble de k couleurs.
Cette formule ne tient pas compte de contraintes d'adjacence comme dans une coloration propre de graphe.
États d'égalité entre variables
Supposons qu'un programme manipule n variables et que l'on souhaite décrire uniquement quelles variables possèdent des valeurs égales.
Chaque configuration d'égalité correspond à une partition des variables en classes.
Le nombre de configurations possibles est donc :
| Bn |
Cette idée intervient dans l'analyse symbolique et la vérification de programmes.
Unification et classes d'équivalence
Dans les algorithmes d'unification, plusieurs symboles peuvent être regroupés en classes d'équivalence.
Le nombre de regroupements théoriquement possibles de n symboles est :
| Bn |
Les algorithmes pratiques ne les énumèrent généralement pas toutes, mais utilisent des structures comme les ensembles disjoints.
Structures Union-Find
Une structure Union-Find, ou structure d'ensembles disjoints, représente une partition dynamique d'un ensemble.
Les opérations principales sont :
| Find |
pour identifier le bloc d'un élément, et :
| Union |
pour fusionner deux blocs.
Chaque état possible de cette structure correspond à une partition et est donc compté par un nombre de Bell.
Partitions de tâches
Dans un système parallèle, on peut vouloir répartir n tâches distinctes dans k groupes d'exécution non vides, sans distinguer l'identité des groupes.
Le nombre de répartitions est :
| S(n,k) |
Si les processeurs sont distingués, le nombre devient :
| k!S(n,k) |
à condition que chaque processeur reçoive au moins une tâche.
Génération récursive des partitions
Une partition de :
| {1,2,...,n} |
peut être construite à partir d'une partition de :
| {1,2,...,n-1} |
Le nouvel élément n peut :
- être ajouté à l'un des blocs existants ;
- former un nouveau bloc.
Cette construction correspond directement à la récurrence des nombres de Stirling de seconde espèce.
Représentation par croissance restreinte
Une partition peut être représentée par une chaîne de croissance restreinte.
Par exemple, la partition :
| {{1,3},{2,5},{4}} |
peut être représentée par :
| 0,1,0,2,1 |
Chaque valeur indique le bloc auquel appartient l'élément correspondant.
Règle d'une chaîne de croissance restreinte
Une chaîne :
| a1,a2,...,an |
est valide si :
| a1 = 0 |
et, pour :
| i > 1 |
|
ai ≤ 1 + max(a1,...,ai-1) |
Chaque chaîne valide correspond exactement à une partition d'ensemble.
Génération de toutes les partitions
|
MODULE GénérerPartitions(position,n,représentation,maximum) SI position > n ALORS AFFICHER représentation RETOURNER FIN SI POUR bloc ← 0 JUSQU'A maximum+1 représentation[position] ← bloc GénérerPartitions( position+1, n, représentation, MAXIMUM(maximum,bloc) ) FIN POUR |
Pour la première position, on fixe généralement :
| représentation[1] = 0 |
Nombre de résultats générés
Un algorithme générant toutes les partitions d'un ensemble de n éléments produit exactement :
| Bn |
résultats.
Comme chaque partition nécessite au moins :
| O(n) |
informations pour être représentée, le coût total est au moins :
| O(nBn) |
si toutes les partitions sont matérialisées ou affichées.
Calcul dynamique des nombres de Stirling
Les nombres de Stirling de seconde espèce peuvent être calculés par programmation dynamique.
|
MODULE StirlingDeuxièmeEspèce(n,k) Créer tableau S[0..n][0..k] S[0][0] ← 1 POUR i ← 1 JUSQU'A n POUR j ← 1 JUSQU'A MINIMUM(i,k) S[i][j] ← S[i-1][j-1] + j × S[i-1][j] FIN POUR FIN POUR RETOURNER S[n][k] |
Complexité du calcul dynamique
Le tableau comporte environ :
| n × k |
cases.
La complexité temporelle est donc :
| O(nk) |
La mémoire est également :
| O(nk) |
Elle peut être réduite à :
| O(k) |
si seule la ligne précédente est conservée.
Optimisation sur une seule ligne
Pour calculer les nombres de Stirling de seconde espèce avec un seul tableau :
|
S[0] ← 1 POUR i ← 1 JUSQU'A n POUR j ← MINIMUM(i,k) JUSQU'A 1 EN DESCENDANT S[j] ← S[j-1] + j × S[j] FIN POUR S[0] ← 0 FIN POUR |
La boucle doit être parcourue en ordre décroissant pour ne pas écraser les valeurs encore nécessaires.
Calcul des nombres de Bell
Les nombres de Bell peuvent être calculés en additionnant une ligne de nombres de Stirling :
|
MODULE Bell(n) résultat ← 0 POUR k ← 0 JUSQU'A n résultat ← résultat + StirlingDeuxièmeEspèce(n,k) FIN POUR RETOURNER résultat |
Une méthode utilisant directement le triangle de Bell peut toutefois être plus simple.
Algorithme du triangle de Bell
|
MODULE NombresDeBell(n) Créer triangle[0..n][0..n] triangle[0][0] ← 1 POUR i ← 1 JUSQU'A n triangle[i][0] ← triangle[i-1][i-1] POUR j ← 1 JUSQU'A i triangle[i][j] ← triangle[i][j-1] + triangle[i-1][j-1] FIN POUR FIN POUR RETOURNER triangle[n][0] |
Exemple en Java
- import java.math.BigInteger;
-
- public final class StirlingBellNumbers {
-
- private StirlingBellNumbers() {
- }
-
- public static BigInteger stirlingSecondKind(
- int n,
- int k
- ) {
- if (n < 0 || k < 0 || k > n) {
- return BigInteger.ZERO;
- }
-
- BigInteger[] values =
- new BigInteger[k + 1];
-
- for (int i = 0; i <= k; i++) {
- values[i] = BigInteger.ZERO;
- }
-
- values[0] = BigInteger.ONE;
-
- for (int i = 1; i <= n; i++) {
- int maximum = Math.min(i, k);
-
- for (
- int j = maximum;
- j >= 1;
- j--
- ) {
- values[j] =
- values[j - 1].add(
- values[j].multiply(
- BigInteger.valueOf(j)
- )
- );
- }
-
- values[0] = BigInteger.ZERO;
- }
-
- return values[k];
- }
-
- public static BigInteger bell(int n) {
- if (n < 0) {
- throw new IllegalArgumentException(
- "L'indice ne peut pas être négatif."
- );
- }
-
- BigInteger resultat =
- BigInteger.ZERO;
-
- for (int k = 0; k <= n; k++) {
- resultat = resultat.add(
- stirlingSecondKind(n, k)
- );
- }
-
- return resultat;
- }
-
- public static void main(String[] args) {
- System.out.println(
- "S(5,3) = "
- + stirlingSecondKind(5, 3)
- );
-
- for (int n = 0; n <= 10; n++) {
- System.out.println(
- "B_" + n + " = " + bell(n)
- );
- }
- }
- }
Résultat du programme
Le programme affiche notamment :
| S(5,3) = 25 |
Puis :
|
B_0 = 1 B_1 = 1 B_2 = 2 B_3 = 5 B_4 = 15 B_5 = 52 B_6 = 203 B_7 = 877 B_8 = 4140 B_9 = 21147 B_10 = 115975 |
Calcul des nombres de première espèce
|
MODULE StirlingPremièreEspèce(n,k) Créer tableau C[0..n][0..k] C[0][0] ← 1 POUR i ← 1 JUSQU'A n POUR j ← 1 JUSQU'A MINIMUM(i,k) C[i][j] ← C[i-1][j-1] + (i-1) × C[i-1][j] FIN POUR FIN POUR RETOURNER C[n][k] |
Cette structure est très proche de celle utilisée pour la seconde espèce.
Différence entre les deux récurrences
Première espèce :
|
c(n,k) = c(n-1,k-1) + (n-1)c(n-1,k) |
Seconde espèce :
|
S(n,k) = S(n-1,k-1) + kS(n-1,k) |
Le facteur :
| n-1 |
de la première espèce correspond aux positions d'insertion dans les cycles.
Le facteur :
| k |
de la seconde espèce correspond au choix d'un bloc existant.
Dépassement de capacité
Les nombres de Stirling et de Bell augmentent rapidement.
Les types entiers de 32 ou 64 bits deviennent rapidement insuffisants.
Il est préférable d'utiliser :
- des entiers multiprécision ;
- une arithmétique modulaire ;
- des logarithmes ;
- des approximations asymptotiques ;
- des bibliothèques de calcul symbolique.
Croissance des nombres de Bell
Les nombres de Bell croissent plus rapidement que toute exponentielle de base constante :
| cn |
pour une constante fixe c, lorsque n devient suffisamment grand.
Ils croissent toutefois moins rapidement que :
| n! |
à certains niveaux de comparaison asymptotique, bien que les relations précises soient plus subtiles.
Cette croissance rend l'énumération de toutes les partitions rapidement impraticable.
Valeurs élevées
Par exemple :
| B10 = 115 975 |
| B15 = 1 382 958 545 |
| B20 = 51 724 158 235 372 |
Même pour des ensembles relativement petits, le nombre de partitions devient très important.
Calcul modulo un entier
Dans certains problèmes, on cherche :
| S(n,k) mod m |
ou :
| Bn mod m |
Les relations de récurrence se prêtent directement au calcul modulaire :
|
S(n,k) ≡ S(n-1,k-1) + kS(n-1,k) (mod m) |
On applique le modulo après chaque addition et multiplication afin de limiter la taille des valeurs intermédiaires.
Exemple de récurrence modulaire
|
S[j] ← ( S[j-1] + j × S[j] ) MOD m |
Cette méthode fonctionne avec un module premier ou composé, car elle n'utilise aucune division.
Applications en programmation dynamique
Les nombres de Stirling apparaissent dans les problèmes où un ensemble d'éléments doit être divisé en un nombre fixé de groupes.
Les nombres de Bell apparaissent lorsque le nombre de groupes est libre.
Ces problèmes peuvent être résolus par :
- programmation dynamique ;
- génération récursive ;
- retour arrière ;
- calcul symbolique ;
- inclusion-exclusion ;
- fonctions génératrices.
Applications en analyse d'algorithmes
Les nombres de Bell fournissent une borne sur le nombre de partitions que certains algorithmes peuvent devoir examiner.
Par exemple, un algorithme explorant toutes les manières de regrouper n objets possède un espace de recherche de taille :
| Bn |
Sa complexité devient donc super-exponentielle dans de nombreux cas pratiques.
Applications en compilation
Dans un compilateur ou un optimiseur, on peut vouloir partitionner :
- des variables ;
- des expressions ;
- des blocs d'instructions ;
- des registres ;
- des dépendances ;
- des ensembles d'alias.
Le nombre de partitions possibles est gouverné par les nombres de Bell.
Allocation de registres
Dans une modélisation simplifiée, des variables pouvant partager le même registre peuvent être regroupées.
Chaque regroupement potentiel constitue une partition.
Le nombre théorique de regroupements de n variables est donc :
| Bn |
Les contraintes d'interférence réduisent ensuite l'espace réellement admissible.
Partitionnement de graphes
Le partitionnement d'un ensemble de sommets en k groupes non vides possède :
| S(n,k) |
configurations non étiquetées.
Si les groupes sont associés à des machines, des couleurs ou des zones distinctes, le nombre devient :
| k!S(n,k) |
Clustering
Dans un problème de clustering de n observations en exactement k classes, sans étiqueter les classes, le nombre de partitions possibles est :
| S(n,k) |
Lorsque le nombre de classes est libre, l'espace total contient :
| Bn |
possibilités.
Cette croissance justifie l'utilisation d'heuristiques et d'algorithmes d'optimisation.
Partitions de paramètres
Lors de tests logiciels, on peut répartir des paramètres ou des cas d'entrée en classes d'équivalence.
Le nombre de regroupements possibles de n cas distincts est :
| Bn |
L'examen exhaustif de toutes ces partitions devient rapidement impossible.
Comparaison récapitulative
| Suite | Objet compté |
|---|---|
| Stirling de première espèce c(n,k) | Permutations de n éléments ayant k cycles |
| Stirling de première espèce signée s(n,k) | Coefficients algébriques avec signes |
| Stirling de seconde espèce S(n,k) | Partitions de n éléments en k blocs non vides |
| Bell Bn | Toutes les partitions d'un ensemble de n éléments |
| k!S(n,k) | Surjections vers k valeurs ou groupes nommés non vides |
Tableau de formules
| Formule | Signification |
|---|---|
| c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k) | Récurrence de première espèce |
| S(n,k)=S(n-1,k-1)+kS(n-1,k) | Récurrence de seconde espèce |
| ∑kc(n,k)=n! | Toutes les permutations |
| Bn=∑kS(n,k) | Toutes les partitions |
| k!S(n,k) | Nombre de surjections |
| xn=∑kS(n,k)xk_ | Conversion vers les factorielles descendantes |
| xn_=∑ks(n,k)xk | Conversion vers les puissances ordinaires |
| Bn+1=∑kC(n,k)Bk | Récurrence des nombres de Bell |
Avantages
Les nombres de Stirling et de Bell présentent plusieurs avantages :
- ils fournissent des formules précises pour les problèmes de partitionnement ;
- ils relient les permutations, les cycles et les partitions ;
- ils possèdent des relations de récurrence simples ;
- ils peuvent être calculés efficacement par programmation dynamique ;
- ils interviennent dans le dénombrement des fonctions surjectives ;
- ils permettent d'analyser la taille des espaces de regroupement ;
- ils possèdent des fonctions génératrices élégantes ;
- ils établissent des liens entre la combinatoire et l'algèbre ;
- ils permettent de modéliser des classes d'équivalence ;
- ils apparaissent dans de nombreux problèmes de graphes et de classification.
Limites et précautions
Plusieurs précautions doivent être prises :
- il faut distinguer la première et la seconde espèce ;
- les blocs d'une partition ne sont pas ordonnés ;
- les groupes nommés nécessitent généralement un facteur k! ;
- les blocs doivent être non vides dans S(n,k) ;
- les nombres augmentent très rapidement ;
- les types entiers ordinaires débordent rapidement ;
- l'énumération exhaustive des partitions devient vite impraticable ;
- la version signée de première espèce ne doit pas être confondue avec la version non signée ;
- le nombre de Bell compte tous les nombres possibles de blocs ;
- les récurrences doivent être initialisées avec soin ;
- une boucle d'optimisation mémoire doit être parcourue en ordre décroissant.
Remarque
Les nombres de Stirling et les nombres de Bell constituent des outils essentiels pour étudier les permutations et les partitions d'ensembles. Les nombres de Stirling de première espèce organisent les permutations selon leur nombre de cycles, tandis que ceux de seconde espèce organisent les partitions selon leur nombre de blocs.
Les nombres de Bell additionnent toutes les partitions possibles et permettent ainsi de mesurer la taille totale d'un espace de regroupement. En programmation, ils apparaissent dans les algorithmes de classification, les relations d'équivalence, les structures Union-Find, le partitionnement de graphes, l'apprentissage automatique, la compilation et l'analyse de complexité.
Leur croissance rapide illustre une nouvelle forme d'explosion combinatoire. Ils préparent naturellement à l'étude des nombres de Bell ordonnés, des nombres de Lah, des polynômes de Touchard, des fonctions génératrices exponentielles et des algorithmes avancés de génération de partitions.