第6章組合數(shù)學(xué)初步

第6章組合數(shù)學(xué)初步組合數(shù)學(xué)是既古老又年輕的數(shù)學(xué)分支，它的淵源可以追溯到公元前2200年的大禹治水時(shí)代，大禹治水時(shí)，就已觀察到神龜背上的3階幻方。中外歷史上許多著名的數(shù)學(xué)游戲是它古典部分的主要內(nèi)容。例如數(shù)學(xué)游戲幻方問題：給定自然數(shù)1，2，…，將其排成n階方陣，要求每行、每列和每條對(duì)角線上各數(shù)字之和都相等。這樣的n階方陣稱為n階幻方。每一行（或列、或?qū)蔷€）之和稱為幻和。圖6.1是一個(gè)3階幻方，其幻和等于15。圖6.13階幻方816357492首先人們要問：1)存在性問題：即n階幻方是否存在？2)計(jì)數(shù)問題：如果存在，對(duì)某個(gè)確定的n，這樣的幻方有多少種？3)構(gòu)造問題：即枚舉問題，亦即如何構(gòu)造n階幻方？組合數(shù)學(xué)就是研究上述提出的問題。特別是近年來，隨著電子計(jì)算機(jī)科學(xué)、計(jì)算數(shù)學(xué)、通信以及許多學(xué)科的發(fā)展，組合數(shù)學(xué)這門歷史悠久的學(xué)科得到了迅速發(fā)展。計(jì)算機(jī)的運(yùn)行需要編程來控制，然而編程的基礎(chǔ)往往是求解問題的組合學(xué)算法。組合數(shù)學(xué)主要研究離散對(duì)象的安排或配置方案的存在性、計(jì)數(shù)、枚舉構(gòu)造和優(yōu)化等問題。同時(shí)用計(jì)算機(jī)解決某個(gè)問題如果有多種算法可供選擇時(shí)，就要考慮算法的復(fù)雜度問題。衡量時(shí)間復(fù)雜度的一個(gè)重要指標(biāo)就是算法的運(yùn)算次數(shù)，即求出在最壞情況下的運(yùn)算次數(shù)或按概率分布的平均運(yùn)算次數(shù)。而衡量空間復(fù)雜度的主要指標(biāo)就是所占用的存儲(chǔ)空間大小。為此，就要用到組合數(shù)學(xué)的方法和技巧。因此，組合數(shù)學(xué)已成為計(jì)算機(jī)學(xué)科各專業(yè)的基礎(chǔ)知識(shí)?！?.1計(jì)數(shù)基本原理人們把所研究的對(duì)象叫做元素，把某些元素的總體叫做集合，只有有限個(gè)元素的集合稱為有限集。在通常情況下，組合數(shù)學(xué)研究的對(duì)象是有限集。組合計(jì)數(shù)問題是求n元集合中滿足某些給定條件的子集的個(gè)數(shù)。常常用到下面兩個(gè)基本原理。6.1.1加法原理和乘法原理6.1.1加法原理和乘法原理如果完成一件事情有兩個(gè)方案，而第一種方案有m種方法，第二種方案有n種方法可以實(shí)現(xiàn)，只要選擇任何方案中的某一種方法，就可以完成這件事情，并且這些方法兩兩互不相同，則完成這件事情共有m+n種方法。若用集合語言，加法原理則可以描述為：設(shè)有限集合A有m個(gè)元素，B有n個(gè)元素，且A與B不相交，則A與B的并共有m+n個(gè)元素。如果我們用符號(hào)表示有限集合A的元素的個(gè)數(shù)，上述可描述為定理6.1

設(shè)A，B為有限集，，則

.一般情況有定理6.2

設(shè)n個(gè)有限集合，滿足，則

例6.1某班有男生18人，女生12人，從中選出一名代表參加會(huì)議，問共有多少種選法？解：用集合A表示男生，B表示女生，則該班中的學(xué)生要么屬于A，要么屬于B.根據(jù)加法原理，全班共有18+12=30個(gè)學(xué)生，故有30種選法。例6.2

在所有六位二進(jìn)制數(shù)中，至少有連續(xù)4位是1的有多少個(gè)？解：所有滿足要求的二進(jìn)制數(shù)分成如下3類：（1）恰有4位連續(xù)的1.它們可能是*01111，011110，11110*，其中“*”可能取0或1.故在此情況下，共有5個(gè)不同的六位二進(jìn)制數(shù)。（2）恰有5位連續(xù)的1.它們可能是011111，111110，共有2個(gè)。（3）恰有6位連續(xù)的1.即111111，共有1種可能。（4）綜合以上分析，由加法原理知共有5+2+1=8個(gè)滿足題意要求的六位二進(jìn)制數(shù)。乘法原理

如果完成一件事情需要兩個(gè)步驟，而第一步有m種方法，第二步有n種方法去實(shí)現(xiàn)，則完成該件事情共有種方法。乘法原理也可以用集合語言描述為：設(shè)有限集合A有m個(gè)元素，B有n個(gè)元素，，記(a，b)為一有序?qū)?，所有有序?qū)?gòu)成的集合稱為A和B的積集（或笛卡爾乘積），記作，那么共有個(gè)元素。定理6.3

設(shè)A，B為有限集，，則

一般情況有定理6.4

設(shè)n個(gè)有限集合，則

例6.3

仍設(shè)某班有男生18人，女生12人，現(xiàn)要求從中分別選出男女生各一名代表全班參加比賽,問共有多少種選法?解：仍像例6.1那樣,用集合A表示男生，B表示女生，那么根據(jù)乘法原理，共有種選法。6.1.2包含排斥原理包含排斥原理是計(jì)數(shù)中常用的一種方法，先舉一例說明如下。例，求不超過20的正整數(shù)中為2或3的倍數(shù)的數(shù)。不超過20的數(shù)中2的倍數(shù)有10個(gè)：

2,4,6,8,10,12,14,16,18,20不超過20的數(shù)中3的倍數(shù)有6個(gè)：

3,6,9,12,15,18但其中為2或3的倍數(shù)的數(shù)只有13個(gè)，而不是10+6=16個(gè)，即

2,3,4,6,8,9,10,12,14,15,16,18,20其中6,12,18同時(shí)為2和3的倍數(shù)。若計(jì)算10+6=16，則重復(fù)計(jì)算了一次6，12，18。我們知道加法原理是指時(shí)，若時(shí)，會(huì)怎樣？包含排斥原理回答了這個(gè)問題。正如上面的例子，這時(shí)，將計(jì)算了兩回，所以

定理6.5

設(shè)A，B為有限集，則

.如果A，B是有限集U的子集，若記，則，由集合的德摩根定律，，定理6.5可寫成定理6.5可推廣為或當(dāng)集合A，B是有限集U的子集時(shí)，則有定理6.6

設(shè)n個(gè)有限集合，則或當(dāng)n個(gè)集合是有限集U的子集時(shí)，則例6.5

一個(gè)學(xué)校只有3門課程：數(shù)學(xué)、物理、化學(xué)。已知修這3門課的學(xué)生分別有170、130、120人；同時(shí)修數(shù)學(xué)、物理兩門課的學(xué)生有45人；同時(shí)修數(shù)學(xué)、化學(xué)的有20人；同時(shí)修物理、化學(xué)的有22人；同時(shí)修三門課的學(xué)生有3人。假設(shè)學(xué)校的學(xué)生至少修一門課程，問這個(gè)學(xué)校共有多少學(xué)生？解：令：A為修數(shù)學(xué)課的學(xué)生集合；

B為修物理課的學(xué)生集合；

C為修化學(xué)課的學(xué)生集合；由題意，，，由包含排斥原理知

。即該學(xué)校共有336人。例6.6

求從1到1000不能被5、6和8整除的整數(shù)個(gè)數(shù)。解：為解決這個(gè)問題我們引入一個(gè)概念。對(duì)于實(shí)數(shù)x，代表不超過x的最大整數(shù)。此外，我們將兩個(gè)整數(shù)a，b或三個(gè)整數(shù)a，b，c的最小公倍數(shù)相應(yīng)地記為lcm(a,b)或lcm(a,b,c).令：U是由前1000個(gè)正整數(shù)組成的集合。A1是前1000個(gè)正整數(shù)中能被5整除的整數(shù)集合。A2是前1000個(gè)正整數(shù)中能被6整除的整數(shù)集合。A3是前1000個(gè)正整數(shù)中能被8整除的整數(shù)集合。于是集合中的整數(shù)可同時(shí)被5、6整除，當(dāng)且僅當(dāng)它能被lcm(5,6)整除。由于lcm(5,6)=30，lcm(5,8)=40，lcm(6,8)=24.

于是于是這樣，由包含排斥原理知，從1到1000不能被5、6和8整除的整數(shù)個(gè)數(shù)為§6.2鴿籠原理鴿籠原理(又叫抽屜原理)指的是一個(gè)簡(jiǎn)單明了的事實(shí)：為數(shù)眾多的一群鴿子飛進(jìn)不多的鴿籠里，則至少有一個(gè)鴿籠飛進(jìn)了兩只或更多的鴿子。這個(gè)原理并無深?yuàn)W之處，其正確性也是顯而易見的，但利用它可以解決許多有趣的組合問題，得到一些很重要的結(jié)論，它在數(shù)學(xué)的歷史上起了很重要的作用。6.2.1鴿籠原理鴿籠原理的簡(jiǎn)單形式可以描述為：定理6.7

如果把n+1個(gè)物品放在n個(gè)盒子中，那么至少有一個(gè)盒子中有兩個(gè)或更多的物品。證明：倘若每個(gè)盒子中至多有一個(gè)物品，那么n個(gè)盒子中至多有n個(gè)物品，而我們共有n+1個(gè)物品，矛盾。故定理成立。例如，在13個(gè)人中必有兩人生日的月份是相同的，在367個(gè)人中必有兩人在同一天過生日。鴿籠原理只斷言存在一個(gè)盒子，該盒子中有兩個(gè)或兩個(gè)以上的物品，但它并沒有指出是哪個(gè)盒子，要想知道是哪一個(gè)盒子，則只能逐個(gè)檢查這些盒子。所以，這個(gè)原理只能用來證明某種安排的存在性，而對(duì)找出這些安排卻毫無幫助。例6.7

從1到200的所有整數(shù)中任取101個(gè)，則這101個(gè)整數(shù)中至少有一對(duì)數(shù)，其中的一個(gè)一定能被另一個(gè)整除。證明：設(shè)是被選出的101個(gè)整數(shù)，對(duì)任一，都可以唯一地寫成如下的形式：，其中為正整數(shù)，為奇數(shù)。例如：，

.由于，所以只能取1，3，5，…，199這100個(gè)奇數(shù)，而共有101項(xiàng)，由鴿籠原理知，存在，使得

不妨設(shè)，則

=整數(shù)，即能被整除。6.2.1鴿籠原理的加強(qiáng)形式

定理6.8

設(shè)q1,q2,…,qt是正整數(shù)，把件物品放入t個(gè)盒子里，則存在某一i(1≤i≤t)使第i個(gè)盒子里至少裝qi件物品。證明：倘若對(duì)所有的i(1≤i≤t)均有第i個(gè)盒子至多裝有qi-1件物品，從而這t個(gè)盒子裝有的物件總數(shù)至多為從而產(chǎn)生矛盾。所以定理成立。當(dāng)q1=q2=…=qt=r時(shí)，上述原理可敘述為：如果把t(r-1)+1件物品裝入t個(gè)盒子中，則至少有一個(gè)盒子至少有r件物品。這種情況的另一種提法為：如果t個(gè)整數(shù)q1,q2,…,qt的算術(shù)平均數(shù)大于r-1，則qi(1≤i≤t)中至少有一個(gè)不能小于r.證明：若不然，則qi≤r-1(1≤i≤t).因此，

從而產(chǎn)生矛盾。例6.8

證明每個(gè)長(zhǎng)為n2+1的實(shí)數(shù)序列,,…,含有一個(gè)長(zhǎng)為n+1的遞增子序列或長(zhǎng)為n+1的遞減子序列。證明：倘若不存在長(zhǎng)為n2+1的遞增子序列，我們將證明一定存在長(zhǎng)為n+1的遞減子序列。令qk是以ak為首元素的最長(zhǎng)遞增子序列的長(zhǎng)度，則1≤qk≤n.由鴿籠原理的加強(qiáng)形式，取r=n+1，知n2+1個(gè)數(shù)qk（1≤k≤n2+1），當(dāng)1≤mk≤n時(shí)，至少有n+1個(gè)數(shù)相等。設(shè)此時(shí)必有（1≤i≤n）.若不然，存在某一i，使，取以元素開始的最長(zhǎng)子序列，然后把放在這個(gè)子序列的前面，就得到一個(gè)以為首元素的遞增子序列。這樣與矛盾。故(1≤i≤n)從而是一個(gè)長(zhǎng)為n+1的遞減子序列。從上面的幾個(gè)例子可以看出，盡管鴿籠原理很簡(jiǎn)單，但它卻能解決一些看似很復(fù)雜的組合問題。在將其運(yùn)用到具體的問題時(shí)，需要一定的技巧去構(gòu)造具體問題中的“鴿子”與“鴿籠”?！?.3排列與組合大量的計(jì)數(shù)問題呈現(xiàn)如下的類型：(1)對(duì)元素的有序的擺放數(shù)或有序的選擇數(shù)進(jìn)行計(jì)數(shù)

a)沒有重復(fù)元素。

b)允許元素重復(fù)。(2)對(duì)元素的無序的擺放數(shù)或無序的選擇數(shù)進(jìn)行計(jì)數(shù)

a)沒有重復(fù)元素。

b)允許元素重復(fù)。6.3.1基本的排列與組合集合的排列n元集合S的一個(gè)r排列是指先從S中選出r個(gè)元素，然后將其按次序排列。一般用P(n,r)或表示n元集合的r排列數(shù)。定理6.9對(duì)于滿足的正整數(shù)n和r，有證明：要構(gòu)造n元集合的一個(gè)r排列，我們可以在n個(gè)元素中任取一個(gè)作為第一項(xiàng)，有n種取法；在取定第一項(xiàng)后，第二項(xiàng)可以從剩下的n-1個(gè)元素中任選一個(gè)，有n-1中取法；……；同理，在前r-1項(xiàng)取定后，第r項(xiàng)有n-r+1種取法。由乘法原理知顯然，有⑴P(n,r)=0(r>n);⑵P(n,1)=n(n≥1);⑶全排列數(shù)P(n,n)=n!.我們規(guī)定0!=1.例6.9

大家所熟知的“15迷宮”是將標(biāo)有數(shù)字1到15的15個(gè)可以滑動(dòng)的小正方形裝在一個(gè)4×4的正方形框架上，剩下一個(gè)小的空方塊。游戲是將15個(gè)小方塊從任一排列方式移動(dòng)成如圖6.2所示的初始位置?，F(xiàn)在問：這15個(gè)小方塊在4×4地框架上有多少種不同的排列方式？解原問題就是求將1，2，…，15放在4×4框架中的16個(gè)小方塊上而剩下一個(gè)空方塊的方式數(shù)。我們將空方塊看作16，則原問題就變?yōu)?，2，…，16放入16個(gè)各小方塊中的方式數(shù)，它等于{1,2,…,16}的全排列數(shù)。即有P(16,16)=16!種不同的排列方式。圖6.2123456789101112131415例6.10A單位有7位代表，B單位有3位代表，排成一列合影，要求B單位3人排在一起。問有多少種不同的排列方案？解:B單位3個(gè)人的某一排列作為一個(gè)元素。參加A單位進(jìn)行排列，可得方案數(shù)為(7+1)!=8!.

且B單位的3人有3!種排列.

由乘法原理，總排列方案數(shù)為8!×3!.例6.11若例6.10中B單位的3人不能相鄰，且A單位的2人排在兩端，問有多少種不同的排列方案。解:A單位7人共有7!種排列。設(shè)A1A2A3A4A5A6A7是A的一個(gè)排列。兩端固定后，B單位3人中的第一人有6種選擇

A1*A2*A3*A4*A5*A6*A7即上面*的位置，第二位為了不與第一位相鄰，故只有5種選擇。第三位有4種選擇。故排列總數(shù)為

7!×6×5×4=604800前面考慮的排列是在直線上進(jìn)行的或者確切的說，是r線排列。若在圓周上進(jìn)行排列，結(jié)果又如何呢？在一個(gè)r圓排列的任意兩個(gè)相鄰元素之間都有一個(gè)位置，共有r個(gè)位置。從這r個(gè)位置處將該圓排列斷開，并拉直成線排列?；蛘邠Q個(gè)說法，將r個(gè)r線排列

a1a2…ar-1ar,a2a3…ara1,…,ara1…ar-2ar-1的首位相連圍成圓排列，得到的是同一個(gè)r圓排列。因此，下面的定理成立：定理6.10n元集合的r圓排列數(shù)為例6.1210個(gè)男生和5個(gè)女生聚餐，圍坐在圓桌旁，任意兩個(gè)女生不相鄰的坐法有多少種？解:先把10個(gè)男生排成圓形，有種方法。固定一個(gè)男生的排法，把5位女生插在10個(gè)男生之間，每?jī)蓚€(gè)男生之間只能差一個(gè)女生，而且5個(gè)女生之間還存在著排序問題，故可有P(10,5)種排法。由乘法原則知，共有9!×P(10,5)種坐法。集合的組合n元集合S的r組合是指從S中取出r個(gè)元素的一種無序選擇，其組合數(shù)記為或C(n,r)或.定理6.11若0≤r≤n，則證明:設(shè)S是一n元集合，任取S的一個(gè)r組合，將該r組合中的r個(gè)元素進(jìn)行排列，便可得到P(r,r)=r!個(gè)S中的r排列。而且S中的任一r排列都可恰好通過將S中的某一r組合排序而得到。所以，有，即

.顯然，有⑴，；⑵(r>n).

例6.13

系里欲將6名保送研究生推薦給3個(gè)單位，每個(gè)單位2名，問有多少種方案？

解:推薦給某個(gè)單位的兩名學(xué)生的順序是無關(guān)緊要的，這是一個(gè)組合問題。我們先從6名學(xué)生中選出2名給第一個(gè)單位，有種選法。然后從余下的4名學(xué)生中選出2名給第二個(gè)單位，有種選法。余下的2名學(xué)生給第三個(gè)單位。每一步不同的選法對(duì)應(yīng)著不同的方案，由乘法原理，共有種方案。6.3.2多重集合的排列與組合多重集合的排列前面講的n元集合的r排列，是指從n個(gè)各不相同的元素里，每次取出r個(gè)互不相同的元素進(jìn)行排列，然而在現(xiàn)實(shí)生活中，并不一定是對(duì)不同的元素進(jìn)行排列。例如，對(duì)一組數(shù)據(jù)排序就是求它的一個(gè)排列，而在這些數(shù)據(jù)中可能出現(xiàn)相同的數(shù)。為此，我們引入多重集合的概念。多重集合同一般集合一樣，是一組對(duì)象的整體，只不過不像一般集合那樣必須要求集合中每個(gè)元素互不相同。例如：

M={a,a,a,b,c,c,d,d,d,d}是一個(gè)10個(gè)元素的多重集合，其中有3個(gè)a，1個(gè)b，2個(gè)c,4個(gè)d。通常，我們將M表示為

M={3·a，1·b，2·c，4·d}.一般記多重集合為

M={k1·a1，k2·a2，…，kn·an}其中，a1,a2,…,an為M中所有的互不相同的元素，ki是正整數(shù)，稱ki為ai的重?cái)?shù),表示M中有ki個(gè)ai（1≤i≤n），ki也可以是，表示M中有無限多個(gè)ai.多重集合S的排列同一般集合的r排列一樣，也是從S中選出r個(gè)元素的有序選擇。定理6.12多重集合M={·a1，·a2，…,·ak}的r排列數(shù)為kr.證明:

在構(gòu)造M的一個(gè)r排列時(shí)第一項(xiàng)有k種選擇，第二項(xiàng)有k種選擇……，第r項(xiàng)有k種選擇。由于M中的每個(gè)元素都是無限重的，所以r排列中的任一項(xiàng)都有k種選擇，且不依賴于前面已選擇的項(xiàng)，故M的r排列數(shù)為kr.由上面的證明易知，若M中每個(gè)元素的重?cái)?shù)至少為r，則定理的結(jié)論仍然成立。定理6.13多重集合M={k1·a1，k2·a2，…，kn·an}的全排列數(shù)為證明:集合M中共有k1+k2+…+kn個(gè)元素，a1占集合M的全排列中的k1個(gè)位置，選取a1所占位置的方法數(shù)為；在確定了k1個(gè)a1的位置后，還有k2+…+kn個(gè)位置，a2,占其中的k2個(gè)位置，從中選取k2個(gè)a2的位置的方法數(shù)為；類似的，依次選取位置安排a3，a4，…，an，由乘法原理知，M的全排列數(shù)為

例6.14求不多于四位的二進(jìn)制數(shù)的個(gè)數(shù)。解:此問題相當(dāng)于多重集合的4排列問題，由定理6.12知，所求的二進(jìn)制數(shù)個(gè)數(shù)為24＝16.例6.15設(shè)S={3·a,2·b,4·c},求S的8排列的個(gè)數(shù)。解:S的8排列可分為以下三類：⑴{2·a,2·b,4·c}的8排列，數(shù)目為⑵{3·a,1·b,4·c}的8排列，數(shù)目為⑶{3·a,2·b,3·c}的8排列，數(shù)目為因此S的全部8排列的個(gè)數(shù)為

420+280+560＝1260多重集合的組合多重集合M的r組合是指從M中無序的選出r個(gè)元素。定理6.14多重集合M＝{·a1,·a2,…,·ak}的r組合數(shù)為

.證明:設(shè)多重集合M的某個(gè)r組合為

{x1·a1,x2·a2,…,xk·ak},（6.3.1）則有x1+x2+…+xk=r，（6.3.2）其中，x1,x2,…,xk為非負(fù)整數(shù)。反之，若給出方程（6.3.2）的一組非負(fù)整數(shù)解x1,x2,…,xk，則對(duì)應(yīng)與M的一個(gè)r組合（6.3.1）。所以M的r組合與方程（6.3.2）的非負(fù)整數(shù)解構(gòu)成一一對(duì)應(yīng)，從而將求M的r組合的問題化為求方程（6.3.2）的非負(fù)整數(shù)解。方程x1+x2+…+xk=r的一個(gè)非負(fù)整數(shù)解可以表示成長(zhǎng)為k-1+r的0,1序列

00…0，其中，0的個(gè)數(shù)為k-1個(gè)。該0,1序列是集合{(k-1)·0,r·1}的一個(gè)全排列。方程（6.3.2）的解與集合{(k-1)·0,r·1}的全排列之間是一一對(duì)應(yīng)的，從而多重集合M的r組合數(shù)為

例6.16方程：x1+x2+x3+x4=20的整數(shù)解的個(gè)數(shù)是多少？其中

x1≥3，x2≥1，x3≥0，x4≥5

解：我們引入新變量

y1=x1-3,y2=x2-1,y3=x3,y4=x4-5此時(shí)方程變?yōu)?/p>

y1+y2+y3+y4=11諸xi的下界能夠滿足當(dāng)且僅當(dāng)這些yi是非負(fù)的。新方程的非負(fù)整數(shù)解的個(gè)數(shù)是同理我們可知含有k種元素且重?cái)?shù)為n1，n2，…，nk的多重集

S={n1·a1,n2·a2,…,nk·ak}的r-組合數(shù)和方程

x1+x2+…+xk=r的整數(shù)解的個(gè)數(shù)相同，其中

0≤x1≤n1,0≤x2≤n2,…,0≤xk≤nk.6.3.3二項(xiàng)式系數(shù)表達(dá)式表示n元集合的r組合數(shù)，它具有許多很奇妙的性質(zhì)，關(guān)于它有許多恒等式。由于它出現(xiàn)在下面所介紹的二項(xiàng)式定理中，所以稱其為二項(xiàng)式系數(shù)。在進(jìn)行產(chǎn)生計(jì)算機(jī)算法分析時(shí)，經(jīng)常要用到二項(xiàng)式系數(shù)，因此有必要對(duì)其熟練掌握。定理6.15（二項(xiàng)式定理）設(shè)n為一正整數(shù)，則對(duì)任意的x和y，有證明：將展開，直到?jīng)]有括號(hào)為止。在展開時(shí)，每個(gè)因子中均可取x或y，因而共有2n項(xiàng)，這些項(xiàng)都可以寫成xryn-r(0≤r≤n)的形式。我們可以在n個(gè)x+y因子中選出r個(gè)，從這r個(gè)因子中取x，而在另外的n-r個(gè)因子中取y，如此得到xryn-r項(xiàng)，所以xryn-r的系數(shù)等于n個(gè)因子的組合數(shù)，即.因此

推論n為一正整數(shù)，則對(duì)任意的x，

證明：只要在二項(xiàng)式定理中令y=1即可。二項(xiàng)式系數(shù)的基本性質(zhì)當(dāng)n,r均為非負(fù)整數(shù)，且n≥r時(shí)，有一些最基本的性質(zhì)：（1）對(duì)稱關(guān)系；（2）遞推關(guān)系

(n≥r≥1)；注意：在證明二項(xiàng)式系數(shù)的性質(zhì)或恒等式時(shí)，一般可利用下面三種方法。

1）用二項(xiàng)式系數(shù)的表達(dá)式。

2）利用二項(xiàng)式系數(shù)的組合意義。

3）利用二項(xiàng)式定理。性質(zhì)（1）對(duì)稱關(guān)系的證明。證一：利用二項(xiàng)式系數(shù)的表達(dá)式證二：利用二項(xiàng)式系數(shù)的組合意義表示n元集合A的r元組合數(shù)，或表示n元集合的r元子集的個(gè)數(shù)。同理，表示集合A的n-r元子集的個(gè)數(shù)。設(shè)A1是A的r元子集，則A-A1是A的n-r元子集，且這種關(guān)系顯然是1-1對(duì)應(yīng)的。所以A的r元子集地個(gè)數(shù)等于A的n-r元子集的個(gè)數(shù)。因此證三：利用二項(xiàng)式定理同理

=，所以=因此性質(zhì)（2）遞推關(guān)系，(n≥r≥1)的證明。利用的組合意義來證：N元集合的r元子集可以分成兩類：第一類r元子集含

，第二類r元子集不含

。第一類r元子集中的任一個(gè)去掉

后，就是的r-1元子集；反過來，任給一個(gè)的r-1元子集，添上后就是A的r元子集，故二者之間有一一對(duì)應(yīng)關(guān)系。因而，第一類r元子集共有。第二類r元子集就是的r元子集，共有個(gè)。所以

(n≥r≥1)；由性質(zhì)（2）可得圖6.3所示的著名的楊輝三角形。許多關(guān)于的性質(zhì)都可以通過仔細(xì)考察楊輝三角形而得到。例如（3）單峰性當(dāng)n為偶數(shù)時(shí)，有

當(dāng)n為奇數(shù)時(shí)，有

組合恒等式有關(guān)二項(xiàng)式系數(shù)的恒等式至今已發(fā)現(xiàn)的就有上千個(gè)，而且還在不斷的發(fā)展。這些組合恒等式在許多算法分析中起著重要的作用，這里給大家介紹常用的幾個(gè)。等式1證明：在二項(xiàng)式定理中令x=y=1即可。等式2證明：在在二項(xiàng)式定理中令x=-1,y=1,得

將上式整理一下即得等式2.由等式1，可推得：且推得：等式3證明：對(duì)等式等式兩邊在x=1處求導(dǎo)數(shù)，得6.4.1遞推關(guān)系實(shí)例例6.17Hanoi塔問題現(xiàn)有A，B，C三根立柱以及n個(gè)大小不等的中空?qǐng)A盤，這些圓盤自小到大套在A柱上形成塔形，如圖6.3所示。要把n個(gè)圓盤從A柱上搬到C柱上，并保持原來的順序不變，要求每次只能從一根立柱上拿下一個(gè)圓盤放在另一根立柱上，且不允許大盤壓在小盤上。問至少要搬多少次？解：記T(n)為n個(gè)圓盤從A柱搬到C柱所需的最小次數(shù)。整個(gè)搬動(dòng)過程可以分成三個(gè)階段：（1）將套在A柱上面的n-1個(gè)圓盤從A柱按要求搬到B柱，搬動(dòng)次數(shù)為T(n-1);（2）把A柱上最下面的那個(gè)圓盤搬到C柱上，搬動(dòng)次數(shù)為1；（3）把B柱上的n-1個(gè)圓盤按要求搬到C柱上，搬動(dòng)次數(shù)為T(n-1).由加法原理知:T(n)=2T(n-1)+1,又T(0)=0，所以有如下帶有初值的遞推關(guān)系：

例6.18Fibonacci數(shù)列序列1，1，2，3，5，8，13，21，34，…中，每個(gè)數(shù)都是它前兩者之和，這個(gè)序列稱為Fibonacci數(shù)列。它在算法分析和近代優(yōu)化理論中起著重要作用，又具有很奇特的數(shù)學(xué)性質(zhì)。該數(shù)列來源于1202年由意大利著名數(shù)學(xué)家Fibonacci提出的一個(gè)有趣的兔子問題：有雄雌一對(duì)小兔，一個(gè)月后長(zhǎng)大，兩月起往后每月生（雄雌）一對(duì)兔。小兔亦同樣如此。設(shè)一月份只有一對(duì)小兔，問一年后共有多少對(duì)兔子？更一般此問題可以變?yōu)閚個(gè)月后共有多少對(duì)兔子？將開始有的一對(duì)小兔的月份視為第一個(gè)月，用Fn表示在第n個(gè)月的兔子數(shù)，顯然F1=F2=1.其次，可以看出：Fn=前一個(gè)月兔子數(shù)+本月新增兔子數(shù)=Fn-1+Fn-2因?yàn)橹挥星皟蓚€(gè)月的兔子到本月恰好能生出一對(duì)小兔。所以{Fn}定解問題為6.4.2遞推關(guān)系求解我們先討論一元常系數(shù)線性齊次遞推關(guān)系的求解。一元常系數(shù)線性齊次遞推關(guān)系是指形如：H(n)=a1H(n-1)+a2H(n-2)+…+akH(n-k)其中n=k，k+1，…；a1，a2，…，ak是常數(shù)；ak≠0的遞推關(guān)系。對(duì)上述遞推關(guān)系，只需初始值H(0),H(1),…,H(k-1)給定，就可唯一確定，故遞推關(guān)系稱為k階的。上式也可以寫成H(n)-a1H(n-1)+a2H(n-2)+…+akH(n-k)=0(*)我們稱方程為遞推關(guān)系(*)的特征方程。它的k個(gè)根q1,q2,…,qk稱為該遞推關(guān)系的特征根。其中qi(i=1,2,…,k)是復(fù)數(shù)。不難看出，因?yàn)閍k≠0，所以0不是遞推關(guān)系(*)的特征根。引理6.1設(shè)q是一個(gè)非零的復(fù)數(shù)，則H(n)=qn是遞推關(guān)系(*)的一個(gè)解當(dāng)且僅當(dāng)q是它的一個(gè)特征根。證明：H(n)=qn是遞推關(guān)系(*)的解

qn-a1qn-1-a2qn-2-…-akqn-k=0

qn-k(qk-a1qk-1-a2qk-2-…-ak)=0

qk-a1qk-1-a2qk-2-…-ak=0(q≠0)

q是遞推關(guān)系(*)的特征根。引理6.2設(shè)h1(n)和h2(n)是遞推關(guān)系(*)的兩個(gè)解，c1和c2是任意常數(shù)，則c1h1(n)+c2h2(n)也是遞推關(guān)系(*)的解。證明：把c1h1(n)+c2h2(n)代入(*)式的左邊得[c1h1(n)+c2h2(n)]-a1[c1h1(n-1)+c2h2(n-1)]-…-ak[c1h1(n-k)+c2h2(n-k)]=[c1h1(n)-a1c1h1(n-1)-…-akc1h1(n-k)]]+[c2h2(n)-a1c2h2(n-1)-…-akc2h2(n-k)]=c1[h1(n)-a1h1(n-1)-…-akh1(n-k)]+c2[h2(n)-a1h2(n-1)-…-akh2(n-k)]（h1(n)和h2(n)是(*)的解）=0所以c1h1(n)+c2h2(n)是遞推關(guān)系(*)的解。由兩個(gè)引理可以知道，如果q1,q2,…,qk是遞推關(guān)系(*)的特征根，且c1,c2,…,ck是任意常數(shù)，那么

H(n)=c1q1n+c2q2n+…+ckqkn是遞推關(guān)系(*)的解。如果對(duì)于遞推關(guān)系(*)的每個(gè)解h(n)都可以選擇一組常數(shù)c1’,c2’,…,ck’使得

h(n)=c1’q1n+c2’q2n+…+ck’qkn成立，則稱c1q1n+c2q2n+…+ckqkn是遞推關(guān)系(*)的通解，其中c1,c2,…,ck為任意常數(shù)。定理6.15設(shè)q1,q2,…,qk是遞推關(guān)系(*)的k個(gè)互不相同的特征根，則

H(n)=c1q1n+c2q2n+…+ckqkn是遞推關(guān)系(*)的通解。證明：由前面的分析可知H(n)是遞推關(guān)系(*)的解。設(shè)h(n)是這個(gè)遞推關(guān)系的任意一個(gè)解，則h(n)由k個(gè)初值h(0)=b0,h(1)=b1,…,h(k-1)=bk-1唯一地確定，所以有

如果方程組有唯一解c1’,c2’,…,ck’，這說明可以找到k個(gè)常數(shù)c1’,c2’,…,ck’使得h(n)=c1’q1n+c2’q2n+…+ck’qkn成立，從而證明了c1q1n+c2q2n+…+ckqkn是該遞推關(guān)系的通解?？疾齑朔匠探M，把它寫成矩陣形式

它的系數(shù)矩陣是著名的范德蒙矩陣，因?yàn)楫?dāng)i≠j時(shí)，qi≠qj，可以證明系數(shù)矩陣是滿秩矩陣，這也就是說方程組有唯一解。例6.19

求解Fibonacci數(shù)列的遞推關(guān)系解：這個(gè)遞推關(guān)系為常系數(shù)線性齊次遞推關(guān)系，其特征方程是x2-x-1=0，特征根是，所以通解是因?yàn)椋氤踔祦泶_定c1和c2，得到方程組解這個(gè)方程組得,所以滿足初值條件的特解是

n=0,1,….

對(duì)于k階常系數(shù)線性齊次遞推關(guān)系，當(dāng)特征根q1,q2,…,qk都不相等時(shí)，我們已經(jīng)給出了求通解的方法。但是當(dāng)q1,q2,…,qk中有重根時(shí)，這種方法就不適用了。例6.20

求解遞推關(guān)系：解：它的特征方程是x2-4x-4=0，特征根是q1=q2=2。由定理6.15可知2n是它的解。但必須找一個(gè)與2n線性無關(guān)的解，不妨嘗試n2n，把它代入原遞推關(guān)系得

n2n-4(n-1)2n-1+4(n-2)2n-2=n2n-(n-1)2n+1+(n-2)2n=2n[n-2(n-1)+(n-2)]=0.這說明n2n也是解，且它與遞推關(guān)系的另一解2n線性無關(guān)，所以原遞推關(guān)系的通解是

H(n)=c12n+c2n2n實(shí)際上設(shè)遞推關(guān)系：

H(n)-a1H(n-1)-a2H(n-2)-…-akH(n-k)=0(n≥k，ak≠0)的特征方程是

xk-a1xk-1-a2xk-2-…-ak=0令

P(x)=xk-a1xk-1-a2xk-2-…-ak，

Pn(x)=xn-kP(x)=xn-a1xn-1-a2xn-2-…-akxn-k如果q是P(x)的二重根，則q也是Pn(x)的二重根，那么q也是Pn(x)的微商的根，其中

=nxn-1-a1(n-1)xn-2-a2(n-2)xn-3-…-ak(n-k)xn-k-1因此q是