Exercise · ZW-BELL-NUMBER-005 · ★☆☆ Basic
Which expression relates \(B_n\) to the Stirling numbers of the second kind?
Choose one option.
Show answer
- C. \(B_n=\sum_{k=1}^{n}S(n,k)\)
Explanation
\(B_n\) sums \(S(n,k)\) over all \(k\), since each \(k\) counts the partitions with \(k\) blocks. A product version would multiply instead of adding, and the one with \(k!\) would order blocks that have no order.
Review the concept: Bell number
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-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?
- ZW-BELL-NUMBER-009 Show that B_5=52 by summing S(5,k) for k=1,dots,5, knowing that S(5,1)=1, S(5,2)=15, S(5,3)=25, S(5…