Classical combinatorial numbers · Definition

Bell number

enumerative combinatoricsclassical combinatorial numbers

Before you start you need to know

Bell numbers count groupings without order of distinguishable elements. They are directly related to Stirling numbers of the second kind.

Definition

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\]

By definition, \(B_n=\sum_{k=0}^{n}S(n,k)\), where \(S(n,k)\) is the Stirling number of the second kind. Thus \(B_0=1\), \(B_1=1\), \(B_2=2\), \(B_3=5\) and \(B_4=15\). The sequence satisfies Bell's recurrence, which allows computing it without listing the Stirling numbers one by one.

For \(n=3\), the set \(\{a,b,c\}\) has five partitions: one with a single block \(\{a,b,c\}\), three with a block of two and a block of one, and one with three singleton blocks. Hence \(B_3=1+3+1=5\), which matches \(S(3,1)+S(3,2)+S(3,3)\).

A typical mistake is confusing \(B_n\) with a single Stirling number \(S(n,k)\) for a fixed \(k\), or counting ordered arrangements of the blocks. The blocks of a partition have no order, so they should not be multiplied by factorials.

Think about it

Why does reordering the blocks of a partition not produce a new partition?

Because a partition is a set of subsets and a set has no order, so reordering its blocks gives the same partition.

Exercises 10

  1. What is the value of \(B_2\)?
  2. Which of these collections is a partition of \(\{1,2,3\}\)?
  3. What is the value of \(B_0\)?
  4. How many partitions does a 3-element set have in total?
  5. Which expression relates \(B_n\) to the Stirling numbers of the second kind?
  6. Compute \(B_4\) knowing that \(S(4,1)=1\), \(S(4,2)=7\), \(S(4,3)=6\) and \(S(4,4)=1\).
  7. Using \(B_0=1\), \(B_1=1\) and \(B_2=2\), compute \(B_3\) with Bell's recurrence.
  8. How many partitions of \(\{1,2,3,4\}\) have exactly two blocks?
  9. 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,4)=10\) and \(S(5,5)=1\). Which step gives the correct result?
  10. 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\)?

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.