Bell Numbers

A Bell number, $ B_n $, is the number of ways to partition a set of $ n $ distinct elements into nonempty, disjoint subsets.

The calculation of Bell numbers by recurrence is given by the formula: $$ B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k $$

To partition a set of $ n+1 $ elements, fix an element $ x $. For each $ k $ (the number of elements outside the subset containing $ x $), choose $ k $ elements from $ n $, and then partition these $ k $ elements.

It is possible to calculate Bell numbers using another infinite series formula: $$ B_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!} $$

The first 50 values of $ B_n $ are: 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323, 44152005855084346, 445958869294805289, 4638590332229999353, 49631246523618756274, 545717047936059989389, 6160539404599934652455, 71339801938860275191172, 846749014511809332450147, 10293358946226376485095653, 128064670049908713818925644, 1629595892846007606764728147, 21195039388640360462388656799, 281600203019560266563340426570, 3819714729894818339975525681317, 52868366208550447901945575624941, 746289892095625330523099540639146, 10738823330774692832768857986425209, 157450588391204931289324344702531067, 2351152507740617628200694077243788988, 35742549198872617291353508656626642567, 552950118797165484321714693280737767385, 8701963427387055089023600531855797148876, 139258505266263669602347053993654079693415, 2265418219334494002928484444705392276158355, 37450059502461511196505342096431510120174682, 628919796303118415420210454071849537746015761, 10726137154573358400342215518590002633917247281, 185724268771078270438257767181908917499221852770

See OEIS A000110 here

Bell's triangle (or Aitken's triangle) is a triangular arrangement of numbers that allows for the efficient calculation of Bell numbers $ B_n $.

It is constructed from binomial coefficients and reflects the recurrence relation of Bell numbers:

$$ B_{n+1} = \sum_{k=0}^n \binom{n}{k} $$

Construction:

— The first row contains only the number 1 ($ B_0 $)

— Each subsequent row begins with the last calculated Bell number.

— Subsequent numbers are obtained by adding the previous number to the one above it.

The first column directly gives the Bell numbers.

Bell numbers are the sum of Stirling numbers of the second kind: $$ B_n = \sum_{k=0}^n S(n, k) $$

Where $ S(n, k) $ is the function that counts the number of partitions of a set of $ n $ elements into $ k $ subsets. The sum over $ k $ gives all possible partitions.