組合數(shù)學(xué)第三版@習(xí)題答案

第1章排列與組合

經(jīng)過勘誤和調(diào)整，已經(jīng)消除了全部的文字錯誤，不過仍有以下幾個題目暫時沒有找到解

答：

1.8

1.9

1.16

1.41(答案略)

1.42(答案略)

1.1從｛1,2，…,50｝中找一雙數(shù)｛a,b｝,使其滿足：

⑷,一"=5;

(Z?)|a-i>|<5.

［解］(a)\a-b\=5

將上式分解，得到匕=+5

*

a-b--5

a=b-5,a=0時，b=5,6,7,…,50。滿足a=b-5的點共50-4=46個點.

a=b+5,a=5時,b=0,1,2,…,45。滿足a=b+5的點共45-0+1=46個點.

所以，共計2x46=92個點.

(b)|a-Z>|<5

(6+10)x5+11x(45—4)=16x5+11x41=531個點

O

1.25個女生，7個男生進行排列，

(a)若女生在一起有多少種不同的排列？

(b)女生兩兩不相鄰有多少種不同的排列？

(c)兩男生A和B之間正好有3個女生的排列是多少？

［解］(a)女生在一起當(dāng)作一個人，先排列，然后將女生重新排列。

(7+1)!X5!=8!X5!=40320X120=4838400

(b)先將男生排列有7!種方案，共有8個空隙，將5個女生插入，故需從8個空

中選5個空隙，有種選擇。將女生插入，有5!種方案。故按乘法原理，有：

7!XC：X5!=33868800(種)方案。

(c)先從5個女生中選3個女生放入A,B之間，有種方案，在讓3個女生

排列，有3!種排列，將這5個人看作一個人，再與其余7個人一塊排列，有

(7+1)1=8!

由于A,B可交換，如圖

**A***B**［或**B***A**

故按乘法原理，有：

2XC5X31X81=4838400(種)

1.3m個男生，n個女生，排成一行，其中m,n都是正整數(shù)，若

(a)男生不相鄰(mWn+1)；

(b)n個女生形成一個整床；

(c)男生A和女生B排在一起；

分別討論有多少種方案.

「"I

［解］(a)先將n個女生排列，有n!種方法，共有n+1個空隙，選出m個空隙，共有。用種

方法，再插入男生，有m!種方法，按乘法原理，有：

(〃+1)!叫〃+1)!

n!XC：1Xm!=n!XXm!=種方案。

m\{n+\-m)\(〃+1-/?)!

(b)n個女生形成一個整體，看作一個人，與m個男生做重排列，然后，n個女生內(nèi)部

再作排列，按乘法原理，有(m+1)!Xn!種方案。

(c)男生A和女生B排在一窟，看作一人，和其余n-1+m-1=n+m-2個人一起，作排列,

共有(n+m-2+1)=(n+m-1)!種方法,A,B兩人內(nèi)部交換,故有2X(n+m-1)!種方案。

1.426個英文字母進行排列，要求x和y之間有5個字母的排列數(shù).

［解］選入26—2=24個字母中選取5個字母，有種方法，5個字母內(nèi)部排列，有5!種

方案，再將X*****丫這7個字母看作?個，與其余19個合起來作排列，共有(19+1)!=20!種

方案，又因為X與丫可交換，故按乘法原理，有：

<241,______(24A24

2XC24X5!X20!=2XX5!X20!=40X24!240XJ2%x24——I

又因為：ln40+0.5(lg萬+Ig48)+24(lg24-lge)

=1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481)

=25.39325777

所以，結(jié)果為exl0”=2473i91664X10”

1.5求3000到8000之間的奇整數(shù)的數(shù)目，而且沒有相同的數(shù)字.

［解］3000~8000中各位不同的奇數(shù)，分類討論：

首位3,1X8X7X4(末位不能取3)

首位4,1X8X7X5(末位全取)

首位5,1X8X7X4

首位6,1X8X7X5

首位7,1X8X7X4

從而，由加法原理，得：

8X7X(4+5+4+5+4)=56X22=1232個。

1.6計算

lxl!+2x2!+3x3!+???+〃x〃！

［解］Ixl!+2x2!+3x3!d------F〃x〃!=(〃+1)!-1(參見p14)(”!-1=>,2x2!)

*=i

1.7試證

(〃+1)(〃+2)…(2〃)

被2n除盡.

，，、/?、八、(2〃)！(2〃)!!(2〃-1)!!2"-n!-(2n-l)!!…小八,,

［證］(〃+1)(/2+2)…(2〃)=-~--.........-=-------------------=2"(2n-1)!!

n\n\n\

故能被2"整除。

1.8求1()4°和2()3°的公因數(shù).

1.9試證1?的正除數(shù)的數(shù)目是奇數(shù).

1.10證明任-正整數(shù)n可惟一地表示成如下形式：

n=￡qi!,(0<aj<i,i>1)

i>i

[證].(1)可表示性：

令M={(a*i,am-2,…,。2,。1)：4族"i=l,2,…,m-1},顯然|M|=m!；

N={0,l,2,...,m!-l},顯然|N|=m!,其中m是大于n的彳壬意整數(shù)。

定義函數(shù)7:MfN

式%自小》2,…,42,。i)="m-i(m-l)!+am-2(m-1)!+…+/2!+m1!(*)

顯然，0=0(m-1)!+0(m-1)!+…+02!+0-1!

<am.i(m-l)!+am.2(rn-l)!+...+a22!+ai1!

<(m-l)(m-l)!+(m-2)(m-l)!+...+2-2!+l-1!

=m!-l(見PG

即0</(am-i,am-2....,a2,ai)<m!-1

由于f是用普通乘法和普通加法所定義的，故從而f無歧義。從而有一確定的數(shù)K

(0<K<m!-1)，使

,am-2,???,°2,0I)

為證N中的任一數(shù)均可表示成上邊(*)的形式，只要證明f是滿射函數(shù)即可。但由于在兩

相等且有限的集合上定義的函數(shù)，滿射性與單射性、雙射性是等價的，故只須證明f是單射

函數(shù)即可。

否則,設(shè)存在某數(shù)KoeN,有回一1國一2,...忿向)4％一14一2,...,出，)均屬于M,使

Ko-m-2,,,.,。2,“1)」」.K():1?.力2力I)

由于不相等，故必有某個j(wm-1),使不妨設(shè)這個j是第一個不使相等的，即

ai=bi(i=m-l,j+1),ajxbj且aj<bj,從而由

1)!+〃m-2(m-1)!+...+〃22!+al1!=bm-](m?l)!+/?m-2(m-1)!+...+/?22!+/?11!

就可有

(6廠apj!+(bj-i—i?j.])(j-1)什…+(3-。2)2!+(岳-。1)1!=0

但是

(!+(力-「町1)(j-+(bi-a2)2\+{bz-ai)l!

>(Aj-aj)j)!+...+\b2-a2\-2!+電-田|-1!]

=1

矛盾，這說明f是單射函數(shù)。

由于|M|=|N|=m!有限，故f是雙射函數(shù)，當(dāng)然是滿射函數(shù)，從而。到m!-1中的任何一個

數(shù)都可以表示成上邊(*)的形式。故，由nwN,都有回一1為一2,...在向)€1\/1,使得

n=ani.|(m-l)!+a,n-2(m-1)!+...+“22!+。11!

這就證明了任何n可表示成以上形式。

(2)唯一性：

用證明單射的方法，就可以證明表示法的唯性(表示方法見PR,留給讀者。

1.11證明刀(Cn-l,r)=(r+l)C(n,r+l),并給予組合解釋.

［證］.(參見P28(1-8-4))

(〃-1)!n\

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

r!(n-r-l)!(r+l)!(n-r-l)!

組合意義：(等式右邊)由n個元素中取出r+1個元素組合(有C(n,r+1)種)，再從每個

組合中取出1個(有r+1種)，全部結(jié)果為C(n,r+1)(r+1)o(等式左邊)由此所得的全部結(jié)

果相當(dāng)于從n個元素中直接取1個元素(有n種)，但有重復(fù)，其重復(fù)數(shù)等于剩下的n-1個

元素中取r個元素的組合C(n-1,r),故nC(n-1,r)=(r+1)C(n,r+1),

1.12試證等式：￡kCgk)=n2"T

k=i

［證］.證法一：根據(jù)二項式定理，(參見P29(1-8-5))

(1+x)"=1+C(n,1)x+C(n,2)f+…+x"

兩邊對X求導(dǎo)，有

n(l+x)n"=C(n,l)+2C(n,2)x+...+nx"'1

令x=1,即得￡kC(n,k)=n2"T。

k=l

證法二：

組合意義：設(shè)有n個不同的小球，并有A、B兩個合子，A合中恰好放入一個球，B合

中可放入任意多個球。有兩種放球方法：

(1)(等式左邊)先從n個球中選取k個，再從這k個球中任選一個放入A合，剩下的

k-1個球全部放入B合中，方案數(shù)共為/C(〃水)；

k=\

(2)(等式右邊)先從n個球中任選一個放入A合，剩下的n-1個球每個都有兩種可能，

要么放入B合，要么不放，方案數(shù)共為門2向；

顯然，兩種放球方法等效，兩種放球方案數(shù)相等，即之叱;(〃,女)=〃2"-|。

k=\

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

［解］設(shè)這n個不同的數(shù)為m1<m2<m3<■■■<mn。

若假定第一組取心個數(shù)，第二組取k2個數(shù)，并且令m=ki+k2(mz2),則要求第一組數(shù)

里的最小數(shù)大于第二組的最大數(shù)，我們只要先從上邊那n個數(shù)中任選m個數(shù)(有C(n,m)種選

法)，再從這m個數(shù)中從大到小取發(fā)個數(shù)作為第―組數(shù)(有k『1,2,…,m-1共m-1種取法)，

將其余k2個數(shù)作為第二組數(shù)，即可。故總方案數(shù)為

W(〃?-1)C(”,M=(〃-2)2"T+1(參見第3題等式)。

in=2

1.146個引擎分列兩排，要求引擎的點火順序兩排交錯開來，試求從特定一引擎開始有多少

種方案？

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

三種選擇；第三次有2種,……o

即方案數(shù)為1-3-2-2-1-1=12o

1.15試求從1到1000000的整數(shù)中,0出現(xiàn)的次數(shù).

［解］(參見P8)從1至11000000的整數(shù)中，0出現(xiàn)的次數(shù)相當(dāng)于10-99,100-999,1000-9999,

10000-99999,100000-999999,以及1000000中的0的個數(shù)。

10-99中的零的個數(shù)為：9

100-999中的零的個數(shù)為：2x9+9x9+9x9=18+81+81=180

位為零，

故對百位

的每?種

取法，有

兩個零

1000-9999中的零的個數(shù)為：3x9+2xC；x9x9+C；x9x9x9

有三位為零,有兩.為學(xué)''有一技為零’

=27+486+2187

=2700

10000-99999中的零的個數(shù)為：

4x9+3xC：x9x9+2xC：x9x9x9+C；x9x9x9x9

有四位零,一有三次零一''有Bit零''有一:位零'

=36+972+8748+26244

=36000

100000-99999中的零的個數(shù)為：

5x9+4xC；x9x9+3xC：x9x9x9+2xC：x9x9x9x9+C；x9x9x9x9x9

有五位零有四位零有三位零有二位零有一位零

=45+1620+21870+131220+295245

=450000

1,000,000中的。的個數(shù)為：6

故1到1,000,000的整數(shù)中0的個數(shù)為：

9+180+2700+36000+450000+6=488895。

l16n個完全一樣的球放到r個有標(biāo)志的盒(n》r)中，無一空盒，試問有多少種方案？

闕

lJ7n和r都是正整數(shù)，而且rWn,試證下列等式：

(4)/=叱二：

(〃-廠+1)成

(c)E'=——P；-',r<n

n-r

=r!+r(P^+P^+-+P：_x)

[解](a)方法一

及1

P：=-——=+

(n-r)l

=n{n-1)???[?-1-(r-1)+1]

(〃—1)!

=n------------------

[(?-D-(r-l)+l]!

=〃/

方法二(組合意義)

等式左邊：從n個元素種取r個元素做排列有年種，就是等式左邊：

等式右邊：先從n個元素中拿出一個元素排在首位，有n種方法，然后再從剩下的n-1

個元素中取r-1個元素做后面r-1位的排列，有尸二：種方法，按乘法原理，共有n匕二種方

法。

(b)方法一

幾I

P；=———=n(n-l)---(?-r+2)(H-r+l)

(〃一r)!

=(〃-r+1)?n(n-1)…[〃一(r-1)+1]

n\

=(〃一r+1)

[n-(r-l)]!

=(〃-/?+DEL

方法二(組合意義法)

等式左邊：從n個元素中取r個元素做r位排列，有尸；種方案。

等式右邊:先從n個元素中取r-1個元素做r-1位排歹U，有P；.種方法;再從剩下的n-r+1

個元素中取1個元素，共有n?r+1種選法，按乘法原理，共有(〃-r+1)尸二

(c)方法一

〃！

=-----:-=A2(z2-l)---(/2-r+2)(n-r+l)

(n-r)!

n

------(九一1)???—r+2)(〃-r+2)(〃-r+l)(Ai-r)

n-r

n

=——(”l)???(〃f+1)[(〃一1)_r+1]

n-r

n(n-1)!

n-r[(n-l)-r]!

=」-年t

n-r

方法二：(組合意義法)

等式左邊：從n個元素中取r個元素做r位排列，其方案數(shù)為尸：；

等式右邊：從n個元素中先取出一個元素放在第一位，有n種方法，再從剩下的n-1

個元素種取出r個元素放在第2位，…，第r位，第r+1位，有/二種方法，這樣就多了一

位，故應(yīng)除去第r+1位的選取方法，共有n-r種選法，故總方案為——P；"'.

n-r

(d)方法一

P"+'=J"：",=(〃+1)〃…-r+2)

(n+1-r)!

=[(n-r+1)+r}n???(7/-r+2)

=〃???(〃-r+2)(〃一r+1)+r一(r一1)+1]

n\r-n\

=------------1-----------------

(n-r)l(n-r+1)1

="回

方法二：(組合意義)

等式左邊：從n+1個不同的元素中取r個元素進行r位排列。其方案為片向；

等式右邊：(a)不取某特定元素b,則r個元素需從剩下的n個元素中取，然后做r位

排列，共有年種方案。

(b)取定某特定元素b,則其余r-1個元素需從剩下的n個元素中取，先做r-1位排列，

共有種方法，再將特定元素b插入這r-1個元素形成的r個空隙中，有r種方法，故按

乘法原理，共有rP：種方案。

(e)方法一(根據(jù)(d)可得)

P；+'=P；+rP；-

=邛7+叱1+叱。

^pn-2+rpn-2+rp^+rp^

^pn-2+rpn：2+rpn：\+rp^

=P；+rP：_,+rP；^+…+吃：：+r%

=r!+r(%+?.”：+%)

=r!+NE"哨+???+*巴

方法二：組合意義(同樣根據(jù)d)

等式左邊：從n+1個不同元素取r個元素做r位排列，其方案數(shù)為：P；山

等式右邊：設(shè)々為2，/，…為"+j是n-r+1個特定元素。

(a)不取特定元素仇力2，/，…也,+j，剩下的r個元素做全排列，有P,'=r!種方案。

(b)(1)：取特定元素4,但不取特定元素外力3,…力計?，于是先在剩下的r個元素中

取r-1個元素做排列，有P二種方法，然后將仇插入這r-1個元素的r個空隙，共有r種方

法，故按乘法原理，有rP二種方案。

(2)：取特定元素A，但不取特定元素…為“+~,于是先在剩下的r+1個元素中取r-1

個元素做排列，有匕1種方法，然后，將仇插入這r-1個元素的r個空隙，共有r種方法，

故按乘法原理，有rP二?種方案。

(n-r)：取特定元素々，但不取特定元素2+?，于是先在剩下的n-1個元素中取r-1個

元素做排列，有匕1種方法，然后，將仇插入這r-1個元素的r個空隙，共有r種方法，故

按乘法原理，有r/V?種方案。

(n-r+1)：取特定元素瓦,先在剩下的n個元素中取r-1個元素做排列，有種方法,

然后，將仇插入這r-1個元素的r個空隙，共有r種方法，故按乘法原理，有「尸二種方案。

最后，按加法原理，共有：

r!+r(磯+E才+???+/)

L188個盒子排成一列，5個有標(biāo)志的球放到盒子中，每盒最多放一個球，要求空盒不相鄰,

間有多少種排列方案？

［解］先將5個球進行全排列，有5!種方法，再將三個空格插入5個球的6個空隙中，有°；

種方法，然后將這/〃〃//〃〃〃〃/〃〃/〃/////////////〃//〃〃〃/〃〃〃〃〃元素的排列一對一的放入8個盒子

中，即完成了每盒最多一球，空盒不相鄰的放球要求，總方案有：

C"x5!=2400(種)

1.19n+m位由m個0,n個1組成符號串，其中nWm+1,試問不存在兩個1相鄰的符號串

的數(shù)目。

［解］:先將m個0排成一排，再將n個1插入m個0的m+1個空隙(因為nWm+1,這可實

(m+

現(xiàn))，就得到了無相鄰的n+m位0-1符號串，其方案數(shù)為“L

1.20甲單位有10個男同志，4個女同志，乙單位有15個男同志，10個女同志，由他們產(chǎn)

生一個7人的代表團，要求其中甲單位占4人，而且7人中男同志5位.試問有多少種方案？

［解］甲單位選4人，則乙單位只能選3人；另外男同志要5人，而乙單位的3人全是男同

志，還差2名男同志，故甲單位的男同志人數(shù)應(yīng)至少是2,至多為4。

10Y4Y15Y10"口0丫4丫15丫叫勺0丫叩5丫10、

2hbh，Hhhr768600

1.21一個盒子里有7個無區(qū)別的白球，5個無區(qū)別的黑球.每次從中隨機取走一個球，已知

前面取走6個，其中3個是白的.試問取第6個球是白球的概率.

［解］已知前面取走6個球，有3個白球，則有3個黑球。

⑹

故總的取球方案是］

第六個球是白球的方案是2

Ii-7-6-5-5-4-3

因此取出第6個球是白球的概率P=77V------------------===。-5

612

1.22求下圖中從0到P的路徑數(shù):

(a)路徑必須過A點；

(b)路徑必須過道路AB；

(c)路徑必須過A和C：

(b)路分為三段：先從。到A,再從A到B：再從A到B：然后從B到P；

(3+2、/8-4+5-2、

,1,

25-27

路分為三段：先從0到A；再從A到C；然后從C到P；

氣―6+5_3)_僅丫4丫4、

240

<5-3廠12卜卜,

(d)(采用排除法)

從。到P的滿足不過AB的路=從。到P的路一從。到P經(jīng)過AB的路，因此:

‘8+5、(3+2、，8-4+5-2、1X

,1,

25-2(5

、5,7

=1287—350

=937

1.23另s={1,2,3…,n+l},n22

T={(x,y,z)lx,y,zes,x<z,y<z},試證:

W+1、

\T\=^k2=+2+2

k=l<2,、37

[證]

”+1z-1z-1

M=EEZi

z=ly=lx=l

n

=?

k=\

而G+l)3=%3+3女2+3女+1,故女2=g[k+l)3—%3一3后—1]

n1rnnn

方+1)3-3^k-n

k=\3|_A=Ik=\k=\_

(〃+1)

一(〃+l)3-—n(n+1)一

v

3、'23

11.1

=—n(n+1)4-—(n+1)-z:(n+l)--(n+1)

〃+1、+(〃+叫5+1)2_”；

2>

〃+ni,

+一(“+1)("-+2”+1-3〃-1)

2J3

i

+-(n+l)(?-7-ri)

〃+l)(n+l)n(n-l)

+2--------

23-2-1

\'〃+1、

+2

37、3,

1.24A=((a,b)la,bez,0WaW9,0WbW5}

(a)求x-y平面上以A作頂點的長方形的數(shù)目.

(b)求x-y平面上以A作頂點的正方形數(shù)目.

［解］(a)先選定橫作標(biāo)，再選定縱坐標(biāo)，其方案數(shù)為:

OoY63—675

2人222

(b)求x-y平面上以A作頂點的正方形數(shù)FL

按邊長分類：

邊長為1的正方形:9X5=45

邊長為2的正方形:(9-1)X(5-1)=32

邊長為3的正方形:(9-2)X(5-2)=21

邊長為4的正方形:(9-3)X(5-3)=12

邊長為5的正方形:(9-4)X(5-1)=5

故總的以x—y平面上A點作頂點的正方形的數(shù)目，按加法原理可得數(shù)目為115.

1.25平面上有15個點個P2,…出5,其中P1,P2,P3,P*P5共線,此外不存在3點共線的.

(a)求至少過15個點中兩點的直線的數(shù)目.

(b)求由15個點中3點組成的三角形的數(shù)目.

［解］(a)(采用排除法)

至少過15個點中兩點的直線數(shù)目=在15個點中任選2個點將有一條直線一從P「Ps

中選2點構(gòu)成直線+P「Ps所在的直線?

15，5

+1

=96

(b)(采用排除法)

由15個點中3點組成的三角形的數(shù)目=任在15個點中取3點構(gòu)成三角形的數(shù)目一在

5個點片?與中取3點構(gòu)成的“三角形”的數(shù)目

吧制

=445

1.26S=｛1,2,...,1000),a,b?S,使ab三0mod5,求數(shù)偶｛a,b｝的數(shù)目.

［解］因為?^=0mod5

所以ab=5k(k是整數(shù))

1WaW1000,1WbW1000

1WabW1000000

1W5kW1000000

1WkW200000

所以滿足“b三°mod5且1wa,bW1000的｛a,b｝的數(shù)目為200000

1.276位男賓，5位女賓圍一圓桌而坐

(a)女賓不相鄰有多少種方案？

(b)所有女賓在一起有多少種方案？

(c)一女賓A和兩位男賓相鄰又有多少種方案？

［解］(a)先將6位男賓作圓排列有。；=5!=12°

在將5位女賓插入6個空格，每格一人，共有6X5X4X3X2X1=720

按乘法原理：有120X720=86400

(b)5位女賓在一起，可看作一人，與6位男賓一起，先做圓排列，有°；=6!=720

然后5位女賓內(nèi)部作線排列，有5!=120。

所以，總方案為：720X120=86400

(c)先將6個男賓做圓排列，共有°；=120種方法。

再將女賓A隨便插入6個空格中的一個，有6種方法。

然后將剩下的4個女賓插入5個空格中，但每個空格不限人數(shù)，故相當(dāng)于將4個有區(qū)

，4+5—1、

別的球放入5個不同的盒子中的放球方案(可重組合)，共有4=5X6X7X8=

1680o

所以，按乘法原理，有120X6X1680=1209600種方案。

1.28k和n都是正整數(shù)，kn位來賓圍著k張圓桌而坐，試求其方案數(shù).

［解］先將kxn個來賓分成k堆，每堆n個人，有

kn(4〃)?。輄伏〃)！

(々堆［〃!?〃!...nl)(〃!)*

再將每堆n個人做圓排列，有°；=(n-1)!,共有K〃T)!『種方法。

故按乘法原理，有

野(〃.1)『=幽

1.29從n個對象中取r個作圓排列，求其方案數(shù)目.已知IWrWn.

［解］每一個r個人圍成的圈(圓排列)ax,a2,--,ar_var

a},a2,---,ar_var

0(線排列A%'%，…%嗎

即每一個r圈相當(dāng)于r個r排列。故不同的方案數(shù)為

1?、1?!

N=—P(n,r)=-----------

rr(n-r)!

114

若不計順逆方向，則為N=—P(n,r)=---------:—o

2r2r(H-r)!

1.30試證下列等式

\<r<n

[證](a)方法一

〃！_n(n-1)!

j,r!(n-r)!r(r-1)!x[(n-1)-(r-1)]!

_n(n-1

r1一1

方法二：組合意義法：

一方面，從nd元素中取出r個元素，然后再做排列，故按乘法原理，其數(shù)目為

(n\

?r\

另一方面：先從n個元素中取出1個元素，排在第一位，再從剩下的n-1個元素中取出

r-1個元素，并將這r-1個元素排在第2?r位，故按乘法原理，其方案數(shù)為

這兩方面的組合意義相同,

因此，有:

(b)方法一

〃、n(n-1)???(n—r+2)(M—r+1)

rJ

〃-r+1)/?(/?-1)???(?-r+2)

(r-1)!

n-r+l(n

方法二：組合意義

一方面：從n個元素中取出r個元素來，然后，在做排列，故按乘法原理，其方案數(shù)為

另一方面：先從n個元素中先取出r-1個元素，將其排排列再第1?r-1位，再從剩下的

n-r+1個元素中取出1個元素排在第r位。故按乘法原理，其方案數(shù)為：

?(r-l)!-(n-r+1)

V.

這兩方面的組合意義相同，故有

%、(n)/、

-r!-(r-l)!-(n-r+l)

rJ_lr-lJ

所以，有：

"一r+l(n

r)rJ

(c)方法一

'〃]_〃(〃一1)???(〃-r+1)(〃-r)(H一r-1)???1

jJr!(n-r)(?-r-1)???1

=--n---(〃----1)-…--(〃----r-+-1-)(-〃---r-)(-n--------

n-rr!(n-r-l)**-l

----n---------(-H---1-)--!---

n-rr!(n-l-r)!

n

方法二：組合意義

一方面，從n個元素中取出n-r個元素，然后再做排列，按乘法原理，其方案數(shù)為：

(n-r)!=(n-r)!

另一方面，選從n個元素中取出1個元素排再第一位，再從剩下的n-1個元素中選取

n-r+1個元素，排在第2?n-r位。故按乘法原理，其方案數(shù)為

(n-\、(〃一1)

n■?(〃一/"一］)!=〃.-(n-r-1)!

(〃-r-lj(r)

這兩方面的組合意義相同，可得：

(”+1)(n+2)…+r)

被八除盡.

(“+??)!n+r］

［證］(〃+1)("+2)…("+廠)=-------r\--r\

r\n\(r)

(n-vr\

由于，是從n+r個元素中選取r個元素的組合數(shù)，故當(dāng)然是整數(shù)，因此,

(〃+廣、

(n+1)(n+2)…(n+r)可以整除r!,其商為組合數(shù)。

I.32在a,b,c,d,e,f,x,x,x,y,y的排列中，要求y必須夾在兩個x之間，問這樣的排列數(shù)等

于多少？

［解］由于y必須乘在兩個x之間，故兩個y只能夾在僅有的三個x之間，形成圖象xyxyx,

形成6個空檔。其余的6個元素2,66￡|?乂只能放在這6個空格處，這相當(dāng)于將6個不同

的小球放入6個不同的盒子中，允許空盒，且盒內(nèi)還要排列的方案數(shù)。故：

1.33已知K”，A都是正整數(shù)，r2nk,將r個無區(qū)別的球放在n個有標(biāo)志的盒子里，每盒至

少k個球，試問有多少種方案？

［解］先將nk個球放入n個有標(biāo)志的盒中，每盒k個球，其方案為1。

再將剩下的r-nk個球放入這n個盒中，每盒球數(shù)不限，其方案數(shù)為

/n+(r-nk)-1A(r—n(k-1)-1

j-nkJ(〃一］

故總的方案為

r-n(k-1)-P(r-n(k-1)-P

、〃J>

1.34在os,t,u,v,w,x,y,z的排列中求y居x和z中間的排列數(shù).

［解］由于y必須居于x和z之間，故形成圖象xyz,形成4個空格。其余r,s,t,u,v,w這6個

元素，只能放在這4個空格處，這相當(dāng)于將6個不同的小球放入4個不同的盒子中，允許

空盒，且盒內(nèi)還要進行排列的方案數(shù)。故有：

‘6+4-19'

6!-=6!—=60480

,4-13!6!

方法2：

將9個字母進行全排列，有9!中排列，而x,y,z這3個字母形成的3!個排列只看作一種

排列xyz,故有:

91

-=60480

3!

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

［解］從一個頂點可引出7條線和第一條（從右到左）交的有17,和第二條交的有26條

故和一個頂點引出的7條線相交的點為：

1.7+2.6+3-5+4-4+5.3+6.2+7-1=84

故和從10點引出的對角線交的點有個

84x10=840,但每個點重復(fù)了四次（因為每個點在兩

條線上，而每條線有兩個端點）。故凸10邊形（這

樣的）對角線交于半臼。個點。

10x9x8x7

故也可為。：0==210

4x3x2xl

笫二章母函數(shù)與遞推關(guān)系

1.36試證一整數(shù)是另一整數(shù)的平方的必要條件是除盡它的數(shù)的數(shù)目是整數(shù).

［證］“必要性”。若整數(shù)n是另一個整數(shù)的平方，則n一定可寫成如下形式：

〃=P^a'啜???P”(參見P7例4)

其中P1,P2,...,Pe是e個不同的素數(shù)。由于第9題可得，除盡n的正整數(shù)數(shù)目為

(2a1+1)(2a2+1)…(2ae+1)為奇數(shù)。

“充分性”。若除盡正整數(shù)n的正整數(shù)的數(shù)目為奇數(shù)。則n一定是某個正整數(shù)的平方，

否則，n不是平方數(shù)，則n一定是可分解成如下形式：

n=P：'P*…P：

其中P1,P2,...,Pe是e個不同的素數(shù)，且［32,…,pe中至少有一個奇數(shù)(否則n為平

方數(shù))。于是(201+1)(202+1)…(2pe+1)必為偶數(shù)，與充分性假設(shè)矛盾。

I.37給出

(n-2\(r+2\n-m\(r+rn'n+r+O

++???+

(加-222)、。人機,

的組合意義.

［證］組合意義一：

從(n+r+1)個元素｛1,2,…,n+r+1｝中取出(n+r+1-m)個元素ii