nombre de Bell

Prenons trois objets distincts, nommés a, b et c, puis répartissons-les en groupes sans laisser d'objet de côté. Ils peuvent rester ensemble, être séparés tous les trois, ou former un groupe de deux accompagné d'un objet seul.

Il existe exactement cinq regroupements de ce type. Le nombre de Bell associé à trois éléments vaut donc 5. Seule compte la composition des groupes : leur ordre n'en crée pas de nouveaux.

Une partition d'un ensemble est un découpage en sous-ensembles non vides, deux à deux disjoints, dont la réunion redonne l'ensemble entier. Pour un entier n positif ou nul, le nombre noté B_n compte toutes les partitions d'un ensemble de n éléments. L'identité propre des éléments compte, mais ni le nom ni l'ordre des blocs ne changent le total.

Le cas n = 0 suit une convention cohérente : l'ensemble vide possède une unique partition, la famille vide, donc B₀ = 1. Pour calculer les termes suivants, on peut distinguer un nouvel élément. Si k désigne le nombre d'anciens éléments laissés hors de son bloc, ces k éléments se choisissent puis se partitionnent entre eux.

Le coefficient $\left(\genfrac{}{}{0px}{}{n}{k}\right)\backslash binom\{n\}\{k\}$ compte les façons de choisir les k éléments laissés hors du bloc du nouvel élément ; B_k compte ensuite leurs partitions. Par exemple, avec B₀ = 1, B₁ = 1 et B₂ = 2, prendre n = 2 donne B₃ = 1 × 1 + 2 × 1 + 1 × 2 = 5. La récurrence utilise ainsi uniquement les termes précédents. Compter les partitions revient aussi à compter les relations d'équivalence sur le même ensemble : les éléments d'un même bloc sont équivalents entre eux, et deux éléments de blocs différents ne le sont pas.

Cherchons le nombre de Bell associé à l'ensemble E = {a, b, c}. Nous allons classer ses partitions selon le nombre de blocs, afin de n'en oublier aucune et de ne pas compter deux fois le même regroupement.

Données :
ensemble étudié : E = {a, b, c} ;
nombre d'éléments : n = 3 ;
chaque bloc est non vide ;
l'ordre des blocs ne compte pas.

1. Avec un seul bloc, on obtient {a, b, c}.
2. Avec deux blocs, l'élément isolé peut être a, b ou c : {a} | {b, c}, {b} | {a, c}, {c} | {a, b}.
3. Avec trois blocs, on obtient {a} | {b} | {c}.
4. Le total vaut 1 + 3 + 1 = 5.

Ainsi, B₃ = 5. Le contrôle est refaisable en vérifiant que les cinq lignes du visuel contiennent chacune a, b et c exactement une fois, sans bloc vide, puis que les nombres de blocs possibles sont bien 1, 2 et 3.

Pour un petit ensemble, on peut énumérer les regroupements comme avec {a, b, c}. Le bon contrôle consiste à classer les partitions par nombre de blocs ; une liste non classée expose davantage aux oublis et aux doublons.

Quand n augmente, la récurrence est préférable à l'énumération. On construit une table des valeurs B₀, B₁, puis des termes suivants ; le nombre déjà très élevé B₁₃ = 27 644 437 montre pourquoi la liste exhaustive devient vite impraticable.

Si le problème est formulé avec une relation d'équivalence, on peut compter ses classes plutôt que les relations une par une. Chaque choix de classes forme une partition, ce qui ramène exactement au même nombre de Bell.

Nombre de Stirling de seconde espèce. Il compte les partitions de n éléments en exactement k blocs non vides, tandis que B_n les compte pour tous les nombres de blocs possibles. Pour {a, b, c}, le cas k = 2 donne 3 partitions, alors que B₃ = 5.

Partition ordonnée. Dans une partition d'ensemble ordinaire, permuter les blocs ne produit pas un nouveau découpage : {a} | {b, c} et {b, c} | {a} sont identiques. Si la position des blocs change l'objet compté, il s'agit d'une structure ordonnée et non du nombre de Bell.

Ensemble vide. L'absence d'éléments ne donne pas zéro possibilité : la partition vide est unique, donc B₀ = 1. Commencer la suite par 0 décale et fausse tous les calculs suivants.

Blocs vides. Ajouter un bloc vide ne crée jamais une partition supplémentaire. Le symptôme est une liste contenant un groupe sans élément ; il faut supprimer ce groupe avant de compter.

Ordre artificiel. Échanger deux blocs ou réécrire les mêmes éléments dans un autre ordre ne change pas la partition. Pour éviter les doublons, il faut comparer les sous-ensembles eux-mêmes, et non leur ordre d'affichage.

Croissance rapide. Une énumération qui fonctionne pour n = 3 ne constitue pas une méthode réaliste à toute taille : B₁₃ vaut déjà 27 644 437. Il faut alors employer une récurrence ou une autre méthode de calcul, sans tenter de dresser la liste complète.

Les nombres de Stirling affinent le comptage en fixant le nombre k de blocs. Leur somme sur toutes les valeurs possibles de k redonne le nombre de Bell.

Ici, S(n, k) désigne le nombre de partitions d'un ensemble de n éléments en exactement k blocs non vides. Cette décomposition explique le lien étroit entre les deux suites.

Le dossier Cheminement combinatoire prolonge cette démarche de dénombrement par l'organisation systématique des possibilités.