組合數(shù)學幻燈片13

定義1.4設(shè)A=｛a1,a2,…,an｝是具有n個元素的集合，r是非負整數(shù)。從這n個不同的元素里取r個不考慮次序組合起來(r≤n)，稱為集合A的r組合。記為C(n,r)

換句話說，A的r-組合是A的r-無序子集。§1.3組合對于r≤n，有C(n,r)=P(n,r)/r!=n!/r!(n-r)!(1.7)證明：從n個不相同的元素里取r個元素的組合個數(shù)為C(n,r)。而r個元素可以組成r!個r-排列，一個r-組合

r!個r-排列

C(n,r)個r-組合

r!C(n,r)個r-排列，

這實際上就是從n個元素中選取r個元素組成的r-排列數(shù)P(n,r)r!C(n,r)=P(n,r)。

C(n,r)=P(n,r)/r!=n!/r!(n-r)!定理1.5

C(n,r)=C(n,n-r)(1.8)證明：事實上，從n個不同的元素中選出r個元素，就有n-r個元素沒有被選出。因此選出r個元素的方式數(shù)等于選出n-r個元素的方式數(shù)，即C(n,r)=C(n,n-r)，證畢。另外：式(1.8)的證明也可由公式(1-7)得出，事實上C(n,n-r)=n!/(n-r)!(n-(n-r))!=n!/(n-r)!r!=C(n,r)推論1

(Pascal公式)

C(n,r)=C(n-1,r)+C(n-1,r-1)(1.9)證明：

C(n,r)=n!/r!(n-r)!=n(n-1)!/r!(n-r)!=［(n-r)(n-1)!+r(n-1)!］/［r(r-1)!(n-r)(n-r-1)!］=(n-1)!/r!(n-1-r)!+(n-1)!/(r-1)!(n-1-r+1)!=C(n-1,r)+C(n-1,r-1)推論2

也可用組合分析的方法論證：在集合A的n個元素中固定一個元素，不妨設(shè)為a1，于是，從n個元素中取r個元素的組合(1)r個元素中包含a1。這可以從除去a1的n-1個元素中取r-1個元素的組合，然后將a1加入而得到，其組合個數(shù)為C(n-1,r-1)。

由加法規(guī)則即得C(n,r)=C(n-1,r)+C(n-1,r-1)推論2

（2)r個元素中不包含a1。這可以從除去a1的n-1個元素中取r個元素的組合而得到，其組合個數(shù)為C(n-1,r)。利用式(1-9)和初始值C(n,0)=C(n,n)=1，對所有非負整數(shù)可計算出表1-1的三角形陣列，通常稱這個三角陣列為楊輝三角形或Pascal三角形。01111212131331414641515101051616152015617172135352171818285670562881…

…

…

…

…

…

…

…

…

…數(shù)510510能被多少個不同的奇數(shù)整除?解：510510=2·3·5·7·11·13·17除2是偶數(shù)外都是奇數(shù)，于是要整除510510的奇數(shù)只能是除2以外的奇素數(shù)之積或者1，而且在一個積中一個奇數(shù)至多出現(xiàn)一次。奇素數(shù)之積分下面幾種情況討論：一個奇素數(shù)，一共有C(6，1)=6個……六個奇素數(shù)，一共有C(6，6)=1個被1整除，1個由加法規(guī)則知總共有6+15+20+15+6+1+1=64個。例2

從1，2，…，1000中選出三個整數(shù)，有多少種選法使得所選的三個整數(shù)的和能被3整除?解：把集合A=｛1,2,…,1000｝分成三個子集合，

A1=｛1,4,7,…,1000｝｜A1｜=1000/3+1=334,A2=｛2,5,8,…,998｝｜A2｜=998/3+1=333,A3=｛3,6,9,…,999｝｜A3｜=999/3=333a1+a2+a3能被3整除,則只有下面兩種情形：(1)a1，a2和a3取自同一子集Ai(i=1,2,3)中。選法的種數(shù)為C(334,3)+2·C(333,3)(2)a1，a2和a3分別取自不同的子集A1，A2和A3中。選法的種數(shù)為C(334,1)·C(333,1)·C(333,1)由加法規(guī)則知，符合題意的選法種數(shù)為C(334,3)+2·C(333,3)+334*333*333例3

定義1.5從重集B=｛k1·b1,k2·b2,…,kn·bn｝中選取r個元素不考慮次序組合起來，稱為從B中取r個元素的重復組合定理1.6B=｛∞·b1,∞·b2,…,∞·bn｝的r組合數(shù)為F(n,r)=C(n+r-1,r)(1.11)證明：設(shè)n個元素b1，b2，…，bn和自然數(shù)1，2，…，n一一對應(yīng)，于是所考慮的任何組合便可看成是一個r個數(shù)的組合｛c1,c2,…,cr｝?？烧J為各ci是按大小次序排列的，相同的ci

連續(xù)地排在一起。如按c1≤c2≤…≤cr排列。重復組合

令di=ci+i-1(i=1,2,…,r)即

d1=c1,d2=c2+1,…,dr=cr+r-1。由于ci最大可取n，故di最大可取n+r-1，這樣就得到一個集合｛1,2,…,n+r-1｝的r組合d1,d2,…,dr(d1<d2<…<dr)易見有一種｛c1,c2,…,cr｝的取法便有一種｛d1,d2,…,dr｝的取法。而這兩種取法有一一對應(yīng)關(guān)系，從而這兩個組合計數(shù)問題是等價的。這樣一來，允許重復的從n個不同元素中取r個元素的組合數(shù)和不允許重復的從n+r-1個不同元素中取r個元素的組合數(shù)是相同的。故有

F(n,r)=C(n+r-1,r)重復組合

注意：在定理1.6中，如果B的不同元素的重復數(shù)至少是r，則結(jié)論仍成立。重復組合

某餐廳有7種不同的菜，為了招待朋友，一個顧客需要買14個菜，問有多少種買法?

解：這個問題可以歸結(jié)為集合｛∞·1,∞·2,…,∞·7｝的14組合。共有

F(7，14)=C(20,14)

種買法。

求n個無區(qū)別的球放入r個有標志的盒子(n≥r)而無一空盒的方式數(shù)。解：每個盒子不能為空，故每個盒子中可先放一球，這樣還剩n-r個球，再將這n-r個球放到r個盒子中去例四例五由于這時每盒的球數(shù)不受限制，這相當于從重集｛∞·a1,∞·a2,…,∞·ar｝中取n-r個元素的組合，由式(1.11)知，其組合數(shù)為

F(r,n-r)=C(r+n-r-1,n-r)=C(n-1,n-r)=C(n-1,r-1)例五在由數(shù)0，1，…，9組成的r位整數(shù)所組成的集合中，如果將一個整數(shù)重新排列而得到另一個整數(shù)，則稱這兩個整數(shù)是等價的。那么

(1)有多少不等價的整數(shù)?

(2)如果數(shù)字0和9最多只能出現(xiàn)一次，又有多少不等價的整數(shù)。

例六解：1)由兩個整數(shù)等價的定義知，一個r位整數(shù)只和所取的數(shù)字有關(guān)，而與這些數(shù)字的次序無關(guān)。故這是一個組合問題。而且每一整數(shù)中的每一位可從數(shù)字0，1，…，9中任意選取因此不等價的r位整數(shù)可以看作是重集B=｛∞·0,∞·1,…,∞·9｝的r-組合。由式(111)知，其個數(shù)為

F(10,r)=注意，這里將r個0組成的數(shù)看作是0。例六2)數(shù)字0和9最多只能出現(xiàn)一次，由下列三種情形組成：

a.數(shù)字0和9均不出現(xiàn)，這實際上是重集B=｛∞·1,∞·2,…,∞·8｝的r-組合，其個數(shù)為

F(8,r)=

=例六b.數(shù)字0和9只出現(xiàn)其一，或者數(shù)字0出現(xiàn)一次，或者數(shù)字9出現(xiàn)一次。⑴若數(shù)字0出現(xiàn)，數(shù)字9不出現(xiàn)，這實際上是重集B=｛∞·1,∞·2,…,∞·8｝的(r-1)組合，然后將數(shù)字0加入，其個數(shù)為⑵同樣，數(shù)字9出現(xiàn)，數(shù)字0不出現(xiàn)，其個數(shù)為c.數(shù)字0和9都出現(xiàn)一次，這實際上是重集B=｛∞·1,∞·2,…,∞·8｝的(r-2)-組合，然后將0和9加入，其個數(shù)為由加法規(guī)則知，符合題意要求的不等價整數(shù)個數(shù)為求方程x1+x2+…+xn=r的非負整數(shù)解的個數(shù)。其中,n,r為正整數(shù)。解：

設(shè)b1,b2,…,bn為n個不同的元素，于是重集B=｛∞·b1,∞·b2,…,∞·bn｝的任何一個r-組合都具有形式x1·b1