combinatorics

[gusl]

Sometimes I love Wikipedia: http://en.wikipedia.org/wiki/Partition_(set_theory)#Counting_partitions

Counting partitions

The total number of partitions of an n-element set is the Bell number B_n. The first several Bell numbers are B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52, and B₆ = 203. Bell numbers satisfy the recursion
and have the exponential generating function

The number of partitions of an n-element set into exactly k parts is the Stirling number of the second kind S(n, k).
The number of noncrossing partitions of an n-element set is the Catalan number C_n, given by

See also: Partition (number theory)


---
Also, LJ's HTML mode is very convenient for copy-pasting. Even the images came through automatically.

Comments

[bhudson.livejournal.com]

At some point last year I wondered "how bad can it be to just brute for this?" That's when I learned about the Bell numbers.