《組合數(shù)學》姜建國著第二版-課后習題答案

組合數(shù)學(第2版)?姜建國,岳建國

習題一(排列與組合)

1.在1到9999之間，有多少個每位上數(shù)字全不相同而且由奇數(shù)構成的整數(shù)？

解：該題相當于從“1,3,5,7,9”五個數(shù)字中分別選出1,2,3,4作排列的

方案數(shù)；

(1)選1個，即構成1位數(shù)，共有■個；

(2)選2個，即構成兩位數(shù)，共有片個；

(3)選3個，即構成3位數(shù)，共有片個；

(4)選4個，即構成4位數(shù)，共有&個；

由加法法則可知，所求的整數(shù)共有：月+片+用+廳=205個。

2.比5400小并具有下列性質的正整數(shù)有多少個？

(1)每位的數(shù)字全不同；

(2)每位數(shù)字不同且不出現(xiàn)數(shù)字2與7；

解：(1)比5400小且每位數(shù)字全不同的正整數(shù)；

按正整數(shù)的位數(shù)可分為以下幾種情況：

①一位數(shù)，可從1?9中任取一個，共有9個；

②兩位數(shù)。十位上的數(shù)可從1?9中選取，個位數(shù)上的數(shù)可從其余9個數(shù)

字中選取，根據(jù)乘法法則，共有9x9=81個；

③三位數(shù)。百位上的數(shù)可從1?9中選取，剩下的兩位數(shù)可從其余9個數(shù)

中選2個進行排列，根據(jù)乘法法則，共有9x6=648個；

④四位數(shù)。又可分三種情況：

■千位上的數(shù)從1?4中選取，剩下的三位數(shù)從剩下的9個數(shù)字中選

3個進行排列，根據(jù)乘法法則，共有4x/^=2016個；

■千位上的數(shù)取5,百位上的數(shù)從1?3中選取，剩下的兩位數(shù)從剩

下的8個數(shù)字中選2個進行排列，共有3X6=I68個；

■千位上的數(shù)取5,百位上的數(shù)取0,剩下的兩位數(shù)從剩下的8個數(shù)

字中選2個進行排列，共有4=56個；

根據(jù)加法法則，滿足條件的正整數(shù)共有：9+81+648+2016+168+56=2978個；

(2)比5400小且每位數(shù)字不同且不出現(xiàn)數(shù)字2與7的正整數(shù)；

按正整數(shù)的位數(shù)可分為以下兒種情況：設4={0』,3,4,5,6,8,9}

①一位數(shù)，可從4-{0}中任取一個，共有7個；

②兩位數(shù)。十位上的數(shù)可從A-{0}中選取，個位數(shù)上的數(shù)可從A中其余7

個數(shù)字中選取，根據(jù)乘法法則，共有7x7=49個；

③三位數(shù)。百位上的數(shù)可從A-{0}中選取，剩下的兩位數(shù)可從A其余7

個數(shù)中選2個進行排列，根據(jù)乘法法則，共有7'廳=294個;

④四位數(shù)。又可分三種情況：

■千位上的數(shù)從L3,4中選取，剩下的三位數(shù)從A中剩下的7個

數(shù)字中選3個進行排列，根據(jù)乘法法則，共有3'片=630個；

■千位上的數(shù)取5,百位上的數(shù)從0,1,3中選取，剩下的兩位數(shù)從

A中剩下的6個數(shù)字中選2個進行排列，共有3*片=90個；

根據(jù)加法法則，滿足條件的正整數(shù)共有：7+49+294+630+90=1070個；

3.一教室有兩排，每排8個座位，今有14名學生，問按下列不同的方式入座，

各有多少種做法？

(1)規(guī)定某5人總坐在前排，某4人總坐在后排，但每人具體座位不指定；

(2)要求前排至少坐5人，后排至少坐4人。

解：(1)因為就坐是有次序的，所有是排列問題。

5人坐前排，其坐法數(shù)為P(8,5),4人坐后排，其坐法數(shù)為P(8,4),

剩下的5個人在其余座位的就坐方式有P(7,5)種，

根據(jù)乘法原理，就座方式總共有：

P(8,5)P(8,4)2(7,5)=28449792000(種)

(2)因前排至少需坐6人，最多坐8人，后排也是如此。

可分成三種情況分別討論：

①前排恰好坐6人，入座方式有C(14,6)P(8,6)P(8,8)；

②前排恰好坐7人，入座方式有C(14,7)P(8,7)P(8,7)；

③前排恰好坐8人，入座方式有C(14,8)P(8,8)P(8,6)；

各類入座方式互相不同，由加法法則，總的入座方式總數(shù)為：

C(14,6)P(8,6)P(8,8)+C(14,7)P(8,7)-(8,7)+C(14,8)P(8,8)P(8,6)

=10461394944000

?典型錯誤：

先選6人坐前排，再選4人坐后排，剩下的4人坐入余下的6個座

位。故總的入坐方式共有：C(14,6)P(8,6)C(8,4)P(8,4)P(6,4)種。

但這樣計算無疑是有重復的，例如恰好選6人坐前排，其余8人全

坐后排，那么上式中的C(8,4)尸(8,4)就有重復。

4.一位學者要在一周內安排50個小時的工作時間，而且每天至少工作5小時，

問共有多少種安排方案？

解：用若表示第i天的工作時間，i=l,2,…,7,則問題轉化為求不定方程

+々+工+%4+/+4+毛=50的整數(shù)解的組數(shù)，且XjN5,于是又可以轉

化為求不定方程%+%+為+以+*+%+%=15的整數(shù)解的組數(shù)。

該問題等價于：將15個沒有區(qū)別的球，放入7個不同的盒子中，每盒球數(shù)

不限，即相異元素允許重復的組合問題。

故安排方案共有：RC(oo,15)=C(15+7-l,15)=54264(種)

?另解：

因為允許必=0,所以問題轉化為長度為1的15條線段中間有14個空，再

加上前后兩個空，共16個空，在這16個空中放入6個“+”號，每個空放置的

“十”號數(shù)不限，未放“+”號的線段合成一條線段，求放法的總數(shù)。從而不定

方程的整數(shù)解共有:

21x20x19x18x17x16

/?C(oo,6)=C(16+6-l,6)=54264(組)

6x5x4x3x2xl

即共有54264種安排方案。

5.若某兩人拒絕相鄰而坐，問12個人圍圓周就坐有多少種方式？

解：12個人圍圓周就坐的方式有：CP(12,12)=11!種，

設不愿坐在一起的兩人為甲和乙，將這兩個人相鄰而坐，可看為1人，則這

樣的就坐方式有：CP(11,11)=10!種；由于甲乙相鄰而坐，可能是“甲乙”

也可能是“乙甲”；所以

則滿足條件的就坐方式有：U!-2xl0!=32659200種。

6.有15名選手，其中5名只能打后衛(wèi)，8名只能打前鋒，2名只能打前鋒或后

衛(wèi)，今欲選出11人組成一支球隊，而且需要7人打前鋒，4人打后衛(wèi)，試問

有多少種選法？

解：用A、B、C分別代表5名打后衛(wèi)、8名打前鋒、2名可打前鋒或后衛(wèi)的集合,

則可分為以下幾種情況：

(1)7個前鋒從B中選取，有C；種選法，4個后衛(wèi)從A中選取，有C；種，

根據(jù)乘法法則，這種選取方案有：C；C；種；

(2)7個前鋒從B中選取，從A中選取3名后衛(wèi)，從C中選1名后衛(wèi)，

根據(jù)乘法法則，這種選取方案有：c；c；C；種；

(3)7個前鋒從B中選取，從A中選取2名后衛(wèi)，C中2名當后衛(wèi)，

根據(jù)乘法法則，這種選取方案有：C；C；種；

(4)從B中選6個前鋒，從C中選1個前鋒，從A中選4個后衛(wèi)，

根據(jù)乘法法則，這種選取方案有：C；C；C；種；

(5)從B中選6個前鋒，從C中選1個前鋒，從A中選3個后衛(wèi)，C中剩

下的一個當后衛(wèi)，選取方案有：C；C；種；

(6)從B中選5個前鋒，C中2個當前鋒，從A中選4個后衛(wèi)，

選取方案有：C；種；

根據(jù)加法法則，總的方案數(shù)為：

c；或G+C：C；C；+C：C；+C；=1400

7.求0-〉-22+卬)8展開式中x2y2z2w2項的系數(shù)。

解:令a=x,b=-y,c=-2z,d=w,則(a+b+c+d)8中a262c方2項的系數(shù)為

f8]=—————,即(x-y-2z+w)8中，》2(-)，)2(-2[)2卬2的系數(shù),

[2222J2!2!2!2!2

因此，x2y2z2yp2的系數(shù)為：7!/2(-(-2)2=10080。

8.求(x+y+z)，的展開式。

解:〃=4/=3,展開式共有RC3,4)=C(4+3-1,4)=15(項),所以,

'4、4、4'4、4、

(x+y+z)4x4+/+z4+x?+

、400040004,310301

777

\

'4、44\

+x2y2+X2z2+

202

、2202117

\\

444、49

+xy3+xz3+型2+孫~z

130II103112,121

\

4、4'4、

3322

+yz+yz+yz

<022,

01371031J

=x"+y4+z4+4x3y+4xyz++4xz3+4yz3+4y3z

+6x2y2+6x2z2+6y2z2+12x2yz+12xyz2+12xy2z

9.求(X]+￡+*3+X4+無5嚴展開式中9/X：的系數(shù)。

(10、10!

解:X"/的系數(shù)為:103160,=840

3!1!6!

10.試證任一整數(shù)n可唯一表示成如下形式：

n=!,0<ai<i,i=

證明：(1)可表示性。

令M={(??,_I，??,_2,</,?,=1,2,???,/?-1}?顯然|M=m!,

N={0,1,2,…，根!—1},顯然網(wǎng)=機！，

定義函數(shù)/：MfN,

/(??,_1,%”2，…,4，4)=?,?-1(〃?-1)!+限(加-2)!+…+%2!+q1!,

0=0(m一1)!+0(〃？-2)!+…+02!+01!

am!+a

顯然-m-\(-i)m-2(/?/-2)!+???+a22!+q1!

""'、'<(m-l)(w-l)!+(m-2)(7?t-2)!+---+22!+l1!

=m!-(m-1)!+(m-1)!一(m-2)!+???+3!一2!+2!一1!=m!-1

BPO</（??,_1,am_2%,q）Vm!-1,

由于f是用普通乘法和普通加法所定義的，故f無歧義，肯定是一個函數(shù)。

從而必有一確定的數(shù)K（0WK4機!-1）,使得K=/（《…。吁2,…，%嗎），

為了證明N中的任一數(shù)n均可表示成〃=，>/!的形式，

?>|

只需證明f是滿射函數(shù)即可。又因為f是定義在兩個有限且基數(shù)相等的函

數(shù)上，因此如果能證明f單射，則f必是滿射。

假設f不是單射，則存在（*4-2,…，。2，。1），（想-1也-2,…也，仇）GM,

（?,?.1,am_2,---,a2,ax）^（bm_vbm_2,---,b2,b^,且有K。eN,使得

Ko=f（%'am-2」??，/，卬）=/S,“T4一2，…也，仇）

由于（4_14_2,…,。2，%）*（超-1也-2,…也,仇），故必存在機-1，使得

a產(chǎn)電。不妨設這個j是第一個使之不相等的，即生=〃.（i=〃zT,…,/+1）,

a產(chǎn)電旦\<電,

因為a”-i（加一1）!+《"-2（”-2）!d----\-a22!+q1!

9=6,,1（加一1）!+想_2（加-2）!+…+仇2!+&,1;

0=也"〃?一1)!+想-2(用一2)!+…+&2!+&,1!]

-[o?,_i(〃?-1)!+。,“_2(加一2)!-1----F々2!+q1!]

=(bj-aj)j!+(bj_t-)(j—1)!-+-----+-(b2-a2)2!+(1一q)1!

所以，.',....-]

na

-~j-\\-----H|/?2-a2\2!+|仇_.|llj

>j!-[(J-D(J-l)!+-+22!+l1!]

=j!-O!-D=l

產(chǎn)生矛盾，所以f必是單射函數(shù)。

因為IM=W=加，所以f必然也是滿射函數(shù),

故對任意的〃eN,都存在…，%，%)€〃，使得

n=am_t(m-1)!+am_2(m-2)l+-"+a22!+.1!

這說明對任意的整數(shù)，都可以表示成〃=Zqi!的形式。

/>1

(2)唯一性。

由于函數(shù)廣MfN是一個單射，也是滿射，即f是雙射函數(shù)，

故，對任意的〃wN,都存在唯一的(a,.”。吁2,…，%，。1)€加，使得

n=(m-1)!+am_2(m-2)!+—Fg2!+q1!□

否則，若存在另一個(〃“T，也廣2,…也，仇)e"，使得

?=^,,,-1(w-1)1+bm_2(m-2)!+??■+&22!+41!

將與f是單射函數(shù)矛盾。證畢。

11.證明〃。(〃-1,「)=(r+1)。(〃,r+1),并給出組合意義。

證明：因為。(〃水)。(女,/)=。(〃,/)。(〃一/歡一/),現(xiàn)令％=r+l,/=1,則可得

C(n,r+l)C(r+1,1)=C(n,l)C(n-l,r),BPnC(n-1,r)=(r+l)C(n,r+l)

組合意義：將n個元素分為3堆，1堆1個元素，1堆r個元素，1堆〃個

元素?？梢杂邢旅鎯煞N不同的分法：

(1)先從n個元素中選出r+1個元素，剩下的〃—-1個作為1堆；再將

選出的「+1個元素分為兩堆，1堆1個，1堆r個。

(2)先從n個元素中選出1人作為1堆，再從剩下的〃-1個中選出r個作

為1堆，剩下的〃-廠-1作為1堆。

顯然，兩種分法是等價的，所以等式成立。

12.證明￡紀(小攵)=〃21。

k=l

證明：采用殊途同歸法。

?組合意義一：

考慮從n個人中選出1名正式代表和若干名列席代表的選法(列席代表人數(shù)

不限，可以為0)?？梢杂幸韵聝煞N不同的選法：

(1)先選定正式代表，有C：=〃種選法;然后從1人中選列席代表，這“-1

個人都有選和不選的兩種狀態(tài)，共有2"T種選法；

根據(jù)乘法法則，共有〃2,T種選法；

(2)可以先選出k+l(k=0,l,2,…，〃-1)人，然后再從中選出1名正式代表,

其余k人作為列席代表，對于每個k,這樣的選法有：

從而總選法有：￡c(〃#+1)C(A+1,1)=fC(〃,A)C(A,1)=NkC(〃,k)

k=0k=\k=l

顯然，兩種選法是等價的，所以等式成立。

?組合意義二：

將n個不同的球放入標號為A、B、C的3個盒子，其中要求A盒只放1個

球，其余兩盒的球數(shù)不限。那么，有兩種不同的放法：

(1)先從n個不同的球中選出1個，放入A盒，再將其余〃-1個球放入另

外兩盒，有C：2"T=〃2"T種放法；

(2)先從n個球中選出k個伙=1,2,…,〃)，再從所選的k個球中選出1個

放入A盒，將其余的人-1個球放入B盒，剩下的〃-女個球放入C盒,

根據(jù)乘法法則，對于不同的k,有C：C：C：［：=kC：種放法。

當左=1,2,…,〃時，各種情況互不重復，且包含了所有放法，

根據(jù)加法法則，總的放法有：￡kC(〃,k)。

k=l

顯然兩種放法是等價的，故等式成立。

?另法：

根據(jù)二項式定理：

(1+x)"=1+C(/z,l)x+C(H,2)x24--1-C(n,n—V)x"^'+C(n,?)xn,

兩邊求導，得：

n(l+x)i=C(〃,1)+2C(n,2)x+…+(〃-1)C(〃,n-\)xn-2+nC(n,n)x"'',

令x=l,即得ZkC(〃，k)="2"T

%=i

13.有n個不同的整數(shù)，從中取出兩組來，要求第一組數(shù)里的最小數(shù)大于第二組

的最大數(shù)，問有多少種方案？

解：設這n個不同的數(shù)為q<g<…〈4，

若假定第一組取匕個數(shù)，第二組取心個數(shù)，并且令機=匕+心(血22),

則要求第一組數(shù)里的最小數(shù)大于第二組里的最大數(shù)，我們可以這樣來選：

先從n個數(shù)中任選m個數(shù)出來，有C(〃,⑼種選法；再從這m個數(shù)中從大到

小取占個數(shù)作為第一組數(shù)，匕=1,2,…有機-1種取法；再將其余的心個

數(shù)作為第二組數(shù)。

故總方案數(shù)有：宮2網(wǎng)?、统?M

=〃2"T-〃一(2"-—1)=(〃-2)2"T+1

14.六個引擎分列兩排，要求引擎的點火次序兩排交錯開來，試求從某一特定引

擎開始點火有多少種方案？

解：第一次點火僅有一種選擇，即點某個特定引擎的火；第二次點另一組某個引

擎的火，有三種選擇；第三次有2種,……0

所以方案數(shù)為：1x3x2x2x1x1=12(種)

?如果只指定從第一排先開始點火，不指定某一個，則方案數(shù)為

3x3x2x2x1x1=36(種)

?如果第一個引擎任意選，只要求點火過程是交錯的，則方案數(shù)為

6x3x2x2x1x1=72(種)

15.試求從1至I」1000000的整數(shù)中，0出現(xiàn)了兒次？

解：分別計算0出現(xiàn)在各個位上的次數(shù)。

(1)0出現(xiàn)在個位，此時符合條件的2位數(shù)有9個；3位數(shù)有9X10個；

4位數(shù)有9x102個；5位數(shù)有9x103個；6位數(shù)有9xl()4個；

(2)0出現(xiàn)在十位，此時符合條件的3位數(shù)有9x10個；4位數(shù)有9x10?個；

5位數(shù)有9xK)3個;6位數(shù)有9x10**個；

(3)0出現(xiàn)在百位，此時符合條件的4位數(shù)有9x102個；5位數(shù)有9x103個；

6位數(shù)有9xl(y1個；

(4)0出現(xiàn)在千位，此時符合條件的5位數(shù)有9xl()3個；6位數(shù)有9x10,個；

(5)0出現(xiàn)在萬位，此時符合條件的6位數(shù)有9x1(/個；

另外1000000中有6個0。

所以，從1至IJ1000000的整數(shù)中，0出現(xiàn)的次數(shù)總共有：

9+2X9X10+3X9X102+4X9X103+5X9X104+6=488895(次)

?另法：

先不考慮1000000本身，那么任一個000000-999999之間的數(shù)都可以表

示成如下形式：44d6,其中每個4是0到9的數(shù)字。

因為每位數(shù)字可以有10種選擇，根據(jù)乘法法則，共有IO,個“6位數(shù)”，

又每個“6位數(shù)”由6個數(shù)字組成(包括無效0),所以共有6xl(r個數(shù)字，

又每個數(shù)字出現(xiàn)的概率相等，所以0出現(xiàn)的次數(shù)應是6x105,

但習慣上在計算0的個數(shù)時，不包括無效0(即高位的0),因而要從中去掉

無效0,其中：(1)1位數(shù)有9個(不包括0),其無效0共有5x9個(即000004)；

(2)2位數(shù)有90個，其無效0共4x90個。

依次類推，無效。的總數(shù)為

5x9+4x90+3x900+2x9000+1x90000=111105

因為4d2d3d44d6全為。時的6個0和1000000本身的6個0相互抵消，

所以1至I」1000000之間的自然數(shù)中0出現(xiàn)的次數(shù)為

6xl05-111105=488895(次)

?注意：1出現(xiàn)的次數(shù)為6x105+1(要考慮1oooooo這個數(shù)的首位1),

2,3,9各自出現(xiàn)的次數(shù)為6x10、

16.n個男n個女排成一男女相間的隊伍，試問有多少種不同的方案？

若圍成一圓桌坐下，又有多少種不同的方案？

解：排成男女相間的隊伍：

先將n個男的排成1行，共有療種排法；

再將n個女的往n個空里插，有耳種排法；由于可以先男后女，也可以先

女后男，因此共有2笈種排法；

根據(jù)乘法法則，男女相間的隊伍共有：2P：歲=2〃!〃!種方案。

若圍成一圓周坐下，同理

先將n個男的圍成一圓周，共有種排法，

再將n個女的往n個空中插，有斤種排法，

根據(jù)乘法法則，圍成圓周坐下，總的方案數(shù)有：邛=〃!(“-1)!種。

17.n個完全一樣的球，放到r個有標志的盒子，〃Nr,要求無一空盒，

(〃一D

試證其方案數(shù)為o

V

證明：因為沒有空盒，可先每盒放入一個球，再將剩余的〃-/■球放入r個盒子中，

即將〃-廠個無區(qū)別的球，放入r個不同的盒子中，每盒的球數(shù)不受限制，

因此方案數(shù)有：C(r+n-r-l,n-r)-C(n-l,n-r)-C(/i-l,r-l)□

?另法：插空法。

問題可看為：n個球排成1行，球與球之間形成”-1個空，再在這〃-1個空

中，插入，-1個隔板，這樣就可形成r個盒子，每盒球不空的方案，其方案

數(shù)為C(〃—1,r—1)。

18.設"=pf'p]…，p”P2,…,p*是k個素數(shù),

試求能整除盡數(shù)n的正整數(shù)數(shù)目。

解：能整除數(shù)n的正整數(shù)即n的正約數(shù)，其個數(shù)為：

Q+l)((z2+1)■,,(%+1)o

19.試求n個完全一樣的骰子能擲出多少種不同的方案？

解：每個骰子有六個面，每個面的點數(shù)可以是1,2,…,6中的一種。

由于n個骰子完全一樣，故這樣相當于將n個完全一樣的球放到6個不同的

盒子中，每盒球數(shù)不限。故方案數(shù)有

C(n+6-1,")=C(〃+5,5)=—(n+5)(n+4)(〃+3)(n+2)("+1)(種)

20.凸十邊形的任意三個對角線不共點，試求這凸十邊形的對角線交于多少個

點？乂把所有的對角線分割成多少段?

(1)從一個頂點可引出7條對角線，這7條

對角線和其他頂點引出的對角線的交點情況

如下：從右到左，和第一條對角線的交點有：

17個，和第二條的交點有26,和第三條的

交點有35條，…，故和一個頂點引出的7條

線相交的點為：

17+26+35+44+53+62+71=84,

故和從10點引出的對角線交的點有84x10=840個，但每個點重復了四次(因為

每個點在兩條線上，而每條線又有兩個端點)，故凸十邊形對角線交于

840/4=210個點。

?也可以直接這樣看：

因為一個交點需要兩條對角線相交，而兩條對角線又需要多邊形的四個點構

成一四邊形。反之，從n個頂點中任取四個頂點，連成一四邊形，而四邊形的兩

條對角線必須確定唯一的一個交點，故凸十邊形的對角線的交點共有：

。［=210(個)

(前提：任三個對角線不共點，否則，一個交點不能對應n邊形的唯一四個頂點)

(2)由(1)知，一個點引出的7條對角線中，第一條線上有7個點，故將該線

段分成8段；第二條線上有12個點，故將該線段分成13段，…，故從一個點出

發(fā)的7條線上的段數(shù)為：8+13+16+17+16+13+8=910

現(xiàn)有10個點。故總的段數(shù)為：91x10=910。但每段重復計算了2次(因

為每條線有2個端點)故總的段數(shù)應為：910/2=455o

?另法：

一個交點給相交的兩條對角線各增加1段，所以對角線總的段數(shù)為：

對角線數(shù)+2倍交點數(shù)=1。。。-3)+2x210=455(段)

2

21.試證一整數(shù)n是另一整數(shù)的平方的充要條件是除盡n的正整數(shù)的數(shù)目為奇數(shù)。

證明：必要性：整數(shù)n可表示為〃=p："p￡…p；?,Pi<n,且p,為素數(shù)，a,.>1,

則除盡n的正整數(shù)個數(shù)為：(％+1)(4+1)…(4+1)，

若(q+1)(.+1)…(％+1)為偶數(shù)，則必存在?為奇數(shù)，

則n不可能寫成令一個數(shù)的平方。

所以n是另一整數(shù)的平方的必要條件是除盡n的正整數(shù)數(shù)目為奇數(shù)。

充分性：若除盡n的正整數(shù)的數(shù)目為奇數(shù)，則/(i=l,2,…,幻均為偶數(shù)，

2包2”2組(色竺組、2

則〃=P；E2…PF=P；2P；2…Pk2=p；p/-邛/

\7

可寫成另一整數(shù)的平方。證畢。

22.統(tǒng)計力學需要計算r個質點放到n個盒子里去，并分別服從下列假定之一，

問有多少種不同的圖像？假設盒子始終是不同的。

(1)Maxwell-Boltzmann假定：r個質點是不同的，任何盒子可以放任意個;

(2)Bose-Einstein假定：r個質點完全相同，每一個盒子可以放任意個。

(3)Fermi-Dirac假定：r個質點都完全相同，每盒不得超過一個。

解：(1)問題即：將r個不同的質點放到n個不同的盒子，每個盒子放的質點數(shù)

不受限制，即相異元素允許重復排列，其方案數(shù)有：

RP(oo,r)=nr

(2)問題即：將r個沒有區(qū)別的質點放到n個不同的盒子，每個盒子方的質

點數(shù)不受限制，即相異元素允許重復組合，其方案數(shù)有：

7?C(oo,r)=C(?+r-l,r)=.(”,二■

r!(n-l)!

(3)問題即：將r個沒有區(qū)別的質點放到n個不同的盒子，每盒不超過一個,

即相異元素不允許重復的組合，其方案數(shù)有：

n!

C(〃,r)=

r!(?-r)!

23.從26個英文字母中取出6個字母組成一字，若其中有2或3個母音,

問分別可構成多少個字(不允許重復)？

解：母音指元音，即a,e,i,o,u

(1)有2個元音。先從5個元音中取出2個，再從剩下的21個字母中選出

4個，再將6個字母進行全排列，則可構成的字總共有：

—=43092000(個)

(2)有3個元音。先從5個元音中取出3個，再從剩下的21個字母中選出

4個，再將6個字母進行全排列，則可構成的字總共有：

C；《E=9567000(個)

伊-2]q+2、(n

24.給出(-212,+???+

的組合意義。

證明:

?組合意義一：

從伽+尸+1)個元素｛1,2,…,n+r+1｝中取出(〃+r+l-用)個元素的組合數(shù)為：

C(n+r+l,n+r+l-m)=C(w+r+l,/n),JzLz,<z2<???<<zr+1<<??<in+r+i_m>其中

第r+1位置上的元素ir+i可取r+1,r+2,…,r+l+〃z，

當心取(r+l+幻時(1=0,1,…,加)，前邊的r個數(shù).2,…兒可在

(1,2,…,r+1+(%-1)｝這廠+々個數(shù)中取，故有/+]=-+]種取法；后邊的

Ir)<k)

[(n+r+l-m)-(r+l)]=n-m個數(shù)i心心,…，匕+川.,“可在｛r+1+k+l,…，〃+廠+1｝

這[(〃+「+1)一(r+1+幻]="一女個數(shù)中取，故有一一”〕=("一"】種取法。

^n-m)-KJ

根據(jù)乘法法則，當Q=r+1+女時，這樣的組合數(shù)為:

再根據(jù)加法法則，對％=0,1,…,冽進行求和，就有

?組合意義二：(格路方法)

等式左端：從點A(-廠-1,0)到點。(-1,%)(k=0,1,…，加)，直接經(jīng)過點。(0,4)

再到點8（〃-風團）的路徑數(shù)。

l-(-r-l)+k-Q}(r+k''

從A到C的路徑數(shù)為:

k一°,I，

n-m-Q+m—k(n-k

從D到B的路徑數(shù)為:

、m-k^m-k

mr+&丫n-k^

根據(jù)乘法法則和加法法則，從A到B的路徑數(shù)有:E

k=0\k)\m-k)

等式右端：從點A（-r-l,O）到點3（〃-加,m）的路徑數(shù)為:

，〃一小_r_1)+m_0、G+r+1、

、m-0)<m)

/、

〉+1]+卜+2nn+\

25.給出4-+…+的組合意義。

r+17

證明：（1）等式右端:從w+l個元素…,中，任選r+l個元素的組合

〃+1、

方案數(shù)為:

r+17

(2)等式左端:從"+1不同元素…，中選取r+1個元素，一定

選元素%+*+|伏=0,1,2,-一,〃-7）,但不選元素

%+4+2/-，%，4+1的方案數(shù)。根據(jù)乘法法則，當k值取定時,

這樣的方案數(shù)為從其余的〃+攵個元素中任取r個的方案

r+k\+八

數(shù)，即，再根據(jù)加法法則，總的方案數(shù)有：X

k=0\17

\、

m‘〃2、m-n

26.證明++…+二2〃

0\n)3n-17nJ07\nJ

證明：考慮從m雙互不相同的鞋中取出n只，〃6加，要求其中沒有任何兩只是

成對的，求方案數(shù)。

一方面，先從m雙鞋中選取n雙，共有m種選法，再從此n雙中每雙

抽掉一只，有2"種取法，由乘法原理，總的方案數(shù)為：2","、

另一方面，先取出左(％=0,1,…只左腳的鞋，再在其余的機-女雙中取出

〃-女只右腳的鞋，則總的方案數(shù)為:

所以,2"

nJ

?另法:

(?>r)(r=0,1,2,???,//)

從而有:

'〃、

++???+

\nJ。

27.對于給定的正整數(shù)n,證明在所有C(〃,r)(r=l,2,…中，當

k=<22時，C(",r)取得最大值。

-，〃為偶數(shù)

12

證明：取c(〃,口與c("?-1)進行比較。C=巴9,

C(n,k-l)k

當々(四時，n~k+l>i,即C(〃,Z)>C(〃,A—1),

2k

當—>巴時,n~k+i<1,即C(〃,A)<C(〃,A—1),

2k

因此，只有當上=2或最接近四時，C(〃,外取得最大值。

22

28.⑴用組合方法證明甯和普都是整數(shù)。

(2)證明”?是整數(shù)。

(加嚴

證明：(1)考慮2〃個有區(qū)別的球放入n個不同的盒子里，每盒兩個，盒中球不

(2/?)!(2/7)!

計順序，則方案數(shù)為:

2!2!…2!一2"

方案數(shù)是整數(shù)，所以印是整數(shù)。

2"

同理，考慮3〃個有區(qū)別的球放入n個不同的盒子里，每盒3個，盒

中球不計順，則方案數(shù)為：丁粵二=瞿7，

3!3!…3!2"3"

方案數(shù)是整數(shù)，所以舞是整數(shù)。

(2)考慮〃2個不同的球放入n個相同的盒子，每盒n個，盒中球不計順

序的方案。

先假設盒子是不同的，則這樣的方案數(shù)為：一生2!一="，

n\九！…n\(〃!)

、_____V______j

”個

又盒子是相同的，所以方案數(shù)應為：

(〃!)"(n!)(加嚴

方案數(shù)必然是整數(shù)，所以竺^是整數(shù)。

(加嚴

29.(1)在2n個球中，有n個相同，求從這2n個球中選取n個的方案數(shù)。

(2)在3〃+1個球中，有n個相同，求從這3〃+1個球中選取n個的方案數(shù)。

解：(1)問題即：從集合S={〃61,62」一,6",〃+|}中，選取n個的方案數(shù)，

即多項式(1+X+/+…+x")(l+x)"中x"的系數(shù)，即

1XC：+1XC：I+…+lxC：=2"

從這2n個球中選取n個的方案數(shù)為2"種。

(2)問題即:從集合S={〃qg，…，62.，02.+1，02.+2}中，選取n個的方案數(shù)，

即多項式（1+X+/+…+X"）（1+x）2n+l中X"的系數(shù)，即

1X%+1XC；匕+…+1X匾=￡C222n+l/2=4"

1=0

30.證明在由字母表｛0,1,2｝生成的長度為n的字符串中，

（1）0出現(xiàn)偶數(shù)次的字符串有“匚個；

2

（2）（［才+廠、"<+…+『］2"-"=^L其中4=21|。

［2）yq）212」

證明：（1）采用數(shù)學歸納法

當〃=1時，0出現(xiàn)偶數(shù)次（0次），長度為1的字符串為“1”和“2”

1

兩個字符串，而3±4把-1=2,故結論成立。

2

假設當”=女（221）時，結論成立，

即0出現(xiàn)偶數(shù)次，長度為k的字符串有上個，

2

當〃=左+1時，0出現(xiàn)偶數(shù)次，長度為Z+1的字符串包括兩部分：

①在0出現(xiàn)偶數(shù)次，長度為k的字符串后面再增加一位不是0的數(shù)

（只能是1或2）,因此，這樣的字符串有2、二=中+1個。

2

②給0出現(xiàn)奇數(shù)次，長度為k的字符串后面再增加一個0,

因此，這樣的字符串有：3*-士±=2二。

、2J2

根據(jù)加法法則，0出現(xiàn)偶數(shù)次，長度為&+1的字符串共有：

_1*+/?1

3*+1+--=-----,即”=女+1時，結論也成立。

22

所以，根據(jù)數(shù)學歸納法，結論成立。

（2）由（1）知，右端表示0出現(xiàn)偶數(shù)次的字符串數(shù)。

而左端代表的組合問題是：

長度為n的字符串中，有0個。的字符串數(shù)有：2”,

H

有2個0的字符串數(shù)有：2"<,

有q個0的字符串數(shù)有：("上…,

根據(jù)加法法則，可知，左端代表的是長度為n的字符串中0出現(xiàn)偶數(shù)次

的字符串數(shù)，、因此

n〃、3"+1

2"+2"-2+---+2n~q

,0722

31.5臺教學儀器供m個學生使用，要求使用第1臺和第2臺的人數(shù)相等，

有多少種分配方案？

解：

?方法一：

先從m個學生中選取k個使用第1臺機器，再從剩下的m-左個學生中選取

k個使用第2臺機器，其余m-2k個學生可以任意使用剩下的3臺機器，

按乘法原理，其組合數(shù)為(用丫用：

3吁23這里％=0,1,2,(q=3),

"人k

于是,按加法原理，共有￡,,3'"3種使用方案。

八"，

?方法二：

先從m個學生種選出2k個，再將選出2k個學生平均分到1、2臺機器上,

其余的機-2%個學生可以任意使用剩下的3臺機器，

按乘法法則，其組合數(shù)為佇丫%]3小山，這里女=0,l,2,...q(q=依)

_q(/17\(7k、

于是，按加法原理，共有X3"-2*種使用方案。

我=o12攵八k/

32.由n個0及n個1組成的字符串，其任意前k個字符中，0的個數(shù)不少于1

的個數(shù)的字符串有多少？

解：(參見P2L例1.8.8)轉化為格路問題。即從點(0,0)到(〃,〃)，只能從對角

線上方走，但可以碰到對角線的所有最短路徑數(shù)。顯然，第一步必然要走到

點(0,1),因此可以轉換為從點(0,1)至的所有滿足條件的路徑數(shù)，進一

步，可以轉換為從(0,1)點到+只能從對角線上方走，但不可以碰到

對角線的所有路徑數(shù)，因為從(0,1)點到(〃,〃+1)的所有經(jīng)過對角線的路徑數(shù)

與從(1,0)點到+點的所有路徑數(shù)是一一對應的，因此，所求的字符串

有：

0+(〃+1)-1］(〃-1+(〃+1)-01..zAX

-=C(2”,〃)一rC(n2〃,〃一l)(/|、)

I〃JIn~l)

?方法二：由n個1和n個0組成的2〃位二進制數(shù)共有雪個(2〃個不盡相

(〃!)

異元素的全排列)，

設所求的二進制數(shù)共有2個，不符合要求的數(shù)有乙個。而不合要求的數(shù)的特

征是從左向右掃描時，必然在某一位首次出現(xiàn)0的個數(shù)小于1的個數(shù)，即從左向

右累計到第2A+1位時出現(xiàn)攵個0和Z+1個1。此時，后2(〃-幻-1位上有4-1

個1,女個0。將后部分的0改寫為1,1改寫為0。結果整個數(shù)變成由〃+1個

和〃-1個0組成的2n位數(shù)zo即一個不合要求的數(shù)唯一對應于這樣的一個數(shù)zo

反之，給定一個由〃+1個1和"T個0組成的2〃位數(shù)z.由于1比0多2

個，故一定在某一位首次出現(xiàn)0的累計數(shù)少于1的累計數(shù)。依同法將此位后的0

與1互換，使z變成由〃個1和〃個0組成的2n位數(shù)。

所以，這兩種二進制數(shù)一一對應。即r.=7~(沙、

(2〃)!（2〃）?。?n）!_1（2n）!_

故b.---C（2n,n}o

談一（/T）!（〃+］）!="+］（加J=H+1