Exercise · ZW-BELL-NUMBER-010 · ★★★ Advanced
If \(B_n\) counts partitions of an \(n\)-element set , what is \(B_4\) from the recurrence \(B_4=\sum_{k=0}^{3}\binom{3}{k}B_k\) with \(B_0=1\), \(B_1=1\), \(B_2=2\), \(B_3=5\)?
Choose one option.
A 12 B 15 C 20 D 10 Show answer ← Back to the question
Explanation The terms are \(1+3\cdot1+3\cdot2+1\cdot5=15\), so the recurrence gives 15; the value 10 appears if the \(B_3\) term is omitted.
The Bell number \(B_n\) is the number of partitions of a set with \(n\) elements, that is, of ways to split it into nonempty disjoint subsets .
\[B_n=\sum_{k=0}^{n-1}\binom{n-1}{k}B_k\]
More practice problems: bell number ZW-BELL-NUMBER-001 What is the value of B_2?ZW-BELL-NUMBER-002 Which of these collections is a partition of \1,2,3\?ZW-BELL-NUMBER-003 What is the value of B_0?ZW-BELL-NUMBER-004 How many partitions does a 3-element set have in total?ZW-BELL-NUMBER-005 Which expression relates B_n to the Stirling numbers of the second kind?ZW-BELL-NUMBER-006 Compute B_4 knowing that S(4,1)=1, S(4,2)=7, S(4,3)=6 and S(4,4)=1.ZW-BELL-NUMBER-007 Using B_0=1, B_1=1 and B_2=2, compute B_3 with Bell's recurrence.ZW-BELL-NUMBER-008 How many partitions of \1,2,3,4\ have exactly two blocks?