組合數(shù)學課件

12.7一個袋子里裝了100個蘋果、100個香蕉、100個橘子和100個梨，如果每次從袋子里取出1個水果，那么至少取出多少次后能夠保證已經拿出10個相同種類的水果。解：設a1,a2,a3和a4分別為取出四種水果的個數(shù)，令r=10，由鴿巢原理加強形式推論2，知要使a1，a2，a3，a4至少有一個不小于r，則 （a1+a2+a3+a4）/4>r-1=10-1可得：a1+a2+a3+a4>36，即當至少取37個水果時，可保證已經拿出10個相同種類的水果。鴿巢原理22.10證明：在任意選取的n+2個正整數(shù)中存在兩個正整數(shù)，其差或和能被2n整除。證明：設a1，a2…an+2為任取n+2個正整數(shù)，考慮這n+2個正整數(shù)除以2n的余數(shù)，其余數(shù)只能為0,1,…,2n-1。將余數(shù)分為{0}、{1，2n-1}、{2，2n-2}…{n}這n+1個組，則由鴿巢原理知，n+2個正整數(shù)中至少有兩個數(shù)除以2n的余數(shù)，落入同一組內。

若這個數(shù)的余數(shù)落入{0}、{n}組內，則其差和其和均能被2n整除，若余數(shù)落入其他組內，余數(shù)若相同，則可知其差能被2n整除，若余數(shù)不同，則其和能被2n整除。鴿巢原理32.12某學生有37天的時間準備考試，根據她過去的經驗至多需要復習60個小時，但每天至少復習1小時。證明無論怎樣安排都存在連續(xù)的若干天，使得她在這些天里恰好復習了13小時。證明：設ai是從第1天到第i天復習的小時數(shù)，i=1,2,…,37。因為每天至少復習1小時，所以

1≤a1<a2<…<a37。又因為至多需要復習60小時，因此a37≤60。

1≤a1<a2<…<a37≤60

。做序列：a1+13,a2+13,…,a37+13,

這個序列也是嚴格單調上升的，且有a37+13≤73。

14≤a1+13<a2+13

<…<a37+13

≤73

考察序列：a1,a2,…,a37,a1+13,a2+13,…,a37+13,該序列有74個數(shù)，每個數(shù)都是小于等于73的正整數(shù)，由鴿巢原理必存在i和j,使得ai=

aj+13(j<i)。令n=i-j,則該學生在第j+1,j+2,…,j+n=i的連續(xù)n天中復習了13小時。鴿巢原理4證明：任取三個連續(xù)的扇形，由它們構成一組扇形組合，則圓盤上可取36個不同的扇形組合。這36個扇形組合上數(shù)字之和共為：

3*36*（36+1）

3*（1+2+…+36）=2則每個扇形組合上數(shù)字之和的平均值為：

3*36*（36+1）

=55.5>56-12*36由定理2.2.1的推論2，必存在三個連續(xù)的扇形，其中的數(shù)字之和至少是56.2.14把一個圓盤分成36個相等的扇形，然后把1,2,…,36這些數(shù)任意填入36個扇形中，證明存在三個連續(xù)的扇形，其中的數(shù)字之和至少是56。鴿巢原理53.2比5400大的四位整數(shù)中，數(shù)字2和7不出現(xiàn)，且各位數(shù)字不同的整數(shù)有多少個？解：分成兩種情況考慮：

①若千位為5,則百位可取4,6,8,9，十位可取非2、7以及千位和百位上的數(shù)，即P(6,1)，同樣取個位數(shù)的方案為P(5,1)，則由乘法原則知N1=P(4,1)*P(6,1)*P(5,1)=120。

②若千位不為5，則可取6,8,9，百位可取非2,7和千位上的數(shù)，即P(7,1),同樣,十位和個位上取數(shù)方案分別為P(6,1)和P(5,1),則由乘法原則知 N2=P(3,1)*P(7,1)*P(6,1)*P(5,1)=630。則加法原則可得：

N=N1+N2=750基本計數(shù)原理6加法原則與乘法原則3.312個人圍坐在圓桌旁，其中一個拒絕與另一個相鄰，問有多少種安排方法？

解:(1)若這兩人是確定的：先把其他11個人安排在圓桌旁，共有11!/11種；固定這11人后再把剩下的那個人加以安排，他的位置共9個，所以總的排法為11!/11×9=9×10!（種）.（2）如果這兩個人是任意的：先選出這樣兩個人來，有C(12,2)種選法；確定這兩個人后，排法有11!/11×9種。故總的排法有:C(12,2)×11!/11×9=54×11!（種）.73.4有顏色不同的四盞燈。(1)把它們按不同的次序全部掛在燈桿上表示信號，共有多少種不同的信號？(2)每次使用一盞、二盞、三盞和四盞燈按一定的次序掛在燈桿上表示信號，共有多少種不同的信號？(3)在(2)中，如果信號與燈的次序不關，共有多少種不同的信號？解:(1)為全排列問題，有P(4,4)=24種。

(2)N=C(4,1)*P(1,1)+C(4,2)*P(2,2)+C(4,3)*P(3,3)+C(4,4)*P(4,4)=4+12+24+24=64種。

(3)N=C(4,1)+C(4,2)+C(4,3)+C(4,4)=4+6+4+1=15種。加法原則與乘法原則8排列與組合3.4

有四盞顏色不同的燈：（1）把它們按不同的次序全部掛在燈桿上表示信號，共有多少種不同的信號？（2）每次使用一盞、二盞、三盞或四盞燈按一定的次序掛在燈桿上表示信號，共有多少種不同的信號？解

（1）P(4,4)=24

（2）P(4,1)+P(4,2)+P(4,3)+P(4,4)=6493.10試求不定方程x1+x2+…+x8=40滿足xi≥i(i=1,2,…,8)的整數(shù)解的個數(shù)？解：令yi=xi–

i，因xi≥i，則yi≥0，不定方程轉化為：

(1+y1)+(2+y2)+…+(8+y8)=40 y1+y2+…+y8=40–(1+8)*8/2=4則不定方程y1+y2+…+y8=4滿足yi

≥0的整數(shù)解的個數(shù)即為所求。由定理3.2.4證明可知，該方程的非負整數(shù)解個數(shù)等于集合{7.0,4.1}的全排列，因此所求不定方程x1+x2+…+x8=40滿足xi≥i(i=1,2,…,8)的整數(shù)解的個數(shù)為：=330排列與組合10

解：先考慮對角線下方的路徑，這種路徑都是從(0,0)點出發(fā)經過(1,0)點及(n,n-1)點到達(n,n)點的。可以把它看作是從(1,0)點出發(fā)到達(n,n-1)點的不穿過對角線的非降路徑。從(1,0)點到(n,n-1)點的所有非降路徑數(shù)是3.13計數(shù)從(0,0)點到(n,n)點不穿過直線y=x的非降路徑數(shù)。y=x+1Ay=x(-1,2)(1,0)(0,1)(0,0)xy(n,n)(n,n-1)非降路徑問題11

對其中任意一條穿過對角線的路徑，可以看成從(1,0)點出發(fā)到(n,n-1)點的接觸直線y=x+1的所有非降路徑，把這樣的一條路徑的(1,0)點到其最后離開y=x+1的點A部分按照直線y=x+1作一個反射，就得到一條從(-1,2)到達y=x+1Ay=x(-1,2)(1,0)(0,1)(0,0)xy(n,n)(n,n-1)(n,n-1)的非降路徑，反之，任何一條從(-1,2)出發(fā)到(n,n-1)點的非降路徑也可以通過這種反射對應到一條從(0,1)到達(n,n-1)點并接觸y=x+1的非降路徑。從(-1,2)到達(n,n-1)點的非降路徑數(shù)為：非降路徑問題12，由對稱性可知，所求的路徑數(shù)是：，從而在對角線下方的路徑數(shù)是非降路徑問題13非降路徑問題14非降路徑問題15非降路徑問題16非降路徑問題n越過和接觸y=x越過（不包括接觸）y=x1002423161017nmr0n-1m-1r+11++…+n-m0r+mm=n+r+1m證明：表示從(0,0)點到(n+r+1-m,m)點的非降路徑數(shù)，任何這樣的路徑一定經過圖中x=r線上的點，把它們按經過直線上的不同的點向右而分類。從(0,0)到(r,k)點的非降路徑是條。n+r+1mr+kk(0,0)xy(n+r+1-m,m)x=r…(r,k)(r+1,k)從(r,k)到(r+1,k)的非降路徑是1條。從(r+1,k)到(n+r+1-m,m)的非降路徑是條，由乘法法則，從(0,0)點經(r,k)和(r+1,k)到(n+r+1-m,m)點的非降路徑是條，再對k=0,1,…m求和就得到所有從點(0,0)到點(n+r+1-m,m)的非降路徑數(shù)，等式得證。n-km-kr+kkn-km-k3.28用非降路徑的方法證明以下組合恒等式：183.35用多項式定理展開解：=其中求和是對滿足方程的一切非負整數(shù)解來求。多項式系數(shù)19容斥原理20容斥原理21容斥原理習題4.11與1000之間不能被4,5和6整除的整數(shù)有多少個？解:

令A={1,2,3,…,1000}，則

|A|=1000.記A1、A2、A3分別為在1與1000之間能被4,5和6整除的整數(shù)集合，則有：|A1|=L1000/4」=250,

|A2|=L1000/5」=200,|A3|=L1000/6」=166,于是A1∩A2表示A中能被5和6整除的數(shù),即能被30整除的數(shù)，其個數(shù)為

|A1∩A2|=L1000/20」=50；22容斥原理同理,|A1∩A3|=L1000/12」=83,|A2∩A3|=L1000/30」=33,A1∩A2∩

A3

表示A中能同時被4,5,6整除的數(shù)，即A中能被4,5,6的最小公倍數(shù)lcm(4,5,6)=60整除的數(shù)，其個數(shù)為

|A1∩A2∩A3|=L1000/60」=16.由容斥原理知，A中不能被4，5，6整除的整數(shù)個數(shù)為:=|A|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A3∩A2|)-|A1∩A2∩A3|=53423容斥原理24容斥原理25容斥原理26容斥原理27解：令S’

={

}，S’的所有的9-組合構成集合W，則可得：

4.4求S=｛｝的9-組合數(shù)容斥原理

任取S’的一個9-組合，如果其中的b多于3個，則稱它具有性質p1;如果其中c多于5個，則稱它具有性質p2;如果其中d多于7個，則稱它具有性質p3。不難看出所求的9-組合數(shù)就是W中不具有性質p1，p2和p3的元素個數(shù)。

Ai=｛ｘ∣ｘ∈Ｗ∧ｘ具有性質pi}i=1,2,3,4計算|A1|、|A2|和|A3|：A1中的每個9－組合至少含有4個b，把這4個b拿走就得到S’的一個5－組合。反之，對T的任意一個5－組合加上4個b就得到中的一個9－組合。所以就是S’的6－組合數(shù)，即28用類似的方法可以計算|A1∩A2|

、|A1∩A3|

、|A2∩A3|

和|A1∩A2∩A3

|

則所求9-組合：=220-（56+20+4）=140容斥原理294.9求多重集S={4·a,2·b,3·c}的排列數(shù)，要求排列中的同類字母的全體不能相鄰。解：多重集S={4·a,2·b,3·c}的全排列要構成集合W，則其全排列數(shù)為任取S的一個全排列，如果其中字母a的全體相鄰，則稱它具有性質p1;如果其中字母b的全體相鄰，則稱它具有性質p2;如果其中字母c的全體相鄰，則稱它具有性質p3。

Ai=｛ｘ∣ｘ∈Ｗ∧ｘ具有性質pi}i=1,2,3計算|A1|。

A1中4個a全體相鄰，則將其作為一個整體a’與其它字母排列，為{1·a’,2·b,3·c}全排列，故容斥原理30類似可計算|A2|、|A3|、|A1∩A2|

、|A1∩A3|

、|A2∩A3|

和|A1∩A2∩A3

|。=1260-（60+280+105）+（20+12+30）-6=871則所求為：容斥原理314.10從一個4×4的棋盤中選取2個方格，使得它們不在同一行也不在同一列，共有多少種選法？解：在4×4的棋盤中共有16個方格，因此第1個方格的選取的方案數(shù)為16，第二方格要與第一個方格不在同一行也不在同一列，因此只能選擇去除第1個方格所在行和列的3×3=9個方格中的一個，故可選方案數(shù)為9，而第1個方格與第2個方格與選擇順序無關，故所求的方案數(shù)為：

16*9/2=72。容斥原理32思考題：從一個m×m的棋盤中選取n(n≤m)個方格，使得它們不在同一行也不在同一列，共有多少種選法？解：(P(m,n))2/n!容斥原理33容斥原理R()=x·R()+R() =x(1+2x)+(1+3x) =1+4x+2x2R()=x·R()+R() =x·1+x()+() =x+x(1+x)+(1+x)2=1+4x+2x234容斥原理R()=x·R()+R()=x·[x·R()+R()]+[x·R()+R()]=x[x(1+x)+(1+2x)]+[x(1+2x)+(1+4x+2x2)]=1+6x+7x2+x335容斥原理R()=x·R()+R()=x(1+x)+x·R()+R()=x(1+x)+x(1+2x)+x·R()+R()=x(1+x)+x(1+2x)+x(1+x)+(1+x)3=1+6x+7x2+x336組合數(shù)的生成函數(shù)37組合數(shù)的生成函數(shù)38排列數(shù)的指數(shù)型生成函數(shù)39生成函數(shù)在計數(shù)問題中的應用習題5.3由a,b,c,d,e組成的長為n的字中,要求a與b

的個解

分兩種情況:

數(shù)之和為偶數(shù),問這樣的字有多少個?（1）a與b的個數(shù)都為奇數(shù);則對第一種情況有

（2）

a與b的個數(shù)都為偶數(shù);

該排列的指數(shù)型生成函數(shù)為

40生成函數(shù)在計數(shù)問題中的應用對第二種情況有

所以

的系數(shù)為

該排列的指數(shù)型生成函數(shù)為

故這樣的字的個數(shù)有

所以

的系數(shù)為

41生成函數(shù)在計數(shù)問題中的應用42生成函數(shù)在計數(shù)問題中的應用習題5.4證明方程

有相同數(shù)目的非負和

整數(shù)解.

不同的盒子里放13個相同的球,則各盒子可裝的球的個數(shù)為可以看成是在7個證明

方程

{0,1,2,…,13}個.用生成函數(shù)表示為43生成函數(shù)在計數(shù)問題中的應用當時,的系數(shù)為

.在這里,k=13,故其系數(shù)為

44生成函數(shù)在計數(shù)問題中的應用不同的盒子里放14個相同的球,則各盒子可裝的球的個數(shù)可以看成是在6個同理方程

為{0,1,2,…,6}個.用生成函數(shù)表示為當時,的系數(shù)為

.在這里,k=6,故的.因此得證.

系數(shù)為

45生成函數(shù)在計數(shù)問題中的應用習題5.4證明方程

有相同數(shù)目的非負整數(shù)解和

不同的盒子里放13個相同的球,則各盒子可裝的球的個數(shù)為可以看成是在7個證明

方程

{0,1,2,…}個.用生成函數(shù)表示為當時,的系數(shù)為

.在這里,k=13,故其系數(shù)為

46生成函數(shù)在計數(shù)問題中的應用不同的盒子里放14個相同的球,則各盒子可裝的球的個數(shù)可以看成是在6個同理方程

為{0,1,2,…,6}個.用生成函數(shù)表示為當時,的系數(shù)為

.在這里,k=6,故的.因此得證.

系數(shù)為

47排列數(shù)的指數(shù)型生成函數(shù)48排列數(shù)的指數(shù)型生成函數(shù)49排列數(shù)的指數(shù)型生成函數(shù)50排列數(shù)的指數(shù)型生成函數(shù)51排列數(shù)的指數(shù)型生成函數(shù)52排列數(shù)的指數(shù)型生成函數(shù)53生成函數(shù)54遞推關系55遞推關系56遞推關系57遞推關系58遞推關系59遞推關系60遞推關系61遞推關系62遞推關系63遞推關系64遞推關系65遞推關系66遞推關系67遞推關系68遞推關系69遞推關系70遞推關系71生成函數(shù)72基本計數(shù)原理3.78個棋子大小相同，其中5個紅的，3個藍的。把它們放在8×8的棋盤上，每得、每行、每列只放一個，問有多少種放法？若放在12×12的棋盤上，結果如何？1.先放紅色的.（1）在8行中任選5行放紅色棋子，有C（8,5）種選擇.（2）選定行后，再選列.因為每行都不同，故有P（8,5）種選擇.現(xiàn)在再放藍色的棋子.還剩3行、3列，而每個棋子都是相同的，故可把第一個棋子放在剩下的第一行，3列可選;第二個棋子放第二行，2列可選；第三個棋子則只剩下1行1列可選.于是，有3!種方案.根據乘法原理，共有C（8,5）×P（8,5）×3!=種放法.73基本計數(shù)原理74基本計數(shù)原理75基本計數(shù)原理3.18將52張牌平均分給4個人，問每人有一個5張牌的同花順的概率是多少？解首先分給4個人每人一個5張牌的同花順的個數(shù)：(1)4個人每人的5張同花順顏色均不同.每一種花色均有9種不同的同花順.故共有P（4,4）×94種可能.(2)4個人中有兩人是同色的同花