第一章排列與組合

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

時(shí)間：第九周課內(nèi)形式：閉卷內(nèi)容：上課例題為主成績：平時(shí)+試卷成績2024/10/29組合數(shù)學(xué)-上海理工大學(xué)32024/10/29組合數(shù)學(xué)-上海理工大學(xué)41666年萊布尼茲所著《組合學(xué)論文》一書問世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。1646.7.1.—1716.11.14.）德國最重要的自然科學(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é)位，還聘請他為法學(xué)教授。1700年2月，他還被選為法國科學(xué)院院士。至此，當(dāng)時(shí)全世界的四大科學(xué)院：英國皇家學(xué)會(huì)、法國科學(xué)院、羅馬科學(xué)與數(shù)學(xué)科學(xué)院、柏林科學(xué)院都以萊布尼次作為核心成員。2024/10/29組合數(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)于地球起源的文章，后來擴(kuò)充為《原始地球》一書1677年，他寫成《磷發(fā)現(xiàn)史》，對(duì)磷元素的性質(zhì)和提取作了論述在氣象學(xué)方面。他曾親自組織人力進(jìn)行過大氣壓和天氣狀況的觀察1691年，萊布尼茨致信巴本，提出了蒸汽機(jī)的基本思想。1677年，萊布尼茨發(fā)表《通向一種普通文字》，以后他長時(shí)期致力于普遍文字思想的研究，對(duì)邏輯學(xué)、語言學(xué)做出了一定貢獻(xiàn)。今天，人們公認(rèn)他是世界語的先驅(qū)……2024/10/29組合數(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ā)展起來的一門數(shù)學(xué)分支。計(jì)算機(jī)科學(xué)即算法的科學(xué)，而計(jì)算機(jī)所處理的對(duì)象是離散的數(shù)據(jù)，所以離散對(duì)象的處理就成了計(jì)算機(jī)科學(xué)的核心，而研究離散對(duì)象的科學(xué)恰恰就是組合數(shù)學(xué)。2024/10/29組合數(shù)學(xué)-上海理工大學(xué)7典型問題地圖著色問題：對(duì)世界地圖著色，每一個(gè)國家使用一種顏色。如果要求相鄰國家的顏色相異，是否總共只需四種顏色？這是圖論的問題。船夫過河問題：船夫要把一匹狼、一只羊和一棵白菜運(yùn)過河。只要船夫不在場，羊就會(huì)吃白菜、狼就會(huì)吃羊。船夫的船每次只能運(yùn)送一種東西。怎樣把所有東西都運(yùn)過河？這是線性規(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/10/29組合數(shù)學(xué)-上海理工大學(xué)8第一章排列與組合主要內(nèi)容：一、排列與組合二、排列組合的生成算法三、組合意義的解釋與應(yīng)用舉例2024/10/29組合數(shù)學(xué)-上海理工大學(xué)9一、排列與組合

加法法則和乘法法則

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

排列、組合

圓周排列

可重排列

可重組合

不相鄰的組合2024/10/29組合數(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

。集合論語言：基本假設(shè)：性質(zhì)A和性質(zhì)B是無關(guān)的兩類。2024/10/29組合數(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/10/29組合數(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

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

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

某種樣式的運(yùn)動(dòng)服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42=8種著色方案。若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則方案數(shù)就不是44=16，而只有43=12種。2024/10/29組合數(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/10/29組合數(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/10/29組合數(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/10/29組合數(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/10/29組合數(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/10/29組合數(shù)學(xué)-上海理工大學(xué)19如我們說A集合有n個(gè)元素|A|=n，無非是建立了將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/10/29組合數(shù)學(xué)-上海理工大學(xué)20一種常見的思路是按輪計(jì)場，費(fèi)事。另一種思路是淘汰的選手與比賽(按場計(jì))集一一對(duì)應(yīng)。99場比賽。例9

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

設(shè)凸n邊形的任意三條對(duì)角線不共點(diǎn)，求對(duì)角線在多邊形內(nèi)交點(diǎn)的個(gè)數(shù)。2024/10/29組合數(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/10/29組合數(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/10/29組合數(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)》長度n-2序列n個(gè)字母的長度n-2序列的數(shù)目是2024/10/29組合數(shù)學(xué)-上海理工大學(xué)25

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

|

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

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

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

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

31551111233455567②—③

15511113455567①—③

55111455567④—⑤

51115567⑤—⑥

11157①—⑤

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

由5種顏色的星狀物，20種不同的花排列成如下圖案：兩邊是星狀物，中間是3朵花，問共有多少種這樣的圖案？兩邊是星狀物，從五種顏色的星狀物中取兩個(gè)的排列的排列數(shù)是P(5,2)=20。20種不同的花取3種排列的排列數(shù)是根據(jù)乘法法則得圖案數(shù)為P(20,3)=20×19×18=6840。20×6840=136800。2024/10/29組合數(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/10/29組合數(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/10/29組合數(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/10/29組合數(shù)學(xué)-上海理工大學(xué)37組合的個(gè)數(shù)用C(n,r)

表示?；蛘哂帽硎?。定義：從

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

r個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為從n個(gè)中取r個(gè)的無重組合。C(n,r)=0，若n<r。2024/10/29組合數(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/10/29組合數(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/10/29組合數(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/10/29組合數(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/10/29組合數(shù)學(xué)-上海理工大學(xué)42解1：a1選擇其同伴有7種可能，選定后,余下6人中某一人選擇其同伴只有5種可能，余下4人，其中某1人有3種選擇可能，在余下的2人只好配成一對(duì)，無法選擇，故共有N=7×5×3=105。例17

假定有a1,a2,a3,a4,a5,a6,a7,a8這8位成員，兩兩配對(duì)分成4組，試問有多少種方案？（練習(xí)）2024/10/29組合數(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/10/29組合數(shù)學(xué)-上海理工大學(xué)44一個(gè)進(jìn)站方案可以表示成：00011001010100，其中“0”表示車，“1”表示間隔。其中“0”是不同元，“1”是相同元。給“1”這6個(gè)入口只用5個(gè)間隔。任意進(jìn)站方案可表示成上面14個(gè)元素的一個(gè)排列。例18

某廣場有6個(gè)入口，每個(gè)入口每次只能通過一輛汽車，現(xiàn)有9輛車要開進(jìn)廣場，有多少種入場方案？2024/10/29組合數(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/10/29組合數(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/10/29組合數(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/10/29組合數(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/10/29組合數(shù)學(xué)-上海理工大學(xué)49若無要求，則為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/10/29組合數(shù)學(xué)-上海理工大學(xué)50例215對(duì)夫婦出席一個(gè)宴會(huì)，圍一圓桌坐下，試問有幾種不同的坐法？要求每對(duì)夫婦相鄰又如何？若無限制，則為Q(10,10)；若要求相鄰，則為Q(5,5)×2×2×2×2×2。2024/10/29組合數(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/10/29組合數(shù)學(xué)-上海理工大學(xué)52定理：設(shè)多重集則S的r-(可重)排列數(shù)是kr。推論：設(shè)多重集且對(duì)一切的i=1,2,…k，有ni≥r，則S

的r-(可重)排列數(shù)是kr。2024/10/29組合數(shù)學(xué)-上海理工大學(xué)53所求的標(biāo)