gusl | combinatorics (Reply)

You're viewing

gusl's journal
Create a Dreamwidth Account Learn More

Reload page in style: site light

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 $B_{n+1}=\sum_{k=0}^n {n\choose k}B_k$
and have the exponential generating function

$\sum_{n=0}^\infty\frac{B_n}{n!}z^n=e^{e^z-1}.$
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

$C_n={1 \over n+1}{2n \choose n}.$