はじめに
prevの結果を使います。
自然数の分割
の代わりにを使います。すると積は指数の和になり、自然数の分割に関係した式になります。
べき乗和
べき乗和は以下のようになります。
べき乗和の母関数より
基本対称式
k次の基本対称式は異なるk個の文字からなる項の和です。
はのうち個の異なる文字からなる項の総和ですが、の指数は異なる自然数の和になり、この和がになる組み合わせの数がの係数となります。を個の異なる自然数に分割する方法の数をとすると、以下のように表せます。
ちなみにk個の異なる自然数に分割できる最小の自然数はなので、のとき、です。つまり級数はから始まります。ニュートンの恒等式より
これより
これから以下のような予想ができます。
別の方法でもこの結果を得ることができます。
これから係数比較により
よって
これより
一般に
となります。よって
自然数の分割
を個の異なる自然数に分割する方法の数をとします。いまの結果から
両辺にをかけると
のときなのでの指数がマイナスの項などは生じません。後者から前者を引くと
これからの係数を比較して以下の関係式を得ます。
制限付き分割数の再帰式
nをm個の異なる自然数に分割する方法の数は、n-mをm個の異なる自然数に分割する数と、n-mをm-1個の異なる自然数に分割する数の和に等しい。
ヤング図形による図解
左:1を含まない分割, 右:1を含む分割
自然数の分割はヤング図形により表すことができます。例えば図1はそれぞれ ,という分割を表します。個のヤング図形はすべて、1を含む分割か、1を含まない分割のいずれかに分類できます。まず1を含まない場合(左図)、色のついたブロックを消すと、縦の段数はmのまま、ブロック数はになります。このとき残ったヤング図形はに対応します。1を含む場合、同様に色のついたブロックを消すと、ブロック数は同じくになりますが、縦の段数が一つ減るのでに対応するヤング図形になります。よってが成り立ちます。
異なるルールの分割数との関係
を個の異なる自然数に分割する数をとして
ですが
は完全斉次式の母関数の形をしています。これは重複を許した組み合わせの項からなるので、重複を許した自然数の分割に関係します。用語の使用に関してですが、重複を許すルールをデフォルトにし、許さない場合は「異なる」をつけることにします。をによって分割する数を(独自の記法)とすると
よって
分割数の関係式
nをm個の異なる自然数に分割する数は、を1からmまでの自然数で分割する方法に等しい。
ヤング図形による図解
左:, 右:
個の異なる自然数からなる分割において、分割をのように表し、昇順にすると隣合う数字は必ず1以上の差があります。このためとなるを使ってと表せます。図2の左図のグレーの部分がという分割に対応します。グレーの部分のブロック数はなのでこれを引いたはの分割に対応します。は図2の右図のように並べることができ、これはを1からmまでの自然数で分割する方法に等しくなります。
完全斉次式
を個の自然数に分割する方法の数をとすると、以下のように表せます。
から係数比較より
よって
一般に
となります。よって
異なるルールの分割数との関係
基本対称式の結果と比較すると
一般に
これから以下の関係を得ます。
分割数の関係式
nをm個の異なる自然数に分割する数は、をm個の自然数で分割する方法に等しい。
ヤング図形による図解
左:, 右:
のように分割するとはとなり、ブロック数はとなります。の数はをm個の自然数で分割する方法に等しくなります。
分割数の再帰式
いまの式を公式1
に代入すると
変数を置き換えると以下の式を得ます。
分割数の再帰式
nをm個の異なる自然数に分割する数は、を個の自然数で分割する方法とを個の自然数に分割する方法の和に等しい。
ヤング図形による図解
左:1を含まない分割, 右:1を含む分割
nをm個に分割する方法は、1を含む分割とそうでない分割に分けれます。1を含まない分割から、グレーの部分を引くと、n-mをm個に分割するヤング図形になるので、に対応します。1を含む分割は右図のヤング図形になります。これからグレー部分を引くとに対応するヤング図形になります。このため
となります。
問題によってヤング図形の操作が違う理由
同じ議論がにも使えるじゃないかと思われるかもしれませんが、では、1が一回しか使えないので、その1を引くと、2以上の異なる自然数からなる分割となり、分割のルールが変わってしまいます。逆にの1を含む場合からnを引くと、1の個数によって異なる個数への分割になってしまいます。同じルールの分割数どうしの関係を得たいので、問題によってヤング図形の操作が違うのです。
z=1のとき
とすると個に分割するという制限がなくなります。nを異なる自然数に分割する数を,nを自然数に分割する数をとすると
となります。
オイラーの分割恒等式
なのでnを異なる自然数に分割する方法の数を、nを奇数によって分割する数をとすると
オイラーの分割恒等式
nを異なる自然数に分割する方法の数は、nを奇数による分割する方法の数に等しい。
組み合わせ論的考察
全ての自然数はという形で表せます。これを表にすると
二進数表記を考えれば、全ての自然数は先頭の奇数2n-1と末尾の連続する0の数mを用いた、(n,m)という組に一意に対応することが分かると思います。
全ての自然数はこの表のどれかに対応するので、異なる自然数への分解はこの表のいくつかを埋めたものに対応します。各行の埋まりかたは自然数の二進数表示と対応させることができ、
というように表せます。これは奇数を用いた分割を表します。例えばは
なのでに対応します。
二進数表記の一意性
としてを考えます。
係数比較すると
よって
結局全て1になります。よって
の係数はを異なるで分割する方法の数なので、これが一通りしかないことをこの式は示しています。これは二進数表示が一意であるという証明になっています。
天秤ばかりの問題
さきほどの問題は、天秤ばかりでどんな分銅を持っていれば全ての自然数に対応できるかという問いの答えになります。すなわち1,2,4,8,..という分銅をもっていれば、それの組み合わせで全ての自然数の重さが測れます。しかしこれは天秤の一方だけに分銅をのせる場合の話で、分銅を測りたいものと一緒に乗せてもいいなら、もっと少ない種類の分銅でよくなります。それは1,3,9,27,..という分銅です。これらを引き算と足し算を使って組み合わせることで全ての自然数が表現できます。これをみるため以下のような式を考えます。
として係数比較すると
よって
よって
の係数はを異なるを足し算と引き算で組み合わせて分割する方法の数です。この方法ですべての整数を一意に表すことができます。