Recurrence Relations · Partition Combinatorics

Lesson 8

Nikolai Chukhin · Alexander S. Kulikov

The Bell number \(B(n)\) is defined as the number of ways to partition \([n]\) into non-empty subsets. For example, \(B(3)=5\):

  1. \(\{1, 2, 3\}\),
  2. \(\{1\} \cup \{2, 3\}\),
  3. \(\{2\} \cup \{1, 3\}\),
  4. \(\{3\} \cup \{1, 2\}\),
  5. \(\{1\} \cup \{2\} \cup \{3\}\),

Problem. Compute \(B(10)\).

5 points