Getal van Bell

In de combinatoriek is het $n$-de getal van Bell, $B_{n}$, gelijk aan het totaal aantal partities van een verzameling met $n$ verschillende elementen. Anders uitgedrukt: $B_{n}$ is gelijk aan 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 genoemd naar de wiskundige Eric Temple Bell (1883–1960). Ze worden ook exponentiële getallen genoemd omdat ze in verband staan met de reeksen

$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 een of meer identieke, niet van elkaar te onderscheiden dozen. 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 de 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;
• als er drie dozen zijn is er ook maar één mogelijkheid: elke doos krijgt één balletje.

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

Recursieformule

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

Schematisch verloop van het driehoekschema

De getallen van Bell kan men met de hand berekenen door middel van het "driehoekschema":

1. Begin met een rij bestaande uit het getal 1.
2. Vorm een volgende rij, die één getal meer dan de vorige rij zal bevatten.
3. Het eerste getal in die rij is gelijk aan het laatste getal uit de vorige rij.
4. De volgende getallen bekomt men als de som van de linkerbuur en de linkerbovenbuur 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

Bronnen, noten en/of referenties