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 zijn ^[1]:

n	B_n
0	1
1	1
2	2
3	5
4	15
5	52
6	203
7	877
8	4140
9	21147
10	115975

De getallen van Bell zijn genoemd naar de wiskundige Eric Temple Bell (1883–1960). Ze worden ook exponentiële getallen genoemd. Ze komen tot uiting in de sommatie van de reeks

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

Men vindt namelijk: S₀=e, S₁ = e, S₂ = 2e, S₃ = 3e, S₄ = 15e, S₅ = 52e, enz. Dus B_n = S_n/e; dit is de voortbrengende functie van de getallen van Bell.

De getallen van Bell kan men ook interpreteren als het aantal mogelijke manieren om n onderscheiden balletjes te verdelen over een of meerdere identieke, niet van elkaar te onderscheiden dozen. Er mogen geen lege dozen overblijven. Als men bijvoorbeeld drie balletjes a, b en c 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: a in een doos en b en c in de andere; b in een doos en a en c in de andere; of c in een doos en a en b in de andere;
als er drie dozen zijn is er ook maar één mogelijkheid: elk balletje gaat in een andere doos.

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

Recursieformule

De getallen van Bell kunnen met deze recursieve betrekking berekend worden:

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

.

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

Het n^e 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":

Begin met een rij bestaande uit het getal 1.
Vorm een volgende rij, die één getal meer dan de vorige rij zal bevatten.
Het eerste getal in die rij is gelijk aan het laatste getal uit de vorige rij.
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

↑ rij A000110 in OEIS

[1] rij A000110 in OEIS

[1]