二項係数の偶奇(解決編)

{}_nC_{r}の偶奇について考えたのは、2013年頃の話で、当時の結論は、

{}_\mod (nC_{r},2)の値はビット演算子を用いて

n == ( r | (n - r) ) 

となる。

というものだ。例えば、{}_5C_{2}=10は偶数だが、

( 10 | 11 ) = 11 

は101ではないので、命題は偽となり、値は0となる。また{}_6C_{2}=15は奇数だが、

( 10 | 100 ) ) = 110 

により命題は真となり、値は1となる。という具合である。
この方法なら、大きな数に対する二項係数の偶奇もあっという間に計算できる。

何故、これで良いのかについて書こう。

(1) n!が持つ素因数2の個数f(n) \displaystyle\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{2^2} \rfloor + \lfloor \frac{n}{2^3} \rfloor +\cdotsである。

ちなみに、これはnを2進数表示したときの2^kの位の数をg_n(k)\in \{0,1\}とし、nl桁の2進数するとき、\displaystyle f(n)=\sum_{k=0}^{l-1} (2^{k}-1)g_n(k)と表現できる。

(2) f(a+b)\geq f(a)+f(b)である。これは一般に\lfloor p+q\rfloor=\lfloor p\rfloor+\lfloor q\rfloorまたは
\lfloor p+q\rfloor=\lfloor p\rfloor+\lfloor q\rfloor+1となることからわかる。

(3) f(a+b)\geq f(a)+f(b)の等号成立は\displaystyle\lfloor \frac{a+b}{2^k} \rfloor
=\lfloor \frac{a}{2^k} \rfloor+\lfloor \frac{b}{2^k} \rfloorが任意のkについて成立することだから、kが大きい順に考えていくと、任意のlについてg_l(a+b)=g_l(a)+g_l(b)が成立することである。つまり、2進数におけるa+bの筆算において繰り上がりが生じないことが必要十分条件となる。

(4)繰り上がりが生じない2進数の筆算においては、0+0=0,0+1=1,1+0=1の3つしか登場せず、1+1=10は登場しない。よって、足し算とビット毎の or 演算が等価となる。つまりビット演算子「OR」を用いて a+b= (a OR b)と表現することができる。XOR でも構わない。

(5) {}_nC_{r}が奇数である必要十分条件f(n)=f(r)+f(n-r)であるから n+(n-r)= (n OR (n-r))となる。

(2019.1.12追記)
spherical-harmonics.hatenablog.com
により、

(6) この条件はn XOR r XOR (n-r) =0 となる。