判断组合数奇偶性(组合数学&位运算)
结论:
这里只将证明方法不做证明:证明方法:数学归纳法。先证几个较小的数满足结论,再假设C(n-1,k-1),C(n-1,k)满足结论,分四种情况讨论:
pos1:C(n-1,k-1),C(n-1,k)都为偶数。
pos2:C(n-1,k-1),C(n-1,k)都为奇数。
对pos1,pos2用反证法,假设C(n,k)是奇数,证矛盾即可。
pos3:C(n-1,k-1)为奇数,C(n-1,k)为偶数。
pos4:C(n-1,k-1)为偶数,C(n-1,k)为奇数。
讨论完四种情况即证。