希賽網MPAcc頻道為廣大考生整理出MPAcc數學排列與組合考點總結，供大家參考學習。希望能為大家在研究生考試中提供到幫助。

一、基本計數原理

(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。

綜上，結論得證。