分割数

$n, k$ を自然数とする

$P(n, k)$ を $n$ を $k$ 個以下の正整数に分割する方法の数とする。

以下の漸化式が成り立つ

• $P(0, 0) = 1$
• $P(n, k) = P(n, k-1) \quad (n < k)$
• $P(n,k) = P(n-k, k) + P(n, k-1)\quad (\text{otherwise})$

分割の個数 $k$ は大きすぎても意味がない。とくに $k > n$ のとき、$P(n,k) = P(n,n)$ である。

$P(n,k)$ は 写像12相 の一つである。

$P(n) = P(n,n)$ として、$P(n)$ を $n$ の分割数という。

ヤング図形の共役

$P(n, k)$ は以下の2つの解釈が可能

• $n$ を $k$ 個以下の正整数に分割する方法の数

• $n$ を $k$ 以下の正整数に分割する方法の数

• たとえば $n=11, k= 3$ の場合

分割数全列挙