離散数学・組合せ論の問題

分割を「いちばん大きい部分 $k$」で分類して数える。いちばん大きい部分が $k$ である $7$ の分割は、$k$ を 1 つ取り除くと、残りの $7-k$ を「$k$ 以下の部分」に分割したものと 1 対 1 に対応する。

• $k=7$: $7$ の 1 個。
• $k=6$: $6+1$ の 1 個。
• $k=5$: 残り $2$ を $5$ 以下に分割。$5+2,5+1+1$ の 2 個。
• $k=4$: 残り $3$ を $4$ 以下に分割。$4+3,4+2+1,4+1+1+1$ の 3 個。
• $k=3$: 残り $4$ を $3$ 以下に分割。$3+3+1,3+2+2,3+2+1+1,3+1+1+1+1$ の 4 個。
• $k=2$: 残り $5$ を $2$ 以下に分割。$2+2+2+1,2+2+1+1+1,2+1+1+1+1+1$ の 3 個。
• $k=1$: $1+1+1+1+1+1+1$ の 1 個。

よって
$$p(7)=1+1+2+3+4+3+1=15.$$

（母関数で見ると、$\frac{1}{1-x^k}=1+x^k+x^{2k}+\cdots$ から $x^{k\cdot m_k}$ を選ぶことが「部分 $k$ を $m_k$ 個使う」ことに対応し、$x^7$ の係数は $1\cdot m_1+2m_2+\cdots +7m_7=7$ を満たす 0 以上の整数の組 $(m_1,\dots ,m_7)$ の個数、すなわち上で数えた分割の個数 $15$ に等しい。）

分割数 $p(n)$ を、最大の部分が $k$ 以下となる分割の個数として数える。

$p(n,k)$ を、$n$ の分割のうち各部分が $k$ 以下であるものの個数とする。漸化式は $p(n,k)=p(n,k-1)+p(n-k,k)$ である。

$n=7$ の分割を、最大の部分ごとに数える。
- 最大の部分が 7: $7$ の 1 通り。
- 最大の部分が 6: 残り 1 の分割で 1 通り。
- 最大の部分が 5: 残り 2 の分割（各部分 5 以下）で $p(2)=2$ 通り。
- 最大の部分が 4: 残り 3 の分割（各部分 4 以下）で $p(3)=3$ 通り。
- 最大の部分が 3: 残り 4 の分割（各部分 3 以下）。$p(4)=5$ から $4$ 自身の分割を除いて 4 通り。
- 最大の部分が 2: 残り 5 の分割（各部分 2 以下）で、$2+2+1$、$2+1+1+1$、$1^5$ の 3 通り。
- 最大の部分が 1: $1^7$ の 1 通り。

合計は $1+1+2+3+4+3+1=15$。

検算: $p(0)$ から $p(7)$ は 1, 1, 2, 3, 5, 7, 11, 15 であり、既知の値 $p(7)=15$ と一致する。

また、オイラーの五角数定理による漸化式 $p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+\cdots$ を使うと、$p(7)=p(6)+p(5)-p(2)-p(0)=11+7-2-1=15$ となり、これも一致する。