基本計數原理

(1)加法原理和分類計數法

　　1．加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同的方法，那么完成這件事共有N=m1+m2+m3+…+mn種不同方法。
　　2．第一類辦法的方法屬于集合A1，第二類辦法的方法屬于集合A2，……，第n類辦法的方法屬于集合An，那么完成這件事的方法屬于集合A1UA2U…UAn。
　　3．分類的要求 ：每一類中的每一種方法都可以獨立地完成此任務；兩類不同辦法中的具體方法，互不相同(即分類不重)；完成此任務的任何一種方法，都屬于某一類(即分類不漏) 。

(2)乘法原理和分步計數法

　　1. 乘法原理：做一件事，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n步有mn種不同的方法，那么完成這件事共有N=m1×m2×m3×…×mn種不同的方法。
　　2．合理分步的要求
　　任何一步的一種方法都不能完成此任務，必須且只須連續完成這n步才能完成此任務；各步計數相互獨立；只要有一步中所采取的方法不同，則對應的完成此事的方法也不同。

二項式定理

　　(a+b)^n=Σ(0->n)C(in)a^(n-i)b^i[1]
　　通項公式：a_(i+1)=C(in)a^(n-i)b^i
　　二項式系數：兩端是1，除1外的每個數是肩上兩數之和。
　　系數性質：（1）和首末兩端等距離的系數相等；
　　（2）當冪指數是奇數時，中間兩項最大且相等；
　�。�3）當冪指數是偶數時，中間一項最大。
　�。�4）奇數項和偶數項總和相同，都是2^(n-1)；
　�。�5）所有系數總和是2^n

組合數的奇偶

　　奇偶定義：對組合數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),若n&k == k 則c(n,k)為奇數，否則為偶數。
　 　證明：
 　　利用數學歸納法：
　　由C(n,k) = C(n-1,k) + C(n-1,k-1);
　　對應于楊輝三角：
 　　1
　　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。
 　　綜上，結論得證。