2014/10/24

自然数の分割とヤング図形

分野: 場合の数  レベル: 数学オリンピック

分割数:自然数 $n$ をいくつかの自然数の和で表す方法の数を $n$ の分割数と言う。

数え上げの有名な話題です。自然数の分割にまつわるごく基本的なこと。

自然数の分割の例と性質

例えば,$5$ をいくつかの自然数の和で表す方法は,
$5=4+1=3+2=3+1+1\\=2+2+1=2+1+1+1=1+1+1+1+1$
と $7$ 通りなので $5$ の分割数は $7$ です。

次に,自然数の分割にまつわるの有名な性質です。

性質1:「 $k$ 個の自然数に分割する方法の数」と「最大の数が $k$ であるようないくつかの自然数の和に分割する方法の数」は等しい。
性質2:「相異なる自然数に分割する方法の数」と「奇数個の自然数に分割する方法の数」は等しい。

2についてはオイラーの分割恒等式(Wikipedia)を参照してください。

以下では性質1について解説します。「対応付け(全単射)をつくる」という重要なテクニックを使います。

性質1の具体例:
$7$ を $3$ 個の自然数に分割する方法は,
$5+1+1=4+2+1=3+3+1=3+2+2$ の $4$ 通り。
最大の数が $3$ であるような自然数に分割する方法は,
$3+3+1=3+2+2=3+2+1+1=3+1+1+1+1$ の $4$ 通りとなり,両者は一致する。

自然数の分割とヤング図形

ヤング図形

自然数 $n$ の分割に対して,正方形を $n$ 個並べた右図のような図形をヤング図形といいます。右図は $7=4+2+1$ という分割に対応しています。下の行に行くに連れて正方形の数が減少していきます。

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

ヤング図形を使えば上記の性質1を簡単に証明することができます。

自然数分割の性質の証明

(性質1の証明)
「 $k$ 個の自然数への分割」を一つとってきて,それに対応するヤング図形を書く。これを行ではなく列に関して見ると,「最大の数が $k$ であるような自然数の和への分割」に対応している(上の図)。
逆に,「最大の数が $k$ であるような自然数の和への分割」をとってくると,そのヤング図形を列に関してみると「 $k$ 個の自然数への分割」に対応している(下の図)。
これらの操作は互いに逆の操作になっていて,一対一対応が得られる(例えば,$4+2+1$ と $3+2+1+1$ は対応している)。
よって,両者の分割の方法の数は等しい。

対応づけるテクニック

全単射

二つの集合 $A$ と $B$ の要素が等しいことを証明するために,上記のように一対一対応(全単射)を作ることがしばしばあります。具体的には以下の3つを言えばOKです。

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

3は自明なことが多いですが,一応主張しておく必要があります。1と2だけでは下側の図のようになってしまうことがあるためです。

全単射というと難しく聞こえますが,要するに一対一対応です。
分野: 場合の数  レベル: 数学オリンピック