パスカルの三角形の各段の奇数の数 - 球面倶楽部零八式 mark II

問題: ${}_nC_r(r=0,1,...,n)$ のうち奇数はいくつあるか

解答:(1) ${}_nC_r$ が奇数になる必要十分条件は2進法での $(n-r)+r=n$ の筆算において繰り上がりが生じないことである。

(2) つまり、 $n$ を2進数で表示したときに登場する「1」を $0+1$ とみる( $r$ の桁)か、 $1+0$ とみる( $n-r$ の桁)かのいずれかである。

(3) よって

pow( 2 , bitCount( n ) )

である。

例えば、 $n=2^k$ のときは、最上位ビットのみが1なので奇数は2個。最上位ビットを $0+1$ とみると、それは $0$ と $n$ に対応するので、2つの奇数は ${}_nC_0$ と ${}_nC_n$ である。