C(n,k)组合数的奇偶性判定方法及证明

证明：

确定组合数奇偶性的方法是：

公式P指的是排列，就是从N个元素中取出R个元素，然后进行排列（即排序）。（P是老用法了，现在教科书多用A。）

公式C指组合，从N个元素中取出R个元素，不进行排列（即不进行排序），组合数奇偶性的判断方法为：结论：

对于 C(n,k)，如果 n&k == k 则 c(n,k) 为奇数，否则为偶数。证明：

使用数学归纳法：

来自 C(n,k) = C(n,k-1) + C(n-1,k-1)；对应于帕斯卡三角形：1 1 2 1 1 3 3 1 1 4 6 4 1

………………

可以验证在前面各层以及当k = 0时奇偶性，该结论都得到满足。下面证明当C(n-1,k)和C(n-1,k-1)（k > 0）满足该结论时，C(n,k)满足该结论。

1).设C(n-1,k)和C(n-1,k-1)为奇数：则： (n-1)&k == k; (n-1)&(k-1) == k-1;

由于 k 和 k-1 的最后一位数字必须不同，所以 n-1 的最后一位数字必须是 1。现在假设 n&k == k。

由于n-1和n的末位数字不同，我们可以推断k的末位数字是1。

由于 n-1 的最后一位是 1，而 n 的最后一位是 0，因此 n&k != k，这与假设相矛盾。因此 n&k != k。

2). 假设C(n-1,k)和C(n-1,k-1)为偶数： 则： (n-1)&k != k; (n-1)&(k-1) != k-1; 现在假设n&k == k。

那么对于 k 的最后一位数字是 1 的情况：

此时，n 的最后一位数字也是 1，因此 (n-1)&(k-1) == k-1，这与假设相矛盾。对于 k 的最后一位数字为 0 的情况：

那么k的末尾肯定有这样的部分：10；代表任意多个0。对应的，n的对应部分是：1{*}*；*代表0或者1。

如果 n 对应的 {*}* 中只有一个为 1，则 (n-1)&k == k 成立，因此 n 的对应部分也应该是 10。

相应的，k-1和n-1的末位都是01，所以(n-1)&(k-1) == k-1成立，与假设相矛盾。

所以 n&k != k。

由1）和2）可知，当C(n,k)为偶数时，n&k != k。

3).设C(n-1,k)为奇数，C(n-1,k-1)为偶数： 则： (n-1)&k == k; (n-1)&(k-1) != k-1; 显然k的最后一位只能是0，否则(n-1)&k == k可以推导出(n-1)&(k-1) == k-1。因此k末尾必定有一部分形式为：10； 对应的n-1对应部分为：1{*}*； 对应的k-1对应部分为：01；

如果要使得 (n-1)&(k-1) != k-1，那么 n-1 对应的 {*}* 至少有一个为 0，所以 n 的对应部分为：1{*}*;（不会因为进位而由 1 变成 0），所以 n&k = k。

4).设C(n-1,k)为偶数，C(n-1,k-1)为奇数：则： (n-1)&k != k; (n-1)&(k-1) == k-1; 有两种情况：

当k-1的最后一位数字为0时：

那么k-1的末尾肯定有这样的部分：10；对应的，k的对应部分就是：11；

对应的，n-1对应部分为：1{*}0；（如果是1{*}1，则(n-1)&k == k） 对应的，n对应部分为：1{*}1；所以n&k = k。

当k-1的最后一位数字为1时：

那么k-1的末尾一定有这样的部分：01；（前面的0可以自己添加）对应的k的对应部分为：10；

对应的，n-1对应部分为：01；（如果是11，则 (n-1)&k == k） 对应的，n对应部分为：10；所以n&k = k。

由3）和4）可知，当C(n,k)为奇数时，n&k = k。

综上所述，结论被证明！

n&k 表示 n（按位与）k。例如 n=9，k=3，则转换成二进制 n=1001，k=0011，进行运算（全 1 为 1，否则为 0）得到 1。如果等于 k，则组合数为奇数，否则为偶数。原因是：按照二进制运算规则，从后往前数，有多少个偶数因子（这里我们说 2 是因子）就有多少个 0（不间断），按位与的作用就是消去 0。当然，按照组合公式，分子上的偶数因子不可能比分母上的少，但如果相等，那么该数就是奇数。按位与的作用就是 0 和 1 相加会消去 1，所以如果要保持原来的 k 值，n 转换成二进制（通俗地说）后就必须有许多个 1，这样它的偶数因子也会减少。 已证明，当 n&k==k 时，n! 与 k!(nk)! 有相同个数的偶数因子，因此可消去它们得到奇数。

文档来源：