MPAcc數(shù)學(xué)排列與組合考點(diǎn)總結(jié)

希賽網(wǎng)MPAcc頻道為廣大考生整理出MPAcc數(shù)學(xué)排列與組合考點(diǎn)總結(jié)，供大家參考學(xué)習(xí)。希望能為大家在研究生考試中提供到幫助。

一、基本計(jì)數(shù)原理

(1)加法原理和分類計(jì)數(shù)法

1．加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同的方法，那么完成這件事共有N=m1+m2+m3+…+mn種不同方法。

2．第一類辦法的方法屬于集合A1，第二類辦法的方法屬于集合A2，……，第n類辦法的方法屬于集合An，那么完成這件事的方法屬于集合A1UA2U…UAn。

3．分類的要求 ：每一類中的每一種方法都可以獨(dú)立地完成此任務(wù)；兩類不同辦法中的具體方法，互不相同(即分類不重)；完成此任務(wù)的任何一種方法，都屬于某一類(即分類不漏) 。

(2)乘法原理和分步計(jì)數(shù)法

1. 乘法原理：做一件事，完成它需要分成n個(gè)步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n步有mn種不同的方法，那么完成這件事共有N=m1×m2×m3×…×mn種不同的方法。

2.合理分步的要求

任何一步的一種方法都不能完成此任務(wù)，必須且只須連續(xù)完成這n步才能完成此任務(wù)；各步計(jì)數(shù)相互獨(dú)立；只要有一步中所采取的方法不同，則對(duì)應(yīng)的完成此事的方法也不同。

二、二項(xiàng)式定理

(a+b)^n=Σ(0->n)C(in)a^(n-i)b^i[1]

通項(xiàng)公式：a_(i+1)=C(in)a^(n-i)b^i

二項(xiàng)式系數(shù)：兩端是1，除1外的每個(gè)數(shù)是肩上兩數(shù)之和。

系數(shù)性質(zhì)：（1）和首末兩端等距離的系數(shù)相等；

（2）當(dāng)冪指數(shù)是奇數(shù)時(shí)，中間兩項(xiàng)最大且相等；

（3）當(dāng)冪指數(shù)是偶數(shù)時(shí)，中間一項(xiàng)最大。

（4）奇數(shù)項(xiàng)和偶數(shù)項(xiàng)總和相同，都是2^(n-1)；

（5）所有系數(shù)總和是2^n

三、組合數(shù)的奇偶

奇偶定義：對(duì)組合數(shù)C(n,k) (n>=k)：將n,k分別化為二進(jìn)制，若某二進(jìn)制位對(duì)應(yīng)的n為0，而k為1 ，則C(n,k)為偶數(shù)；否則為奇數(shù)。

下面是判定方法：

結(jié)論：

對(duì)于C(n,k),若n&k == k 則c(n,k)為奇數(shù)，否則為偶數(shù)。

證明：

對(duì)于C(n,k),若n&k == k 則c(n,k)為奇數(shù)，否則為偶數(shù)。

證明：

利用數(shù)學(xué)歸納法：

由C(n,k) = C(n-1,k) + C(n-1,k-1);

對(duì)應(yīng)于楊輝三角：

    1

   1 1

  1 2 1

 1 3 3 1

1 4 6 4 1

………………

可以驗(yàn)證前面幾層及k = 0時(shí)滿足結(jié)論，下面證明在C(n-1,k)和C(n-1,k-1) (k > 0) 滿足結(jié)論的情況下，C(n,k)滿足結(jié)論。

1)假設(shè)C(n-1,k)和C(n-1,k-1)為奇數(shù)：

則有：(n-1)&k == k;

(n-1)&(k-1) == k-1;

由于k和k-1的最后一位(在這里的位指的是二進(jìn)制的位，下同)必然是不同的，所以n-1的最后一位必然是1 　　。

現(xiàn)假設(shè)n&k == k。

則同樣因?yàn)閚-1和n的最后一位不同推出k的最后一位是1。

因?yàn)閚-1的最后一位是1，則n的最后一位是0，所以n&k != k，與假設(shè)矛盾。

所以得n&k != k。

2)假設(shè)C(n-1,k)和C(n-1,k-1)為偶數(shù)：

則有：(n-1)&k != k;

(n-1)&(k-1) != k-1;

現(xiàn)假設(shè)n&k == k.

則對(duì)于k最后一位為1的情況：

此時(shí)n最后一位也為1，所以有(n-1)&(k-1) == k-1，與假設(shè)矛盾。

而對(duì)于k最后一位為0的情況：

則k的末尾必有一部分形如：10; 代表任意個(gè)0。

相應(yīng)的，n對(duì)應(yīng)的部分為： 1{*}*; *代表0或1。

而若n對(duì)應(yīng)的{*}*中只要有一個(gè)為1，則(n-1)&k == k成立，所以n對(duì)應(yīng)部分也應(yīng)該是10。

則相應(yīng)的，k-1和n-1的末尾部分均為01,所以(n-1)&(k-1) == k-1 成立，與假設(shè)矛盾。

所以得n&k != k。

由1)和2)得出當(dāng)C(n,k)是偶數(shù)時(shí)，n&k != k。

3).假設(shè)C(n-1,k)為奇數(shù)而C(n-1,k-1)為偶數(shù)：

則有：(n-1)&k == k;

(n-1)&(k-1) != k-1;

顯然，k的最后一位只能是0，否則由(n-1)&k == k即可推出(n-1)&(k-1) == k-1。

所以k的末尾必有一部分形如：10;

相應(yīng)的，n-1的對(duì)應(yīng)部分為： 1{*}*;

相應(yīng)的，k-1的對(duì)應(yīng)部分為： 01;

則若要使得(n-1)&(k-1) != k-1 則要求n-1對(duì)應(yīng)的{*}*中至少有一個(gè)是0.

所以n的對(duì)應(yīng)部分也就為 ： 1{*}*; (不會(huì)因?yàn)檫M(jìn)位變1為0)

所以 n&k = k。

4).假設(shè)C(n-1,k)為偶數(shù)而C(n-1,k-1)為奇數(shù)：

則有：(n-1)&k != k;

(n-1)&(k-1) == k-1;

分兩種情況：

當(dāng)k-1的最后一位為0時(shí):

則k-1的末尾必有一部分形如： 10;

相應(yīng)的，k的對(duì)應(yīng)部分為 : 11;

相應(yīng)的，n-1的對(duì)應(yīng)部分為 : 1{*}0; (若為1{*}1,則(n-1)&k == k)

相應(yīng)的，n的對(duì)應(yīng)部分為 : 1{*}1;

所以n&k = k。

當(dāng)k-1的最后一位為1時(shí)：

則k-1的末尾必有一部分形如： 01; (前面的0可以是附加上去的)

相應(yīng)的，k的對(duì)應(yīng)部分為 : 10;

相應(yīng)的，n-1的對(duì)應(yīng)部分為 : 01; (若為11，則(n-1)&k == k)

相應(yīng)的，n的對(duì)應(yīng)部分為 : 10;

所以n&k = k。

由3),4)得出當(dāng)C(n,k)為奇數(shù)時(shí)，n&k = k。

綜上，結(jié)論得證。