The Problem Pit: The Pit of Set Partitions

 

---

The Pit of Set Partitions: Counting Chaos with Bell Numbers

Some problems trick you by asking a question so plain it feels like arithmetic.

How many ways can I split a set of $n$ objects into groups?

That’s it. No geometry, no probability, no fancy structures. Just take, say, $\{1,2,3\}$ and divide it into nonempty subsets.

I thought: this will be easy. Count by hand, notice a pattern, done.

Instead, I fell into enumerative chaos.

---

Step 1: The Small Numbers (Deceptive Simplicity)

Start small:

• $n=1$: just $\{1\}$. Only 1 partition.

• $n=2$: either $\{1,2\}$ or $\{1\}\{2\}$. So 2 partitions.

• $n=3$:

  • All together: $\{1,2,3\}$.

  • One split: $\{1,2\}\{3\}, \{1,3\}\{2\}, \{2,3\}\{1\}$.

  • All separate: $\{1\}\{2\}\{3\}$.
    Total = 5.

So far: $1,2,5$.

For $n=4$, I counted 15. For $n=5$, 52.

The sequence looked familiar:

$$1, 2, 5, 15, 52, 203, 877, \dots$$

The Bell numbers.

---

Step 2: First Wrong Guess

I thought maybe Bell numbers followed a neat formula, like factorials. Something like $B_n = 2^{n-1}$ or $\binom{n}{k}$.

I tried to guess patterns:

• $B_2 = 2$.

• $B_3 = 5$.

• $B_4 = 15$.

But nothing fit. My formulas broke instantly.

Dead end #1.

---

Step 3: Stirling Numbers Sneak In

Then I learned: the Bell number is the sum of Stirling numbers of the second kind:

$$B_n = \sum_{k=1}^n S(n,k),$$

where $S(n,k)$ counts the number of partitions of an $n$-element set into exactly $k$ parts.

So:

• For $n=3$: $S(3,1)=1, S(3,2)=3, S(3,3)=1$. Add them = 5.

• For $n=4$: $S(4,1)=1, S(4,2)=7, S(4,3)=6, S(4,4)=1$. Add them = 15.

This worked. But it only pushed the chaos one level down. Instead of one hard sequence, now I had two.

Dead end #2.

---

Step 4: The Recurrence Trap

Then I found the recurrence:

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

This made sense: to partition $n+1$ elements, decide which subset the last element joins.

I tried computing with it. For small $n$, it worked. For large $n$, the sums blew up. I couldn’t see the structure.

It felt like juggling too many balls.

---

Step 5: Generating Functions (False Clarity)

Finally, someone whispered: use generating functions.

The exponential generating function for Bell numbers is:

$$\sum_{n=0}^\infty B_n \frac{x^n}{n!} = e^{e^x - 1}.$$

This was elegant. So elegant, in fact, that it scared me. Why should a double exponential appear in a counting problem?

I thought: maybe this would simplify things. Instead, it revealed the true depth of the pit.

---

Step 6: Dobinski’s Formula — Chaos Unleashed

Then came the formula that floored me:

$$B_n = \frac{1}{e} \sum_{k=0}^\infty \frac{k^n}{k!}.$$

That’s Dobinski’s formula.

It says: to count partitions of a finite set, take an infinite sum of exponential terms, weighted by factorials, normalized by $e$.

How could something so finite be counted by something so infinite?

This was chaos incarnate.

---

Step 7: Asymptotics — The Explosion

I tried to understand how fast $B_n$ grows.

Stirling’s approximation told me roughly:

$$B_n \sim \frac{1}{\sqrt{n}} \left(\frac{n}{W(n)}\right)^n,$$

where $W(n)$ is the Lambert W function.

So not only do Bell numbers explode faster than $n!$, they drag in exotic functions just to describe their growth.

Dead end #3.

---

Step 8: Bell Numbers Everywhere

I realized Bell numbers appear in places I didn’t expect:

• Counting equivalence relations on an $n$-element set.

• Number of ways to factor a polynomial completely over an algebraically closed field (up to isomorphism).

• Feynman diagrams in quantum field theory.

• Moments of the Poisson distribution.

Everywhere I looked, partitions were hiding.

---

Step 9: Probability Creeps In

Then I noticed: the EGF $e^{e^x-1}$ is the moment generating function of a Poisson(1) random variable.

That means Bell numbers are the raw moments of Poisson(1).

Suddenly, counting partitions wasn’t just combinatorics. It was probability theory.

Another trapdoor opened.

---

Step 10: Climbing Out (Kind Of)

After wandering through Stirling numbers, generating functions, infinite sums, asymptotics, and probability, I finally stopped.

What had begun as a child’s counting exercise had dragged me through half of discrete mathematics.

Here’s what I carried out of the pit:

• Bell numbers count partitions, but no neat formula exists.

• They obey recurrences, generating functions, and infinite sums.

• Their growth is so fast it requires Lambert W to describe.

• They connect combinatorics, probability, and physics.

The problem looked like simple arithmetic. Instead, it opened a door into enumerative chaos.

That’s The Problem Pit: you walk in thinking you’ll count a few subsets, you come out tangled in $e^e$.

---