2べき分割
はじめに
最近面白い発見をしたので共有します．
かなり既出っぽいです．既出だったらこっそり教えて下さい
$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$べき分割の個数｣は等しい．
拡張？
同様に$m$べき分割を考えると次のこともいえます．
$\mathbf{(A_m)}$ $m$べき分割に使っている$m$べきのうち，最大のものがちょうど$1$つ存在する．
$\mathbf{(B_m)}$ $m$べき分割に使っている$m$べきのうち，最大のものが$m$個以上存在する．
という$2$つのグループを考えれば，この間に全単射が作れる．
これが何かに使えるかは不明です
最後に
すごい綺麗な議論を思い付いたので嬉しいです．ここまで読んで頂きありがとうございました！