集合の分割
n 個の元を持つ集合の分割の総数はベル数 Bn である。n の小さいベル数を列挙すると、B0 = 1、B1 = 1、B2 = 2、B3 = 5、B4 = 15、B5 = 52、B6 = 203 となっている。ベル数は次の漸化式で表される。
B n + 1 = ∑ k = 0 n ( n k ) B k {\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}}
そして、次のような指数型母関数が存在する。
∑ n = 0 ∞ B n n ! z n = e e z − 1 {\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}}
n 個の元を持つ集合を k 個のブロックに分ける分割の総数は、第2種スターリング数 S(n, k) である。
n 個の元を持つ集合の非交差な分割の総数はカタラン数 Cn であり、次の式で表される。
C n = 1 n + 1 ( 2 n n ) {\displaystyle C_{n}={1 \over n+1}{2n \choose n}}