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

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

習(xí)題一(排列與組合)

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

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

方案數(shù)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

字中選2個(gè)進(jìn)行排列，共有4=56個(gè)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

各有多少種做法？

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

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

解：(1)因?yàn)榫妥怯写涡虻?，所有是排列問題。

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

剩下的5個(gè)人在其余座位的就坐方式有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

?典型錯(cuò)誤：

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

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

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

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

4.一位學(xué)者要在一周內(nèi)安排50個(gè)小時(shí)的工作時(shí)間，而且每天至少工作5小時(shí)，

問共有多少種安排方案？

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

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

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

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

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

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

?另解：

因?yàn)樵试S必=0,所以問題轉(zhuǎn)化為長(zhǎng)度為1的15條線段中間有14個(gè)空，再

加上前后兩個(gè)空，共16個(gè)空，在這16個(gè)空中放入6個(gè)“+”號(hào)，每個(gè)空放置的

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

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

21x20x19x18x17x16

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

6x5x4x3x2xl

即共有54264種安排方案。

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

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

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

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

也可能是“乙甲”；所以

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

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

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

有多少種選法？

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

則可分為以下幾種情況：

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

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

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

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

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

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

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

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

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

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

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

選取方案有：C；種；

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

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

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

解:令a=x,b=-y,c=-2z,d=w,則(a+b+c+d)8中a262c方2項(xiàng)的系數(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(項(xiàng)),所以,

'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嚴(yán)展開式中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)=機(jī)！，

定義函數(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無歧義，肯定是一個(gè)函數(shù)。

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

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

?>|

只需證明f是滿射函數(shù)即可。又因?yàn)閒是定義在兩個(gè)有限且基數(shù)相等的函

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

假設(shè)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,…也,仇），故必存在機(jī)-1，使得

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

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

因?yàn)閍”-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ù)。

因?yàn)镮M=W=加，所以f必然也是滿射函數(shù),

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

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

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

/>1

(2)唯一性。

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

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

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

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

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

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

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

證明：因?yàn)椤?〃水)。(女,/)=。(〃,/)。(〃一/歡一/),現(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個(gè)元素分為3堆，1堆1個(gè)元素，1堆r個(gè)元素，1堆〃個(gè)

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

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

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

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

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

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

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

k=l

證明：采用殊途同歸法。

?組合意義一：

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

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

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

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

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

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

其余k人作為列席代表，對(duì)于每個(gè)k,這樣的選法有：

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

k=0k=\k=l

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

?組合意義二：

將n個(gè)不同的球放入標(biāo)號(hào)為A、B、C的3個(gè)盒子，其中要求A盒只放1個(gè)

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

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

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

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

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

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

當(dāng)左=1,2,…,〃時(shí)，各種情況互不重復(fù)，且包含了所有放法，

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

k=l

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

?另法：

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

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

兩邊求導(dǎo)，得：

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個(gè)不同的整數(shù)，從中取出兩組來，要求第一組數(shù)里的最小數(shù)大于第二組

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

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

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

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

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

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

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

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

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

14.六個(gè)引擎分列兩排，要求引擎的點(diǎn)火次序兩排交錯(cuò)開來，試求從某一特定引

擎開始點(diǎn)火有多少種方案？

解：第一次點(diǎn)火僅有一種選擇，即點(diǎn)某個(gè)特定引擎的火；第二次點(diǎn)另一組某個(gè)引

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

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

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

3x3x2x2x1x1=36(種)

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

6x3x2x2x1x1=72(種)

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

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

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

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

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

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

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

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

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

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

另外1000000中有6個(gè)0。

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

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

?另法：

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

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

因?yàn)槊课粩?shù)字可以有10種選擇，根據(jù)乘法法則，共有IO,個(gè)“6位數(shù)”，

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

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

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

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

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

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

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

因?yàn)?d2d3d44d6全為。時(shí)的6個(gè)0和1000000本身的6個(gè)0相互抵消，

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

6xl05-111105=488895(次)

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

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

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

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

解：排成男女相間的隊(duì)伍：

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

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

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

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

若圍成一圓周坐下，同理

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

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

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

17.n個(gè)完全一樣的球，放到r個(gè)有標(biāo)志的盒子，〃Nr,要求無一空盒，

(〃一D

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

V

證明：因?yàn)闆]有空盒，可先每盒放入一個(gè)球，再將剩余的〃-/■球放入r個(gè)盒子中，

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

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

?另法：插空法。

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

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

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

18.設(shè)"=pf'p]…，p”P2,…,p*是k個(gè)素?cái)?shù),

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

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

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

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

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

由于n個(gè)骰子完全一樣，故這樣相當(dāng)于將n個(gè)完全一樣的球放到6個(gè)不同的

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

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

20.凸十邊形的任意三個(gè)對(duì)角線不共點(diǎn)，試求這凸十邊形的對(duì)角線交于多少個(gè)

點(diǎn)？乂把所有的對(duì)角線分割成多少段?

(1)從一個(gè)頂點(diǎn)可引出7條對(duì)角線，這7條

對(duì)角線和其他頂點(diǎn)引出的對(duì)角線的交點(diǎn)情況

如下：從右到左，和第一條對(duì)角線的交點(diǎn)有：

17個(gè)，和第二條的交點(diǎn)有26,和第三條的

交點(diǎn)有35條，…，故和一個(gè)頂點(diǎn)引出的7條

線相交的點(diǎn)為：

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

故和從10點(diǎn)引出的對(duì)角線交的點(diǎn)有84x10=840個(gè)，但每個(gè)點(diǎn)重復(fù)了四次(因?yàn)?/p>

每個(gè)點(diǎn)在兩條線上，而每條線又有兩個(gè)端點(diǎn))，故凸十邊形對(duì)角線交于

840/4=210個(gè)點(diǎn)。

?也可以直接這樣看：

因?yàn)橐粋€(gè)交點(diǎn)需要兩條對(duì)角線相交，而兩條對(duì)角線又需要多邊形的四個(gè)點(diǎn)構(gòu)

成一四邊形。反之，從n個(gè)頂點(diǎn)中任取四個(gè)頂點(diǎn)，連成一四邊形，而四邊形的兩

條對(duì)角線必須確定唯一的一個(gè)交點(diǎn)，故凸十邊形的對(duì)角線的交點(diǎn)共有：

。［=210(個(gè))

(前提：任三個(gè)對(duì)角線不共點(diǎn)，否則，一個(gè)交點(diǎn)不能對(duì)應(yīng)n邊形的唯一四個(gè)頂點(diǎn))

(2)由(1)知，一個(gè)點(diǎn)引出的7條對(duì)角線中，第一條線上有7個(gè)點(diǎn)，故將該線

段分成8段；第二條線上有12個(gè)點(diǎn)，故將該線段分成13段，…，故從一個(gè)點(diǎn)出

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

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

為每條線有2個(gè)端點(diǎn))故總的段數(shù)應(yīng)為：910/2=455o

?另法：

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

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

2

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

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

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

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

則n不可能寫成令一個(gè)數(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)計(jì)力學(xué)需要計(jì)算r個(gè)質(zhì)點(diǎn)放到n個(gè)盒子里去，并分別服從下列假定之一，

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

(1)Maxwell-Boltzmann假定：r個(gè)質(zhì)點(diǎn)是不同的，任何盒子可以放任意個(gè);

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

(3)Fermi-Dirac假定：r個(gè)質(zhì)點(diǎn)都完全相同，每盒不得超過一個(gè)。

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

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

RP(oo,r)=nr

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

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

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

r!(n-l)!

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

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

n!

C(〃,r)=

r!(?-r)!

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

問分別可構(gòu)成多少個(gè)字(不允許重復(fù))？

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

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

4個(gè)，再將6個(gè)字母進(jìn)行全排列，則可構(gòu)成的字總共有：

—=43092000(個(gè))

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

4個(gè)，再將6個(gè)字母進(jìn)行全排列，則可構(gòu)成的字總共有：

C；《E=9567000(個(gè))

伊-2]q+2、(n

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

的組合意義。

證明:

?組合意義一：

從伽+尸+1)個(gè)元素｛1,2,…,n+r+1｝中取出(〃+r+l-用)個(gè)元素的組合數(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，

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

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

Ir)<k)

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

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

^n-m)-KJ

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

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

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

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

再到點(diǎn)8（〃-風(fēng)團(tuán)）的路徑數(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)

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

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

、m-0)<m)

/、

〉+1]+卜+2nn+\

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

r+17

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

〃+1、

方案數(shù)為:

r+17

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

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

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

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

r+k\+八

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

k=0\17

\、

m‘〃2、m-n

26.證明++…+二2〃

0\n)3n-17nJ07\nJ

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

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

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

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

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

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

所以,2"

nJ

?另法:

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

從而有:

'〃、

++???+

\nJ。

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

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

-，〃為偶數(shù)

12

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

C(n,k-l)k

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

2k

當(dāng)—>巴時(shí),n~k+i<1,即C(〃,A)<C(〃,A—1),

2k

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

22

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

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

(加嚴(yán)

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

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

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

2!2!…2!一2"

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

2"

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

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

3!3!…3!2"3"

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

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

序的方案。

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

n\九！…n\(〃!)

、_____V______j

”個(gè)

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

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

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

(加嚴(yán)

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

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

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

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

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

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

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

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

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

1=0

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

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

2

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

［2）yq）212」

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

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

1

兩個(gè)字符串，而3±4把-1=2,故結(jié)論成立。

2

假設(shè)當(dāng)”=女（221）時(shí)，結(jié)論成立，

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

2

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

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

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

2

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

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

、2J2

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

_1*+/?1

3*+1+--=-----,即”=女+1時(shí)，結(jié)論也成立。

22

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

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

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

長(zhǎng)度為n的字符串中，有0個(gè)。的字符串?dāng)?shù)有：2”,

H

有2個(gè)0的字符串?dāng)?shù)有：2"<,

有q個(gè)0的字符串?dāng)?shù)有：("上…,

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

的字符串?dāng)?shù)，、因此

n〃、3"+1

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

,0722

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

有多少種分配方案？

解：

?方法一：

先從m個(gè)學(xué)生中選取k個(gè)使用第1臺(tái)機(jī)器，再從剩下的m-左個(gè)學(xué)生中選取

k個(gè)使用第2臺(tái)機(jī)器，其余m-2k個(gè)學(xué)生可以任意使用剩下的3臺(tái)機(jī)器，

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

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

"人k

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

八"，

?方法二：

先從m個(gè)學(xué)生種選出2k個(gè)，再將選出2k個(gè)學(xué)生平均分到1、2臺(tái)機(jī)器上,

其余的機(jī)-2%個(gè)學(xué)生可以任意使用剩下的3臺(tái)機(jī)器，

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

_q(/17\(7k、

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

我=o12攵八k/

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

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

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

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

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

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

對(duì)角線的所有路徑數(shù)，因?yàn)閺?0,1)點(diǎn)到(〃,〃+1)的所有經(jīng)過對(duì)角線的路徑數(shù)

與從(1,0)點(diǎn)到+點(diǎn)的所有路徑數(shù)是一一對(duì)應(yīng)的，因此，所求的字符串

有：

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

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

I〃JIn~l)

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

(〃!)

異元素的全排列)，

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

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

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

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

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

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

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

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

所以，這兩種二進(jìn)制數(shù)一一對(duì)應(yīng)。即r.=7~(沙、

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

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

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