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

分割数の意味とおもしろい性質について整理しました。

数え上げの有名な話題です。ヤング図形や分割数の漸化式についても紹介します。

分割数とは

分割数の定義

正の整数 nn をいくつかの正の整数の和で表す方法の数を nn の分割数と言う。

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

55 をいくつかの正の整数の和で表す方法は,

  • 55
  • 4+14+1
  • 3+23+2
  • 3+1+13+1+1
  • 2+2+12+2+1
  • 2+1+1+12+1+1+1
  • 1+1+1+1+11+1+1+1+1

77 通りなので p(5)=7p(5)=7 である。

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

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

分割数に関する性質1

kk 個の正の整数に分割する方法の数」と「最大の数が kk であるようないくつかの正の整数に分割する方法の数」は等しい。

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

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

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

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

ヤング図形とは

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

ヤング図形

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

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

性質1の証明

自然数分割の性質の証明

  • kk 個の分割」を一つとってきて,それに対応するヤング図形を書く。これを行ではなく列に関して見ると,「最大の数が kk である分割」に対応している(上側の図)。

  • 逆に,「最大の数が kk である分割」をとってきて,そのヤング図形を列に関してみると「kk 個の分割」に対応している(下側の図)。

  • これらの操作は互いに逆の操作になっていて,一対一対応が得られる(例えば,4+2+14+2+13+2+1+13+2+1+1 は対応している)。

よって,両者の分割の方法の数は等しい。

分割数の漸化式

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

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

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

pk(n)=pk(nk)+pk1(n1)p_k(n)=p_k(n-k)+p_{k-1}(n-1)

ただし,k>nkk>n-k のとき pk(nk)=0p_k(n-k)=0 とします。

漸化式の証明

nnkk 個に分割する方法について「11 を含まないもの」と「11 を含むもの」にわけて考える。

  • 11 を含まないものは pk(nk)p_k(n-k) 通り
    なぜなら「11 を含まない nnkk 個の分割」と「nkn-kkk 個の分割」には1対1対応があるから。実際,前者についてそれぞれから 11 を引くと後者が得られ,後者についてそれぞれに 11 を足すと前者が得られる。それらの操作は互いに逆の操作になっている。

  • 11 を含むものは pk1(n1)p_{k-1}(n-1) 通り
    なぜなら「11 を含む nnkk 個の分割」と「n1n-1k1k-1 個の分割」には1対1対応があるから。実際,前者について 11 を一つ除くと後者が得られ,後者について 11 を一つ加えると前者が得られる。それらの操作は互いに逆の操作になっている。

以上より目標の漸化式が成立。

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

分割数に関する性質3

「相異なる正の整数に分割する方法の数」と「正の奇数のみに分割する方法の数」は等しい。

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

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

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

対応づけるテクニック

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

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

全単射

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

全単射というと難しく聞こえますが,要するに一対一対応です。