1のかたまり

TAOCPに  A_n=Σ_k=0ⁿ _n-kC_2k  という式があった(演習問題7.1.4--125).

その解答のHistorical Noteに A_ncounts binary x₁...x_n-1 with each 1 next to another と書いてある. なんだろうと思っているうちに, Knuth先生からのある手紙にヒントがあった.

ちなみにA_nの値は

n   1 2 3 4 5  6  7  8  9 ...
An  1 1 2 4 7 12 21 37 65 ... .

とりあえずn=5を考える. するとbinary x₁...x_n-1は

0 0 0 0 *
0 0 0 1
0 0 1 0
0 0 1 1 *
0 1 0 0
0 1 0 1
0 1 1 0 *
0 1 1 1 *
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0 *
1 1 0 1
1 1 1 0 *
1 1 1 1 *

with each 1 next to another は, 1があれば単独では現れないということで, そういうものは, 上で星印をつけた7=A₅個になる. 1は孤立していて失格である. 問題はこのパターンの見つけかたである. 星印のものを取り出すと

0 0 0 0
0 0 1 1
0 1 1 0
0 1 1 1
1 1 0 0
1 1 1 0
1 1 1 1

最初のは1がないから別にして, 残りは1のかたまりが1個ある. 1が孤立するかたまりはないから, 1のかたまりから1個外したパターンを書くと

1 2 3 4
 0 0 1
 0 1 0
 0 1 1
 1 0 0
 1 1 0
 1 1 1

となる. ビットの境界に左から1,2,3,4と番号をつけ, 0と1の境界の位置を書いてみると

3 4
2 3
2 4
1 2
1 3
1 4

となり, これは4個から2個選ぶ数であった. つまり₄C₂=_n-1C₂=6.


同様にして, 1のかたまりが2個あるパターンは, n=7の0 1 1 0 1 1 から考え始めて

1 2 3 4 5
 0 1 0 1    2 3 4 5
 1 0 0 1    1 2 4 5
 1 0 1 0    1 2 3 4
 1 0 1 1    1 2 3 5
 1 1 0 1    1 3 4 5

だから, 右にあるような境界の位置を見れば, ₅C₄=_n-2C₄(1のかたまりが2個の場合).

という次第で, 一般に1のかたまりがk個ある数は_n-kC_2k.
一番上の1のかたまりのないものは_nC₀=1.



2項係数_nC_mは, n<mの時に0だから, かたまりがとれるところまで足せばよく, 1のかたまりの置き方の数になるのであった. 結構むずかしい. 私もヒントなしでは, ここまで辿りつかなかっただろう.