组合数奇偶

小巧思这个分类会放一些,在写题时遇到的或者是自己思考的一些有意思的问题。都是自己的思考,当然未来可能不止在数学/计算机方面。

结论

思考组合数的奇偶,能否通过$n,m$快速判断。
得到了很有意思的结论,$m$ & $n$ == $m$时,组合数$C_n^m$为奇数。&代表二进制与运算,也就是说:只有当$m$和$n-m$的二进制中的$1$所在位置各不相同时,组合数$C_n^m$为奇数。

推导

$ C_n^m =\cfrac {n!} {m!(n-m)!} $
显然分子,分母包含$2$这个因子的次数相等时,是奇数。
考虑$k!$中含有几个质因子$2$,质因子数可以表示为:
$ \sum_{j=1}^\infty \lfloor \cfrac {k} {2^j} \rfloor$
考虑$k$的二进制展开:
$ k = \sum_{i} 2 ^ {k_i} $,每个$k_i$不同。用$k$的二进制拆分表示$k$,带入上式有:
$ \sum_{j=1}^\infty \lfloor \cfrac {k} {2^j} \rfloor = \sum_{j=1}^\infty \sum_{i=1} \lfloor \cfrac {2 ^ {k_i}} {2^j} \rfloor$
因为右边求和的项在取整前一定是整数或者总和不超过$1$的小数,因此可以交换求和次序:
$\sum_{j=1}^\infty \sum_{i=1} \lfloor \cfrac {2 ^ {k_i}} {2^j} \rfloor = \sum_{i=1} \sum_{j=1}^\infty \lfloor \cfrac {2 ^ {k_i}} {2^j} \rfloor = \sum_{i} (2^{k_i}-1) = k - I(k) $
其中$I(k)$为$k$的二进制表示中$1$的个数。
$C_n^m$为奇数也就是分子分母含2的次数相等,等价于:
$ n-I(n) = m-I(m) +(n-m) -I(n-m) $
$ I(n) = I(m) + I(n-m) $
转换成了$n$,$m$二进制中$1$的个数的关系

注意到$n = m + (n-m)$,当二进制加法发生进位时,每一次进位都会减少一个二进制位中的1,(1+1=10)。因此只有当$m$和$n-m$的二进制中的1所在位置各不相同时,相加不会产生进位,才有$ I(n) = I(m) + I(n-m) $成立。

在计算机位运算中为m & (n-m) == 0或者m & n == m。

最后修改:2022 年 03 月 25 日
如果觉得我的文章对你有用,请随意赞赏