整数の分割とヤング図形（可積分系入門）

この記事の続きですが，本記事だけで楽しめます．
tetobourbaki.hatenablog.com
当分は可積分理論に現れる基本的な手法を見ていきます．

組み合わせ問題

組み合わせ問題は一般に解くことが難しいです．組み合わせ問題の面白さというのは、全ての組み合わせを数えれば原理的には答えを求めることができるものの，それは計算機を使ってすら難しいところでしょう．

以下の動画を見れば，簡単そうな問題でも数え上げると大変なことになることが分かります．

次の動画では，簡単に計算するソフトを紹介しています．数学の力を使えばこんなことが可能になるのですね．

今回はこの問題ではなく、整数の分割を取り上げます。

整数の分割

整数の分割とは，与えられた自然数を自然数の和で書くことです．
例えば，3$3$は
3=1+1+13=2+13=3$$\begin{gathered} {\displaystyle 3=1+1+1} \\ 3=2+1 \\ 3=3 \end{gathered}$$
の 3$3$通りの分割法があります．

もう少し正確に定義しましょう．和の順番を変えても同じ分割だと考えることにするので，和を書くときは大きい数字の順に並べることにしましょう．すると以下のように定義ができます．

定義
自然数 N$N$の分割とは自然数の列 a1≥a2≥⋯≥an$a_1\ge a_2\ge \cdots \ge a_n$を用いて書ける
N=a1+a2+⋯+an${\displaystyle N=a_1+a_2+\cdots +a_n}$
のことを言う．このときの ai$a_i$を和因子という．

4$4$の分割を並べてみると，
4=1+1+1+14=2+1+14=2+24=3+14=4$$\begin{gathered} 4=1+1+1+1 \\ 4=2+1+1 \\ 4=2+2 \\ 4=3+1 \\ 4=4 \end{gathered}$$
の 5$5$通りがある．
5$5$の分割を並べてみると，
5=1+1+1+1+15=2+1+1+15=2+2+15=3+1+15=3+25=4+15=5$$\begin{gathered} 5=1+1+1+1+1 \\ 5=2+1+1+1 \\ 5=2+2+1 \\ 5=3+1+1 \\ 5=3+2 \\ 5=4+1 \\ 5=5 \end{gathered}$$
の 7$7$通りがある．
分割の数を分割数という．N$N$の分割数を p(N)$p(N)$と書く．
ここまでの例では分割数はそれほど大きくならないようにも見える．しかし，分割数は爆発的に大きくなる．
p(6)=11$p(6)=11$であるが，分割数が100$100$を越えるのはN=13$N=13$の時で p(13)=101$p(13)=101$である．100$100$の分割数は p(100)=190,569,292$p(100)=190,569,292$でありずいぶん大きい．1000$1000$の分割数になるととてつもなく大きくて，31$31$桁の自然数となる．

分割数が面白くなるのは、単に全ての分割を考えるのではなく、分割に条件をつけた場合の分割数である．（ラマヌジャンはこの分野でたくさん業績があるらしい．）例えば，全ての和因子が 2$2$以上という条件をつけると，上に列挙したものをみれば，5$5$の分割数は 2$2$となり非常に小さくなることが分かる．この方向で面白く深い問題を考えるのは次回以降の記事に回すことにして，次にヤング図形という便利な道具を導入しよう．

ヤング図形

ヤング図形とは以下のような箱の集まりでできる図形のことである．２つ例を挙げる．
$$

$$
適当に箱を並べたのではなくルールがある．i$i$行目に並べた箱の個数を bi$b_i$と表すことにすると，b1≥b2≥…bn$b_1\ge b_2\ge \dots b_n$が成り立つ必要がある．つまり下の行は上の行より多くの箱を並べてはダメだということである．最初の例では，
b1=3,b2=1,b3=1,b4=1$b_1=3,b_2=1,b_3=1,b_4=1$
であり，2$2$番目の例では
b1=4,b2=2,b3=1$b_1=4,b_2=2,b_3=1$
となっている．ヤング図形のルールを見れば分かるように，ヤング図形は整数の分割を表している．最初の例は 6$6$の分割 3+1+1+1$3+1+1+1$を表しており，2$2$番目の例は7$7$の分割 4+3+1$4+3+1$を表している．数の分割とヤング図形は一対一に対応していることが分かる．

ヤング図形を線対称にひっくり返したものを共役という．（線は左上から右下への斜めの線にとる．）
言葉では分かりにくいので，例で説明する．上で挙げた最初の例とその共役を並べると
$$ $$ $$
である．2$2$番目の例とその共役を並べると，
$$ $$ $$
である．ヤング図形の共役はやはりヤング図形になっていることが分かる．つまり，分割をヤング図形と考えて，その共役を取ることで新しい共役を得ることができる．この操作はヤング図形を使わなくても定義できるものの，ヤング図形を使うとイメージが湧く．

応用

行の個数が m$m$個以下のヤング図形を考えよう．これは和因子の個数が m$m$個以下になる分割を考えていることになる．一方，その共役をとると，「行の個数が m$m$個以下」のヤング図形の共役は「それぞれの行の箱の数が m$m$個以下」のヤング図形になる．これは全ての和因子が m$m$以下の分割に対応する．このことを踏まえると以下の定理が成り立つ．

定理
自然数 N$N$に対して，和因子の個数が m$m$個以下になる N$N$の分割数と，全ての和因子が m$m$以下の N$N$の分割数は等しい．

このことを N=5,m=3$N=5,m=3$で確認しよう．
和因子の個数が 3$3$個以下になる 5$5$の分割は
5=2+2+15=3+1+15=3+25=4+15=5$$\begin{gathered} 5=2+2+1 \\ 5=3+1+1 \\ 5=3+2 \\ 5=4+1 \\ 5=5 \end{gathered}$$
の 5$5$個である．一方，全ての和因子が 3$3$以下の N$N$の分割
5=1+1+1+1+15=2+1+1+15=2+2+15=3+1+15=3+2$$\begin{gathered} 5=1+1+1+1+1 \\ 5=2+1+1+1 \\ 5=2+2+1 \\ 5=3+1+1 \\ 5=3+2 \end{gathered}$$
の 5$5$個であり，確かに定理が成り立つ．

共役を使えば色々定理が作れそうである．

まとめ

今回は整数の分割を通して，ヤング図形を導入しました．ヤング図形は可積分理論の様々な場面で現れますが，それは整数の分割を表すと覚えておくと，損はないでしょう．

次回はq類似とかqアナローグとか呼ばれるものを導入します．これも可積分理論でよく使われるものですが，整数の分割とも関係の深い分野です．

続き
tetobourbaki.hatenablog.com