Triangle de Bell

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.

${\displaystyle {\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}}}$

Notant, pour ${\displaystyle 0\leqslant k\leqslant n}$, ${\displaystyle 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 :

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

Les nombres de Bell ${\displaystyle 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 : ${\displaystyle B(n,0)=B_{n},B(n,n)=B_{n+1}}$.

La relation: ${\displaystyle 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 : ${\displaystyle 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 : ${\displaystyle B(n,k)=\sum _{i=0}^{k}{\binom {k}{i}}B_{n-i}}$.

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

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

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

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

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

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

La relation ${\displaystyle 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[2], 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.

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

• (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).