2べき分割

281

はじめに

　最近面白い発見をしたので共有します．
　かなり既出っぽいです．既出だったらこっそり教えて下さい

　$9$を$2^2+2^2+2^0$や$2^1+2^1+2^1+2^1+2^0$にするように，正整数を$1$個以上の$2$べきの和として表す方法を$2$べき分割とよぶ．この際，$\textbf{和の順序は区別しない}$．(例えば，$2^3+2^0$と$2^0+2^3$は同一視する．)

本題

　本題になってしまいました

　$2$以上の整数について，その$2$べき分割の総数は偶数である．

　これは証明を考えるだけでもかなり面白いので考えてみて下さい．

.
..
.
..
.
..
...
.
..
.
.
..
.
..
.
.
.
..
...
.
....
.
.

　$2$べき分割を，次のように$2$グループに分ける．(当然共通部分を持たない．)

$\mathbf{(A)}$　$2$べき分割に使っている$2$べきのうち，最大のものがちょうど$1$つ存在する．

$\mathbf{(B)}$　$2$べき分割に使っている$2$べきのうち，最大のものが$2$つ以上存在する．

　例えば，$10$の$2^3+2^1$という分割について，最大の$2$べきは$2^3$だが，これは$1$回しか表れていないので$\mathbf{(A)}$に分類される．逆に，$2^2+2^2+2^1$や$2^1+2^1+2^1+2^1+2^1$は$\mathbf{(B)}$に分類される．

　実は，この$2$グループの間には次のように$1$対$1$対応が作れる．

$\mathbf{(A)}$の分割について，最大の$2$べきを$2^n$として，それを$2^{n-1}+2^{n-1}$に置き換える．すると$2^{n-1}$は必ず$2$つ以上使っていることになり，$\mathbf{(B)}$の分割に変わる．
逆に，$\mathbf{(B)}$の分割について，最大の$2$べきを$2^n$として，$2^n+2^n$を$2^{n+1}$に置き換える．すると$2^{n+1}$は必ずちょうど$1$つ使っていることになり，$\mathbf{(A)}$の分割に変わる．

　よって，$\mathbf{(A)}$と$\mathbf{(B)}$に含まれる分割の個数は等しく，全体では偶数になる．

　($6$のときの対応の例を示す．)
$$(4+2 \iff 2+2+2),　(4+1+1 \iff 2+2+1+1),　(2+1+1+1+1 \iff 1+1+1+1+1+1)$$

　面白いと思いませんか？　$2^{n+1} = 2^n + 2^n$という$2$べき特有の性質を使っているのがポイントになっています．ちなみに，$2$以上の整数の$2$べき分割の個数は必ず偶数になりますが，$1$のときは奇数になります．$1$は$2^n+2^n$にできないので上の議論が崩れるんですね．

　上の全単射において，使う$2$べきの個数はちょうど$1$個変わります．従ってこんなこともいえます．

　$2$以上の整数について，｢使う$2$べきの個数が$\textbf{偶数}$である$2$べき分割の個数｣と，｢使う$2$べきの個数が$\textbf{奇数}$である$2$べき分割の個数｣は等しい．