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

分割を、いちばん大きい部分（最大部分）$k$ で分類して数えます。最大部分が $k$ の $7$ の分割は、$k$ を 1 つ取り除くと、各部分が $k$ 以下である $7-k$ の分割になり、これは 1 対 1 に対応します。母関数でいえば、$\frac{x^k}{1-x^k}\cdot {\prod }_{j=1}^{k-1}\frac{1}{1-x^j}$ の $x^7$ の係数を数えることにあたります。

• $k=7$：$7$ の 1 通り。
• $k=6$：残り $1$ を部分 $6$ 以下で分割すると $1$ の 1 通り。つまり $6+1$。
• $k=5$：残り $2$ の分割は $2,1+1$ の 2 通り。
• $k=4$：残り $3$ の分割は $3,2+1,1+1+1$ の 3 通り。
• $k=3$：残り $4$ を部分 $3$ 以下で分割すると $3+1,2+2,2+1+1,1+1+1+1$ の 4 通り。
• $k=2$：残り $5$ を部分 $2$ 以下で分割すると $2+2+1,2+1+1+1,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$$
です。

（確認）母関数 ${\prod }_{k\ge 1}\frac{1}{1-x^k}$ を展開すると $1+x+2x^2+3x^3+5x^4+7x^5+11x^6+15x^7+\cdots$ となり、$x^7$ の係数は $15$ で一致します。

p(n) の値を表で求める。p(0)=1, p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, p(6)=11 であり、p(7)=15 である。

検算として、最大の部分が k である 7 の分割の個数を数える。
- 最大の部分が 7: 7 → 1 個
- 最大の部分が 6: 6+1 → 1 個
- 最大の部分が 5: 5+2, 5+1+1 → 2 個
- 最大の部分が 4: 4+3, 4+2+1, 4+1+1+1 → 3 個
- 最大の部分が 3: 3+3+1, 3+2+2, 3+2+1+1, 3+1+1+1+1 → 4 個
- 最大の部分が 2: 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1 → 3 個
- 最大の部分が 1: 1+1+1+1+1+1+1 → 1 個

合計は 1+1+2+3+4+3+1=15 となる。

さらに母関数からも確かめる。(1-x)(1-x^2)(1-x^3)... の係数を使う五角数定理により、p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+... が成り立つ。これより p(7)=p(6)+p(5)-p(2)-p(0)=11+7-2-1=15 となり、一致する。