ヴァン・リント&ウィルソン組合せ論上の練習問題13Iの、組合せ論的別解

本来は代数的手法を用いて示せという証明問題なのですが、組合せ論系手法を用いた面白い別解が思いついたので、共有しようと思います。

問題(改)

Σ(0≦j≦a)((a+j j)2^(-j))=2^aを示せ。
ただし、(n r)は二項係数とする。

解答

Σ(0≦j≦a)((a+j j)2^(a-j))=2^(2a)…①
を示す。
2×aのマス目の1行目右端に、「符号マス」と呼称する1マスがついたマス目Xを考える。
以下の方法で、マス目Xの各マス目に0,1のいずれかを書き込み、「特別なマス」を一つ決めるようなものは、(a+j j)2^(a-j)通りである。

1.1行目、(j+1)列目に1を書き込み、これを特別なマスとする。
2.1行目の(j+1)列目以降は適当に0,1を書き込む。
3.それ以外については、1行目の(j+1)列目以前に書き込んだ0の個数と、2行目に書き込んだ1の個数の和がjとなるように、0,1を書き込む。

このとき、1行目の(j+1)列目以前に書き込んだ1の個数と、2行目に書き込んだ1の個数は等しい。
よって、マス目Xの1行目に書き込んだ1の個数は2行目に書き込んが1の個数より多くなる。
逆に、1行目に書き込んだ1の個数は2行目に書き込んが1の個数より多いような全ての書き込み方について、特別なマスは一意的に定まる。

よって、マス目Xの各マス目に0,1のいずれかを書き込む方法であり、1行目に書き込んだ1の個数は2行目に書き込んが1の個数より多いようなもの全体のの集合をAとすると、Aの元の個数は①の左辺に等しい。

ここで、2×aのマス目の各マス目に0,1のいずれかを書き込む方法すべての集合をBとすると、その元の個数は①の右辺に等しい。
Aの元aに対して、Bの元を定める以下の対応Fを考える。

1.aの符号マスに書き込まれた数が1の場合、符号マスを取り除き、1行目と2行目を入れ替えたものを対応させる。
2.aの符号マスに書き込まれた数が0の場合、符号マスを単に取り除いたものを対応させる。

Bの元bに対して、Aの元を定める以下の対応F'は、対応Fの逆である。

1.bの1行目に書き込まれた1の個数が、2行目に書き込まれた1の個数以下であるとき、1行目と2行目を入れ替え、符号マスとして1を書き込んだものを対応させる
2.bの1行目に書き込まれた1の個数が、2行目に書き込まれた1の個数より大きいとき、単に符号マスとして0を書き込んだものを対応させる。

よってA,B間に一対一対応が存在し、A,Bの元の個数は等しく、①が示された。…(答)