組合數(shù)學(xué)課件：基本計(jì)數(shù)原理

基本計(jì)數(shù)原理2.1和式與積式

2.2加法原理和乘法原理

2.3鴿巢原理

2.4Ramsey問題

2.5排列與組合

2.6排列與組合的進(jìn)一步討論

2.7二項(xiàng)式系數(shù)

2.8楊輝三角（或稱賈憲三角）

2.9多項(xiàng)式定理

2.10集合的劃分的計(jì)數(shù)2.1和式與積式2.1.1和式(Sumformula）

定義1

a0+a1+…+an稱為a0,a1,…,an的和式，常簡(jiǎn)記為或(2.1.1)“∑”稱為和號(hào)；“ai”稱為和式的通項(xiàng)或累加項(xiàng)，“i”為通項(xiàng)的下標(biāo)或足標(biāo)，用來標(biāo)識(shí)和式中不同的項(xiàng)。下標(biāo)i的變化范圍常以邏輯表達(dá)式的形式寫在和號(hào)下面，簡(jiǎn)單時(shí)也以羅列的形式表示在和號(hào)“∑”的上、下方，下邊指明初值，上邊指明終值，其變化取由初值到終值的相繼遞增整數(shù)。若令Nn表示前n+1個(gè)自然數(shù)所成之集，即Nn={0,1,2,…,n}，則（2.1.1）式還可表示為

命題1

用和號(hào)∑表示的和式中，通項(xiàng)下標(biāo)的改變不影響和式。例如都表示同一和式。當(dāng)通項(xiàng)下標(biāo)不取連續(xù)整數(shù)時(shí)，也希望能尋找一些規(guī)律，以便于用和式寫出簡(jiǎn)單的表示式，下面給出一些特殊和式的例子。1.奇數(shù)做下標(biāo)2.偶數(shù)做下標(biāo)3.雙下標(biāo)4.給定數(shù)42的所有因子之和

1+2+3+6+7+14+21+42=5.求給定數(shù)42的真因子個(gè)數(shù)6.空和（由邏輯表達(dá)式不成立所致，約定空和的值為0）命題2（加法的交換律）

如果（i1,i2,…,ii）是(1,2,…,n)的一個(gè)置換，則命題3（加法的結(jié)合律）如果1≤m≤n，則命題4（乘法交換律）命題5（乘法對(duì)加法的分配律）推論·

對(duì)（2.1.1）式的求和算法

№1定義數(shù)組A(0∶N)；

№2對(duì)i=0,N

輸入A(i)；

№3

S

0；（累加器S置0）

№4對(duì)i=0,N,做

S

S+A(i)；（S中存放（2.1.1）式的值）；

№5輸出S；

№6結(jié)束?！?/p>

對(duì)（2.1.2）及（2.1.3）式的求和算法

№1定義數(shù)組A（0：N）；(N=2k+1)

№2對(duì)j=0,N,輸入A(j)；

№3

S1

0;S2

0;

№4對(duì)j=1,N,步長(zhǎng)取2，做

S1

S1+A(j);（S1中存放（2.1.2）式的值）

№5對(duì)j=0,N,步長(zhǎng)取2，做

S2

S2+A(j)；（S2中存放（2.1.3）式的值）

№6輸出S1,S2;

№7結(jié)束。·

對(duì)（2.1.4）式的求和算法

№1定義數(shù)組A(1：M,1：N)；

№2對(duì)i=1,M

對(duì)j=1,N

輸入A(i,j)；

№3

S

0；

№4對(duì)i=1,M,做 對(duì)j=1,N,做

S

S+A(i,j)；（S中存放（2.1.4）式的值）

№5輸出S;

№6結(jié)束?！?/p>

對(duì)（2.1.5）式及（2.1.6）式的求和算法№1

N

42;S

0；（累加器置0）T

0；（計(jì)數(shù)器置0）№2對(duì)k=2,N/2,做若N/k=［N/k］則

S

S+k；（S中存放42的真因子和）

T

T+1；（T中存放42的真因子數(shù)）№3打印S+1+N,T；№4結(jié)束。2.1.2積式（Productformula）與和式類似,還可以并行的討論積式或更一般地寫為注意到若附加條件xi＞0(1≤i≤n)，則即積式可轉(zhuǎn)化為和式來處理。條件xi＞0并無實(shí)質(zhì)性的限制，因若某個(gè)xi=0，則整個(gè)積式為0，又恰有k項(xiàng)取負(fù)時(shí)，可先對(duì)（2.1.8）式兩邊乘(-1)k，以確保xi＞0，最后再將其恢復(fù)過來。例如：（1）n的階乘n!還可遞歸定義如下：0!∷=1（“∷=”取自BNF，讀作定義為）n!∷=n·(n-1)!（2）矩陣An×n的跡=·

對(duì)（2.1.8）式的算法№1定義數(shù)組X(0∶N)；№2對(duì)i=0,N,輸入X(i)；№3

M

1；（累乘器M置1）№4對(duì)i=0,N,做

M

M*

X(i)；№5打印M；№6結(jié)束。·

對(duì)（2.1.9）式的算法№1輸入N

№2

M

1；（累乘器M置1）№3對(duì)k=2,N,做

M

M*k；№4打印M；№5結(jié)束。對(duì)（2.1.9）式亦可改用遞歸算法，其主體語句為ifN=0thenf（N）=1elsef（N）=N*f（N-1）;·

對(duì)（2.1.10）式的算法№1定義數(shù)組A(1∶N,1∶N)；№2對(duì)i=1,N,輸入A(i,i)；№3

M

1；（累乘器M置1）№4對(duì)i=1,N,做

M

M*A(i,i);

№5打印″方陣An×n的跡是″M

№6結(jié)束。·

求 的算法№1輸入N；№2

E

1；（累加器E置1）№3

T

1；（累乘器T置1）№4對(duì)k=1,N,做

T

T/k；E

E+T；№5打印E；№6結(jié)束?！?/p>

求和式 的算法№1輸入N,A;

№2

S

0;B

1；№3對(duì)k=1,N,做

B

B*A;S

S+B；№4打印N,A,S；№5結(jié)束。2.2加法原理和乘法原理2.2.1加法原理（AdditionPrinciple）設(shè)A，B為兩個(gè)不同類事件，若事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A或者事件B”有m+n種產(chǎn)生方式。用集合論的術(shù)語，加法原理也可描述如下：設(shè)S為m元集，T為n元集，如果S∩T=￠,則S∪T為m+n元集。

推廣的加法原理是：如果Ti為ni元集（i=1,2,…,r），并且π={T1,T2,…,Tr}形成 的一個(gè)劃分，則 為元集。加法原理的通俗說法是：部分之和等于全體。約束條件是：(1)討論范圍局限于有限集；(2)任意兩個(gè)部分都不相交。若有相交的情形出現(xiàn)，則要用到后面討論的包含排斥原理。

例1

小于100的正偶數(shù)有49個(gè)，小于100的正奇數(shù)有50個(gè)，則小于100的正整數(shù)有49+50=99個(gè)。2.2.2乘法原理(MultiplicationPrinciple)

設(shè)A，B為二不同類事件，若事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A與事件B”有mn種產(chǎn)生方式用集合論的術(shù)語，乘法原理也可描述如下：設(shè)S，T為二集，若S為m元集，T為n元集，則S與T的叉積之集合S×T為mn元集。推廣的乘法原理是：如果Ti為ni元集(i=1,2,…,r)，則 元集。

推論設(shè)X為n元集，則是nr元集。這是乘法原理中取Ti=X(i=1,2,…,r)均為n元集的特殊情形。

例2

從u到v有3條不同的道路，從v到w有2條不同的道路，則從u經(jīng)v到w有3×2=6條不同的道路。

例3

某高級(jí)語言的標(biāo)識(shí)符規(guī)定長(zhǎng)度最多為6位，其中第一位限取字母，其余各位可取字母，也可取數(shù)字。求所有可能出現(xiàn)的標(biāo)識(shí)符總數(shù)。

解長(zhǎng)為1的只有26個(gè)；長(zhǎng)為2的由乘法原理有26(26+10)個(gè)；……長(zhǎng)為6的由乘法原理有26(26+10)5個(gè)。最后由加法原理，所有可能出現(xiàn)的標(biāo)識(shí)符總數(shù)為

例4

用四子于兩路棋盤，能擺出34=81種兩兩不同的棋局；用九子于三路棋盤，能擺出39=19683種兩兩不同的棋局；用16子于四路棋盤，能擺出316=43046721種兩兩不同的棋局，用25子于五路棋盤，能擺出325=847288609443種兩兩不同的棋局；……用361子于十九路棋盤，能擺出3361種兩兩不同的棋局。

注:

本例指圍棋，現(xiàn)代圍棋采用十九路，即有19×19=361個(gè)交叉點(diǎn)可落黑子、白子或留空。

例5

求含有數(shù)字1的4位數(shù)的個(gè)數(shù)。

解先求不含有1的4位數(shù)的個(gè)數(shù)，即求由{0,2,3,4,5,6,7,8,9}9個(gè)數(shù)字組成的4位數(shù)的個(gè)數(shù)（第一位不得出現(xiàn)0）。由乘法原理，有8×9×9×9=5832個(gè)又4位數(shù)共有9999-999=9000個(gè)。因此,含有數(shù)字1的4位數(shù)的個(gè)數(shù)為9000-5832=3168。注：本例中用到了一種求補(bǔ)原理。提法是：由總數(shù)中去掉不滿足某些性質(zhì)的物件數(shù)，則剩余者即為滿足該性質(zhì)的物件總數(shù)。2.3鴿巢原理2.3.1鴿巢原理（Thepigeonholeprinciple）之一若在n個(gè)盒子中放有n+1個(gè)物件，則至少有一個(gè)盒子中放有兩個(gè)或更多的物件。

證明若每個(gè)盒子中至多存放1個(gè)物件，則n個(gè)盒子中至多存放n個(gè)物件，但因最初已有n+1個(gè)物件，這是不可能的。請(qǐng)注意，鴿巢原理沒有能力指出究竟哪個(gè)盒子中放有兩個(gè)或更多的物件,若要做到這一點(diǎn)，除非逐個(gè)檢查n個(gè)盒子。即應(yīng)用鴿巢原理只能證明某種安排或某些現(xiàn)象的存在性，但卻不能用來構(gòu)造這種安排或找出某些現(xiàn)象中的具體例子。

例113個(gè)人中，至少有2個(gè)人的生日在同一個(gè)月。

例2

從1到2n的正整數(shù)中任取n+1個(gè)數(shù)，則這n+1個(gè)數(shù)中至少有一對(duì)數(shù)，其中一個(gè)數(shù)可整除另一個(gè)數(shù)。

證明設(shè)所取的n+1個(gè)數(shù)是a1,a2,…,an,an+1將序列中每個(gè)數(shù)都寫成一個(gè)奇數(shù)乘以2的次冪的形式，得到相應(yīng)序列

例3某次會(huì)議有n位代表參加，已知每一位代表至少認(rèn)識(shí)其余n-1位中的一位，則n位代表中至少有兩位認(rèn)識(shí)的人數(shù)相等。

證明n位代表認(rèn)識(shí)的人數(shù)有1,2,…,n-1，由鴿巢原理知至少兩位代表認(rèn)識(shí)的人數(shù)相等。

例4

給定m個(gè)整數(shù)a1,a2,…,am。則至少存在整數(shù)k和l(1≤k≤l≤m)，使得證明構(gòu)造序列s1=a1,s2=a1+a2,…,sm=a1+a2+…+am (2.3.1)

則有s1＜s2

＜…＜sm

如下分兩種情況討論：

(a)若有一個(gè)sh,使m|sh,則命題已明（此時(shí)k=1,l=h）;

(b)設(shè)若單調(diào)增序列（2.3.1）式中任何一個(gè)元素都不能被m整除。令sh≡rh(modm)(h=1,2,…,m),則因0＜rh＜m，由鴿巢原理，序列r1,r2,…,rm相對(duì)于序列1,2,…,m-1必要選中i≠j（不妨設(shè)i＜j）使ri=rj,從而這時(shí)

例5設(shè)a1,a2,a3為任意三個(gè)整數(shù)，(b1,b2,b3)為(a1,a2,a3)的一個(gè)任意置換，則(ai-bi)(i=1,2,3)中至少有一個(gè)是偶數(shù)。

證明由鴿巢原理a1,a2,a3中至少有兩個(gè)數(shù)同為奇數(shù)或同為偶數(shù)，不妨設(shè)a1,a2同為奇數(shù)，又b1,b2中至少有一個(gè)是奇數(shù)，從而a1-b1與a2-b2中至少有一個(gè)偶數(shù),原因是二奇數(shù)之差必為偶數(shù)。當(dāng)a1,a2同取偶數(shù)時(shí)，討論過程類似（因二偶數(shù)之差必為偶數(shù)）。2.3.2鴿巢原理之二設(shè)有n個(gè)正整數(shù)q1,q2,…,qn,若將 個(gè)物件放進(jìn)n個(gè)盒子，則或者第一個(gè)盒子中至少放進(jìn)了q1個(gè)物件，或者第二個(gè)盒子中至少放進(jìn)了q2個(gè)物件，……或者第n個(gè)盒子中至少放進(jìn)了qn個(gè)物件。

證明若第i個(gè)盒子中至多放進(jìn)qi-1個(gè)物件(i=1,2,…,n)，則放進(jìn)n個(gè)盒子的物件總數(shù)是這與最初放進(jìn)的物件總數(shù)是矛盾。

注：鴿巢原理之一是鴿巢原理之二當(dāng)qi(i=1,2,…,n)都取2時(shí)的特殊形式。

推論1

m個(gè)物件放進(jìn)n個(gè)盒子，則至少有一個(gè)盒子里放的物件數(shù)不少于［(m-1)/n］+1。

推論2

若n(r-1)+1個(gè)物件放進(jìn)n個(gè)盒子中，則至少有一個(gè)盒子放進(jìn)了r個(gè)或更多的物件。

推論3

若q1,q2,…,qn是n個(gè)正整數(shù)，而且，則qi(i=1,2,…,n)中至少有一個(gè)不小于r。

例1

把兩個(gè)大小不等的同心圓盤都劃分成20個(gè)相等的扇區(qū)。在大圓盤的20個(gè)扇區(qū)中分別填入10個(gè)0及10個(gè)1,對(duì)小圓盤只要求用0或1兩種數(shù)字把扇區(qū)填滿而不限制雙方的個(gè)數(shù)。斷言存在某種配合，可使小圓盤的20個(gè)扇區(qū)中至少有10個(gè)與大圓盤的對(duì)應(yīng)扇區(qū)中數(shù)字相同。

證明固定小圓盤并讓大圓盤依次轉(zhuǎn)過20個(gè)扇面,這使小圓盤的每個(gè)扇面恰碰到10次與自己相同的數(shù)字。對(duì)整個(gè)小圓盤來說，相同的數(shù)字總數(shù)應(yīng)是20×10=200。從而大圓盤平均轉(zhuǎn)過一個(gè)扇面使大小圓盤對(duì)應(yīng)扇面數(shù)字相同者應(yīng)是200/20=10。根據(jù)鴿巢原理，至少有一次，其中對(duì)應(yīng)扇面數(shù)字相同者不少于10。

例2

（P.ErdosandA.Szekeres,1935）試證任意n2+1個(gè)實(shí)數(shù)所成的序列a1,a2,…,an2+1中都含有一個(gè)長(zhǎng)為n+1的遞增子序列或遞減子序列。

證明證明思路:假定沒有長(zhǎng)為n+1的遞增子序列，必可推得存在長(zhǎng)為n+1的遞減子序列或反之。對(duì)每個(gè)k(k=1,2,…,n2+1)，令mk表以ak為首的最長(zhǎng)遞增子序列的長(zhǎng)度。若有一個(gè)mk＞n,則命題已明。下設(shè)對(duì)每個(gè)k(k=1,2,…,n2+1),mk≤n，即假設(shè)不存在任何一條長(zhǎng)度大于n的遞增子序列。因?qū)γ總€(gè)k(k=1,2,…,n2+1),mk≥1，這使n2+1個(gè)正整數(shù)m1,m2,…,mn2+1都落在1,2,…,n之間。由鴿巢原理之二的推論2（取r=n+1的特殊形式），上述n2+1個(gè)整數(shù)中必有n+1個(gè)完全相同。不失一般性，令其中，1≤k1＜k2＜…＜kn+1≤n2+1。下證ak1,ak2,…,akn+1構(gòu)成一長(zhǎng)為n+1的遞增子序列。用反證法，設(shè)若不然，即存在某個(gè)i(i=1,2,…,n)使 ，則因ki＜ki+1，故可對(duì)以 為首的最長(zhǎng)遞增子序列前再置以而得到一條以為首的最長(zhǎng)遞增子序列，但這將導(dǎo)致 ，與 矛盾。結(jié)論是 ，而這對(duì)每個(gè)i(i=1,2,…,n)都是對(duì)的，從而有 。2.4Ramsey問題2.4.1

Ramsey問題

問題16人行，必有3人或互相認(rèn)識(shí)，或互不認(rèn)識(shí)。類似于問題1，還有問題2和問題3。問題29人行，或有3人互相認(rèn)識(shí)，或有4人互不認(rèn)識(shí)。

問題318人行，定有4人或互相認(rèn)識(shí)，或互不認(rèn)識(shí)。上述問題，可用圖論的方法予以解決。即將n個(gè)人視為n個(gè)頂點(diǎn)（設(shè)n個(gè)頂點(diǎn)中任意3點(diǎn)不共線），并構(gòu)造n點(diǎn)完全圖Kn，對(duì)Kn中的邊染以紅、藍(lán)兩種顏色，2人相識(shí)染紅色，不相識(shí)染藍(lán)色，最后求證圖中必存在同色三角形，或同色四邊形。對(duì)于問題1，轉(zhuǎn)化為圖論問題即為如下定理：

定理1

K6中的邊染以紅、藍(lán)兩種顏色，則必存在同色三角形。證明令K6=(V,E),V={v0,v1,…,v5}，任選一點(diǎn)v0，由鴿巢原理，v0與其余5個(gè)頂點(diǎn)所成的5條邊中必有3條屬于同色，不妨設(shè)為(v0,v1),(v0,v2),(v0,v3)，且均系紅色。此時(shí)，若v1,v2,v3兩兩連線中有一邊為紅色，設(shè)為(v1,v2)，則v0,v1,v2形成一同色紅色三角形；又如果v1,v2,v3兩兩連線無一為紅，則v1,v2,v3形成一同色藍(lán)色三角形。如圖2.4.1所示。注意:6是染兩色時(shí)出現(xiàn)同色三角形的最小點(diǎn)數(shù)。若取5點(diǎn)，則可舉出反例(如圖2.4.2所示)，即可使K5不存在同色三角形。圖2.4.1K4二染色(帶有限制)圖2.4.2K5二染色

定理2

K9中的邊染以紅、藍(lán)2色，則或有一同色三角形，或有另一同色完全四邊形。

證明第一步：若將K9染色，則其中必存在一點(diǎn)，從這點(diǎn)到其余8點(diǎn)的邊中，同色者不等于3。設(shè)若不然，K9中每個(gè)點(diǎn)與其余8個(gè)頂點(diǎn)所成之邊都是恰染3條紅色（或藍(lán)色），現(xiàn)從每個(gè)端點(diǎn)統(tǒng)計(jì)各點(diǎn)引出的這些紅色（或藍(lán)色）邊的總數(shù)應(yīng)是3×9=27，但這是不可能的，因每條邊關(guān)聯(lián)兩個(gè)端點(diǎn)，對(duì)這種統(tǒng)計(jì)，所有點(diǎn)引出的紅色（或藍(lán)色）連邊的總數(shù)應(yīng)為偶數(shù)。結(jié)論是，必存在一點(diǎn)，從該點(diǎn)到其余各點(diǎn)的邊染紅色（或藍(lán)色）者一定大于3或小于3。

第二步：（1）設(shè)從v0向其余8點(diǎn)引出的邊中，染紅色者多于3條，即至少有4條，不妨設(shè)為(v0,v1),(v0,v2),(v0,v3),(v0,v4)。再看v1,v2,v3,v4所成完全圖K4，若有一紅色邊，則其兩端點(diǎn)連同v0已構(gòu)成紅色三角形,否則全為藍(lán)色，這時(shí)v1,v2,v3,v4就構(gòu)成一藍(lán)色完全四邊形。

（2）設(shè)從v0向其余8點(diǎn)引出的邊中，紅色邊少于3條，即至多有2條，這時(shí)從v0引出的藍(lán)色邊至少會(huì)有6條，不妨設(shè)為(v0,v1),(v0,v2),…,(v0,v6)。再看v1,v2,v3,v4,v5,v6所成完全圖K6，由定理1，其中若有紅色三角形，則結(jié)論已真；若K6中有藍(lán)色三角形，則其3個(gè)頂點(diǎn)連同v0即構(gòu)成一藍(lán)色完全四邊形，結(jié)論亦真。由（1）及（2），定理得證。注意：當(dāng)n＞9時(shí)，定理2自然成立。但當(dāng)n=8時(shí)，可舉出反例(如圖2.4.3所示)，即可使其既無同色三角形，又無同色完全四邊形。圖2.4.3K8二染色

定理3

若將K18染以紅、藍(lán)兩色，則一定會(huì)出現(xiàn)同色完全四邊形（或稱單色四面體）。

證明設(shè)K18的點(diǎn)集為V={v0,v1,…,v17}，考察v0到其余各點(diǎn)引出的17條邊，因只有紅、藍(lán)兩色，由鴿巢原理，至少有9條邊染以紅色（或藍(lán)色），進(jìn)一步，考察這9條邊與異于v0的9個(gè)端點(diǎn)所成的完全圖。由定理2，若K9中有一同色藍(lán)色完全四邊形，則問題已明；若K9中只有同色紅色三角形，該三角形的3個(gè)頂點(diǎn)連同v0即已構(gòu)成一個(gè)紅色完全四邊形。

與前邊問題類似，18是染兩色且有同色完全四邊形的最少點(diǎn)數(shù)。即可以構(gòu)造17點(diǎn)染兩色的K17，使其中不存在同色完全四邊形。其方法如下：對(duì)K17的點(diǎn)集V={v0,v1,…,v16}各點(diǎn)的下標(biāo)，構(gòu)造集合X、Y，使得X={1,2,4,8,9,13,15,16}

Y={3,5,6,7,10,11,12,14}

對(duì)i,j∈{0，1，2,…，15，16}，按以下規(guī)則染色：當(dāng)|i-j|∈X時(shí)，(vi,vj)染紅色；當(dāng)|i-j|∈Y時(shí)，(vvi,vj)染藍(lán)色。這樣構(gòu)造的K17不存在同色完全四邊形。作為練習(xí)，請(qǐng)讀者畫出該圖。將前面的問題加以推廣，對(duì)于K17可有如下定理：

定理4

若將K17的邊染以紅、藍(lán)、黃三色，則一定會(huì)出現(xiàn)一個(gè)同色三角形。

證明設(shè)V={v0,v1,…,v16}為K17的點(diǎn)集，任取一點(diǎn)v0，在v0與其余16點(diǎn)相連的邊中，因染有三色，由鴿巢原理知至少有［16/3］+1=6條邊染以同色。不妨設(shè)(v0,v1),

(v0,v2),…,(v0,v6)這6條邊染為紅色?？疾靨1,v2,v3,v4v5,v6組成的完全圖K6，分兩種情況討論：

（1）如果該K6中有一條邊為紅色，設(shè)為(v1,v2)，則v0,,

v1,v2所成三角形已是同色三角形，定理得證。（2）如果該K6中沒有紅色邊，即只染有黃、藍(lán)兩色，則由定理1，這個(gè)K6中就有同色三角形，定理同樣為真。特別地，定理4中的17點(diǎn)恰是染三色時(shí)的最少點(diǎn)數(shù)，亦即K16用三色涂染時(shí)，可以構(gòu)造一種圖形，使得其中不存在同色三角形。

考慮四位的二進(jìn)制數(shù)所成的集合V={0000，0001，0010,…,1111},若對(duì)V中的每個(gè)元素，施行按位加運(yùn)算“+”，即不考慮進(jìn)位，則（V,+）構(gòu)成一16階交換群，其中，0000為幺元。將V\{0000}分成三個(gè)不封閉的子集v1,v2,v3,

：v1={1100，0011，1001，1110，1000}

v2={1010，0101，0110，1101，0100}

v3={0001，0010，0111，1011，1111}然后構(gòu)造圖Γ，使其頂點(diǎn)與群的元素對(duì)應(yīng)，并按如下方法進(jìn)行三種顏色染色：

當(dāng)x+y∈Vi時(shí)，邊（x,y）染以顏色i，當(dāng)x∈Vi時(shí)，邊（0000，x）亦染以顏色i。這樣構(gòu)造的圖Γ不存在同色三角形。定理1和定理4分別是對(duì)完全圖K16和K17用兩種、三種顏色染色，證明存在同色三角形及最少點(diǎn)數(shù)的問題。若令r（3,3;2）(可簡(jiǎn)記為r（3，3）或r2)表示用兩種顏色涂染完全圖的邊存在三角形的最少點(diǎn)數(shù)，即有r(3,3;2）=r(3，3）=r2=6這就是Ramsey問題中的Ramsey數(shù)。

若進(jìn)一步將用兩種、三種顏色擴(kuò)展到用任意有限（不妨設(shè)成m）種顏色涂染完全圖的邊，則有r1=3，r2=6，r3=17，有人證明了r4=65。找出rm的準(zhǔn)確值是件困難的事情，目前僅知道以上幾種。

定理5

rm≤m·(rm-1-1)+2。

證明若令t=m·(rm-1-1)+2，從完全圖Kt的任一頂點(diǎn)v0引出的m·(rm-1-1)+1條邊中，由鴿巢原理必有rm-1條染為同一種顏色，不妨設(shè)(v0,v1),(v0,v2,…,(v0,vrm-1)均為紅色。v1,v2,…,vrm-1構(gòu)成一完全圖Krm-1

，若當(dāng)

（1）Krm-1

中有一條紅色邊，比如（v1,v2)，則v0,v1,v2就形成一紅色三角形。定理亦真。（2）Krm-1

中沒有紅色邊，則因其rm-1條邊只染有m-1種顏色，根據(jù)rm-1的定義知，這個(gè)Krm-1中必有一同色三角形。定理亦真。推論1

證明用數(shù)學(xué)歸納法。

(1)基礎(chǔ)步：當(dāng)m=1時(shí)，r1=3≤1+1+1，不等式成立；

(2)歸納步：設(shè)小于等于m-1時(shí)命題成立。由定理5知rm≤m!(rm-1-1)+2

由歸納假設(shè)得即這就證明了對(duì)m結(jié)論亦成立。命題得證。推論2

rm≤［m!·e］+1。證明因?yàn)樽⒁獾?/p>

推論3

rm≤3m!。證明因rm≤［m!e］+1＜m!e+1＜3m!+1，故rm≤3m!。一般地，對(duì)p,q∈Z+，

r(p,q)∈Z+。對(duì)n∈Z+，n≥r(p,q)，若對(duì)完全圖Kn的邊任意染以紅、藍(lán)兩色的一種，則染色后Kn中或存在一紅色Kp，或存在一藍(lán)色Kq。

Ramsey數(shù)r(p,q;2)簡(jiǎn)記為r(p,q)，對(duì)定理2（問題2）即為r(3,4;2)=r(3,4)=9

又已知r(3,5)=14，r(4,4)=18（定理3）。許多教科書中都有關(guān)于已知的、為數(shù)不多的一些r(p,q)的列表，其中有的僅給出了上下界。

定理6

設(shè)p,q∈Z+，則對(duì)Ramsey數(shù)r(p,q)有

(1)r(p,q)=r(q,p);

(2)r(p,1)=r(1,q)=1;

(3)r(p,2)=p,r(2,q)=q。

證明

(1)由Ramsey數(shù)的對(duì)稱性可得。

(2)是顯然的。

(3)的第一式指，若Kp中有一條邊染以紅、藍(lán)二色之一，則顯見該邊已構(gòu)成一紅色（或藍(lán)色）完全子圖K2;若不存在紅色（或藍(lán)色）K2，則Kp全染以藍(lán)色（或紅色），那么，Kp便構(gòu)成了一藍(lán)色（或紅色）完全子圖。由Ramsey數(shù)的對(duì)稱性有r(2,q)=q。

定理7

對(duì)p,q∈Z+，p≥2,q≥2有r(p,q)≤r(p,q-1)+r(p-1,q)(2.4.1)

證明令r(p,q)≤r(p,q-1)+r(p-1,q)=n，考慮這n個(gè)點(diǎn)構(gòu)成的完全圖Kn，將Kn著以紅、藍(lán)二色。需要證明的是必定或出現(xiàn)紅色完全子圖Kp，或出現(xiàn)藍(lán)色完全子圖Kq。為此，從這n個(gè)點(diǎn)中任選一點(diǎn)v，考慮v與其余n-1個(gè)點(diǎn)連線所成的n-1條邊，設(shè)這n-1條邊中有紅色n1條，藍(lán)色n2條，這時(shí)n1+n2+1=n=r(p,q-1)+r(p-1,q)

如下分情況討論：

(1)若n1≥r(p-1,q)，可考察n1條邊所有異于v的端點(diǎn)構(gòu)成的完全子圖Kn1。這時(shí)，Kn1中必或有紅色完全子圖Kp-1，或有藍(lán)色完全子圖Kq。若是后者，則結(jié)論已明，若是前者，則紅色Kp連同v點(diǎn)一起便構(gòu)成紅色子圖Kp。命題亦真。(2)若n1＜r(p-1,q)，則n2+1＞r(p,q-1)。于是，n2≥r(p,q-1)。剩下的討論類似于(1)。無論是(1)還是(2)，都證明了Kn上必定或出現(xiàn)紅色Kp，或出現(xiàn)藍(lán)色Kq。本定理當(dāng)r(p,q-1)和r(p-1,q)都為偶數(shù)時(shí)，(2.4.1)式的不等式嚴(yán)格成立。事實(shí)上，當(dāng)r(p,q-1)和r(p-1,q)都為偶數(shù)時(shí)，有r(p,q)≤r(p,q-1)+r(p-1,q)-1

令 n=r(p,q-1)+r(p-1,q)-1

設(shè)v是完全圖Kn上的任意一點(diǎn)，則v恰是n-1條邊的公共端點(diǎn)。由于n-1是偶數(shù)，因此這些邊中可能紅、藍(lán)邊均為偶數(shù),也可能紅、藍(lán)邊均為奇數(shù)。如下證明Kn上至少有一點(diǎn)vi，它恰是偶數(shù)條紅邊的公共端點(diǎn)。采用反證法，用tj表示與vj關(guān)聯(lián)的全部紅邊數(shù)，j=1,2,…,n。若tj無一為偶，則t=t1+t2+…+tn也是奇數(shù)，從而，Kn上的全部紅邊數(shù) ，矛盾。因vi是恰與偶數(shù)條紅邊關(guān)聯(lián)的公共頂點(diǎn)，所以，以vi為一端的r(p,q-1)+r(p-1,q)-2條邊中，或有不少于r(p,q-1)條紅邊,或有不少于r(p-1,q)條藍(lán)邊（因紅邊不多于r(p,q-1)-2條）。若是前者，則vi連同與之關(guān)聯(lián)為紅邊的其余r(p,q-1)個(gè)端點(diǎn)構(gòu)成的完全圖中，按r(p,q-1)的定義，一定或存在同色完全子圖Kp

，或存在同色完全子圖Kq

。若是后者，結(jié)論亦然。定理8(2.4.2)

證明對(duì)p+q施用歸納法。

(1)基礎(chǔ)步：只要p、q中有一個(gè)為1，或有一個(gè)為2，(2.4.2)式中的等號(hào)成立。p+q≤5時(shí)，易證(2.4.2)式成立。(2)歸納步：設(shè)小于等于p+q-1時(shí)(2.4.2)式恒為真，對(duì)p+q，據(jù)定理7和歸納假設(shè)，有

定理9

對(duì)p∈Z∧p≥2,有

r(p,p)≥2p/2 (2.4.3)

證明當(dāng)p=1時(shí)，r(1,1)=1,21/2= ，(2.4.3)式不成立；當(dāng)p=2時(shí)，r(2,2)=2=22/2，(2.4.3)式成立。對(duì)p≥3,設(shè)V={v1,v2,…,vn}是完全圖Kn的頂點(diǎn)集，若用紅、藍(lán)二色對(duì)Kn的邊著色，由于每邊有且僅有兩種可能的染色選擇，所以，共有種不同的著色方案。用Sn表示全部雙色Kn所成之集,則令事實(shí)上，從n個(gè)頂點(diǎn)中確定p個(gè)頂點(diǎn)，共有種不同方案,而對(duì)于p個(gè)確定的頂點(diǎn)，Kp上條邊全著紅色只有一種可能，故包含某特定紅色Kp的雙色Kn恰有 個(gè)。當(dāng)2p/2＞n時(shí),有其中,基于以下事實(shí):

當(dāng)p=3時(shí)，該式成立，對(duì)于不小于3的一切整數(shù)p，有p!＞2p-1，對(duì)于不小于4的一切整數(shù)p，又有2p-1≥2p/2+1。由對(duì)稱性，不難證得對(duì)藍(lán)色類似有其中，={S|S∈Sn

且藍(lán)色Kp

S},Sn為雙色Kn所成之集。

綜上所述，只要完全圖頂點(diǎn)數(shù)n＜2p/2，則必存在這樣的雙色Kn，其上不含任何同色Kp。故知r(p,p)≥2p/2

2.4.2Ramsey定理

1.先將r(p,q;2)推廣到r(p,q;k)，k為任一正整數(shù)

采用圖論的術(shù)語：r(p,q;k)為滿足如下條件的最小正整數(shù)n。用兩種顏色對(duì)Kn染色時(shí)，可用同一種顏色涂染Kn的任意2點(diǎn)連線（一邊）；任意3點(diǎn)（不共線）所成三角形的邊；任意4點(diǎn)（不共面）所成四面體的棱；……任意k點(diǎn)所成的完全圖Kk的邊（有些教科書中稱其為k級(jí)邊，相應(yīng)地，稱n個(gè)點(diǎn)連同其所有k級(jí)邊所成之完全圖為k級(jí)完全圖，記為

，常稱其為超圖）。則Kn中或者存在p點(diǎn)完全子圖Kp，其上的所有k級(jí)邊全染為同一顏色；或者存在q點(diǎn)完全子圖Kq，其上的所有k級(jí)邊全染為同一顏色。

采用集合論的術(shù)語：對(duì)n元集合V={v1,v2,…,vn}，當(dāng)n充分大時(shí)，對(duì)V的2元子集族S={X|X

V,|X|=2}，及S的任一2-拆分{S1,S2}，使得或者存在V的p元子集V1，滿足V1的2元子集族包含在S1中;或者存在V的q元子集V2，滿足V2的2元子集族包含在S2中。

2.將r(p,q;k)推廣到r(p1,p2,…,pm;k)

r(p1,p2,…,pm;k)表示用m種顏色對(duì)Kn的k級(jí)邊染色，尋求使Kn存在pi點(diǎn)完全子圖Kpi，其上的所有k級(jí)邊全染為同一顏色的最小的正整數(shù)n，其中i∈{1,2,…,m}?；蛘弑硎灸硞€(gè)最小的正整數(shù)n，對(duì)這種n元集V的k元子集族，及其上的任一m-拆分{S1,S2,…,Sm}，存在V的pi元子集Vi，滿足Vi的k元子集族包含在m-拆分的某類中，其中i∈{1,2,…,m}。定義設(shè)V={v1,v2,…,vn},V的k元子集族記為{S1,S2,…，Sm}稱為ρk(V)的一個(gè)m-拆分 ,i≠j,Si∩Sj=￠,這里不要求Si≠

￠定理10

Ramsey數(shù)證明設(shè)V={v1,v2,…,vn}，令,易見ρ1(V)={{v1},{v2},…,{vn}}設(shè){S1,S2,…,Sm}是ρ1(V)的任一m-拆分，即S1∪S2∪…∪m=ρ1(V),Si∩Sj=￠,i≠j

這相當(dāng)于有 只鴿子飛進(jìn)了m個(gè)鴿巢。由鴿巢原理可知，一定有一個(gè)鴿巢Si飛進(jìn)了不少于pi只鴿子，即存在包含pi個(gè)元素的子集Vi

V，且ρ1(Vi)

Si。以上只是證明了r(p1,p2,…,pm;1)≤n，進(jìn)一步,為了證明r(p1,p2,…,pm;1)≥n，只需在n-1個(gè)元素所成子集V′={v1,v2,…,vn-1}上找到一種m-拆分，使得在該拆分下，不存在包含pi個(gè)元素的子集Vi

V′，滿足ρ1(Vi)

Si(i=1,2,…,m)。事實(shí)上，由于因而，總存在V′上的m-拆分{S1,S2,…,Sm},使得|Si|=pi-1,i=1,2,…，m

綜上所述，即得

定理11

對(duì)于不小于k的一切正整數(shù)p,q，有r(p,k;k)=p,r(k,q;k)=q

證明只證前者，后者可由對(duì)偶原理給出。設(shè)V={v1,v2,…,vp}，ρk(V)={X|X

V,|X|=k}，令{S1,S2}是ρk(V)的任一2-拆分，即S1∪S2=ρk(V),S1∩S2=￠若S2≠￠，即存在X∈S2，則X

V,|X|=k，即找到了一個(gè)包含k個(gè)元素的子集X,使得

若S2=￠,即ρk(V)=S1，這表明V正是要找的子集，它包含了p個(gè)元素，并有ρk(V)=S1

S1

故有 r(p,k;k)≤p

另一方面，對(duì)于任意一個(gè)至多只有p-1個(gè)元素的集合V′，在ρk(V′)上總存在這樣的2-拆分{S1,S2}，其中令S2=￠。于是在V′上既不存在包含p個(gè)元素的子集V1，滿足ρk(V1)

S1,也沒有包含k個(gè)元素的子集V2，滿足ρk(V2)

S2。因此有r(p,k;k)≥p。定理11得證。

定理12

設(shè)p,q是超過k(k≥1)的整數(shù)，則有遞歸關(guān)系式

r(p,q;k)≤r(r(p-1,q;k),r(p,q-1;k);k-1)+1

證明設(shè)V={v1,v2,…,vn}，n=r(r(p-1,q;k),r(p,q-1;k);k-1)+1ρk(V)={X|X

V,且|X|=k}令{S1,S2}是ρk(V)上的一個(gè)2-拆分，即有S1∪S2=ρk(V),S1∩S2=￠

又設(shè)V′=V-{vn}={v1,v2,…,vn-1}

對(duì)ρk-1(V′)總可構(gòu)造2-拆分{A1,A2},使?jié)M足Ai={Y|Y

V′,|Y|=k-1且Y∪{Vn}∈Si},i=1,2

注意到n-1是Ramsey數(shù)r(r(p-1,q;k),r(p,q-1;k);k-1)。于是，根據(jù)Ramsey數(shù)的定義，在V′上或者存在包含r(p-1,q;k)(≥p-1)個(gè)元素的子集Y1，滿足ρk-1(Y1)A1，從而存在包含p個(gè)元素的V1=(Y1∪{vn})V，滿足ρk(V1)S1。在V′上，或者存在包含r(p,q-1;k)(≥q-1)個(gè)元素的子集Y2，滿足ρk-1(Y2)A2，從而存在包含q個(gè)元素的子集V2=(Y2∪{Vn})

V，滿足ρk(V2)

S2。這就證明了r(p,q;k)≤n。定理得證。

定理13（Ramsey定理）

Ramsey數(shù)r(p1,p2,…,pm;k)存在,其中，pi≥k≥1，i=1,2,…,m。

證明對(duì)m施行歸納法。

(1)基礎(chǔ)步：先證當(dāng)m=2時(shí)，r(p,q;k)的存在性。事實(shí)上，由定理10知r(p,q;1)=p+q-1存在。假設(shè)h≤k-1時(shí)，r(p,q;h)都存在,下證r(p,q;k)也存在。由定理11知，r(p,q;k)=p，r(k,q;k)=q，其中p,q≥k。進(jìn)而利用定理12可得r(p,q;k)≤r(r(p-1,q;k),r(p,q-1;k);k-1)+1

r(p-1,q;k)≤r(r(p-2,q;k),r(p-1,q-1;k);k-1)+1

r(p,q-1;k)≤r(r(p-1,q-1;k),r(p,p-2;k);k-1)+1…經(jīng)有限步迭代與歸納，最終r(p,q;k)的上界一定是一個(gè)關(guān)于r(r(p,k;k),r(k,q;k);k-1)=r(p,q;k-1)的多層嵌套表達(dá)式，根據(jù)假設(shè)，這個(gè)上界存在，從而r(p,q;k)存在。

（2）歸納步：假設(shè)定理對(duì)m-1成立，下證r(p1,p2,…,pm,k)存在。設(shè)V={v1,v2,…,vn},其中n=r(p1,p2,…,pm;k)令{S1,S2,…,Sm}是V的任一m-拆分，即有S1∪S2∪…∪Sm=ρk(V);Si∩Sj=￠,i≠j

則{S1,S2,…,Sm-2,Sm-1∪Sm}是ρk(V)的一個(gè)(m-1)-拆分。

由基礎(chǔ)步可知r(pm-1,pm;k)存在，且不小于k,再由歸納假設(shè)知，r(p1,p2,…,pm-2,q;k)也存在,其中q=r(pm-1,pm;k)。若n≤r(p1,p2,…,pm-2,q;k)，則定理已明?，F(xiàn)設(shè)n＞r(p1,p2,…,pm-2,q;k)。由Ramsey數(shù)的定義知，在V上，或者存在某個(gè)包含pi個(gè)元素的子集Vi，有ρk(Vi)Si,i∈{1,2,…,m-2};或者存在包含q個(gè)元素的子集Y

V，使得ρk(V)

(Sm-1∪Sm)

由于Sm-1∩Sm=￠，所以總存在ρk(Y)的一個(gè)2-拆分{Am-1,Am}，即有Am-1∪Am=ρk(Y),Am-1∩Am=￠使得

對(duì)于q=r(pm-1,pm;k)和2-拆分{Am-1,Am}，根據(jù)Ramsey數(shù)的定義知，或者存在包含pm-1個(gè)元素的子集Vm-1

Y

V，滿足ρk(Vm-1)

Am-1

Sm-1，或者存在包含pm個(gè)元素的子集Vm

YV，滿足ρk(Vm)

Am

Sm。

總之，至少存在一個(gè)包含pi個(gè)元素的子集Vi

V，使得ρk(Vi)

Si,i∈{1,2,…,m}Ramsey定理得證。推論1

Ramsey數(shù)r(p1,p2,…,pm;2)≤r(p1-1,p2,p3,…,pm;2)+r(p1,p2-1,p3,…,pm;2)+…+r(p1,p2

，…,pm-1;2)-m+2

其中，整數(shù)pi≥2,i=1,2,…,m。提示:可令rm(i)=r(p1,p2,…,pi-1,pi-1,…,pm;2),i=1,2,…,m，于是n=rm(1)+rm(2)+…+rm(m)-m+2

=(rm(1)-1)+(rm(2)-1)+…+(rm(m)-1)+2

然后，用m種顏色給完全圖Kn的邊集著色，每邊著一色。換言之，可對(duì)Kn的邊集E構(gòu)造m-拆分{E1,E2,…,Em}，使得 ,i≠j;接著證明在邊集E上，無論怎樣進(jìn)行m-拆分，Kn上總存在一個(gè)同色的Kpi,i∈{1,2,…,m}。推論2

Ramsey數(shù)

推論3

若用rm表示p1=p2=…=pm=3的Ramsey數(shù)r(p1,p2,…,pm;2)，則有遞歸關(guān)系rm≤m·(rm-1-1)+2

此即定理5。

證明由推論1，欲證這一遞歸關(guān)系，只需證：恰存在一個(gè)pi=2，其余都等于3的廣義Ramsey數(shù)r(p1,p2,…,pi-1,2,pi+1,…,

pm;2)不超過rm-1，其中i=1,2,…,m。只證r(2,3,3,…,3;2)≤rm-1，余類同。

令n=rm-1,并用m種顏色c1,c2,…,cm給完全圖Kn的邊集著色，每邊著一色。若Kn上有顏色為c1的邊，證明Kn上存在著顏色c1的同色K2；若Kn上顏色c1未出現(xiàn)，即至多用了m-1種顏色于Kn的邊集,結(jié)合Ramsey數(shù)的定義，在Kn上總存在某種同色K3，其顏色為c2,c3,…,cm中的一種。最后，由推論1和可證的m個(gè)不等式，有rm≤m·rm-1-m+2=m·(rm-1-1)+2

例1

r(3,3,3;2)=17。利用推論3給出的遞歸關(guān)系，有r(3,3,3;2)≤3(r2-1)+2

注意到r2=r(3,3)=6，故r(3,3,3;2)≤17。另一方面，由定理4的反例知，可構(gòu)造出邊集有三色的K16，其上不存在同色K3,從而，r(3,3,3;2)=17。

例2

設(shè)整數(shù)集H={1,2,…,rm}，其中，Ramsey數(shù)rm=(3,3,…,3;2)中的3有m項(xiàng)。那么可以證明，對(duì)于H上的任一m-拆分{H1,H2,…,Hm}，總存在某個(gè)Hi,i∈{1,2,…,m}，在Hi上有x,y和z(不必相異),滿足方程x+y=z。

證明以H為頂點(diǎn)集構(gòu)造完全圖Kn,其中,n=rm。用m種顏色給Kn的邊著色，每邊一色，其中，給邊(i,j)著第k種顏色(當(dāng)且僅當(dāng)|i-j|∈Hk,k=1,2,…,m)。據(jù)Ramsey數(shù)的定義知，Kn上至少存在一同色K3。不妨設(shè)該K3的頂點(diǎn)為a,b,c，且有a＜b＜c，它的邊都著第i種顏色。令x=c-b,y=b-a,z=c-a，則x,y,z∈Hi，且滿足方程x+y=z。

例3

在通信中，由于信道噪聲等意外因素的種種干擾，某些字母被認(rèn)為是“極易混同”的。為了避免這種弊病，可以考慮能否從現(xiàn)有字母表中抽出一盡可能大的子集，使得該子集中任意二字母在任何通信環(huán)境下不會(huì)混同，或者讓可能混同的概率幾乎為零。

解設(shè)字母表為A={a,b,c,…,x,y,z}以A為頂點(diǎn)集構(gòu)造完全圖K26，兩頂點(diǎn)Vi,Vj∈A,(i≠j)，連一條紅邊的充要條件是二者極易混同,連一條藍(lán)邊的充要條件是Vi和Vj間不易混同。問題轉(zhuǎn)化為在K26上尋找最大的藍(lán)色完全子圖。該子圖的頂點(diǎn)集即為不易混同的字母子集。

實(shí)際上，從26個(gè)字母中剔除容易混同的字母后，往往所剩無幾。進(jìn)一步的考慮就是對(duì)長(zhǎng)度大于1的符號(hào)串尋找最大的非混符號(hào)串子集。如對(duì)串長(zhǎng)等于2的串集，令A(yù)×A={(x,y)|x∈A∧y∈A}構(gòu)造以A×A為頂點(diǎn)集的完全圖K26×26，點(diǎn)(x1,x2)與(y1,y2)連一紅邊當(dāng)且僅當(dāng)如下三條件中任一成立：(1)(x1,y1)，(x2,y2)在K26×26中都是紅邊，即x1與易混，且x2與y2易混。

(2)x1=y1,(x2,y2)在K26×26

中是紅邊，即x1與y1相同，且x2與y2易混。

(3)x2=y2,(x1,y1)在K26×26

中是紅色，即x1與y1易混，且x2與y2相同。

在K26×26上凡不是紅邊的均染藍(lán)邊。圖論中，把圖K26×26稱為K26和K26的正規(guī)積，記為K26

·

K26

。這里關(guān)心的是K26

·

K26上最大藍(lán)色完全子圖的頂點(diǎn)集Vw。若用α(K26,K26)表示Vw中頂點(diǎn)數(shù)，則Z.Hedrlin于1966年證明的結(jié)果可述為定理14。

定理14

α(Km·Kn)≤r(p,q;2)-1,其中，Ramsey數(shù)r(p,q;2)中p=α(Km)+1,q=α(Kn)+1。2.5排列與組合

定義1(排列（Permutation）)設(shè)m元集A={a1,a2,…,am}，從A中取出n個(gè)不同元素按次序排列，稱為A的一個(gè)n排列，其個(gè)數(shù)稱為n排列數(shù)，記作P(m,n)或。當(dāng)n=m時(shí)，A的n排列又稱A的全排列，其個(gè)數(shù)P(m,m)又稱全排列數(shù)。命題1

證明

A的一個(gè)n排列由n個(gè)不同的元素組成，其中第一位有m種可能。第二位有m-1種可能；……第n位有m-(n-1)種可能。由乘法原理，m元集A的不同排列數(shù)為

推論

P(m,m)=m!。

例1

從A={a,b,c}中任取兩個(gè)不同的字母構(gòu)成的字共有3×2=6個(gè)。羅列如下：ab,ac,ba,bc,ca,cb

例23個(gè)物件分放4個(gè)不同的盒子中，要求每個(gè)盒子至多放一個(gè)物件的放法共有4×3×2=24種。

定義2(組合（Combination）)

設(shè)m元集A={a1,a2,…,am}，從A中取出n個(gè)不同元素構(gòu)成一組，稱為A的一個(gè)n組合，其個(gè)數(shù)稱為n組合數(shù)，記作C(m,n)，

命題2

由m個(gè)不同的元素共可構(gòu)成P(m,n)/n!種組合。即C(m,n)=P(m,n)/n!。

證明由定義n組合與n排列的區(qū)別在于前者不計(jì)較元素的先后順序，因此由每個(gè)n組合可以作出n！個(gè)不同的n排列。于是若有C(m,n)種n組合，則有C(m,n)*n!種排列,因此C(m,n)=P(m,n)/n!。

推論1

任意n個(gè)相繼的正整數(shù)之積可被n！整除，即有

推論2

推論3

C(m,n)=C(m,m-n)。

推論4

m元集A的n元子集的個(gè)數(shù)等于C(m,n)。

推論5

設(shè)m元集A={a1,a2,…,am},其字典序如下標(biāo)所示，則從A中每次取出滿足條件 的n個(gè)元的方式數(shù)等于C(m,n)。

證明A的任一組合都可調(diào)整為 并使其滿足 ；另一方面，任一滿足條件 的n個(gè)元都是A的一個(gè)n組合。

例3

平面上任三點(diǎn)都不共線的25個(gè)點(diǎn)，可形成多少條直線？可形成多少個(gè)三角形？

解

25點(diǎn)中任取2點(diǎn)即可惟一確定一條直線，故可形成C(25,2)=25!/(2!23!)=300條直線；同理，任取3點(diǎn)即可惟一確定一個(gè)三角形，故三角形的數(shù)目等于C(25,3)=25!/(3!22!)

=2300。

例4

用26個(gè)英文字母能構(gòu)成多少個(gè)含有3個(gè)、4個(gè)或5個(gè)元音的長(zhǎng)為8位的單詞？其中，一個(gè)字母出現(xiàn)在單詞中的次數(shù)不限。）

解對(duì)于含有3個(gè)元音（Vowel）的長(zhǎng)為8位的單詞,8位中任三位都可是元音，故共有C(8,3)種不同的方式,每種方式有53種可能，其余5位都是輔音(Consonant)有215種可能，從而具有3個(gè)元音的單詞數(shù)為C(8,3)53215=(8!/3!5!)53215

同理，含有4個(gè)元音的單詞數(shù)為C(8,4)54214=(8!/4!4!)54214

含有5個(gè)元音的單詞數(shù)為C(8，5)55213=(8!/5!3!)55213

從而，滿足題設(shè)的單詞共有8!(53215/3!5!+54214/4!4!+55213/5!3!)·求的算法№1輸入M，N；

№2

P1;M1

M+1

№3對(duì)K=1,2,…,N,做

M1

M1-1;P

P*M1

№4打印M,N,P

№5結(jié)束。

·

求 的算法

№1輸入M,N;

№2

C

1;M1

M+1;

№3對(duì)K=1,2,…,N,做

M1

M1-1;C

C*M1/K;

№4打印M,N,C;

№5結(jié)束。

·

生成n!個(gè)全排列的錯(cuò)位置數(shù)算法當(dāng)n=1，排列方式只有一種，就是1。當(dāng)n=2時(shí)，先將惟一的1排列1寫出兩次，并錯(cuò)位置以2，即得兩個(gè)2排列如下：1221

當(dāng)n=3時(shí)，先將兩個(gè)2排列分別寫出3次，并錯(cuò)位置以3，即得3!=6個(gè)3排列如下：123

132

312

321

231

213

當(dāng)n=4時(shí)，先將6個(gè)3排列分別寫出4次，并錯(cuò)位置以4，即得4!=24個(gè)4排列。（請(qǐng)仿上法自