数列の問題

第 $m$ 群は ${}_r{\mathrm{C}}_j$ $(r=m-1,0\leqq j\leqq r)$ の並びなので、$r=m-1$ とおき、$r$ に対する群を「段 $r$」と呼ぶ。第 $1$ 群〜第 $100$ 群は段 $0$〜段 $99$ である。段 $r$ に含まれる奇数の個数を $g(r)$ とする。また $j<0$ または $j>r$ のとき ${}_r{\mathrm{C}}_j=0$ と約束すると、すべての整数 $j$ で ${}_{r+1}{\mathrm{C}}_j={}_r{\mathrm{C}}_j+{}_r{\mathrm{C}}_{j-1}$ が成り立つ。

補題 1 $k$ を $0$ 以上の整数とすると、$0<j<2^k$ のとき ${}_{2^k}{\mathrm{C}}_j$ は偶数である。

（証明）$j\cdot {}_{2^k}{\mathrm{C}}_j=2^k\cdot {}_{2^k-1}{\mathrm{C}}_{j-1}$ が成り立つ。$0<j<2^k$ なので $j$ を割り切る $2$ の累乗は $2^{k-1}$ 以下であり、右辺は $2^k$ で割り切れるから、${}_{2^k}{\mathrm{C}}_j$ は $2$ で割り切れる。

補題 2（鍵） $0\leqq r<2^k$ のとき、すべての整数 $j$ について
$${}_{2^k+r}{\mathrm{C}}_j\equiv {}_r{\mathrm{C}}_j+{}_r{\mathrm{C}}_{j-2^k}(\mathrm{mod}2)(1)$$

（証明）$r$ についての数学的帰納法。$r=0$ のとき、補題 1 より ${}_{2^k}{\mathrm{C}}_j$ は $j=0,2^k$ で $1$、それ以外で偶数であり、右辺 ${}_0{\mathrm{C}}_j+{}_0{\mathrm{C}}_{j-2^k}$ も $j=0,2^k$ で $1$、それ以外で $0$ なので成り立つ。$r$ で成り立ち $r+1<2^k$ とすると、パスカルの関係式から
$${}_{2^k+r+1}{\mathrm{C}}_j={}_{2^k+r}{\mathrm{C}}_j+{}_{2^k+r}{\mathrm{C}}_{j-1}\equiv \left({}_r{\mathrm{C}}_j+{}_r{\mathrm{C}}_{j-1}\right)+\left({}_r{\mathrm{C}}_{j-2^k}+{}_r{\mathrm{C}}_{j-1-2^k}\right)={}_{r+1}{\mathrm{C}}_j+{}_{r+1}{\mathrm{C}}_{j-2^k}$$
となり、$r+1$ でも成り立つ。

$(1)$ の右辺の $2$ つの項は、${}_r{\mathrm{C}}_j\ne 0$ なら $j\leqq r<2^k$、${}_r{\mathrm{C}}_{j-2^k}\ne 0$ なら $j\geqq 2^k$ なので、同時に $0$ でないことはない。したがって段 $2^k+r$ の奇数は、段 $r$ の奇数の位置 $j$ と、それを $2^k$ だけずらした位置 $j+2^k$ にちょうど現れ、
$$g(2^k+r)=2g(r)(0\leqq r<2^k)(2)$$
が成り立つ。

段 $0$〜段 $2^k-1$ の合計 $T(k)=\sum _{r=0}^{2^k-1}g(r)$ とおくと、$(2)$ より段 $2^k$〜段 $2^{k+1}-1$ の合計は $2T(k)$ なので $T(k+1)=T(k)+2T(k)=3T(k)$。$T(0)=g(0)=1$ より $T(k)=3^k$。

段 $0$〜段 $99$ の合計 $100=64+32+4$ と分ける。
- 段 $0$〜$63$：$T(6)=3^6=729$。
- 段 $64$〜$95$：段 $64+r$ $(0\leqq r\leqq 31)$ で、$(2)$ より $g(64+r)=2g(r)$。合計は $2T(5)=2\cdot 243=486$。
- 段 $96$〜$99$：$g(96+t)=2g(32+t)=4g(t)$ $(t=0,1,2,3)$。$g(0)=1,g(1)=2,g(2)=2,g(3)=4$（段 $3$ は $1,3,3,1$）より、合計は $4(1+2+2+4)=36$。

よって求める個数は
$$729+486+36=1251.$$

第 $m$ 群は $r=m-1$ として ${}_r{\mathrm{C}}_0,\dots ,{}_r{\mathrm{C}}_r$。第 1〜100 群は $r=0,1,\dots ,99$。

${}_r{\mathrm{C}}_k$ が奇数となる $k$ の個数は、$r$ の 2 進表示で 1 の個数を $s(r)$ とすると $2^{s(r)}$（リュカの定理。パスカルの三角形の mod 2 でも確かめられる：$r=0,1,2,3,4$ で $1,2,2,4,2$ 個）。よって求める個数は $T=\sum _{r=0}^{99}{2}^{s(r)}$。

$0\le r<2^k$ について $\sum 2^{s(r)}=3^k$（各ビットが 0 なら因子 1、1 なら因子 2 で、各ビット $1+2=3$）。
- $r=0,\dots ,63$: $3^6=729$。
- $r=64+t$（$t=0,\dots ,35$）: $s(r)=1+s(t)$ なので $2{\sum }_{t=0}^{35}{2}^{s(t)}$。
- $t=0,\dots ,31$: $3^5=243$。
- $t=32+u$（$u=0,\dots ,3$）: $2{\sum }_{u=0}^3{2}^{s(u)}=2(1+2+2+4)=18$。
- 合計 $243+18=261$。
よって $2\cdot 261=522$。

$T=729+522=1251$。

検算: $r\le 3$ では $1+2+2+4=9=3^2$、$r\le 7$ では $27$ と一致。$r=64$ から $99$ の個数は $36$ 個で各々 $2^{1+s(t)}$ と数えている。