Getal van Bell

In de combinatoriek is het $n$-de getal van Bell $B_{n}$ het totale aantal partities van een verzameling met $n$ verschillende elementen. Anders gezegd is $B_{n}$ het aantal equivalentierelaties op die verzameling.

De eerste Bell-getallen, te beginnen met $B_{0}=B_{1}=1$ zijn:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ...

De getallen van Bell zijn naar de wiskundige Eric Temple Bell (1883–1960) genoemd. Ze worden ook wel exponentiële getallen genoemd, vanwege hun verband met de reeks

$S_{n}=\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}},\quad n=0,1,2\ldots$

Daarvoor geldt namelijk: $S_{n}=B_{n}\cdot e$.

De getallen van Bell kan men ook interpreteren als het aantal mogelijke manieren om $n$ verschillende balletjes te verdelen over identieke, niet van elkaar te onderscheiden dozen. Er mogen een tot en met $n$ dozen worden genomen en er mogen geen lege dozen overblijven. Als men bijvoorbeeld drie balletjes heeft, zijn die mogelijkheden:

• als er maar één doos is, is er maar één mogelijkheid: alle balletjes gaan in die doos,
• als er twee dozen zijn kan men de balletjes verdelen op drie manieren: een van de balletjes gaat in de ene doos en de overige twee in de andere en
• als er drie dozen zijn is er ook maar één mogelijkheid: iedere doos krijgt één balletje.

Het aantal mogelijkheden is dus vijf, het derde getal van Bell.

Recursie

De getallen van Bell voldoen aan de recursieve betrekking:

$B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}$,

waarin ${n \choose k}$ de binomiaalcoëfficiënt $n$ over $k$ is.

Het $n$-de getal van Bell is de som van de Stirling-getallen van de tweede soort $S2(n,k)$:

$B_{n}=\sum _{k=1}^{n}S2(n,k)$.

Berekening

De getallen van Bell kunnen aan de hand van een driehoekschema worden berekend:

1. Begin met een rij met alleen het getal 1.
2. Vorm een volgende rij, met daarin één getal meer dan in de vorige rij.
3. Het eerste getal in die rij is het laatste getal uit de vorige rij.
4. De volgende getallen ontstaan als de som van de linkerbuur en de linker bovenbuur van het te bepalen getal.

Het eerste getal van elke rij is dan een getal van Bell:

1
1	2
2	3	5
5	7	10	15
15	20	27	37	52

Voetnoten