Triangle de Bell

En mathématiques, plus précisément en combinatoire, le triangle de Bell est un tableau triangulaire de nombres analogue au triangle de Pascal, dont les termes dénombrent les partitions d'un ensemble dans lesquelles un élément donné forme le singleton de plus grande valeur. Il est ainsi appelé pour sa connexion étroite avec les nombres de Bell, que l'on trouve des deux côtés du triangle. La construction de ce triangle est du reste un moyen simple d'obtenir les premiers nombres de Bell. Le triangle de Bell a été découvert indépendamment par plusieurs auteurs, dont Charles Sanders Peirce en 1880 et Alexander Aitken en 1933 et pour cette raison a également été appelé triangle de Peirce ou tableau d'Aitken .

Construction du triangle de Bell

Ce triangle forme la suite A011971 de l'OEIS.

Construction

On commence par écrire 1 sur la première ligne, puis chaque ligne est obtenue en commençant par le dernier nombre de la ligne précédente et pour obtenir un terme, on additionne le nombre précédent avec celui qui se trouve immédiatement au dessus de celui-ci. Chaque ligne aura ainsi un terme de plus que la ligne précédente.

${\begin{array}{cc|cccccc}&k&0&1&2&3&4&5\\n&&\\\hline 0&&1\\1&&1&2\\2&&2&3&5\\3&&5&7&10&15\\4&&15&20&27&37&52\\5&&52&67&87&114&151&203\end{array}}$

Définition par récurrence

Notant, pour $0\leqslant k\leqslant n$, $B(n,k)$ le terme de la ligne d'indice n et de la colonne d'indice k, la définition par récurrence s'écrit :

$B(0,0)=1$, $B(n,0)=B(n-1,n-1)$ pour $n\geqslant 1$, $B(n,k)=B(n,k-1)+B(n-1,k-1)$ pour $1\leqslant k\leqslant n$.

Lien avec les nombres de Bell

Les nombres de Bell $B_{n}$, dénombrant les partitions d'un n-ensemble ou de manière équivalente les relations d'équivalence sur cet ensemble, apparaissent dans la première colonne et la diagonale : $B(n,0)=B_{n},B(n,n)=B_{n+1}$.

La relation: $B(n,k)=\sum _{i=0}^{k}{\binom {k}{i}}B(n-i,0)$, se démontrant facilement par récurrence, conjointement à la relation définissant les nombres de Bell : $B_{n}=\sum _{i=0}^{n}{\binom {n}{i}}B_{i}=\sum _{i=0}^{n}{\binom {n}{i}}B_{n-i}$, permettent de prouver ce résultat.

On en déduit donc l'expression des termes du triangle de Bell en fonction des nombres de Bell : $B(n,k)=\sum _{i=0}^{k}{\binom {k}{i}}B_{n-i}$.

Interprétation combinatoire

Sun & Wu ont donné en 2011 l'interprétation combinatoire suivante des termes du triangle : $B(n,k)$ dénombre les partitions de l'ensemble $\{0,1,2,..,n,n+1\}$ possédant $\{k+1\}$ comme élément, et tel que $\{k+1\}$ est le singleton ayant la plus grande valeur parmi les singletons de la partition.

Par exemple, $B(n,n)$ dénombre les partitions de $\{0,1,2,..,n,n+1\}$ dont $\{n+1\}$ est un élément, donc dénombre les partitions de $\{0,1,2,..,n\}$ et est bien égal à $B_{n+1}$.

$B(2,0)=2$ dénombre les partitions de $\{0,1,2,3\}$ dont $\{1\}$ est un élément, et n'ayant pas d'autre singleton que $\{0\}$ ; il existe bien deux partitions de ce type : $\{\{1\},\{0\},\{2,3\}\}$ et $\{\{1\},\{0,2,3\}\}$.

$B(2,1)=3$ dénombre les partitions de $\{0,1,2,3\}$ dont $\{2\}$ est un élément, et n'ayant pas d'autre singleton que $\{0\}$ ou $\{1\}$ ; Il existe bien trois partitions de ce type : $\{\{2\},\{0\},\{1,3\}\}$ , $\{\{2\},\{1\},\{0,3\}\}$ et $\{\{2\},\{0,1,3\}\}$.

L'interprétation suivante a été donnée par Knuth : $B(n,k)$ dénombre les partitions de $\{0,1,2,..,n\}$ dans lesquelles les parties contenant n ne contiennent aucun nombre entre k et n-1.

Par exemple, $B(n,n)$ dénombre les partitions de $\{0,1,2,..,n\}$ et est bien égal à $B_{n+1}$. $B(n,0)$ dénombre les partitions de $\{0,1,2,..,n\}$ dont le seul élément contenant n est $\{n\}$ et est bien égal à $B_{n}$.

Diagonales et sommes de ligne

La relation $B(n,k)=B(n,k+1)-B(n-1,k)$ montre que chaque diagonale est formée des différences successives des termes de la diagonale située au-dessus.

De cette façon, comme l'a observé Aitken, ce triangle peut être interprété comme implémentant la formule d'interpolation de Gregory – Newton, qui trouve les coefficients d'un polynôme à partir de la séquence de ses valeurs à des entiers consécutifs en utilisant des différences successives. Cette formule ressemble étroitement à une relation de récurrence qui peut être utilisée pour définir les nombres de Bell.

Les sommes successives des termes d'une ligne du triangle : 1, 3, 10, 37, ..., forment la même suite des premières différences apparaissant dans la deuxième diagonale à partir de la droite du triangle. Il s'agit de la suite A005493 de l'OEIS. Le n-ième nombre de cette suite dénombre les partitions d'un n-ensemble, où l'un des sous-ensembles se distingue des autres ; par exemple, il existe 10 façons de partitionner trois éléments en sous-ensembles, puis de choisir l'un des sous-ensembles.

Lien externe

• (en) Eric W. Weisstein, « Bell Triangle », sur MathWorld.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bell triangle » (voir la liste des auteurs).