自然数を足し算に分ける「分割」とフェラーズの点図

6 を自然数の足し算で書き表す方法は 11 通りあります。$4+1+1$ と $1+4+1$ は同じものと数える。

順序を区別すると 32 通りになります。区別するかしないかで 3 倍近く変わる。ここが分割の問題の入口です。

分割とは何か

自然数 $n$ を、1 以上の整数の和で表す方法を分割といいます。足す順序は区別しません^[1]。

数え落としを防ぐため、大きい順に並べて書き出します。6 なら次の 11 通り。

分割の総数を $p(n)$ と書きます。$p(6)=11$ です。

順序を区別すると別の数になる

順序まで区別する書き方を、分割と分けて考えます。$4+1+1$、$1+4+1$、$1+1+4$ を別々に数える形です。

こちらは仕切りの方法で数えられます。6 個の印を一列に並べ、印と印の間の 5 か所に仕切りを入れるか入れないかを決める^[5]。

$$2^5=32$$

32 通り。一般に $2^{n-1}$ 通りです。順序を区別しないほうには、こういう簡単な式がありません。

フェラーズの点図

分割を点の並びで表す方法があります。大きい順に並べた各項の個数だけ、点を横に並べる^[1]。

$4+2+1$ なら、1 行目に 4 個、2 行目に 2 個、3 行目に 1 個。左そろえで積みます。

この図を、対角線について折り返すと別の分割が現れます。行と列を入れかえる操作です。

共役の分割

折り返してできた分割を、もとの分割の共役といいます。$4+2+1$ の共役は $3+2+1+1$ です。

もとの図は 3 行あり、いちばん長い行が 4 個でした。折り返すと 4 行になり、いちばん長い行が 3 個になる。

つまり、項の個数と最大の項が入れかわります。この対応から、次のことがすぐ分かる^[1]。

「$k$ 個以下の項に分ける分け方」と「最大の項が $k$ 以下になる分け方」は、同じ個数になる。

例：6 を 3 個以下に分ける

書き出します。$6$、$5+1$、$4+2$、$3+3$、$4+1+1$、$3+2+1$、$2+2+2$ の 7 通り。

共役を取ると、最大の項が 3 以下になるものが並びます。$1$ を 6 個、$2+1+1+1+1$、$2+2+1+1$、$2+2+2$、$3+1+1+1$、$3+2+1$、$3+3$ の 7 通り。

同じ 7 でした。片方が数えにくいときは、共役に置きかえて数える手が使えます。

例：ちょうど 3 個に分ける

6 をちょうど 3 個の自然数の和にする分け方は、$4+1+1$、$3+2+1$、$2+2+2$ の 3 通り。

共役を取ると、最大の項がちょうど 3 になる分割に移ります。$3+1+1+1$、$3+2+1$、$3+3$ の 3 通りで、確かに一致します。

漸化式で追う

$n$ を $k$ 個以下に分ける分け方の総数を $p(n,k)$ とします。

いちばん小さい項が 1 かどうかで分けます。1 があるなら、それを取り除いて $n-1$ を $k-1$ 個以下に分ける問題になる。

1 がないなら、すべての項が 2 以上です。各項から 1 ずつ引くと、$n-k$ を $k$ 個以下に分ける問題になります。

$$p(n,k)=p(n-1,k-1)+p(n-k,k)$$

$p(6,3)=p(5,2)+p(3,3)$。$p(5,2)=2$、$p(3,3)=1$ で合計 3 になり、ちょうど 3 個に分ける数と一致します。

自己共役の分割

折り返しても形が変わらない分割を、自己共役といいます。6 では $3+2+1$ だけです。

点図が階段状になっていて、対角線について左右対称になっている。他の 10 通りは、折り返すと別の分割に移ります。

自己共役の分割は、相異なる奇数の和で表す分割と同じ数だけあることが知られています^[1]。6 なら $5+1$ の 1 通りで、確かに 1 つ。

玉と箱の言葉に直す

分割は、区別しない玉を区別しない箱に入れる問題と同じです^[2]。

6 個の同じ玉を 3 個以下の箱に入れる入れ方が 7 通り。箱に区別がないので、入った個数の組だけが問題になる。

箱に番号があれば話が変わります。そのときは仕切りの方法が使える。区別の有無で式がまったく変わる点は、配る問題と同じです。

例：最大の項を制限する

6 を、どの項も 4 以下になるように分けます。共役を取れば「項の個数が 4 以下」の分割に移ります。

項が 4 個以下の分割を数えると、$1$ を 6 個並べる形と $2+1+1+1+1$ を除いた 9 通り。

直接数えても、$6$ を除いた 10 通りから $5+1$ を除いて 9 通り。一致しました。

数えにくいと感じたら、共役に置きかえて数え直す。これが点図を使ういちばんの利点です。

高校での扱い

分割の総数を求める公式は、高校の範囲にありません。出題されるのは、書き出せる大きさに限られます。

大きい順に並べて、いちばん大きい項ごとに整理する。この手順で書けば、数え落としも重複も防げます。

よくある誤り

大きい順に書き出し、数えにくければ点図を折り返す。この 2 つで足ります。

参考文献

^[1] が分割の定義と点図と共役、^[2] が玉と箱の言葉での整理、^[3] が集合の分割との違い、^[4] が順序を区別する数え方、^[5] が各国語での基本の整理です。