組合數(shù)學(xué)課教材

2024/7/271組合數(shù)學(xué)2024/7/27組合數(shù)學(xué)-上海理工大學(xué)2教材組合數(shù)學(xué)（第四版），盧開澄盧華明著，清華大學(xué)出版社，2008本書共分8章，內(nèi)容包括:排列與組合遞推關(guān)系與母函數(shù)容斥原理與鴿巢原理Burnside引理與Polya定理區(qū)組設(shè)計(jì)線性規(guī)劃編碼簡(jiǎn)介組合算法簡(jiǎn)介考試

時(shí)間：第九周課內(nèi)形式：閉卷內(nèi)容：上課例題為主成績(jī)：平時(shí)+試卷成績(jī)2024/7/27組合數(shù)學(xué)-上海理工大學(xué)32024/7/27組合數(shù)學(xué)-上海理工大學(xué)41666年萊布尼茲所著《組合學(xué)論文》一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。1646.7.1.—1716.11.14.）德國(guó)最重要的自然科學(xué)家、數(shù)學(xué)家、物理學(xué)家、歷史學(xué)家和哲學(xué)家，一個(gè)舉世罕見的科學(xué)天才，和牛頓同為微積分的創(chuàng)建人。1664年1月，萊布尼茨完成了論文《論法學(xué)之艱難》，獲哲學(xué)碩士學(xué)位。1665年，萊布尼茨向萊比錫大學(xué)提交了博士論文《論身份》，1666年，審查委員會(huì)以他太年輕(年僅20歲)而拒絕授予他法學(xué)博士學(xué)位，1667年2月，阿爾特多夫大學(xué)授予他法學(xué)博士學(xué)位，還聘請(qǐng)他為法學(xué)教授。1700年2月，他還被選為法國(guó)科學(xué)院院士。至此，當(dāng)時(shí)全世界的四大科學(xué)院：英國(guó)皇家學(xué)會(huì)、法國(guó)科學(xué)院、羅馬科學(xué)與數(shù)學(xué)科學(xué)院、柏林科學(xué)院都以萊布尼次作為核心成員。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)5始創(chuàng)微積分高等數(shù)學(xué)上的眾多成就

計(jì)算機(jī)科學(xué)貢獻(xiàn)1673年萊布尼茨特地到巴黎去制造了一個(gè)能進(jìn)行加、減、乘、除及開方運(yùn)算的計(jì)算機(jī)率先為計(jì)算機(jī)的設(shè)計(jì)，系統(tǒng)提出了二進(jìn)制的運(yùn)算法則，為計(jì)算機(jī)的現(xiàn)代發(fā)展奠定了堅(jiān)實(shí)的基礎(chǔ)

豐碩的物理學(xué)成果

充分地證明了“永動(dòng)機(jī)是不可能”的觀點(diǎn)哲學(xué)貢獻(xiàn)單子論多才多藝

1693年，萊布尼茨發(fā)表了一篇關(guān)于地球起源的文章，后來(lái)擴(kuò)充為《原始地球》一書1677年，他寫成《磷發(fā)現(xiàn)史》，對(duì)磷元素的性質(zhì)和提取作了論述在氣象學(xué)方面。他曾親自組織人力進(jìn)行過大氣壓和天氣狀況的觀察1691年，萊布尼茨致信巴本，提出了蒸汽機(jī)的基本思想。1677年，萊布尼茨發(fā)表《通向一種普通文字》，以后他長(zhǎng)時(shí)期致力于普遍文字思想的研究，對(duì)邏輯學(xué)、語(yǔ)言學(xué)做出了一定貢獻(xiàn)。今天，人們公認(rèn)他是世界語(yǔ)的先驅(qū)……2024/7/27組合數(shù)學(xué)-上海理工大學(xué)6組合數(shù)學(xué)概述組合數(shù)學(xué)（combinatorialmathematics），又稱為離散數(shù)學(xué)。狹義的組合數(shù)學(xué)主要研究滿足一定條件的組態(tài)（也稱組合模型）的存在、計(jì)數(shù)以及構(gòu)造等方面問題。組合數(shù)學(xué)主要內(nèi)容有組合計(jì)數(shù)、組合設(shè)計(jì)、組合矩陣、組合優(yōu)化等。組合數(shù)學(xué)是計(jì)算機(jī)出現(xiàn)以后迅速發(fā)展起來(lái)的一門數(shù)學(xué)分支。計(jì)算機(jī)科學(xué)即算法的科學(xué)，而計(jì)算機(jī)所處理的對(duì)象是離散的數(shù)據(jù)，所以離散對(duì)象的處理就成了計(jì)算機(jī)科學(xué)的核心，而研究離散對(duì)象的科學(xué)恰恰就是組合數(shù)學(xué)。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)7典型問題地圖著色問題：對(duì)世界地圖著色，每一個(gè)國(guó)家使用一種顏色。如果要求相鄰國(guó)家的顏色相異，是否總共只需四種顏色？這是圖論的問題。船夫過河問題：船夫要把一匹狼、一只羊和一棵白菜運(yùn)過河。只要船夫不在場(chǎng)，羊就會(huì)吃白菜、狼就會(huì)吃羊。船夫的船每次只能運(yùn)送一種東西。怎樣把所有東西都運(yùn)過河？這是線性規(guī)劃的問題。中國(guó)郵差問題：由中國(guó)組合數(shù)學(xué)家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是一個(gè)NP完全問題，存在多項(xiàng)式復(fù)雜度算法：先求出度為奇數(shù)的點(diǎn)，用匹配算法算出這些點(diǎn)間的連接方式，然后再用歐拉路徑算法求解。這也是圖論的問題。任務(wù)分配問題（也稱婚配問題）：有一些員工要完成一些任務(wù)。各個(gè)員工完成不同任務(wù)所花費(fèi)的時(shí)間都不同。每個(gè)員工只分配一項(xiàng)任務(wù)。每項(xiàng)任務(wù)只被分配給一個(gè)員工。怎樣分配員工與任務(wù)以使所花費(fèi)的時(shí)間最少？這是線性規(guī)劃的問題。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)8第一章排列與組合主要內(nèi)容：一、排列與組合二、排列組合的生成算法三、組合意義的解釋與應(yīng)用舉例2024/7/27組合數(shù)學(xué)-上海理工大學(xué)9一、排列與組合

加法法則和乘法法則

一一對(duì)應(yīng)

排列、組合

圓周排列

可重排列

可重組合

不相鄰的組合2024/7/27組合數(shù)學(xué)-上海理工大學(xué)101.加法法則與乘法法則加法法則：設(shè)具有性質(zhì)A的事件有m個(gè)，具有性質(zhì)B的事件有n個(gè)，則具有性質(zhì)A或B的事件有m+n個(gè)。若

|A|=m,|B|=n,A∩B=,則

|A∪B|=m+n

。集合論語(yǔ)言：基本假設(shè)：性質(zhì)A和性質(zhì)B是無(wú)關(guān)的兩類。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)11例1

某班選修企業(yè)管理的有18人，不選的有10人，則該班共有18+10=28人。例2

假設(shè)要從北京坐飛機(jī)或者火車或者客車到上海。北京每天到達(dá)上海的飛機(jī)有5個(gè)航班，火車有7趟，客車有10趟，則每天由北京到達(dá)上海的旅行方式有5+7+10=22種。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)12乘法法則：設(shè)具有性質(zhì)A的事件有m個(gè)，具有性質(zhì)B的事件有n個(gè)，則具有性質(zhì)A和B的事件有mn個(gè)。若

|A|=m,|B|=n,A

B={(a,b)|a

A,b

B},則

|A

B

|=mn

。集合論語(yǔ)言：例3從A到B有三條道路，從B到C有兩條道路，則從A經(jīng)B到C有32=6

條道路。加法法則：得到事件通過兩種不同的方法。乘法法則：得到事件通過兩個(gè)步驟。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)13例4

某種樣式的運(yùn)動(dòng)服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42=8種著色方案。若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則方案數(shù)就不是44=16，而只有43=12種。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)14例5(1)求小于10000的含1的正整數(shù)的個(gè)數(shù)；

(2)求小于10000的含0的正整數(shù)的個(gè)數(shù)。(1)小于10000的不含1的正整數(shù)可看做4位數(shù)，但

0000除外.故有9×9×9×9－1＝6560個(gè)。含1的有：9999－6560=3439個(gè)，

另：全部4位數(shù)有104個(gè)，不含1的四位數(shù)有94個(gè)，含1的4位數(shù)為兩個(gè)的差：104－94=3439個(gè)。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)159999－7380=2619.9+9+9+9=(9－1)/(9－1)=73802345(2)“含0”和“含1”不可直接套用。0019含1但不含0。不含0的1位數(shù)有9個(gè)，2位數(shù)有92個(gè)，3位數(shù)有93個(gè)，4位數(shù)有94個(gè)。不含0小于10000的正整數(shù)有含0小于10000的正整數(shù)有2024/7/27組合數(shù)學(xué)-上海理工大學(xué)164×3×5＝60；(2)6×3＝18個(gè)位數(shù)有5種取法，千位數(shù)有8種取法，百位，十位各有8，7種取法。5×8×8×7＝2240。例6(1)n=73*112*134，求除盡n的數(shù)的個(gè)數(shù)；(2)n=73*142，求除盡n的數(shù)的個(gè)數(shù)；例7

在1000和9999之間有多少每位上的數(shù)字均不同的奇數(shù)？2024/7/27組合數(shù)學(xué)-上海理工大學(xué)17例8

由a,b,c,d,e這5個(gè)字符，從中取6個(gè)構(gòu)成字符串，要求(1)第1，6個(gè)字符必為子音字符b，c，d；(2)每個(gè)字符串必有兩個(gè)母音字符a或e，且兩個(gè)母音字符不相鄰；(3)相鄰的兩個(gè)子音字符必不相同。求滿足這樣的條件的字符串的個(gè)數(shù)。由條件(1)，兩個(gè)母音字符的位置不能在1，6，又由條件(2)，位置只能是(2,4),(2,5)和(3,5)之一。對(duì)每種格式，母音2×2，相鄰子音3×2，其他兩個(gè)子音3×3。因此答案為

3×（2×2×3×2×3×3）=648。課堂練習(xí)2024/7/27組合數(shù)學(xué)-上海理工大學(xué)18abcde1b/c/d32a/e23b/c/d34a/22526b/c/d31b/c/d3223a/e24a/b/c35a/e26b/c/d31b/c/d32a/e23b/c/d3425a/e26b/c/d32024/7/27組合數(shù)學(xué)-上海理工大學(xué)19如我們說A集合有n個(gè)元素|A|=n，無(wú)非是建立了將A中元與[1,n]元一一對(duì)應(yīng)的關(guān)系。在組合計(jì)數(shù)時(shí)往往借助于一一對(duì)應(yīng)實(shí)現(xiàn)模型轉(zhuǎn)換。比如要對(duì)A集合計(jì)數(shù)，但直接計(jì)數(shù)有困難，于是可設(shè)法構(gòu)造一易于計(jì)數(shù)的B，使得A與B一一對(duì)應(yīng)。2.一一對(duì)應(yīng)“一一對(duì)應(yīng)”概念是一個(gè)在計(jì)數(shù)中極為基本的概念。一一對(duì)應(yīng)既是單射又是滿射。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)20一種常見的思路是按輪計(jì)場(chǎng)，費(fèi)事。另一種思路是淘汰的選手與比賽(按場(chǎng)計(jì))集一一對(duì)應(yīng)。99場(chǎng)比賽。例9

在100名選手之間進(jìn)行淘汰賽(即一場(chǎng)的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問要舉行幾場(chǎng)比賽？2024/7/27組合數(shù)學(xué)-上海理工大學(xué)21可以先計(jì)算對(duì)角線的個(gè)數(shù)，然后計(jì)算交點(diǎn)，但是存在在多邊形內(nèi)無(wú)交點(diǎn)的情形，比較復(fù)雜?？梢钥紤]對(duì)應(yīng)關(guān)系：多邊形內(nèi)交點(diǎn)to多邊形四個(gè)頂點(diǎn)。可以證明這是一一映射（映射，單且滿）。例10

設(shè)凸n邊形的任意三條對(duì)角線不共點(diǎn)，求對(duì)角線在多邊形內(nèi)交點(diǎn)的個(gè)數(shù)。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)22

一一對(duì)應(yīng)例

CnH2n+2是碳?xì)浠衔?隨著n的不同有下列不同的枝鏈：

H|H—C—H|H

H|H—C—H|H—C—H|H

H|H—C—H|H—C—H|H—C—H|Hn=1甲烷n=2乙烷n=3丙烷2024/7/27組合數(shù)學(xué)-上海理工大學(xué)23

一一對(duì)應(yīng)

H|H—C—H|H—C—H|H—C—H|H—C—H|H

H|HH—CH||H—C—C—H||H—CH|HHn=4丁烷n=4異丁烷這說明對(duì)應(yīng)CnH2n+2的枝鏈?zhǔn)怯?n+2個(gè)頂點(diǎn)的一棵樹，其中n個(gè)頂點(diǎn)關(guān)聯(lián)的邊數(shù)為4；其它2n+2個(gè)頂點(diǎn)是葉子。對(duì)于這樣結(jié)構(gòu)的每一棵樹，就對(duì)應(yīng)有一種特定的化合物。構(gòu)造化合物轉(zhuǎn)化為圖論問題，計(jì)算符合上述條件的樹的數(shù)目，便可確定對(duì)應(yīng)的不同化合物的數(shù)目2024/7/27組合數(shù)學(xué)-上海理工大學(xué)241.2一一對(duì)應(yīng)例

(Cayley定理)n個(gè)有標(biāo)號(hào)的頂點(diǎn)的樹的數(shù)目等于

。兩個(gè)頂點(diǎn)的樹是唯一的。1－2n＝3時(shí)，數(shù)的數(shù)目3。1－2－3，1－3－2，2－1－3思路：n點(diǎn)樹《一一對(duì)應(yīng)》長(zhǎng)度n-2序列n個(gè)字母的長(zhǎng)度n-2序列的數(shù)目是2024/7/27組合數(shù)學(xué)-上海理工大學(xué)25

一一對(duì)應(yīng)⑦⑥

|

|②—③—①—⑤—④41253逐個(gè)摘去標(biāo)號(hào)最小的葉子，葉子的相鄰頂點(diǎn)(不是葉子，是內(nèi)點(diǎn))形成一個(gè)序列，序列的長(zhǎng)度為n-2例給定一棵有標(biāo)號(hào)的樹邊上的標(biāo)號(hào)表示摘去葉的順序。(摘去一個(gè)葉子相應(yīng)去掉一條邊)

第一次摘掉②，③為②相鄰的頂點(diǎn)，得到序列的第一個(gè)數(shù)3

以此類推，消去23465，得到序列31551,長(zhǎng)度為7－2=5，這是由樹形成序列的過程。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)26

一一對(duì)應(yīng)（復(fù)雜）由序列形成樹的過程：由序列31551得到一個(gè)新序列111233455567生成的過程是首先將31551排序得到11355，因?yàn)樾蛄?1551的長(zhǎng)度為5，得到按升序排序的序列1234567，序列的長(zhǎng)度為5+2(即n)，然后將11355按照大小插入到序列1234567中，得到111233455567然后將兩個(gè)序列排在一起315511112334555672024/7/27組合數(shù)學(xué)-上海理工大學(xué)27一一對(duì)應(yīng)

31551111233455567②—③

15511113455567①—③

55111455567④—⑤

51115567⑤—⑥

11157①—⑤

17第一步推導(dǎo)：將上下兩個(gè)序列同時(shí)去掉上行序列的第一個(gè)元素3(用藍(lán)色表示)，去掉下行序列的第一個(gè)無(wú)重復(fù)的元素2(用紅色表示)。生成一條邊(②—③)。由上序列確定3（藍(lán)色），再確定2（紅色），在下序列最小無(wú)重元，于是生成邊23。（并消除紅藍(lán)色點(diǎn)。）依此類推，減到下面剩最后兩個(gè)元素，這兩個(gè)元素形成最后一條邊。最后形成樹。（生成邊的序列23，13，45，56，15，17）2024/7/27組合數(shù)學(xué)-上海理工大學(xué)281.2一一對(duì)應(yīng)上述算法描述：給定序列b=(b1b2…bn-2)設(shè)a=(123…n-1n)將b的各位插入a,得a’,對(duì)()做操作。a’是2n-2個(gè)元的可重非減序列。ba’操作是從a’中去掉最小無(wú)重元，設(shè)為a1,再?gòu)腷和a’中各去掉一個(gè)b中的第一個(gè)元素，設(shè)為b1，則無(wú)序?qū)?a1,b1)是一條邊。重復(fù)這一操作，得n-2條邊，最后a’中還剩一條邊，共n-1條邊，正好構(gòu)成一個(gè)樹。b中每去掉一個(gè)元，a’中去掉2個(gè)元。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)291.2一一對(duì)應(yīng)由算法知由樹T得b=(b1b2…bn-2)，反之，由b可得T。即f：T→b是一一對(duì)應(yīng)。由序列確定的長(zhǎng)邊過程是不會(huì)形成回路的。因任意長(zhǎng)出的邊(u,v)若屬于某回路，此回路中必有一條最早生成的邊，不妨就設(shè)為(u,v)，必須使u,v都在長(zhǎng)出的邊中重復(fù)出現(xiàn)，但照算法u,v之一從下行消失，不妨設(shè)為u，從而不可能再生成與u有關(guān)的邊了，故由()得到的邊必構(gòu)成一個(gè)n個(gè)頂點(diǎn)的樹。ba’2024/7/27組合數(shù)學(xué)-上海理工大學(xué)30證明23

1

5

511

23

456

7

第一個(gè)不出現(xiàn)在上面的數(shù)2-3

3-1

4-56-55-11-7⑦⑥

|

|②—③—①—⑤—④2024/7/27組合數(shù)學(xué)-上海理工大學(xué)311.2一一對(duì)應(yīng)證由一棵n個(gè)頂點(diǎn)的樹可得到一個(gè)長(zhǎng)度為n－2的序列，且不同的樹對(duì)應(yīng)的序列不同，因此。對(duì)n用歸納法可證反之，由一個(gè)長(zhǎng)度為n－2的序列(每個(gè)元素為1~n的一個(gè)整數(shù))，可得到一棵樹，且不同的序列對(duì)應(yīng)的樹是不同的，因此 2024/7/27組合數(shù)學(xué)-上海理工大學(xué)32排列的典型例子是取球模型：從n個(gè)不同的球中,取出r個(gè),放入r個(gè)不同的盒子里，每盒1個(gè)。第1個(gè)盒子有n種選擇,第2個(gè)有n-1種選擇，······，第r個(gè)有n-r+1種選擇。故由乘法法則有3.排列、組合定義：從n個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的無(wú)重排列。排列的個(gè)數(shù)用P(n,r)表示。當(dāng)r=n

時(shí)稱為全排列。P(n,r)=n(n-1)······(n-r+1)=n!/(n-r)!P(n,n)=n!2024/7/27組合數(shù)學(xué)-上海理工大學(xué)33例11

由5種顏色的星狀物，20種不同的花排列成如下圖案：兩邊是星狀物，中間是3朵花，問共有多少種這樣的圖案？?jī)蛇吺切菭钗?，從五種顏色的星狀物中取兩個(gè)的排列的排列數(shù)是P(5,2)=20。20種不同的花取3種排列的排列數(shù)是根據(jù)乘法法則得圖案數(shù)為P(20,3)=20×19×18=6840。20×6840=136800。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)34接上例，若A單位的2人排在隊(duì)伍兩端，B單位的3人不能相鄰，問有多少種不同的排列方案？(練習(xí))B單位3人按一個(gè)元素參加排列，P(8,8)×P(3,3)。

A單位的人排法固定后A*A*A*A*A*A*A，B單位第一人有6種選擇，第二人有5種，第三人有4種，因此答案為P(7,7)×6×5×4。例12

A單位有7名代表，B單位有3位代表，排成一列合影要求B單位的3人排在一起，問有多少種不同的排列方案。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)35例13

試求由{1,3,5,7}組成的所有不重復(fù)出現(xiàn)的整數(shù)的總和。這樣的整數(shù)可以是1位數(shù),2位數(shù),3位數(shù),4位數(shù)，若設(shè)是i位數(shù)的總和，則S=S1+S2+S3+S4,S1=1+3+5+7=16；于是我們只需要計(jì)算Si即可。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)36S4=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=96000+9600+960+96=106656；S=16+528+10656+106656=117856。

S2=3(1+3+5+7)10+3(1+3+5+7)=480+48=528；S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=9600+960+96=10656；2024/7/27組合數(shù)學(xué)-上海理工大學(xué)37組合的個(gè)數(shù)用C(n,r)

表示?；蛘哂帽硎尽６x：從

n個(gè)不同元素中取

r個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為從n個(gè)中取r個(gè)的無(wú)重組合。C(n,r)=0，若n<r。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)38故有C(n,r)·r!=P(n,r)，C(n,r)=P(n,r)/r!，從n個(gè)不同的球中,取出r個(gè),放入r個(gè)相同的盒子里,每盒1個(gè)，這是從n個(gè)中取r個(gè)的組合的模型。若放入盒子后再將盒子標(biāo)號(hào)區(qū)別，則又回到排列模型。每一個(gè)組合可有r!個(gè)標(biāo)號(hào)方案。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)39(2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76；(1)5×7+5×10+7×10=155;(3)155+76=231=C(5+7+10,2)。例14

有5本不同的日文書，7本不同的英文書，10本不同的中文書。(1)取2本不同文字的書；(2)取2本相同文字的書；(3)任取兩本書。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)40例15

甲和乙兩單位共11個(gè)成員，其中甲單位7人，乙單位4人，擬從中組成一個(gè)5人小組：(1)要求包含乙單位恰好2人；(2)要求至少包含乙單位2人；(3)要求乙單位某一人與甲單位特定一人不能同時(shí)在這個(gè)小組。試求各有多少種方案。(1)C(4,2)×C(7,3)；(2)C(4,2)×C(7,3)+C(4,3)×C(7,2)+C(4,4)×C(7,1)；(3)C(10,5)+C(9,4)，或C(11,5)-C(9,3)。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)41將[1,300]分成3類：A={i|i≡1(mod3)}={1,4,7,…,298},B={i|i≡2(mod3)}={2,5,8,…,299},C={i|i≡3(mod3)}={3,6,9,…,300}。例16

從[1,300]中取3個(gè)不同的數(shù)，使這3個(gè)數(shù)的和能被3整除，有多少種方案？（練習(xí)）要滿足條件，有四種情形：1.3個(gè)數(shù)同屬于A;2.3個(gè)數(shù)同屬于B;3.3個(gè)數(shù)同屬于C;4.A,B,C各取一數(shù)。故共有3C(100,3)+1003=485100+1000000=1485100。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)42解1：a1選擇其同伴有7種可能，選定后,余下6人中某一人選擇其同伴只有5種可能，余下4人，其中某1人有3種選擇可能，在余下的2人只好配成一對(duì)，無(wú)法選擇，故共有N=7×5×3=105。例17

假定有a1,a2,a3,a4,a5,a6,a7,a8這8位成員，兩兩配對(duì)分成4組，試問有多少種方案？（練習(xí)）2024/7/27組合數(shù)學(xué)-上海理工大學(xué)43解2：分成4組。第一組取法為C(8,2)，余下6人，第二組取法為C(6,2)，第三組取法為C(4,2)，剩下為第四組。但4組的順序是重復(fù)的，因此答案為

C(8,2)×C(6,2)×C(4,2)/P(4,4)=105。解3：8人全排列有P(8,8)。分成4組。每組中2人交換是重復(fù)的，重復(fù)數(shù)為2×2×2×2，另外4組的順序也是重復(fù)的，重復(fù)數(shù)為P(4,4)，因此答案為

P(8,8)/(2×2×2×2×P(4,4))=105。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)44一個(gè)進(jìn)站方案可以表示成：00011001010100，其中“0”表示車，“1”表示間隔。其中“0”是不同元，“1”是相同元。給“1”這6個(gè)入口只用5個(gè)間隔。任意進(jìn)站方案可表示成上面14個(gè)元素的一個(gè)排列。例18

某廣場(chǎng)有6個(gè)入口，每個(gè)入口每次只能通過一輛汽車，現(xiàn)有9輛車要開進(jìn)廣場(chǎng)，有多少種入場(chǎng)方案？2024/7/27組合數(shù)學(xué)-上海理工大學(xué)45解2：在14個(gè)元的排列中先確定“1”的位置，有C(14,5)種選擇，再確定車的位置，有9！種選擇。故C(14,5)·9!即為所求。解3：實(shí)際上相當(dāng)于14個(gè)位置中選取9輛汽車的排列，即為P(14,9)。解1：標(biāo)號(hào)可產(chǎn)生5!個(gè)14個(gè)元的全排列。若設(shè)x為所求方案，則x·5!=14!。故

x=14!/5!=726485760。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)46注意到，每個(gè)交點(diǎn)只有兩個(gè)對(duì)角線通過，對(duì)應(yīng)了4個(gè)頂點(diǎn)所組成的一個(gè)組合，不同的交點(diǎn)對(duì)應(yīng)的組合也不相同。故共有C(n,4)個(gè)交點(diǎn)。例19

一個(gè)凸n邊形，它的任何3條對(duì)角線都不交于同一點(diǎn)，問它的所有對(duì)角線在凸n邊形內(nèi)部有多少個(gè)交點(diǎn)。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)47定義：從n個(gè)不同的數(shù)中不重復(fù)的取出取出r個(gè)沿一圓周排列，稱為一個(gè)圓周排列。所有的r-圓周排列數(shù)記為Q(n,r)（計(jì)算公式？）。注意圓周排列與排列的不同之處在于圓周排列首尾相鄰。如a、b、c、d的4種不同排列

abcd,dabc,cdab,bcda,在圓周排列中都是一個(gè)排列。4.圓周排列2024/7/27組合數(shù)學(xué)-上海理工大學(xué)48124

31234124

32341124

33412124

34123以4個(gè)元素為例Q(n,r)=P(n,r)/r,2≤r≤nQ(n,n)=(n-1)!從n

個(gè)中取r

個(gè)的圓周排列的排列數(shù)為：2024/7/27組合數(shù)學(xué)-上海理工大學(xué)49若無(wú)要求，則為Q(8,8)；若要求藍(lán)色珠子一起，則為Q(6,6)×P(3,3)；若要求藍(lán)色珠子不相鄰，則為Q(5,5)×5×4×3。例205顆紅珠子，3顆藍(lán)珠子裝在圓板的四周，試問有多少種方案？若要求藍(lán)色珠子不相鄰，又有多少種排列方案？藍(lán)色珠子在一起呢？2024/7/27組合數(shù)學(xué)-上海理工大學(xué)50例215對(duì)夫婦出席一個(gè)宴會(huì)，圍一圓桌坐下，試問有幾種不同的坐法？要求每對(duì)夫婦相鄰又如何？若無(wú)限制，則為Q(10,10)；若要求相鄰，則為Q(5,5)×2×2×2×2×2。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)51選取的r個(gè)元素叫做S的一個(gè)r-(可重)排列。當(dāng)時(shí)也叫做S

的一個(gè)排列。定義：從一個(gè)多重集

中有序5.可重排列定義：多重集是指元素可以多次出現(xiàn)的集合，即元素可以重復(fù)。我們把某個(gè)元素ai出現(xiàn)的次數(shù)ni(ni=0,1,2,…)叫做該元素的重復(fù)數(shù)。通常把含有k種不同元素的多重集S記作2024/7/27組合數(shù)學(xué)-上海理工大學(xué)52定理：設(shè)多重集則S的r-(可重)排列數(shù)是kr。推論：設(shè)多重集且對(duì)一切的i=1,2,…k，有ni≥r，則S

的r-(可重)排列數(shù)是kr。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)53所求的標(biāo)志數(shù)是多重集{2紅旗，3黃旗}的排列數(shù)，故N=5!/(2!×3!)=10。例23

用兩面紅旗，三面黃旗依次懸掛在一根旗桿上，問可以組成多少種不同的標(biāo)志?例22

求不多于4位數(shù)的二進(jìn)制數(shù)的個(gè)數(shù)。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)54定理：從中取r個(gè)作可重的組合，其個(gè)數(shù)為C(k+r-1,r)。6.可重組合2024/7/27組合數(shù)學(xué)-上海理工大學(xué)55

r個(gè)相同的球

/\———————

————————／\0…010…01…10…0

\/————————

\/

k-1個(gè)相同的盒壁而后一問題又可轉(zhuǎn)換為r

個(gè)相同的球與k-1

個(gè)相同的盒壁的排列的問題。則所求計(jì)數(shù)為C(k+r-1,r)。這個(gè)計(jì)數(shù)問題相當(dāng)于r個(gè)相同的球放入k個(gè)不同的盒子里，個(gè)數(shù)沒有限制的計(jì)數(shù)。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)56另證：不妨假設(shè)k個(gè)不同元素為1,2,…,k，設(shè)某一個(gè)r可重組合為b1,b2,…,br。由于允許重復(fù)，可以假設(shè)這相當(dāng)于從1到k+r-1中取r個(gè)不允許重復(fù)的組合。很容易驗(yàn)證，這是一個(gè)一一對(duì)應(yīng)，從而定理成立。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)57任取一個(gè)所求的r組合，從中拿走每個(gè)元素一個(gè)就得到S

的一個(gè)r-k組合，反之,對(duì)于S

的一個(gè)r-k組合，加入元素a1,a2,…ak

就得到所求組合，所以其組合數(shù)即為S

的r-k可重組合數(shù)。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)58典型模型：定理：線性方程的非負(fù)整數(shù)解的個(gè)數(shù)為C(k+r-1,r)。取r個(gè)無(wú)區(qū)別的球放進(jìn)k個(gè)有標(biāo)志的盒子，每個(gè)盒子中的球的數(shù)目不加限制,允許重復(fù)的組合數(shù)即其方案數(shù)。有多少項(xiàng)？4個(gè)無(wú)標(biāo)志的球放進(jìn)3個(gè)有標(biāo)志的盒子x,y,z從3個(gè)元素可重復(fù)的取4個(gè)的組合數(shù)目。2024/7/27組合數(shù)學(xué)-上海理工大學(xué)60定理：從{1,2,…n}中取r個(gè)作不相鄰的組合，其個(gè)數(shù)為C(n-r+1,r)。7.不相鄰的組合不相鄰的組合是指從{1,2,…n}中取r個(gè)，不允許重復(fù)且不存在相鄰的數(shù)同時(shí)出現(xiàn)的組合。設(shè)某一個(gè)不相鄰組合為b1,b2,…,br，可以假設(shè)b1<b2<…<br,而且相鄰兩項(xiàng)至少相差2。這相當(dāng)于從1到n-r+1中取r個(gè)不允許重復(fù)的組合。很容易驗(yàn)證，這是一個(gè)一一對(duì)應(yīng)，從而定理成立。組合數(shù)學(xué)-上海理工大學(xué)1.2排列組合生成算法

全排列的生成算法

組合的生成算法

一般排列的生成算法組合數(shù)學(xué)-上海理工大學(xué)1.全排列的生成算法全排列的生成算法就是對(duì)于給定的字符集，用有效的方法將所有可能的全排列無(wú)重復(fù)無(wú)遺漏地枚舉出來(lái)。這里介紹4種全排列算法：(A)

直接生成法(B)

序數(shù)法(C)

字典序法(D)換位法組合數(shù)學(xué)-上海理工大學(xué)遞推算法：假設(shè)已經(jīng)生成n-1個(gè)數(shù)的所有(n-1)!個(gè)全排列，將n插入到每一個(gè)排列的前面、第12之間、第23之間、。。。最后，即得到n個(gè)數(shù)的所有n(n-1)!=n!個(gè)全排列。優(yōu)點(diǎn)是生成簡(jiǎn)便，缺點(diǎn)是速度慢。(A)直接生成法組合數(shù)學(xué)-上海理工大學(xué)n的p進(jìn)制表示：(B)序數(shù)法n的十進(jìn)制表示：我們來(lái)看另一種表示n!=((n-1)+1)(n-1)!=(n-1)(n-1)!+(n-1)!,(n-1)!=(n-2)(n-2)!+(n-2)!,…,故n!=(n-1)(n-1)!+(n-2)(n-2)!+…+2×2!+2!組合數(shù)學(xué)-上海理工大學(xué)不難證明，從0到n!-1的任何數(shù)m可唯一的表示為其中所以從0到n!-1的n!個(gè)整數(shù)與(an-1,an-2,…a2,a1)一一對(duì)應(yīng)。組合數(shù)學(xué)-上海理工大學(xué)從m計(jì)算出an-1,an-2,…a2,a1的算法如下：…………….組合數(shù)學(xué)-上海理工大學(xué)求序數(shù)例子：m=4000,6!<4000<7!組合數(shù)學(xué)-上海理工大學(xué)反過來(lái),由(a3,a2,a1)=(301)也可以得到排列4213，下面我們?cè)噲D將n-1個(gè)元素的序列(an-1,…,a1)與n個(gè)元素的排列建立起一一對(duì)應(yīng)關(guān)系。例如：p=4213(a3,a2,a1)=(301)序列(an-1,…,a1)與某一排列p=p1p2…pn之間的對(duì)應(yīng)關(guān)系為：ai表示排列p中的數(shù)i+1所在位置的右邊比它小的數(shù)的個(gè)數(shù)。組合數(shù)學(xué)-上海理工大學(xué)____4321而a2=0,說明3的右邊沒有比它更小的，故3放在最右端，考慮a1=1,容易得出，2右邊還有一個(gè)空格放1，于是得到了排列4213。由a3=3,知4放在空格的最左端,這個(gè)算法的優(yōu)點(diǎn)是建立了自然序數(shù)和排列之間的一一對(duì)應(yīng)關(guān)系(通過n-1個(gè)元素的序列(an-1,…,a1))。缺點(diǎn)是這種對(duì)應(yīng)關(guān)系需要通過序列轉(zhuǎn)換，即兩層對(duì)應(yīng)關(guān)系，多一層計(jì)算量。

Na3a2a1p1p2p3p4Na3a2a1p1p2p3p401234567891011000001010011020021100101110111120121123421341324231431243214124321431342234131423241121314151617181920212223200201210211220221300301310311320321142324131432243134123421412342134132423143124321a1最大1a2最大2a3最大3組合數(shù)學(xué)-上海理工大學(xué)一個(gè)全排列可看做一個(gè)字符串，字符串可有前綴、后綴。關(guān)鍵是如何生成給定全排列的下一個(gè)排列。(C)字典序法字典序：對(duì)于兩個(gè)序列a1…ak和b1…bk

，若存在t，使得ai=bi,i<t，但at<bt

，則稱例如對(duì)于字符集{1,2,3}，較小的數(shù)字較先，這樣按字典序生成的全排列是：123,132,213,231,312,321所謂一個(gè)的下一個(gè)就是這一個(gè)與下一個(gè)之間沒有其他的。這就要求這一個(gè)與下一個(gè)有盡可能長(zhǎng)的共同前綴，也即變化限制在盡可能短的后綴上。組合數(shù)學(xué)-上海理工大學(xué)839647521的下一個(gè)為839651247。例如：839647521是1-9的一個(gè)排列，求出下一個(gè)。(1-9的排列最前面的是123456789，最后面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下一個(gè)了。)(1)從右向左掃描找出第一次出現(xiàn)下降的位置。(4)(2)在4的右邊按從左往右的順序找出最后一個(gè)比4大的數(shù)字(5)，交換這兩個(gè)數(shù)字，得到839657421。(3)把5后面的數(shù)字順序完全顛倒過來(lái)即得到：組合數(shù)學(xué)-上海理工大學(xué)P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…PnP1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即是P的下一個(gè)。(2)對(duì)換Pj，Pk；(1)找出j=max{i|Pi<Pi+1}，k=max{i|Pi>Pj}；該算法的優(yōu)點(diǎn)是排列清晰，而且保持著字典序。缺點(diǎn)是算法較繁瑣。一般而言，設(shè)P是[1,n]的一個(gè)全排列。(3)將Pj+1…Pk-1PjPk+1…Pn翻轉(zhuǎn)，組合數(shù)學(xué)-上海理工大學(xué)p1

p2…npn-1np1

p2…pn-1…p1

p2…pn-1n基于直接生成法，[n]的全排列可由[n-1]的全排列生成：(D)換位法給定[n-1]的一個(gè)排列п,將n

由最右端依次插入排列п，即得到n個(gè)[n]的排列：組合數(shù)學(xué)-上海理工大學(xué)例如對(duì)于n=4第三步：12122121122133333322第二步：11第一步：1組合數(shù)學(xué)-上海理工大學(xué)

321321321321231231231231213213213213444444444444444444444444第四步：123123123123132132132132312312312312組合數(shù)學(xué)-上海理工大學(xué)對(duì)給定的一個(gè)整數(shù)k，我們賦其一個(gè)方向，即在其上寫一個(gè)箭頭（指向左側(cè)或右側(cè)）下面我們用較正式的語(yǔ)言來(lái)說這件事。kk或者對(duì)上述過程，一般地，對(duì)于i，將前一步所得的每一排列重復(fù)i次，然后將i由第一排的最后往前移，至最前列，正好走了i次,下一個(gè)接著將i放在下一排列的最前面，然后依次往后移，一直下去即得i元排列。組合數(shù)學(xué)-上海理工大學(xué)顯然1永遠(yuǎn)不可移；(1)n是第一個(gè)數(shù)，且其方向指向左側(cè)，(2)n是最后一個(gè)數(shù)，且其方向指向右側(cè)?？紤]{1,2…n}的一個(gè)排列，其上每一個(gè)整數(shù)都給了一個(gè)方向。我們稱整數(shù)k是可移的(Mobile&Active)，如果它的箭頭所指的方向的鄰點(diǎn)小于它本身。例如

中6、3、5都是可移的。n除了以下兩種情形外，它都是可移的：組合數(shù)學(xué)-上海理工大學(xué)于是，我們可由按如下算法產(chǎn)生所有排列：1、開始時(shí)：2、當(dāng)存在可移數(shù)時(shí)，(a)找最大的可移數(shù)m；(b)將m與其箭頭所指的鄰數(shù)互換位置；(c)將所得排列中比m大的數(shù)p的方向調(diào)整，即改為相反方向。組合數(shù)學(xué)-上海理工大學(xué)

123123123123132132132132312312312312

321321321321231231231

231213213213213444444444444444444444444組合的生成設(shè){1,2,3,4,5,6}中取3個(gè)的組合，20個(gè)，按照字典序排列。123，124，125，126，134，135，136，145，146，156，234，235，236，245，246，256，345，346，356，456。第1位1到4，第2位2到5，第3位3到6。

組合的生成每個(gè)組合C1C2C3滿足條件1

C1<C2<C3

6.C3最大可以到6,C2最大可以到5,C1最大可以到4.如果每個(gè)數(shù)都已經(jīng)達(dá)到最大,那就結(jié)束了.如果沒有,就找最右面一個(gè)還沒有達(dá)到最大值的數(shù),給這個(gè)數(shù)加1，(并依次寫出后續(xù)各數(shù))，得到下一個(gè)組合.重復(fù)這個(gè)過程就可以得到整個(gè)組合.組合數(shù)學(xué)-上海理工大學(xué)設(shè)從[1,n]中取r元的一個(gè)組合為C1C2…Cr，不妨設(shè)C1＜…＜Cr,則

i≤Ci≤(n-r+i),i=1,2,…,r。(1)找j

=

max{

i

|Ci＜n-r+i}；這等于給所有的組合建立了字典序。生成C1C2…Cr的下一個(gè)組合的算法如下：(2)令Cj=Cj+1；(3)令Ci=Ci-1+1,i=j+1,…,r。2.組合的生成算法3.一般排列的生成算法n中取r的排列生成可以由組合生成和全排列生成結(jié)合而得到。組合數(shù)學(xué)-上海理工大學(xué)1.3組合意義的解釋與應(yīng)用舉例

非降路徑問題

組合意義的解釋

應(yīng)用舉例組合數(shù)學(xué)-上海理工大學(xué)從(0,0)點(diǎn)出發(fā)沿x軸或y軸的正方向每步走一個(gè)單位，最終走到(m,n)點(diǎn)，有多少條路徑？（思考）y

x(m,n)......01.非降路徑問題組合數(shù)學(xué)-上海理工大學(xué)因此若記所求方案數(shù)為P(m+n;m,n)，則無(wú)論怎樣走法,總有：在x方向上總共走m步，在y方向上總共走n步。若用一個(gè)x表示x方向上的一步，一個(gè)字母y表示y方向上的一步，則(0,0)→(m,n)的每一條路徑可表示為m個(gè)相同的x與n個(gè)相同的y的一個(gè)排列。這相當(dāng)于從m+n個(gè)位置中選出m個(gè)位置放x，剩下的位置自然放置y。組合數(shù)學(xué)-上海理工大學(xué)(c,d)(a,b)或記為設(shè)c≥a,d≥b,則由(a,b)到(c,d)的非降路徑數(shù)為：組合意義的解釋等式1.

組合意義：從[1,n]去掉一個(gè)r子集，剩下一個(gè)(n-r)子集。由此建立C(n,r)與C(n,n-r)的一個(gè)一一對(duì)應(yīng)。故又證：組合意義的解釋等式2.組合意義：1.7組合意義的解釋等式2.

組合意義：組合意義的解釋等式3證:可從前例推論，也可做一下組合證明組合意義的解釋組合意義：從[1,n+r+1]取r個(gè)的組合是右邊。左邊最后一項(xiàng)不含1，n+r個(gè)取r左邊最后第二項(xiàng)含1不含2,n+r-1個(gè)取r-1左邊最后第三項(xiàng)含1,2不含3,n+r-2個(gè)取r-2…,左邊第一項(xiàng)含1,2,…,r,則不取r+1以后組合意義的解釋另組合意義:從(0,0)到(n+1,r),過且僅過一條帶箭頭的邊,而過這些邊的路徑有(從下到上)故有

(0,0)到(n,0)到(n+1,0)

(0,0)到(n,1)到(n+1,1)

。。。(0,0)到(n,r)到(n+1,r)

r(n+1,r)

...(0,0)nn+1從（0，0）到（n+1,r)必經(jīng)（n,0）,(n,1)…之一組合意義的解釋等式4.①選政治局,再選常委,n個(gè)中央委員選出l名政治局委員,再?gòu)钠渲羞x出r名常委②選常委,再選非常委政治局委員兩種選法都無(wú)遺漏,無(wú)重復(fù)地給出可能的方案，應(yīng)該相等。組合意義的解釋等式4.n=5l=4r=2組合意義的解釋等式4證明：組合意義的解釋等式5

證1組合意義的解釋等式5.

組合證1[1,m]的所有方案.每一子集都可取或不取.這樣有個(gè)方案.另可有0-子集(空集),1-子集,…,m-子集.組合證2從(0,0)走m步有種走法,都落在直線x+y=m上,而達(dá)到(m,0),(m-1,1),…,(1,m-1),(0,m)各點(diǎn)的走法各有種組合意義的解釋等式6證1

.組合意義的解釋組合證2在[1,n]的所有組合中,含1的組合←→不含1的組合.有1—1對(duì)應(yīng)關(guān)系。在任一含1組合及與之對(duì)應(yīng)的不含1組合中，必有一奇數(shù)個(gè)元的組合與一偶數(shù)個(gè)元的組合。將含奇數(shù)個(gè)元的組合做成集，將含偶數(shù)個(gè)元的組合做成另一集。此二集的元數(shù)相等。奇abc→偶bc有a的去掉a奇bcd→偶abcd無(wú)a的增加a組合意義的解釋等式7.即Vandermonde恒等式證1從m個(gè)互異紅球和n個(gè)互異藍(lán)球中取r個(gè)球,按r個(gè)球中紅球的個(gè)數(shù)分類.組合證法:(0,0)到(m+n-r,r)點(diǎn)的路徑.P(m-r,r)(m+n-r,r)(m-l,l)l=0,1,2,…,r

Q(m,0)

組合意義的解釋等式8.例證：

應(yīng)用舉例例某保密裝置須同時(shí)使用若干把不同的鑰匙才能打開?，F(xiàn)有７人，每人持若干鑰匙。須４人到場(chǎng)，所備鑰匙才能開鎖。問①至少有多少把不同的鑰匙？②每人至少持幾把鑰匙？解①每３人至少缺１把鑰匙，且每３人所缺鑰匙不同。故至少共有C(7,3)=35把不同的鑰匙。②任一人對(duì)于其他６人中的每３人，都至少有１把鑰匙與之相配才能開鎖。故每人至少持C(6,3)＝20把不同的鑰匙。組合數(shù)學(xué)-上海理工大學(xué)對(duì)每一條接觸x=y的非降路徑，做(0,1)點(diǎn)到第一個(gè)接觸點(diǎn)部分關(guān)于x=y的對(duì)稱非降路徑，這樣得到一條從(1,0)到(m,n)的非降路徑。從(0,1)點(diǎn)到(m,n)點(diǎn)的非降路徑，有的接觸x=y，有的不接觸。在原模型的基礎(chǔ)上若設(shè)m<n，求(0,1)點(diǎn)到(m,n)點(diǎn)不接觸對(duì)角線x=y的非降路徑的數(shù)目(“接觸”包括“穿過”)?y

y=x(m,n)0(1,0)x(0,1)..組合數(shù)學(xué)-上海理工大學(xué)故所求非降路徑數(shù)為容易看出從(0,1)到(m,n)接觸x=y的非降路徑與(1,0)到(m,n)的非降路徑(必穿過x=y)一一對(duì)應(yīng)。組合數(shù)學(xué)-上海理工大學(xué)所求非降路徑數(shù)為若條件進(jìn)一步改為可接觸但不可穿過，則限制線要向下或向右移一格，得x-y=1,(0,0)關(guān)于x-y=1的對(duì)稱點(diǎn)為(1,-1).y

x-y=1(m,n)

x(0,1).........(2,-1)組合數(shù)學(xué)-上海理工大學(xué)假設(shè)一場(chǎng)音樂會(huì)的票價(jià)為50元，排隊(duì)買票的顧客中有n位只有50元的鈔票，m位只有100元的鈔票。售票處沒有準(zhǔn)備50元的零錢。試問有多少種排隊(duì)的方法使得購(gòu)票能順利進(jìn)行，即不會(huì)出現(xiàn)找不出錢的狀態(tài)。假定每位顧客只買一張票，且n>m。用一個(gè)m+n維的向量來(lái)表示一個(gè)排隊(duì)狀態(tài)，其中每個(gè)分量只能取x或y，這里取值y表示這個(gè)位置的顧客持有50元的鈔票，取值x表示只有100元的鈔票。因此這等價(jià)于一個(gè)從(0,0)到(m,n)點(diǎn)的非降路徑，且滿足y≥x，即可以接觸但不能穿過對(duì)角線。因此所求排隊(duì)方法即為上頁(yè)討論的答案結(jié)果。組合數(shù)學(xué)-上海理工大學(xué)第一章總結(jié)加法原理:乘法原理:組合數(shù)學(xué)-上海理工大學(xué)第一章總結(jié)定義從n個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的無(wú)重排列。排列個(gè)數(shù):定義從n個(gè)不同的元素中，取r個(gè)可重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的可重排列。排列個(gè)數(shù):組合數(shù)學(xué)-上海理工大學(xué)第一章總結(jié)定義從n個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，組成子集，稱為從n個(gè)中取r個(gè)的無(wú)重組合。組合個(gè)數(shù):定義從n個(gè)不同的元素中，取r個(gè)可重復(fù)的元素，組成子集，稱為從n個(gè)中取r個(gè)的可重組合。組合個(gè)數(shù):組合數(shù)學(xué)-上海理工大學(xué)第一章總結(jié)定義從1,2,…,n中n個(gè)不同的元素中，取r個(gè)不相鄰的元素，組成子集，稱為從n個(gè)中取r個(gè)的不相鄰組合。組合個(gè)數(shù):組合數(shù)學(xué)-上海理工大學(xué)第一章總結(jié)組合數(shù)學(xué)-上海理工大學(xué)第一章總結(jié)組合數(shù)學(xué)-上海理工大學(xué)第二章母函數(shù)與遞推關(guān)系2.1母函數(shù)與指數(shù)型母函數(shù)2.2遞推關(guān)系與Fibonacci數(shù)列2.3線性常系數(shù)遞推關(guān)系2.4非線性遞推關(guān)系舉例2.5應(yīng)用舉例組合數(shù)學(xué)-上海理工大學(xué)2.1母函數(shù)與指數(shù)型母函數(shù)

母函數(shù)

母函數(shù)的性質(zhì)

整數(shù)的拆分

Ferrers圖像

指數(shù)型母函數(shù)組合數(shù)學(xué)-上海理工大學(xué)1.母函數(shù)母函數(shù)方法是一套非常有用的方法，應(yīng)用極廣。這套方法的系統(tǒng)敘述，最早見于Laplace在1812年的名著—概率解析理論。我們來(lái)看如下的例子：兩個(gè)骰子擲出6點(diǎn)，有多少種選法？注意到，出現(xiàn)1，5有兩種選法，出現(xiàn)2，4也有兩種選法，而出現(xiàn)3，3只有一種選法，按加法法則，共有2+2+1=5種不同選法?；蛘撸谝粋€(gè)骰子除了6以外都可選，有5種選法，一旦第一個(gè)選定，第二個(gè)骰子就只有一種可能的選法，按乘法法則有5×1=5種。組合數(shù)學(xué)-上海理工大學(xué)但碰到用三個(gè)或四個(gè)骰子擲出n點(diǎn)，上述兩方法就不勝其煩了。設(shè)想把骰子出現(xiàn)的點(diǎn)數(shù)1,2,…,6和t,t2,…,t6對(duì)應(yīng)起來(lái)，則每個(gè)骰子可能出現(xiàn)的點(diǎn)數(shù)與(t+t2+…+t6)中t的各次冪一一對(duì)應(yīng)。若有兩個(gè)骰子，則其中t6的系數(shù)為5，顯然來(lái)自于這表明，擲出6點(diǎn)的方法一一對(duì)應(yīng)于得到t6的方法。組合數(shù)學(xué)-上海理工大學(xué)故使兩個(gè)骰子擲出n點(diǎn)的方法數(shù)等價(jià)于求中tn的系數(shù)。這個(gè)函數(shù)f(t)稱為母函數(shù)。母函數(shù)方法的基本思想：把離散數(shù)列和冪級(jí)數(shù)一一對(duì)應(yīng)起來(lái)，把離散數(shù)列間的相互結(jié)合關(guān)系對(duì)應(yīng)成為冪級(jí)數(shù)間的運(yùn)算關(guān)系，最后由冪級(jí)數(shù)形式來(lái)確定離散數(shù)列的構(gòu)造。組合數(shù)學(xué)-上海理工大學(xué)再來(lái)看下面的例子：若令a1=a2=…=an=1，則有這就是二項(xiàng)式展開定理。組合數(shù)學(xué)-上海理工大學(xué)比較等號(hào)兩端項(xiàng)對(duì)應(yīng)系數(shù)，可以得到恒等式：組合數(shù)學(xué)-上海理工大學(xué)比較等式兩端的常數(shù)項(xiàng)，可以得到恒等式：組合數(shù)學(xué)-上海理工大學(xué)中令x=1可得又如在等式兩端對(duì)x求導(dǎo)可得：再令x=1可得類似還可以得到組合數(shù)學(xué)-上海理工大學(xué)還可以類似地推出一些等式，但通過上面一些例子已可見函數(shù)(1+x)n在研究序列C(n,0),C(n,1),…,C(n,n)的關(guān)系時(shí)所起的作用。定義：對(duì)于序列a0,a1,a2,…，函數(shù)稱為序列a0,a1,a2,…的母函數(shù)。例如函數(shù)(1+x)n就是序列C(n,0),C(n,1),…,C(n,n)的母函數(shù)。如若已知序列，則對(duì)應(yīng)的母函數(shù)可根據(jù)定義給出。反之，如果已經(jīng)求出序列的母函數(shù)G(x)，則該序列也隨之確定。組合數(shù)學(xué)-上海理工大學(xué)DDD輸入u輸出v例1

下圖是一邏輯回路，符號(hào)D是一延遲裝置，即在時(shí)間t輸入一個(gè)信號(hào)給延遲裝置D，在t+1時(shí)刻D將輸出同樣的信號(hào)，符號(hào)

表示加法裝置。若在t=0,1,2,…時(shí)刻的輸入為u0,u1,u2,…求在這些時(shí)刻的輸出v0,v1,v2,…組合數(shù)學(xué)-上海理工大學(xué)顯然，一般的有若信號(hào)輸入的序列u0,u1,…的母函數(shù)為U(x)，輸出的信號(hào)序列v0,v1,…的母函數(shù)為V(x)，則其中被裝置的特性所確定，稱為該裝置的傳遞函數(shù)。組合數(shù)學(xué)-上海理工大學(xué)設(shè)r，w，y分別代表紅球，白球，黃球。例2

有紅球兩個(gè)，白球、黃球各一個(gè)，試求有多少種不同的組合方案。(1)取一個(gè)球的組合數(shù)為3，即分別取紅，白，黃。(2)取兩個(gè)球的組合數(shù)為4，即兩個(gè)紅的，一紅一黃，一紅一白，一白一黃。(3)取三個(gè)球的組合數(shù)為3，即兩紅一黃，兩紅一白，一紅一黃一白。(4)取四個(gè)球的組合數(shù)為1，即兩紅一黃一白。組合數(shù)學(xué)-上海理工大學(xué)共有1+3+4+3+1=12種組合方式。令取r的組合數(shù)為,則序列的母函數(shù)為組合數(shù)學(xué)-上海理工大學(xué)令an為從8位男同志中抽取出n個(gè)的允許組合數(shù)。由于要男同志的數(shù)目必須是偶數(shù)。故例3

某單位有8個(gè)男同志，5個(gè)女同志，現(xiàn)要組織一個(gè)由數(shù)目為偶數(shù)的男同志和數(shù)目不少于2的女同志組成的小組，試求有多少種組成方式？因此序列a1,a2,…,a8對(duì)應(yīng)的母函數(shù)為：組合數(shù)學(xué)-上海理工大學(xué)類似可得女同志的允許組合數(shù)對(duì)應(yīng)的母函數(shù)為其中xk的系數(shù)就是組成符合要求的k人小組的數(shù)目。組合數(shù)學(xué)-上海理工大學(xué)組合數(shù)學(xué)-上海理工大學(xué)2.母函數(shù)的性質(zhì)設(shè)序列ak,bk對(duì)應(yīng)的母函數(shù)分別為A(x),B(x)。則下面的兩個(gè)性質(zhì)顯然成立：(1)A(x)=B(x)當(dāng)且僅當(dāng)ak=bk。(2)若A(x)+B(x)=c0+c1x+c2x2+…，則ck=ak+bk。性質(zhì)1：若則B(x)=xlA(x)。證:組合數(shù)學(xué)-上海理工大學(xué)則例4

已知性質(zhì)2：若bk=ak+l，則則例5

已知組合數(shù)學(xué)-上海理工大學(xué)性質(zhì)3：若bk=a0+…+ak，則1:x:x2:xk:+)組合數(shù)學(xué)-上海理工大學(xué)則例6

已知組合數(shù)學(xué)-上海理工大學(xué)性質(zhì)4：若bk=ak+ak+1+…，則1:x:x2:+)組合數(shù)學(xué)-上海理工大學(xué)性質(zhì)5：若bk=kak，則性質(zhì)6：若bk=ak/(1+k)，則則例7

已知組合數(shù)學(xué)-上海理工大學(xué)性質(zhì)7：若ck=a0bk+a1bk-1+…+ak-1b1+akb0，則1:x:x2:+)組合數(shù)學(xué)-上海理工大學(xué)令例8

已知?jiǎng)t組合數(shù)學(xué)-上海理工大學(xué)3.整數(shù)的拆分所謂正整數(shù)拆分即把正整數(shù)分解成若干正整數(shù)的和。相當(dāng)于把n個(gè)無(wú)區(qū)別的球放到n個(gè)無(wú)標(biāo)志的盒子，盒子允許空著，也允許放多于一個(gè)球。整數(shù)拆分成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做拆分?jǐn)?shù)。拆分可以分為無(wú)序拆分和有序拆分；不允許重復(fù)的拆分和允許重復(fù)的拆分。組合數(shù)學(xué)-上海理工大學(xué)例9

若有1克、2克、3克、4克的砝碼各一枚，問能稱出那幾種重量？有幾種可能方案？從右端的母函數(shù)知可稱出從1克到10克，系數(shù)便是方案數(shù)。例如右端有2x5項(xiàng)，即稱出5克的方案有2種：5=2+3=1+4。類似的，稱出6克的方案也有2種：6=2+4=1+2+3。組合數(shù)學(xué)-上海理工大學(xué)例10

求