奇分割と異分割の間の1対1対応

ブログを書く練習がてら軽く．

分割って？

正の整数 $n$ の，いくつかの正の整数の和としての表し方を「分割」といい，個々の正の整数を「因子」という．たとえば， $5$ の分割は

${ \displaystyle 5 \\ 4 + 1 \\ 3 + 2 \\ 3 + 1 + 1 \\ 2 + 2 + 1 \\ 2 + 1 + 1 + 1 \\ 1 + 1 + 1 + 1 + 1 \\ }$

の $7$ 通り．因子を並べ替えただけの分割(たとえば $1+1+2+3+3$ と $3+1+2+1+3$ ) は同一視する*1．

分割の中でも特に，因子がすべて奇数のもの(e.g. $9+5+5+1$ )を「奇分割」，因子が相異なるもの(e.g. $5+9+6+3$ )を「異分割」と呼ぶ．実は任意の $n$ について， $n$ の奇分割と異分割は同数である．オイラーはこのことを母関数から示し，その式は「オイラーの分割恒等式」と名付けられているが，ここでは小学生でも理解できるよう，簡単な1対1対応を与えることにする．

1対1対応

分割 $n=A_1+A_2+ \cdots +A_N$ をおく．

異分割について，すべての $A_i=2^ k a$ ( $a$ は奇数) を $2^ k$ 個の $a$ に置き換えて新たな(元と同じかもしれない)分割を作る操作 P (Partition)を考える(結果は明らかに奇分割である)．たとえば， $7+6+5+4+3$ は $(7)+(3+3)+(5)+(1+1+1+1)+(3)$ ，即ち $7+5+3+3+3+1+1+1+1$ となるし， $7+3+1$ は元のままである．

また，奇分割について，因子のうち奇数 $a$ の個数が $K$ のとき， $K=2^{k_1}+2^{k_2}+ \cdots +2^{k_L}$ と2進展開して，分割中の「 $K$ 個の $a$ 」を「 $2^{k_1} a, 2^{k_2} a, \cdots , 2^{k_L} a$ 」に置き換えるという動作を任意の奇数に対して同時に行い，新たな分割を作る操作 U (Unite)を考える(結果はよく考えると異分割であるとわかる)．たとえば， $7+5+3+3+3+1+1+1+1$ は， $2^ 0$ 個の $7$ を $7$ に， $2^ 0$ 個の $5$ を $5$ に， $2^ 1+2^ 0$ 個の $3$ を $6+3$ に， $2^ 2$ 個の $1$ を $4$ に置き換えて， $7+6+5+4+3$ になる．