12024/5/5離散數(shù)學(xué)DiscreteMathematics

汪榮貴教授合肥工業(yè)大學(xué)軟件學(xué)院專用課件.4第1頁(yè)第三章計(jì)數(shù)技術(shù)

第2頁(yè)學(xué)習(xí)內(nèi)容3.1TheBasicofCounting

計(jì)數(shù)基礎(chǔ)3.2ThePigeonholePrinciple鴿巢原理3.3PermutationsandCombinations排列與組合3.4RecurrenceandDivide-and-Conquer遞推與分治3.5GeneratingFunction生成函數(shù)3.6inclusion-exclusion容斥原理應(yīng)用第3頁(yè)

PermutationsandCombinations排列與組合

Generalized

PermutationsandCombinations普通性排列和組合GeneratingPermutationsandCombinations生成排列和組合

排列與組合

PermutationsandCombinations第4頁(yè)Introduction

Torecallpermutationsandcombinations回顧以前學(xué)過關(guān)于排列與組合知識(shí)Tounderstandpermutationsandcombinationsfromdifferentdegrees從不一樣角度了解排列與組合Tosolvecountingproblemsusingthem使用排列與組合處理計(jì)數(shù)問題Toshowhowtheoremsareprovedbycombinatorialarguments

排列與組合

PermutationsandCombinations第5頁(yè)ForexampleInhowmanywayscanweselectthreestudentsfromagroupoffivestudentstostandinlineforapicture?

從5個(gè)學(xué)生種選出3個(gè)學(xué)生站成一排攝影，一共有多少種選擇方式？

p(5,3)=5*4*3=60Thisexampleillustrateshoworderedarrangementsofdistinctobjectscanbecounted.Thisleadstosometerminology.這個(gè)例子顯示了怎樣計(jì)數(shù)不一樣目標(biāo)次序安排問題，并引入一些術(shù)語。

排列（Permutations）

第6頁(yè)Notation:P(n,r)

排列（Permutations）

【Definition】Apermutationofasetofdistinctobjectsisanorderedarrangementoftheseobjects.Anordered

arrangementofrelementsofasetiscalledanr-permutation.

不一樣個(gè)體集合一個(gè)排列是這些個(gè)體一個(gè)有序安排.一個(gè)集合r個(gè)元素有序安排叫做r排列.

第7頁(yè)Example1設(shè)S={1,2,3}。3，1，2是S一個(gè)排列，3，2是S一個(gè)2排列。一個(gè)n元集r排列數(shù)積為P（n,r）.我們能夠使用乘積法則求出P（n,r）第8頁(yè)【Theorem1】Ifnisapositiveintegerandrisanintegerwith1<r<n,thentherearer-permutationsofasetwithndistinctelements.含有n個(gè)不一樣元素集合r排列數(shù)是

P(n,r)=n(n-1)(n-2)…(n-r+1)Proof:Usingtheproductrule.

從定理1得出P(n,r)=n(n-1)(n-2)…(n-r+1)=n!/(n-r)!

尤其地有，

P(n,n)=n!

排列（Permutations）

第9頁(yè)Example2在進(jìn)入競(jìng)賽100個(gè)不一樣人中有多少種方法選出一個(gè)一等獎(jiǎng)得主、一個(gè)二等獎(jiǎng)得主和一個(gè)三等獎(jiǎng)得主？Solution：

不論哪個(gè)人得哪個(gè)獎(jiǎng)，選取3個(gè)得獎(jiǎng)人方法是從100個(gè)元素集合中有序選擇3個(gè)元素方法數(shù)，即100個(gè)元素集合3-排列數(shù)。所以，答案是

P(100,3)=100*99*98=970200第10頁(yè)Example3假定有8個(gè)賽跑運(yùn)動(dòng)員。第一名得到一枚金牌，第二名得到一枚銀牌，第三名得到一枚銅牌。假如比賽可能出現(xiàn)全部可能結(jié)果，有多少種不一樣頒獎(jiǎng)方式？Solution：

頒獎(jiǎng)方式就是8元素集合3-排列數(shù)。所以存在P(8,3)=8*7*6=336種可能頒獎(jiǎng)方式。第11頁(yè)Example4假定一個(gè)女推銷員要訪問8個(gè)不一樣城市。她訪問必須從某個(gè)指定城市開始，但對(duì)其它7個(gè)城市訪問能夠按照任何次序進(jìn)行。當(dāng)訪問這些城市時(shí)，這個(gè)女推銷員能夠有多少種可能次序？第12頁(yè)Solution：

因?yàn)榈谝粋€(gè)城市是確定，而其它7個(gè)城市能夠使任意次序，故城市之間可能路徑數(shù)是7個(gè)元素排列數(shù)。所以，這個(gè)女推銷員有7!=7*6*5*4*3*2*1=5040種方式選擇她旅行。比如說，假如這個(gè)女推銷員想要在城市中找出含有最短距離路徑，而且她對(duì)每一條可能路徑計(jì)算總距離，那么她必須考慮5040條路徑。第13頁(yè)Example5字母ABCDEFGH有多少種排列包含串ABC？Solution：

因?yàn)樽帜窤BC必須成組出線，我們能夠經(jīng)過找6個(gè)對(duì)象，即組ABC和單個(gè)字母D、E、F、G和H排列數(shù)得到答案。因?yàn)檫@6個(gè)對(duì)象能夠按任何次序出線，存在6！=6*5*4*3*2*1=720種ABCDEFGHZ字母排列，其中ABC成組出現(xiàn)。第14頁(yè)【Example】集合{a,b,c,d,e,f,g}有多少個(gè)排列？Solution：

本題就是一個(gè)7元集合全排列問題，所以，答案是p(7,7)=7*6*5*4*3*2*1=5040第15頁(yè)【example】{a,b,c,d,e,f,g}有多少個(gè)排列以a結(jié)尾？Solution：

符合題意7元素排列中都是以字母a結(jié)尾，其它6個(gè)位置能夠是任何次序排列，故以a結(jié)尾排列數(shù)有6！=6*5*4*3*2*1=720個(gè)第16頁(yè)Solution：

7個(gè)子母中有A和E兩個(gè)元音字母.所以符合要求排列中，前兩個(gè)字母只能從兩個(gè)元音字母中選擇可能方法數(shù)是2!對(duì)于后面五個(gè)輔音字母可能排列數(shù)是5!.所以完成符合題意排列全部可能排列數(shù)為2!5!【example】以A、B、C、D、E、F、G7個(gè)字母組成排列中在多少個(gè)排列中是兩個(gè)元音字母在五個(gè)輔音字母之前？第17頁(yè)【Example】一個(gè)組有n個(gè)男士和n個(gè)女士。假如把他們男女相間地排成一排，有多少種方式？Solution:

我們假設(shè)這一排列能夠有不一樣性別排頭。首先我們先考慮n個(gè)男士排列，全部排列數(shù)P(n,n)=n!

一樣我們也能夠得到n個(gè)女士排列數(shù)也為n!.

現(xiàn)在將n個(gè)男士與n個(gè)女士相間排列，我們能夠采取先將女士排列好，然后往其中進(jìn)行男士排列，并存在男士作為排頭或女士作為排頭兩種情況。由乘積法則能夠知道總排列方式數(shù)為

第18頁(yè)【example】有多少種方式使得10個(gè)女士和6個(gè)男士站成一排而且沒有兩個(gè)男士彼此相鄰？（提醒：先放女士，后考慮男士位置）Solution：

首先考慮女士排列，一共有10個(gè)女士可能排列數(shù)為P(10,10)

然后由10個(gè)女生組成排列形成了11個(gè)空隙，然后我們分別將6名男士安排站入11個(gè)空隙中，全部可能方式數(shù)為P(11,6).所以完成整個(gè)任務(wù)排列數(shù)為

P(10,10)P(11,6)=10！11！/5！第19頁(yè)Solution：

a)將B單位3個(gè)人某一排列作為一個(gè)元素，參加A單位進(jìn)行排列?？傻梅桨笖?shù)為(7+1)!=8!且B單位3人有3!種排列。

由乘法原理，總排列方案數(shù)為8!3!【example】A單位有7位代表，B單位有3位代表，排成一列合影，要求B單位3人排在一起。

a)

問有多少種不一樣排列方案？

b)若B單位3人不能相鄰，且A單位2人排在兩端，問有多少種不一樣排列方案。第20頁(yè)

b)先對(duì)A單位7人進(jìn)行排列。全部可能排列數(shù)共有7!種。假設(shè)A1A2A3A4A5A6A7是A一個(gè)排列。兩端固定后，B單位3人中第一人有6種選擇

A1*A2*A3*A4*A5*A6*A7即上面*位置，第二位為了不與第一位相鄰，故只有5種選擇。第三位有4種選擇。故排列總數(shù)為7!×6×5×4=604800第21頁(yè)

組合(Combinations)

【Definition】Anr-combinationofelementsofasetisanunorderedselectionofrelementsfromtheset.

集合元素一個(gè)r組合是從這個(gè)集合無序選取r個(gè)元素Example6設(shè)S是集合{1，2，3，4}，那么{1，3，4}是S一個(gè)3組合。Note:Anr-combinationissimplyasubsetofasetwithrelements.

一個(gè)r組合是這個(gè)集合一個(gè)r個(gè)元素子集。Notation符號(hào):第22頁(yè)Example7因?yàn)閧a,b,c,d}

2-組合是{a,b},{a,c},{a,d},{b,c},{b,d}和{c,d}6個(gè)子集，我們有C（4，2）=6.注意：我們能夠用關(guān)于集合r排列數(shù)公式確定n元素集合r組合數(shù)。為此只需注意到集合r排列能夠按下述方法得到：先構(gòu)成集合r組合，然后排列這些組合種元素。下面定理給出了C(n,r)值。第23頁(yè)

組合(Combinations)

【

Theorem2】Thenumberofr-combinationofasetwith

nelements,wherenisapositiveintegerandrisanintegerwith0

r

n,equals設(shè)n是正整數(shù)，r是滿足0

r

n整數(shù)，n元素集合r組合數(shù)等于

C(n,r)=n!/r!(n-r)!第24頁(yè)proof：

能夠以下得到這個(gè)集合r排列。首先得到集合C(n,r)個(gè)r-組合，然后以P(n,r)

種方式排序每個(gè)r組合中元素，這能夠用P(r,r)種方式來做。所以，

P(n,r)=C(n,r)*P(r,r)這就推出注意：該公式在n和r很大時(shí)候，計(jì)算并不方便，且有可能產(chǎn)生值不是一個(gè)整數(shù)。在實(shí)踐中，能夠從分子和分母中消去分母大因式中全部項(xiàng)，把分子中全部沒有消去項(xiàng)相乘，然后除以分母中較小因式。第25頁(yè)下面給出一個(gè)關(guān)于集合r組合數(shù)有用恒等式。[推論1]設(shè)n和r是滿足r

n非負(fù)整數(shù)，那么C(n,r)=C(n,n-r).Proof:由定理2得到和所以，C(n,r)=C(n,n-r).第26頁(yè)Example8有多少種方式從10個(gè)選手網(wǎng)球隊(duì)中選擇5個(gè)選手外出參加在另一個(gè)學(xué)校比賽？Solution：答案由10元素集合5-組合數(shù)給出。依據(jù)定理2，這個(gè)組合數(shù)是

第27頁(yè)Example9一組30個(gè)人被培訓(xùn)作為宇航員去完成首次登陸火星任務(wù)。有多少種方式選出6個(gè)人小組來完成這個(gè)任務(wù)（假設(shè)全部小組組員有一樣工作）？Solution：

因?yàn)椴豢紤]這些人被選次序，從30個(gè)人中選6個(gè)人小組方式數(shù)是30元素集合6-組合數(shù)。依據(jù)定理2，這個(gè)組合數(shù)是

第28頁(yè)Example10有多少個(gè)長(zhǎng)為n二進(jìn)制串恰好包含r個(gè)1？Solution：

在長(zhǎng)為n二進(jìn)制串中r個(gè)1位置組成了集合{1,2,…,n}r組合。所以有C(n,r)個(gè)長(zhǎng)為n二進(jìn)制串恰好包含r個(gè)1.第29頁(yè)Example11

為開發(fā)學(xué)校離散數(shù)學(xué)課程要選出一個(gè)委員會(huì)。假如數(shù)學(xué)系有9個(gè)教師，計(jì)算機(jī)科學(xué)系有11個(gè)教師。而這個(gè)委員會(huì)要由3個(gè)數(shù)學(xué)系教師和4個(gè)計(jì)算機(jī)科學(xué)系教師組成，那么有多少種選擇方式？Solution：

由乘積法則，答案是9元素集合3組合數(shù)與11元素集合4組合數(shù)之積。依據(jù)定理2，選擇這個(gè)委員會(huì)方式數(shù)是第30頁(yè)【example】一個(gè)10元素集合有多少個(gè)子集含有奇數(shù)個(gè)元素？Solution：

10元素集合含有奇數(shù)個(gè)元素子集分別有：

1元素子集，3元素子集，5元素子集，7元素子集，9元素子集所以我們能夠得到10元素集合含有奇數(shù)元素全部子集數(shù)即為

C(10,1)+C(10,3)+C(10,5)+C(10,7)+C(10,7)=512第31頁(yè)【example】Asoccerclubhas8femaleand7malemembers.Fortoday’smatch,howmanypossibleconfigurationsarethere?英式足球俱樂部有8名女性和7名男性，對(duì)于今天比賽，有多少可能性搭配？（1）Thecoachwantstohave6femaleand5maleplayersonthegrass.俱樂部想要6名女性和5名男性參加比賽（2）Thecoachwantstohave11playerswithatmost5maleplayers

onthegrass.俱樂部想要選出11名運(yùn)動(dòng)員參加比賽，其中至多由5名男性運(yùn)動(dòng)員第32頁(yè)Solution:C(8,6)C(7,5)=8!/(6!2!)7!/(5!2!)=2821=588(2)C(8，6)C(7，5)+C(8，7)C(7，4)+C(8，8)C(7，3)第33頁(yè)【example】多少個(gè)12位二進(jìn)制串包含

a)恰好3個(gè)1？b)至多3個(gè)1？c)最少3個(gè)1？d)0個(gè)數(shù)和1個(gè)數(shù)相等？Solution:a)我們能夠把問題看做從12個(gè)位置中選出3個(gè)位置放置1，全部可能二進(jìn)位串個(gè)數(shù)為C(12,3)=220

b)可了解為在12個(gè)位置中放入3個(gè)1、2個(gè)1、1個(gè)1、0個(gè)1情況，所有可能二進(jìn)位串個(gè)數(shù)為

C(12,3)+C(12,2)+C(12,1)+C(12,0)=298第34頁(yè)

c)12位二進(jìn)位串中包含1個(gè)數(shù)最少是3，就意味著包含1個(gè)數(shù)可能是3個(gè)、4個(gè)、5個(gè)、6個(gè)、7個(gè)、8個(gè)、9個(gè)、10個(gè)、11個(gè)、12個(gè)，所以能夠得到全部二進(jìn)位串個(gè)數(shù)為C(12,3)+C(12,4)+C(12,5)+C(12,6)+C(12,7)+C(12,8)+C(12,9)+C(12,10)+C(12,11)+C(12,12)d)長(zhǎng)度為12二進(jìn)位串中當(dāng)0個(gè)數(shù)為6時(shí)，恰好0和1個(gè)數(shù)是相同。所以能夠得到全部可能二進(jìn)位串個(gè)數(shù)為C(12,6)=924第35頁(yè)【example】一個(gè)壘球隊(duì)13個(gè)人出席一場(chǎng)比賽。

a)有多少種方式選10個(gè)選手上場(chǎng)？

b)有多少種方式從13個(gè)在場(chǎng)人中分配10個(gè)選手位置？

c)13個(gè)出席人中有3個(gè)女士。假如上場(chǎng)選手中要求最少有一個(gè)女士，那么有多少種方式選擇10個(gè)選手？第36頁(yè)Solution：

a)該題即為從13個(gè)人中任選10個(gè)人出席比賽。全部可能方式數(shù)為C(13,10)=286

b)該題可了解為從13個(gè)人中選出10個(gè)人排成一排情況。全部可能方式數(shù)為P(13,10)=13!/3!=1037836800c)由a)中解答知道從13個(gè)人中任選10個(gè)人全部組合數(shù)為286。其中只有全選男士這一個(gè)組合方式中石不包含女士。所以該題中全部可能方式數(shù)為286-1=285第37頁(yè)【example】假定某個(gè)系包含10名男士和15名女士。有多少種方式組成一個(gè)6人委員會(huì)且使得它含有女士比男士多？Solution：當(dāng)6人委員會(huì)中女士多于男士時(shí)有三種情況：包含0名男士和6名女士、包含1名男士和5名女士、包含2名男士和4名女士這三種情況可能方式數(shù)分別為

C(15,6)、C(15,5)C(10,1)、C(15,4)C(10,2)

所以，全部可能方式數(shù)為

C(15,6)+C(15,5)C(10,1)+C(15,4)C(10,2)=96460第38頁(yè)Solution:

將每個(gè)0個(gè)2個(gè)1綁定在一起作為一個(gè)元素，所以5個(gè)0和14個(gè)1能夠變?yōu)?個(gè)011和4個(gè)1一共是9個(gè)元素。然后該問題就能夠了解為在字符串中9個(gè)位置中選擇4個(gè)位置來放置1?？偪赡茏址畟€(gè)數(shù)為

C(9,4)=126【example】有多少個(gè)二進(jìn)制串恰好包含5個(gè)0和14個(gè)1，假如每個(gè)0后面緊跟著2個(gè)1？第39頁(yè)

PermutationsandCombinations排列與組合

Generalized

PermutationsandCombinations普通性排列和組合GeneratingPermutationsandCombinations生成排列和組合

排列與組合

PermutationsandCombinations第40頁(yè)Introduction普通性排列和組合Generalized

PermutationsandCombinations

r-permutation,r-combinationwithnorepetitionallowed無重復(fù)r-排列和r-組合

r-permutation,r-combinationwithrepetition有重復(fù)r-排列和r-組合

第41頁(yè)P(yáng)ermutationsWithRepetition

有重復(fù)排列

Example1用英文字母能夠組成多少個(gè)n位字符串？

solution：

因?yàn)橛?6個(gè)字母，且每個(gè)字母能夠被重復(fù)使用，由乘積法則能夠看出存在26n個(gè)n位字符串。下面定理1給出了當(dāng)允許重復(fù)時(shí)一個(gè)n元素集合r排列數(shù)。第42頁(yè)P(yáng)ermutationsWithRepetition有重復(fù)排列

Proof：

當(dāng)允許重復(fù)時(shí)，在r排列中對(duì)r個(gè)位置中每個(gè)位置有n種方式選擇集合元素，因?yàn)閷?duì)每個(gè)選擇，全部n個(gè)物體都是有效。所以，有乘積法則，當(dāng)允許重復(fù)時(shí)存在nr個(gè)r排列?！?/p>

Theorem1】Thenumberofr-permutationsofasetofn

objectswithrepetitionallowedisnr.含有n個(gè)物體集合允許重復(fù)r排列數(shù)是nr.

第43頁(yè)Solution：

當(dāng)允許重復(fù)時(shí)，在5排列中對(duì)5個(gè)位置中每個(gè)位置有5種方式選擇集合元素。因?yàn)閷?duì)每個(gè)選擇，全部5個(gè)元素都是有效。所以，由乘積法則，當(dāng)允許重復(fù)時(shí)存在5排列數(shù)為55【example】從一個(gè)5元素集合中允許重復(fù)地有序選取5個(gè)元素有多少種不一樣方式？第44頁(yè)Solution：

因?yàn)檫@個(gè)學(xué)生天天都能夠從這6中三明治中選一個(gè)作為午餐。所以一周7天里這個(gè)學(xué)生選擇三明治全部方式數(shù)為67【example】天天一個(gè)學(xué)生從一堆包好三明治中隨機(jī)選1塊三明治作為午飯。假如有6種三明治而且選擇三明治次序無關(guān)，在一周7天里這個(gè)學(xué)生選擇三明治有多少種不一樣方式？第45頁(yè)CombinationWithRepetition有重復(fù)組合

由下面實(shí)例考慮怎樣處理元素允許重復(fù)組合問題。Example2

從包含蘋果、橙子、和梨碗里選4個(gè)水果。假如選擇水果次序無關(guān)，且只關(guān)心水果類型而不論是該類型哪一個(gè)水果，那么當(dāng)碗中每類水果最少有4個(gè)時(shí)有多少種選法？

第46頁(yè)解答：為了求解這個(gè)問題，我們列出選擇水果全部可能方式。共有15種方式：

4個(gè)蘋果

4個(gè)橙子

4個(gè)梨3個(gè)蘋果，1個(gè)橙子

3個(gè)蘋果，1個(gè)梨

3個(gè)梨，1個(gè)蘋果3個(gè)橙子，1個(gè)梨

3個(gè)梨，1個(gè)蘋果

3個(gè)梨，1個(gè)橙子2個(gè)蘋果，2個(gè)橙子

2個(gè)蘋果，2個(gè)梨

2個(gè)橙子，2個(gè)梨2個(gè)蘋果，1個(gè)橙子，1個(gè)梨

2個(gè)橙子，1個(gè)蘋果，1個(gè)梨2個(gè)梨，1個(gè)蘋果，1個(gè)橙子

這個(gè)解是從3個(gè)元素集合{蘋果、梨、橙子}中允許重復(fù)4組合數(shù)。第47頁(yè)Solution：

因?yàn)榧垘疟贿x次序是無關(guān)且7種不一樣類型紙幣都能夠選5次，該題是計(jì)數(shù)從7個(gè)元素集合中允許重復(fù)5組合數(shù)。列出全部可能性將是很繁瑣，因?yàn)榇嬖诮馓嗔?。在這里我們將給出一個(gè)方法來計(jì)數(shù)允許重復(fù)組合數(shù)。

Example3

從包含1美元、2美元、5美元、10美元、20美、元、50美元及100美元錢袋中選5張紙幣，有多少種方式？假定不論紙幣被選次序，同種幣值紙幣都是不加區(qū)分，而且最少每張紙幣有5張。第48頁(yè)

假設(shè)一個(gè)零錢盒子有7個(gè)隔間，每個(gè)保留一個(gè)紙幣，以下列圖所表示。這些隔間被6塊隔板分開，每選擇1張紙幣就在對(duì)應(yīng)隔間里放置1個(gè)標(biāo)識(shí)。針對(duì)選擇5張紙幣3種不一樣方式給出了這種對(duì)應(yīng)，其中豎線表示6個(gè)隔板，星表示5張紙幣。

第49頁(yè)第50頁(yè)

選擇5張紙幣方法數(shù)對(duì)應(yīng)了安排6條豎線和5顆星方法數(shù)。所以，選擇5張紙幣方法數(shù)就是從11個(gè)可能位置選5顆星位置方法數(shù)。這對(duì)應(yīng)了從含11個(gè)物體集合中無序地選擇5個(gè)物體方法數(shù)，能夠有C(11,5)種方法.所以從7類紙幣袋中選擇5張紙幣方式數(shù)有第51頁(yè)將例3中方法普通化得到定理2.【

Theorem2】ThereareC(n-1+r,r)r-combinationfromasetwithnelementswhenrepetitionofelementsisallowed.n個(gè)元素集合中允許重復(fù)r組合有C(n-1+r,r)

第52頁(yè)P(yáng)roof:

當(dāng)允許重復(fù)時(shí)n元素集合每個(gè)r組合能夠用n-1條豎線和r顆星表表示這n-1條豎線用來標(biāo)識(shí)n個(gè)不一樣單元。每當(dāng)集合第i個(gè)元素出現(xiàn)在組合中，第i個(gè)單元就包含一顆星。比如，4元素集合一個(gè)6組適用3條數(shù)先和6顆星來表示。這里**|*||***代表了恰好包含2個(gè)第一元素、2個(gè)第二元素、0個(gè)第三元素和3個(gè)第四元素組合。正如我們已經(jīng)看到，包含n-1條豎線和r顆星每一個(gè)不一樣表對(duì)應(yīng)了n元素集合允許重復(fù)一個(gè)r組合。這種表個(gè)數(shù)是C(n-1+r,r),因?yàn)槊總€(gè)表對(duì)應(yīng)了從包含r顆星和n-1條豎線n-1+r個(gè)位置來放r顆星一個(gè)選擇。第53頁(yè)Example4設(shè)一家甜點(diǎn)店有4種不一樣類型甜點(diǎn)，那么從中選6塊甜點(diǎn)有多少種不一樣方式？假定只關(guān)心甜點(diǎn)類型，而不論是哪一塊甜點(diǎn)或者選擇次序。定理2使用Solution：

選擇6塊甜點(diǎn)方式數(shù)是含有4類元素集合6組合數(shù)。由定理2這等于C(4+6-1,6)=C(9,6).所以能夠得到選擇6塊甜點(diǎn)不一樣方式數(shù)有第54頁(yè)Example5方程x1+x2+x3=11有多少個(gè)解？其中x1、x2、x3是非負(fù)整數(shù)。使用定理2求解線性方程組整數(shù)解個(gè)數(shù)Solution：為計(jì)數(shù)解個(gè)數(shù)，注意到一個(gè)解對(duì)應(yīng)了從3元素集合中選11個(gè)元素方式，以使得x1選自第一類，x2選自第二類，x3選自第三類。所以，解得個(gè)數(shù)等于3元素集合允許重復(fù)11組合數(shù)。由定理2，存在解個(gè)數(shù)為

第55頁(yè)討論：當(dāng)例5中變?cè)菨M足整數(shù)時(shí)求出這個(gè)方程解個(gè)數(shù)？Solution：

滿足此限制方程解對(duì)應(yīng)于11個(gè)項(xiàng)選擇，使得項(xiàng)x1取自第一類，項(xiàng)x2取自第二類，項(xiàng)x3取自第三類，而且第一類元素最少取1個(gè)，第二類元素最少取2個(gè)，第三類元素最少去3個(gè)。所以，先選1個(gè)第一類元素，2個(gè)第二類元素，3個(gè)第三類元素：然后再多項(xiàng)選擇5個(gè)元素。由定理2，方程解個(gè)數(shù)為

C(3+5-1,5)=C(7,5)=C(7,2)=7*6/2=21第56頁(yè)在一個(gè)n元素集合允許重復(fù)r組合和把r個(gè)相同球放到n個(gè)不一樣箱子方法之間存在一一對(duì)應(yīng)關(guān)系。為建立這種對(duì)應(yīng)，每次我們把一個(gè)球放到第i個(gè)箱子里，集合第i個(gè)元素就加到這個(gè)r組合中。第57頁(yè)Example6

有多少種方法把10個(gè)相同球放入8個(gè)不一樣箱子？solution：把10個(gè)相同球放入8個(gè)不一樣箱子方法數(shù)等于8個(gè)元素集合允許重復(fù)10組合數(shù)，所以存在方法有

第58頁(yè)Example7在下面?zhèn)未a被執(zhí)行后k值是多少？

第59頁(yè)Solution:

k初值是0，且對(duì)于滿足整數(shù)序列每次經(jīng)過這個(gè)嵌套循環(huán)時(shí)k值就加1.這種整數(shù)序列個(gè)數(shù)是從{1,2,…,n}種允許重復(fù)地選擇m個(gè)整數(shù)方式數(shù)。（為看到這一點(diǎn)只需注意到一旦這個(gè)整數(shù)序列選定以后，如果我們按非降次序排列序列中整數(shù)，這就唯一地確定了一組對(duì)賦值。相反，每個(gè)這么賦值對(duì)應(yīng)了一個(gè)唯一無序集合。）所以由定理2得出在這個(gè)代碼被執(zhí)行后

k=C(n+m-1，m)第60頁(yè)從一個(gè)n元集合中，允許重復(fù)和不允許重復(fù)地選擇r個(gè)元素，其有序或無序選擇數(shù)公式在下表中給出。第61頁(yè)Solution：

選擇12個(gè)多納圈方式數(shù)是含有21類元素12組合數(shù)。由定理2這等于C(21+12-1,12)=C(32,12)=9817080【example】從一個(gè)商店21種多納圈中選擇12個(gè)多納圈有多少種不一樣方式？第62頁(yè)Solution：該題是從5中硬幣中允許重復(fù)取出20個(gè)硬幣組合問題。由定理2得到全部方式數(shù)為C(5+20-1,20)=C(24,20)=C(24,4)=10626【example】假如一個(gè)小豬儲(chǔ)錢罐中有1美分5美分10美分25美分50美分等硬幣，那么20個(gè)硬幣有多少種方式？第63頁(yè)Solution：

假設(shè)3個(gè)庫(kù)房是不一樣，而且wi表示放入第i個(gè)庫(kù)房書數(shù)量，則滿足w1+w2+w3=3000由定理2可知全部方式數(shù)為C(3000+3-1,3000)=C(3002,3000)=C(3002,2)=4504501【example】一個(gè)出版商有3000本離散數(shù)學(xué)書，假如這些書是沒有區(qū)分，那么將這些書存放在3個(gè)庫(kù)房有多少種方式？第64頁(yè)【example】方程

x1+x2+x3+x4+x5+x6=29有多少個(gè)解？第65頁(yè)Solution:

為計(jì)數(shù)解得個(gè)數(shù)，注意到一個(gè)解對(duì)應(yīng)了從6個(gè)元素集合中選29個(gè)元素方式，以使得項(xiàng)xi取自第i類（i=1,2,3,4,5,6,）。

a)滿足此限制方程解對(duì)應(yīng)于29個(gè)項(xiàng)選擇，使得項(xiàng)xi取自第i類，而且第i類最少選2個(gè)。所以先從第i類選2個(gè)元素（i=1,2,3,4,5,6,），然后再多項(xiàng)選擇17個(gè)元素。由定理2，全部方式數(shù)為C(6+17-1,17)=C(22,17)=C(22,5)=26334第66頁(yè)

b)

滿足此限制時(shí):先選1個(gè)第一類元素、2個(gè)第二類元素、3個(gè)第三類元素、4個(gè)第四類元素、6個(gè)第五類元素、6個(gè)第六類元素.然后再多項(xiàng)選擇7個(gè)元素。由定理2，全部方式數(shù)為C(6+7-1,7)=C(12,7)=C(12,5)=792

c)

本題中沒有限制條件時(shí)，方程全部解得個(gè)數(shù)為C(6+29-1,29)=C(34,29)=C(34,5)=278256

而滿足限制時(shí)方程解個(gè)數(shù)為C(6+23-1,23)=C(28,23)=C(28,5)=98280所以滿足本題方程解個(gè)數(shù)為

278256-98280=179976第67頁(yè)

d)在限制條件同時(shí)x1無限制情況下，方程解個(gè)數(shù)為C(6+20-1,20)=C(25,20)=53130

當(dāng)又添加條件后，方程解個(gè)數(shù)即為

C(6+12-1,12)=C(17,12)=6188

所以，符合本題條件方程解個(gè)數(shù)53130-6188=46942第68頁(yè)【example】12本書在一個(gè)書架上排成一排。從中選5本書而且使得沒有2本書相鄰有多少種方式？Solution：

我們將選書用豎線表示，沒選書用星表示，則本題即為計(jì)數(shù)含5條豎線和7顆星且沒有2條豎線相鄰序列數(shù)。因?yàn)?條豎線排列組成了6個(gè)空隙

1|2|3|4|5|6

第二到第五個(gè)空隙每一個(gè)中都最少插入一個(gè)星使得沒有2本選中數(shù)是相鄰，最終還剩下3個(gè)星能夠任意插入這6個(gè)空隙。所以，全部可能方式數(shù)有C(6+3-1,3)=C(8,3)=56第69頁(yè)P(yáng)ermutationsofSetsWithIndistinguishableObjects

含有不可區(qū)分物體集合排列Example8重新排序單詞SUCCESS字母能組成多少個(gè)不一樣串？在計(jì)數(shù)問題中一些元素可能是沒有區(qū)分，在這種情況下必須小心防止重復(fù)計(jì)數(shù)。下面以一個(gè)實(shí)例說明該問題。第70頁(yè)Solution：

因?yàn)镾UCCESS中一些字母是重復(fù)，答案并不是7個(gè)字母排列數(shù)。這個(gè)單詞包含3個(gè)S、2個(gè)C、1個(gè)U和1個(gè)E.為確定重新排序單詞中字母能組成多少個(gè)不一樣串,首先，注意到3個(gè)S能夠用C(7,3)種不一樣方式放在7個(gè)位置中，剩下4個(gè)空位。然后能夠用C(4,2)中方式放2個(gè)C，留下2個(gè)空位。又能夠用C(2,1)種方式放U，留下1個(gè)空位。所以，放E只有C(1,1)種方式。從而，由乘積法則，產(chǎn)生不一樣串?dāng)?shù)是第71頁(yè)由例8中推論，我們得到定理3。【

Theorem3】Thenumberofdifferentpermutationsofnobjects,wheretherearen1indistinguishableobjectsoftype1,…,andnk

indistinguishableobjectsoftypek,is設(shè)類型1相同物體有n1個(gè)，類型2相同物體有n2個(gè)，…，類型k相同物體有nk個(gè)，那么n個(gè)物體不一樣排數(shù)是

n!/(n1!n2!…nk!)

第72頁(yè)P(yáng)roof:為確定排列數(shù)，首先能夠用C(n,n1)種方式在n個(gè)位置中放置類型1n1個(gè)物體，剩下n-n1個(gè)空位。然后用C(n-n1，n2)種方式放類型2物體，剩下n-n1-n2個(gè)空位。繼續(xù)放類型3物體,...,類型k-1物體，直到最終可用C(n-n1-n2-…-nk-1,nk)種方式放類型k物體。所以由乘積法則，不一樣排列總數(shù)是第73頁(yè)【example】假設(shè)一個(gè)大家庭有14個(gè)孩子，包含2組三胞胎、3組雙胞胎以及2個(gè)單胞胎。這些孩子坐在一排椅子上，假如相同三胞胎或雙胞胎孩子不能相互區(qū)分，那么有多少種方式？第74頁(yè)Solution：

因?yàn)檫@些孩子中有些孩子是不能相互區(qū)分，答案并不是14個(gè)孩子排列數(shù)。這些孩子中包含2組三胞胎、3組雙胞胎已近2個(gè)單胞胎。為確定排列這些孩子能組成多少個(gè)不一樣排列，首先注意到一組三胞胎能夠用C(14,3)中不一樣方式放在14個(gè)位置中，剩下11個(gè)空位。然后能夠用C(11,3)中可能方式放另一組三胞胎，留下8個(gè)空位又能夠用C(8,2)中方式將一組雙胞胎放在8個(gè)位置中。依次類推，將剩下孩子放入方式數(shù)分別為C(6,2)、C(4,2)、C(2,1)、C(1,1)。由乘積法則，產(chǎn)生不一樣排列數(shù)是

第75頁(yè)Solution：若要求3個(gè)字母A必須連續(xù)，不妨將3個(gè)A看做是一個(gè)元素，則總元素?cái)?shù)為6，其中有2個(gè)字母R。對(duì)于兩個(gè)字母R我們能夠用C(6,2)種方式放在6個(gè)位置中，剩下4個(gè)字母分別有C(4,1)C(3,1)C(2,1)C(1,1)中方式放入排列中。由乘積法則，產(chǎn)生不一樣串?dāng)?shù)是C(6,2)C(4,1)C(3,1)C(2,1)C(1,1)=6!/2!=360【example】使用AARDVARK中全部字母且全部3個(gè)A必須連續(xù)，能夠結(jié)構(gòu)多少個(gè)不一樣串？第76頁(yè)【example】使用SEERESS中字母能夠結(jié)構(gòu)多少個(gè)最少含5個(gè)字符串？Solution：我們需要使用定理3對(duì)長(zhǎng)度為5、6、7字符串分別進(jìn)行考慮。字符串長(zhǎng)度為7時(shí)，全部可能字符串?dāng)?shù)是7!/(3!3!1!)=140字符串個(gè)數(shù)長(zhǎng)度為6時(shí)，我們刪去字母R時(shí)，全部可能字符串?dāng)?shù)是6!/(3!3!)=20刪去字母S時(shí)，全部可能字符串?dāng)?shù)是

6!/(3!2!1!)=60刪去字母E時(shí)，全部可能字符串?dāng)?shù)是

6!/(3!2!1!)=60第77頁(yè)

由此我們能夠得到字符串長(zhǎng)度為6時(shí)，總可能字符串?dāng)?shù)20+60+60=140

字符串長(zhǎng)度為5時(shí)，存在情況分別為：刪去2個(gè)字符E或者2個(gè)字符S時(shí)，每一個(gè)可能存在字符串?dāng)?shù)為5!/(3!1!1!)=20刪除字符E和S時(shí)，可能存在字符串?dāng)?shù)為5!/(2!2!1!)=30

刪除字符R和E或者是刪除字符R和S時(shí)，可能存在字符串?dāng)?shù)都為5!/(3!2!)=10由此我們能夠得到字符串長(zhǎng)度為5時(shí)，總可能字符串?dāng)?shù)為20+20+30+10+10=90第78頁(yè)【example】有多少種不一樣方法在xyzw空間上從原點(diǎn)（0，0，0，0）抵達(dá)（4，3，5，4）點(diǎn)？這個(gè)旅行每一步是在x、y、z或w正方向移動(dòng)一個(gè)單位。Solution：我們使用一個(gè)包含4個(gè)x，3個(gè)y，5個(gè)z和4個(gè)w序列來表示任何一次旅行。由定理3，存在全部不一樣方法數(shù)是16!/(4!3!5!4!)=50450400第79頁(yè)對(duì)于有些計(jì)數(shù)問題能夠經(jīng)過枚舉把不一樣物體放入不一樣盒子方式數(shù)來求解。Example9有多少種方式把52張標(biāo)準(zhǔn)撲克牌發(fā)給4個(gè)人似每個(gè)人5張牌？把物體放入盒子問題Solution：

第一個(gè)人得到5張牌能夠有C(52,5)種方式，剩下47張牌。第二個(gè)人得到5張牌可能有C(47,5)種方式。第三個(gè)人得5張牌有C(42,5)種方式，第四個(gè)人得5張牌有C(37,5)種方式。所以發(fā)給4個(gè)人每人5張牌方式總數(shù)是第80頁(yè)由前面例子能夠得到以下定理用于求解把不一樣物體分配到不一樣盒子計(jì)數(shù)問題。【

Theorem4】Thenumberofwaystodistributen

distinguishableobjectsintokdistinguishableboxessothatniobjectsareplaceintoboxi,i=1,2,…,k,equals把n個(gè)不一樣物體分配到k個(gè)不一樣盒子使得ni個(gè)物體放入盒子方式數(shù)等于

n!/(n1!n2!…nk!)第81頁(yè)P(yáng)roof:

首先，在第1個(gè)盒子中放入n1個(gè)物體，能夠有C(n,n1)種方式，然后剩下物體有n-n1個(gè)，對(duì)第2個(gè)盒子中放入n2個(gè)物體方式有C(n-n1,n2)類似地能夠得到放n3個(gè)物體到第3個(gè)盒子方式數(shù)為C(n-n1-n2,n3),依次進(jìn)行，直到放nk個(gè)物體到第k個(gè)盒子中可能方式數(shù)為C(n-n1-n2-…-nk-1,nk),因?yàn)榇嬖趎1+n2+…+nk=n,得到

C(n-n1-n2-…-nk-1,nk)=C(nk,nk)=1現(xiàn)在依據(jù)乘積法則，完成整個(gè)任務(wù)方式數(shù)為第82頁(yè)Solution：把12個(gè)相同物體放到6個(gè)不一樣盒子方式數(shù)是含有6類元素集合12組合數(shù)。由定理2，這等于C(12+6-1,12)=C(17,12)因?yàn)镃(17,12)=C(17,5)=6188所以，把12個(gè)相同求放到6個(gè)不一樣箱子方式數(shù)為6188?！緀xample】把12個(gè)相同球放到6個(gè)不一樣箱子里有多少種方法？第83頁(yè)Solution：假設(shè)5個(gè)盒子是相同。使用乘積法則計(jì)算以下：首先對(duì)第一個(gè)盒子中放入1個(gè)物體能夠有C(15,1)種方式，對(duì)第二個(gè)盒子放入2個(gè)物體能夠有C(14,2)中方式，第三個(gè)盒子得到3個(gè)物體方式數(shù)為C(12,3)種，第四個(gè)盒子得到4個(gè)物體方式數(shù)是C(9,4)種，第五個(gè)盒子得到5個(gè)物體方式數(shù)是C(5,5).

而在題目中要求盒子是不一樣，5個(gè)不一樣盒子排列數(shù)是5！則可知全部符合題意可能方式數(shù)為5!C(15,1)C(14,2)C(12,3)C(9,4)C(5,5)=5!15!/(1!2!3!4!5!)=4540536000【example】把15個(gè)不一樣物體放到5個(gè)不一樣盒子里而且這些盒子分別有1個(gè)、2個(gè)、3個(gè)、4個(gè)和5個(gè)物體，有多少種方法？第84頁(yè)【example】一個(gè)教授把40本數(shù)學(xué)期刊放入4個(gè)盒子，每盒10本，分配這些期刊有多少種方式？

a)假如每個(gè)盒子被編號(hào)使得它們是可區(qū)分。

b)這些盒子是相同，使得它們是不可區(qū)分。第85頁(yè)Solution：

a)因?yàn)?個(gè)盒子被編上號(hào)碼彼此之間不一樣，也是能夠區(qū)分。由定理4，我們把40本數(shù)學(xué)期刊放入4個(gè)不一樣盒子，而且每個(gè)盒子10本書方式數(shù)為C(40,10)C(30,10)C(20,10)C(10,10)=40!/(10!10!10!10!)=40!/(10!)4

b)因?yàn)?個(gè)不一樣盒子排列數(shù)是4！，所以我們能夠得到將a)中將49本書放入4個(gè)不一樣盒子方式數(shù)40!/（10!）除以4個(gè)不一樣盒子排列數(shù)4！即為將40本書放入4個(gè)相同盒子可能方式數(shù)。則得到符合題意全部方式數(shù)為

40!/(10!)4/4!

第86頁(yè)

PermutationsandCombinations排列與組合

Generalized

PermutationsandCombinations

普通性排列和組合GeneratingPermutationsandCombinations生成排列和組合

排列與組合

PermutationsandCombinations第87頁(yè)生成排列和組合Generating

PermutationsandCombinationsGeneratingPermutations

生成排列Problem:Listthepermutationsofanysetofnelements.

列出n個(gè)元素集合全部排列Solution:任何n元素集合能夠與集合{1,2,…,n}建立一一對(duì)應(yīng)生成n個(gè)最小正整數(shù)排列，然后用對(duì)應(yīng)元素替換這些整數(shù).Introduce:lexicographicorderingforpermutation字典次序排列

第88頁(yè)假如對(duì)于某個(gè)k,1

k

n,a1=b1,a2=b2,…,ak-1=bk-1,而且ak

<bk,，那么排列a1a2…an在排列b1b2…bn

前邊。換句話說，假如在n個(gè)最小正整數(shù)集合兩個(gè)排列不等第一個(gè)位置，一個(gè)排列數(shù)小于第二個(gè)排列數(shù)，那么這個(gè)排列按照字典次序排在第二個(gè)排列前邊。

以{1,2,…,n}排列集合為基礎(chǔ)字典次序算法Forexample:123478124635第89頁(yè)Example1

集合{1,2,3,4,5}排列23415在排列23514前邊。因?yàn)檫@些排列在前兩位相同，但第一排列在第三位置中數(shù)是4，小于第二排列在第三位置中數(shù)5.類似地，排列41532在排列52143前邊。第90頁(yè)生成{1,2,…,n}排列算法基礎(chǔ)是從一個(gè)給定排列a1a2…an按照字典次序結(jié)構(gòu)下一個(gè)排列過程。給定排列a1a2…an,按字典次序找到下一個(gè)最大排列算法以下:

(1)找到整數(shù)即在這個(gè)排列中最終一對(duì)相鄰整數(shù)，使這個(gè)正確第一個(gè)整數(shù)小于第二個(gè)整數(shù)。(2)把中大于最小整數(shù)放到第j個(gè)位置(3)按照遞增次序排列以下整數(shù)

第91頁(yè)Solution：

使得aj<aj+1最終一對(duì)整數(shù)aj和aj+1是a3=2和a4=5。排列在2右邊大于2最小整數(shù)是a5=4,所以4被放在第三位置。然后整數(shù)2，5和1依次遞增次序放到最終3個(gè)位置，即這個(gè)排列最終3個(gè)位置是125.于是下一個(gè)最大排列是364125Example2

在362541后面按照字典次序下一個(gè)最大排列是什么？第92頁(yè)Solution：

從123開始，由交換3和2得到下一個(gè)排列132，下一步，因?yàn)?>2,和1<3,排列在132中3個(gè)整數(shù)，把3和2中較小放到第一個(gè)位置，然后按遞增次序把1和3放到位置2和3而得到213.跟著213是231，它是由交換1和3得到，因?yàn)?<3。下一個(gè)最大排列把3放在第一位置，然后是1和2按遞增次序排列，即312.最終，交換1和2得到最終一個(gè)排列321。Example3

按字典次序生成整數(shù)1,2,3排列。第93頁(yè)【Example】

Whatisthenextlargestpermutationinlexicographicorderafter124653?按照字典次序求在124653之后下一個(gè)最大排列是多少？Solution：

Thenextlargestpermutationof124653inlexicographicorderis125346第94頁(yè)算法1顯示了在給定排列不是最大排列nn-1n-2…21時(shí)，在它后面按照字典次序找到下一個(gè)最大排列過程。第95頁(yè)Solution:一個(gè)組合就是一個(gè)子集。

需要列出有限集全部子集。使用n位二進(jìn)位串表示n元素集合一個(gè)子集。

需要列出全部長(zhǎng)度為n二進(jìn)制串。按照一個(gè)n位二進(jìn)制串二進(jìn)制展開式中整數(shù)遞增次序能夠列出這2n個(gè)二進(jìn)制串。GeneratingCombinations

生成組合

Problem1

:Generateallcombinationsoftheelementsofafiniteset.

生成一個(gè)有窮集元素全部組合

第96頁(yè)在每一步找下一個(gè)最大二進(jìn)制展開式時(shí)先確定從右邊起第一個(gè)不是1位置.然后把這個(gè)位置右邊全部1變成0，而且將這第一個(gè)0（從右邊數(shù)）變?yōu)?。Algorithmofproducingallbitstrings產(chǎn)生全部二進(jìn)位串算法

從含有n個(gè)0二進(jìn)位串00…00開始.

然后，繼續(xù)找下一個(gè)最大展開式，直到得到

111…11為止.尋找下一個(gè)最大二進(jìn)制展開式方法：第97頁(yè)Example4

找出1000100111后面下一個(gè)最大二進(jìn)位串。Solution：這個(gè)串從右邊數(shù)不是1第1位是從右邊起第4位。把這一位變成1，而且將它后面全部位變成0.這就生成了下一個(gè)最大二進(jìn)位串1000101000第98頁(yè)下面以算法形式給出生成bn-1bn-2…b1b0后面下一個(gè)最大二進(jìn)位串過程。第99頁(yè)P(yáng)roblem2:Generateallr-combinationsoftheset{1,2,…,n}Thealgorithmforgeneratingther-combinationoftheset{1,2,…,n}(1)S1={1,2,…,r}

(2)Ifhasfound,thenthenextcombinationcanbeobtainedusingthefollowingrules.First,locatethelastelementinthesequencesuchthat.Thenreplacewithandwith第100頁(yè)Solution：在含有a1=1,a2=2,a3=5,a4=6項(xiàng)中使得最終項(xiàng)是a2=2。為得到下一個(gè)最大4組合，把a(bǔ)2加1得a2=3。然后，置a3=3+1=4且a4=3+2=5。從而下一個(gè)最大4組合是{1，3，4，5}Example5找出集合{1,2,3,4,5,6}在{1,2,5,6}后面下一個(gè)最大4組合。第101頁(yè)算法3中給出了按字典次序生成集合{1，2，3,…,n}下一個(gè)r組合偽代碼。第102頁(yè)【example】找出按照字典次序跟在下面每一個(gè)排列后面下一個(gè)最大排列。

a)1342b)45321c)13245d)612345e)1623547f)23587416第103頁(yè)Solution:a)使得aj<aj+1最終一對(duì)整數(shù)aj和aj+1是a2=3,a3=4。排列在3右邊大于3最小整數(shù)是a3=4,則將4放在第三位.然后整數(shù)2，3依遞增次序放入最終2個(gè)位置。于是下一個(gè)最大排列是1423.

同理能夠計(jì)算出

b)51234c)13254

d)612354e)1623574f)23587461第104頁(yè)【example】按照字典次序排列下述{1,2,3,4,5,6}排列：234561，231456，165432，156423，543216，541236，231465，314562，432561，654321，654312，435612.第105頁(yè)Solution：

首先，我們先排列首個(gè)數(shù)字是1排列，則有165432和156423，因?yàn)檫@兩個(gè)排列中第二位上數(shù)字是6和5，因?yàn)?<6,所以排列在最前面排列數(shù)是156423，第二個(gè)是165432。其次對(duì)以數(shù)字2開頭排列進(jìn)行排序，有231456，231465，234561。以數(shù)字3開頭只有314562。

依次類推后面能夠得到432561，435612，541236，543216，654312，654321。則對(duì)著12個(gè)排列按照字典次序排列后次序?yàn)?/p>

156423，165432，231456，231465，234561，314562，432561，435612，541236，543216，654312，654321

第106頁(yè)Solution：首先第一個(gè)子集對(duì)應(yīng)于字符串0000，即空集。下一個(gè)子集對(duì)應(yīng)于字符串0001，為集合{4}。字符串0010對(duì)應(yīng)于子集{3}，0011對(duì)應(yīng)于子集{3，4},…繼續(xù)這種方式能夠得到其余子集:{2}

{2，4}

{2，3}

{2，3，4}

{1}

{1，4}

{1，3}

{1，3，4}

{1，2}

{1，2，4}

{1，2，3}

{1，2，3，4}【example】使用算法2列出集合{1，2，3，4}全部子集。第107頁(yè)【練習(xí)】1.令S={1，2，3，4，5},a)列出S全部3排列。b)列出S全部3組合。2.求出下面每個(gè)值。

a)C(5,1)b)C(5,3)c)C(8,4)d)C(8,8)e)C(8,0)f)C(12,6)第108頁(yè)3.多少個(gè)12位二進(jìn)制串包含

a)恰好3個(gè)1？

b)至多3個(gè)1？

c)最少3個(gè)1？

d)0個(gè)數(shù)和1個(gè)數(shù)相等？第109頁(yè)4.一個(gè)硬幣被擲8次，每次可能出現(xiàn)頭像或非頭像。有多少種可能結(jié)果

a)包含各種可能情況？

b)包含恰好3個(gè)頭像？

c)包含最少3個(gè)頭像？

d)頭像和非頭像數(shù)目相等？第110頁(yè)5.一個(gè)俱樂部有25個(gè)組員。

a)有多少種方式從中選擇4個(gè)人作為董事會(huì)組員。

b)有多少種方式從中選出俱樂部主席、副主席、書記和司庫(kù)。第111頁(yè)、6.一個(gè)教授寫了40道離散數(shù)學(xué)真假判斷題。在這些題中有17個(gè)語句為真。假如能夠按照任意次序排列這些題，可能有多少種不一樣答案？第112頁(yè)7.一個(gè)小豬儲(chǔ)錢罐包含100個(gè)相同1美分和80個(gè)相同5美分硬幣，從中選8個(gè)硬幣有多少種方式？8.有多少20位十進(jìn)制數(shù)字包含有2個(gè)0、4個(gè)1、3個(gè)2、1個(gè)3、2個(gè)4、3個(gè)5、2個(gè)7和3個(gè)9？第113頁(yè)9.方程有多少個(gè)解？其中