對組合數C(n,k) (n>=k)：將n,k分別化為二進位制，若某二進位制位對應的n為0，而k為1 ，則C(n,k)為偶數；否則為奇數。 組合數的奇偶性判定方法為: 結論： 對於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。 綜上，結論得證!
對組合數C(n,k) (n>=k)：將n,k分別化為二進位制，若某二進位制位對應的n為0，而k為1 ，則C(n,k)為偶數；否則為奇數。 組合數的奇偶性判定方法為: 結論： 對於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。 綜上，結論得證!