分割数の意味と性質・ヤング図形の活躍

分割数とは

$n$ の分割数を $p(n)$ と書くことにします。

以下では，分割数にまつわるおもしろい性質を3つ紹介します。

「個数」と「最大数」に関する性質

例えば，さきほどの例である $5$ の分割について，$k=3$ で確認してみます。

• $3$ 個に分割する方法は $3+1+1,\:2+2+1$ の2通り
• 最大が $3$ である分割は $3+2,3+1+1$ の2通り

どちらも $2$ 通りで一致しますね。ヤング図形というものを使って性質1を証明してみます。

ヤング図形の意味と性質1の証明

また，正方形の代わりに点で表したものをフェラーズ図形といいます。どちらも同じですが，正方形の中に数字を書き込んだりできるのでヤング図形の方が便利なことがあります。

ヤング図形を使えば上記の性質1を簡単に証明できます。「対応付け（全単射）をつくる」という重要なテクニックを使います。

分割数の漸化式

2つめの性質は，分割数に関する漸化式です。

$n$ を $k$ 個の正の整数に分割する方法の数を $p_k(n)$ と書くことにします。

• $p_k(n)$ は，性質1より「最大の数が $k$ であるような $n$ の分割の数」と等しいです。
• $\displaystyle\sum_{k=1}^np_k(n)=p(n)$ なので，各 $p_k(n)$ が計算できれば $p(n)$ がわかります。
• $p_k(n)$ については以下の漸化式を使って順々に計算できます。

ただし，$k>n-k$ のとき $p_k(n-k)=0$ とします。

「相異なる分割」と「奇数への分割」

例えば，さきほどの例である $5$ の分割について確認してみます。

• 「相異なる分割」は $5,\:4+1,\:3+2$ の3通り
• 「奇数への分割」は $5,\:3+1+1,1+1+1+1+1$ の3通り

どちらも $3$ 通りで一致しますね。詳細はオイラーの分割恒等式(Wikipedia)を参照してください。

対応づけるテクニック

2つの集合 $A$ と $B$ の要素数が等しいことを証明するために，性質1や性質2の証明で見たように一対一対応（全単射）を作ることがしばしばあります。具体的には以下の3つを言えばOKです。

1. 集合 $A$ の任意の元からある操作で集合 $B$ の元が得られる。
2. 集合 $B$ の任意の元からある操作で集合 $A$ の元が得られる。
3. それらの操作は互いに逆の操作になっている。

3は自明なことが多いですが，一応確認しておきましょう。1と2だけでは下側の図のようになってしまうことがあるためです。