离散数学3省公开课一等奖全国示范课微课金奖

12024/5/5离散数学DiscreteMathematics

汪荣贵教授合肥工业大学软件学院专用课件.4第1页第三章计数技术

第2页学习内容3.1TheBasicofCounting

计数基础3.2ThePigeonholePrinciple鸽巢原理3.3PermutationsandCombinations排列与组合3.4RecurrenceandDivide-and-Conquer递推与分治3.5GeneratingFunction生成函数3.6inclusion-exclusion容斥原理应用第3页

PermutationsandCombinations排列与组合

Generalized

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

排列与组合

PermutationsandCombinations第4页Introduction

Torecallpermutationsandcombinations回顾以前学过关于排列与组合知识Tounderstandpermutationsandcombinationsfromdifferentdegrees从不一样角度了解排列与组合Tosolvecountingproblemsusingthem使用排列与组合处理计数问题Toshowhowtheoremsareprovedbycombinatorialarguments

排列与组合

PermutationsandCombinations第5页ForexampleInhowmanywayscanweselectthreestudentsfromagroupoffivestudentstostandinlineforapicture?

从5个学生种选出3个学生站成一排摄影，一共有多少种选择方式？

p(5,3)=5*4*3=60Thisexampleillustrateshoworderedarrangementsofdistinctobjectscanbecounted.Thisleadstosometerminology.这个例子显示了怎样计数不一样目标次序安排问题，并引入一些术语。

排列（Permutations）

第6页Notation:P(n,r)

排列（Permutations）

【Definition】Apermutationofasetofdistinctobjectsisanorderedarrangementoftheseobjects.Anordered

arrangementofrelementsofasetiscalledanr-permutation.

不一样个体集合一个排列是这些个体一个有序安排.一个集合r个元素有序安排叫做r排列.

第7页Example1设S={1,2,3}。3，1，2是S一个排列，3，2是S一个2排列。一个n元集r排列数积为P（n,r）.我们能够使用乘积法则求出P（n,r）第8页【Theorem1】Ifnisapositiveintegerandrisanintegerwith1<r<n,thentherearer-permutationsofasetwithndistinctelements.含有n个不一样元素集合r排列数是

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页Example2在进入竞赛100个不一样人中有多少种方法选出一个一等奖得主、一个二等奖得主和一个三等奖得主？Solution：

不论哪个人得哪个奖，选取3个得奖人方法是从100个元素集合中有序选择3个元素方法数，即100个元素集合3-排列数。所以，答案是

P(100,3)=100*99*98=970200第10页Example3假定有8个赛跑运动员。第一名得到一枚金牌，第二名得到一枚银牌，第三名得到一枚铜牌。假如比赛可能出现全部可能结果，有多少种不一样颁奖方式？Solution：

颁奖方式就是8元素集合3-排列数。所以存在P(8,3)=8*7*6=336种可能颁奖方式。第11页Example4假定一个女推销员要访问8个不一样城市。她访问必须从某个指定城市开始，但对其它7个城市访问能够按照任何次序进行。当访问这些城市时，这个女推销员能够有多少种可能次序？第12页Solution：

因为第一个城市是确定，而其它7个城市能够使任意次序，故城市之间可能路径数是7个元素排列数。所以，这个女推销员有7!=7*6*5*4*3*2*1=5040种方式选择她旅行。比如说，假如这个女推销员想要在城市中找出含有最短距离路径，而且她对每一条可能路径计算总距离，那么她必须考虑5040条路径。第13页Example5字母ABCDEFGH有多少种排列包含串ABC？Solution：

因为字母ABC必须成组出线，我们能够经过找6个对象，即组ABC和单个字母D、E、F、G和H排列数得到答案。因为这6个对象能够按任何次序出线，存在6！=6*5*4*3*2*1=720种ABCDEFGHZ字母排列，其中ABC成组出现。第14页【Example】集合{a,b,c,d,e,f,g}有多少个排列？Solution：

本题就是一个7元集合全排列问题，所以，答案是p(7,7)=7*6*5*4*3*2*1=5040第15页【example】{a,b,c,d,e,f,g}有多少个排列以a结尾？Solution：

符合题意7元素排列中都是以字母a结尾，其它6个位置能够是任何次序排列，故以a结尾排列数有6！=6*5*4*3*2*1=720个第16页Solution：

7个子母中有A和E两个元音字母.所以符合要求排列中，前两个字母只能从两个元音字母中选择可能方法数是2!对于后面五个辅音字母可能排列数是5!.所以完成符合题意排列全部可能排列数为2!5!【example】以A、B、C、D、E、F、G7个字母组成排列中在多少个排列中是两个元音字母在五个辅音字母之前？第17页【Example】一个组有n个男士和n个女士。假如把他们男女相间地排成一排，有多少种方式？Solution:

我们假设这一排列能够有不一样性别排头。首先我们先考虑n个男士排列，全部排列数P(n,n)=n!

一样我们也能够得到n个女士排列数也为n!.

现在将n个男士与n个女士相间排列，我们能够采取先将女士排列好，然后往其中进行男士排列，并存在男士作为排头或女士作为排头两种情况。由乘积法则能够知道总排列方式数为

第18页【example】有多少种方式使得10个女士和6个男士站成一排而且没有两个男士彼此相邻？（提醒：先放女士，后考虑男士位置）Solution：

首先考虑女士排列，一共有10个女士可能排列数为P(10,10)

然后由10个女生组成排列形成了11个空隙，然后我们分别将6名男士安排站入11个空隙中，全部可能方式数为P(11,6).所以完成整个任务排列数为

P(10,10)P(11,6)=10！11！/5！第19页Solution：

a)将B单位3个人某一排列作为一个元素，参加A单位进行排列。可得方案数为(7+1)!=8!且B单位3人有3!种排列。

由乘法原理，总排列方案数为8!3!【example】A单位有7位代表，B单位有3位代表，排成一列合影，要求B单位3人排在一起。

a)

问有多少种不一样排列方案？

b)若B单位3人不能相邻，且A单位2人排在两端，问有多少种不一样排列方案。第20页

b)先对A单位7人进行排列。全部可能排列数共有7!种。假设A1A2A3A4A5A6A7是A一个排列。两端固定后，B单位3人中第一人有6种选择

A1*A2*A3*A4*A5*A6*A7即上面*位置，第二位为了不与第一位相邻，故只有5种选择。第三位有4种选择。故排列总数为7!×6×5×4=604800第21页

组合(Combinations)

【Definition】Anr-combinationofelementsofasetisanunorderedselectionofrelementsfromtheset.

集合元素一个r组合是从这个集合无序选取r个元素Example6设S是集合{1，2，3，4}，那么{1，3，4}是S一个3组合。Note:Anr-combinationissimplyasubsetofasetwithrelements.

一个r组合是这个集合一个r个元素子集。Notation符号:第22页Example7因为{a,b,c,d}

2-组合是{a,b},{a,c},{a,d},{b,c},{b,d}和{c,d}6个子集，我们有C（4，2）=6.注意：我们能够用关于集合r排列数公式确定n元素集合r组合数。为此只需注意到集合r排列能够按下述方法得到：先构成集合r组合，然后排列这些组合种元素。下面定理给出了C(n,r)值。第23页

组合(Combinations)

【

Theorem2】Thenumberofr-combinationofasetwith

nelements,wherenisapositiveintegerandrisanintegerwith0

r

n,equals设n是正整数，r是满足0

r

n整数，n元素集合r组合数等于

C(n,r)=n!/r!(n-r)!第24页proof：

能够以下得到这个集合r排列。首先得到集合C(n,r)个r-组合，然后以P(n,r)

种方式排序每个r组合中元素，这能够用P(r,r)种方式来做。所以，

P(n,r)=C(n,r)*P(r,r)这就推出注意：该公式在n和r很大时候，计算并不方便，且有可能产生值不是一个整数。在实践中，能够从分子和分母中消去分母大因式中全部项，把分子中全部没有消去项相乘，然后除以分母中较小因式。第25页下面给出一个关于集合r组合数有用恒等式。[推论1]设n和r是满足r

n非负整数，那么C(n,r)=C(n,n-r).Proof:由定理2得到和所以，C(n,r)=C(n,n-r).第26页Example8有多少种方式从10个选手网球队中选择5个选手外出参加在另一个学校比赛？Solution：答案由10元素集合5-组合数给出。依据定理2，这个组合数是

第27页Example9一组30个人被培训作为宇航员去完成首次登陆火星任务。有多少种方式选出6个人小组来完成这个任务（假设全部小组组员有一样工作）？Solution：

因为不考虑这些人被选次序，从30个人中选6个人小组方式数是30元素集合6-组合数。依据定理2，这个组合数是

第28页Example10有多少个长为n二进制串恰好包含r个1？Solution：

在长为n二进制串中r个1位置组成了集合{1,2,…,n}r组合。所以有C(n,r)个长为n二进制串恰好包含r个1.第29页Example11

为开发学校离散数学课程要选出一个委员会。假如数学系有9个教师，计算机科学系有11个教师。而这个委员会要由3个数学系教师和4个计算机科学系教师组成，那么有多少种选择方式？Solution：

由乘积法则，答案是9元素集合3组合数与11元素集合4组合数之积。依据定理2，选择这个委员会方式数是第30页【example】一个10元素集合有多少个子集含有奇数个元素？Solution：

10元素集合含有奇数个元素子集分别有：

1元素子集，3元素子集，5元素子集，7元素子集，9元素子集所以我们能够得到10元素集合含有奇数元素全部子集数即为

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

onthegrass.俱乐部想要选出11名运动员参加比赛，其中至多由5名男性运动员第32页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页【example】多少个12位二进制串包含

a)恰好3个1？b)至多3个1？c)最少3个1？d)0个数和1个数相等？Solution:a)我们能够把问题看做从12个位置中选出3个位置放置1，全部可能二进位串个数为C(12,3)=220

b)可了解为在12个位置中放入3个1、2个1、1个1、0个1情况，所有可能二进位串个数为

C(12,3)+C(12,2)+C(12,1)+C(12,0)=298第34页

c)12位二进位串中包含1个数最少是3，就意味着包含1个数可能是3个、4个、5个、6个、7个、8个、9个、10个、11个、12个，所以能够得到全部二进位串个数为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)长度为12二进位串中当0个数为6时，恰好0和1个数是相同。所以能够得到全部可能二进位串个数为C(12,6)=924第35页【example】一个垒球队13个人出席一场比赛。

a)有多少种方式选10个选手上场？

b)有多少种方式从13个在场人中分配10个选手位置？

c)13个出席人中有3个女士。假如上场选手中要求最少有一个女士，那么有多少种方式选择10个选手？第36页Solution：

a)该题即为从13个人中任选10个人出席比赛。全部可能方式数为C(13,10)=286

b)该题可了解为从13个人中选出10个人排成一排情况。全部可能方式数为P(13,10)=13!/3!=1037836800c)由a)中解答知道从13个人中任选10个人全部组合数为286。其中只有全选男士这一个组合方式中石不包含女士。所以该题中全部可能方式数为286-1=285第37页【example】假定某个系包含10名男士和15名女士。有多少种方式组成一个6人委员会且使得它含有女士比男士多？Solution：当6人委员会中女士多于男士时有三种情况：包含0名男士和6名女士、包含1名男士和5名女士、包含2名男士和4名女士这三种情况可能方式数分别为

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

所以，全部可能方式数为

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

将每个0个2个1绑定在一起作为一个元素，所以5个0和14个1能够变为5个011和4个1一共是9个元素。然后该问题就能够了解为在字符串中9个位置中选择4个位置来放置1。总可能字符串个数为

C(9,4)=126【example】有多少个二进制串恰好包含5个0和14个1，假如每个0后面紧跟着2个1？第39页

PermutationsandCombinations排列与组合

Generalized

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

排列与组合

PermutationsandCombinations第40页Introduction普通性排列和组合Generalized

PermutationsandCombinations

r-permutation,r-combinationwithnorepetitionallowed无重复r-排列和r-组合

r-permutation,r-combinationwithrepetition有重复r-排列和r-组合

第41页PermutationsWithRepetition

有重复排列

Example1用英文字母能够组成多少个n位字符串？

solution：

因为有26个字母，且每个字母能够被重复使用，由乘积法则能够看出存在26n个n位字符串。下面定理1给出了当允许重复时一个n元素集合r排列数。第42页PermutationsWithRepetition有重复排列

Proof：

当允许重复时，在r排列中对r个位置中每个位置有n种方式选择集合元素，因为对每个选择，全部n个物体都是有效。所以，有乘积法则，当允许重复时存在nr个r排列。【

Theorem1】Thenumberofr-permutationsofasetofn

objectswithrepetitionallowedisnr.含有n个物体集合允许重复r排列数是nr.

第43页Solution：

当允许重复时，在5排列中对5个位置中每个位置有5种方式选择集合元素。因为对每个选择，全部5个元素都是有效。所以，由乘积法则，当允许重复时存在5排列数为55【example】从一个5元素集合中允许重复地有序选取5个元素有多少种不一样方式？第44页Solution：

因为这个学生天天都能够从这6中三明治中选一个作为午餐。所以一周7天里这个学生选择三明治全部方式数为67【example】天天一个学生从一堆包好三明治中随机选1块三明治作为午饭。假如有6种三明治而且选择三明治次序无关，在一周7天里这个学生选择三明治有多少种不一样方式？第45页CombinationWithRepetition有重复组合

由下面实例考虑怎样处理元素允许重复组合问题。Example2

从包含苹果、橙子、和梨碗里选4个水果。假如选择水果次序无关，且只关心水果类型而不论是该类型哪一个水果，那么当碗中每类水果最少有4个时有多少种选法？

第46页解答：为了求解这个问题，我们列出选择水果全部可能方式。共有15种方式：

4个苹果

4个橙子

4个梨3个苹果，1个橙子

3个苹果，1个梨

3个梨，1个苹果3个橙子，1个梨

3个梨，1个苹果

3个梨，1个橙子2个苹果，2个橙子

2个苹果，2个梨

2个橙子，2个梨2个苹果，1个橙子，1个梨

2个橙子，1个苹果，1个梨2个梨，1个苹果，1个橙子

这个解是从3个元素集合{苹果、梨、橙子}中允许重复4组合数。第47页Solution：

因为纸币被选次序是无关且7种不一样类型纸币都能够选5次，该题是计数从7个元素集合中允许重复5组合数。列出全部可能性将是很繁琐，因为存在解太多了。在这里我们将给出一个方法来计数允许重复组合数。

Example3

从包含1美元、2美元、5美元、10美元、20美、元、50美元及100美元钱袋中选5张纸币，有多少种方式？假定不论纸币被选次序，同种币值纸币都是不加区分，而且最少每张纸币有5张。第48页

假设一个零钱盒子有7个隔间，每个保留一个纸币，以下列图所表示。这些隔间被6块隔板分开，每选择1张纸币就在对应隔间里放置1个标识。针对选择5张纸币3种不一样方式给出了这种对应，其中竖线表示6个隔板，星表示5张纸币。

第49页第50页

选择5张纸币方法数对应了安排6条竖线和5颗星方法数。所以，选择5张纸币方法数就是从11个可能位置选5颗星位置方法数。这对应了从含11个物体集合中无序地选择5个物体方法数，能够有C(11,5)种方法.所以从7类纸币袋中选择5张纸币方式数有第51页将例3中方法普通化得到定理2.【

Theorem2】ThereareC(n-1+r,r)r-combinationfromasetwithnelementswhenrepetitionofelementsisallowed.n个元素集合中允许重复r组合有C(n-1+r,r)

第52页Proof:

当允许重复时n元素集合每个r组合能够用n-1条竖线和r颗星表表示这n-1条竖线用来标识n个不一样单元。每当集合第i个元素出现在组合中，第i个单元就包含一颗星。比如，4元素集合一个6组适用3条数先和6颗星来表示。这里**|*||***代表了恰好包含2个第一元素、2个第二元素、0个第三元素和3个第四元素组合。正如我们已经看到，包含n-1条竖线和r颗星每一个不一样表对应了n元素集合允许重复一个r组合。这种表个数是C(n-1+r,r),因为每个表对应了从包含r颗星和n-1条竖线n-1+r个位置来放r颗星一个选择。第53页Example4设一家甜点店有4种不一样类型甜点，那么从中选6块甜点有多少种不一样方式？假定只关心甜点类型，而不论是哪一块甜点或者选择次序。定理2使用Solution：

选择6块甜点方式数是含有4类元素集合6组合数。由定理2这等于C(4+6-1,6)=C(9,6).所以能够得到选择6块甜点不一样方式数有第54页Example5方程x1+x2+x3=11有多少个解？其中x1、x2、x3是非负整数。使用定理2求解线性方程组整数解个数Solution：为计数解个数，注意到一个解对应了从3元素集合中选11个元素方式，以使得x1选自第一类，x2选自第二类，x3选自第三类。所以，解得个数等于3元素集合允许重复11组合数。由定理2，存在解个数为

第55页讨论：当例5中变元是满足整数时求出这个方程解个数？Solution：

满足此限制方程解对应于11个项选择，使得项x1取自第一类，项x2取自第二类，项x3取自第三类，而且第一类元素最少取1个，第二类元素最少取2个，第三类元素最少去3个。所以，先选1个第一类元素，2个第二类元素，3个第三类元素：然后再多项选择5个元素。由定理2，方程解个数为

C(3+5-1,5)=C(7,5)=C(7,2)=7*6/2=21第56页在一个n元素集合允许重复r组合和把r个相同球放到n个不一样箱子方法之间存在一一对应关系。为建立这种对应，每次我们把一个球放到第i个箱子里，集合第i个元素就加到这个r组合中。第57页Example6

有多少种方法把10个相同球放入8个不一样箱子？solution：把10个相同球放入8个不一样箱子方法数等于8个元素集合允许重复10组合数，所以存在方法有

第58页Example7在下面伪代码被执行后k值是多少？

第59页Solution:

k初值是0，且对于满足整数序列每次经过这个嵌套循环时k值就加1.这种整数序列个数是从{1,2,…,n}种允许重复地选择m个整数方式数。（为看到这一点只需注意到一旦这个整数序列选定以后，如果我们按非降次序排列序列中整数，这就唯一地确定了一组对赋值。相反，每个这么赋值对应了一个唯一无序集合。）所以由定理2得出在这个代码被执行后

k=C(n+m-1，m)第60页从一个n元集合中，允许重复和不允许重复地选择r个元素，其有序或无序选择数公式在下表中给出。第61页Solution：

选择12个多纳圈方式数是含有21类元素12组合数。由定理2这等于C(21+12-1,12)=C(32,12)=9817080【example】从一个商店21种多纳圈中选择12个多纳圈有多少种不一样方式？第62页Solution：该题是从5中硬币中允许重复取出20个硬币组合问题。由定理2得到全部方式数为C(5+20-1,20)=C(24,20)=C(24,4)=10626【example】假如一个小猪储钱罐中有1美分5美分10美分25美分50美分等硬币，那么20个硬币有多少种方式？第63页Solution：

假设3个库房是不一样，而且wi表示放入第i个库房书数量，则满足w1+w2+w3=3000由定理2可知全部方式数为C(3000+3-1,3000)=C(3002,3000)=C(3002,2)=4504501【example】一个出版商有3000本离散数学书，假如这些书是没有区分，那么将这些书存放在3个库房有多少种方式？第64页【example】方程

x1+x2+x3+x4+x5+x6=29有多少个解？第65页Solution:

为计数解得个数，注意到一个解对应了从6个元素集合中选29个元素方式，以使得项xi取自第i类（i=1,2,3,4,5,6,）。

a)满足此限制方程解对应于29个项选择，使得项xi取自第i类，而且第i类最少选2个。所以先从第i类选2个元素（i=1,2,3,4,5,6,），然后再多项选择17个元素。由定理2，全部方式数为C(6+17-1,17)=C(22,17)=C(22,5)=26334第66页

b)

满足此限制时:先选1个第一类元素、2个第二类元素、3个第三类元素、4个第四类元素、6个第五类元素、6个第六类元素.然后再多项选择7个元素。由定理2，全部方式数为C(6+7-1,7)=C(12,7)=C(12,5)=792

c)

本题中没有限制条件时，方程全部解得个数为C(6+29-1,29)=C(34,29)=C(34,5)=278256

而满足限制时方程解个数为C(6+23-1,23)=C(28,23)=C(28,5)=98280所以满足本题方程解个数为

278256-98280=179976第67页

d)在限制条件同时x1无限制情况下，方程解个数为C(6+20-1,20)=C(25,20)=53130

当又添加条件后，方程解个数即为

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

所以，符合本题条件方程解个数53130-6188=46942第68页【example】12本书在一个书架上排成一排。从中选5本书而且使得没有2本书相邻有多少种方式？Solution：

我们将选书用竖线表示，没选书用星表示，则本题即为计数含5条竖线和7颗星且没有2条竖线相邻序列数。因为5条竖线排列组成了6个空隙

1|2|3|4|5|6

第二到第五个空隙每一个中都最少插入一个星使得没有2本选中数是相邻，最终还剩下3个星能够任意插入这6个空隙。所以，全部可能方式数有C(6+3-1,3)=C(8,3)=56第69页PermutationsofSetsWithIndistinguishableObjects

含有不可区分物体集合排列Example8重新排序单词SUCCESS字母能组成多少个不一样串？在计数问题中一些元素可能是没有区分，在这种情况下必须小心防止重复计数。下面以一个实例说明该问题。第70页Solution：

因为SUCCESS中一些字母是重复，答案并不是7个字母排列数。这个单词包含3个S、2个C、1个U和1个E.为确定重新排序单词中字母能组成多少个不一样串,首先，注意到3个S能够用C(7,3)种不一样方式放在7个位置中，剩下4个空位。然后能够用C(4,2)中方式放2个C，留下2个空位。又能够用C(2,1)种方式放U，留下1个空位。所以，放E只有C(1,1)种方式。从而，由乘积法则，产生不一样串数是第71页由例8中推论，我们得到定理3。【

Theorem3】Thenumberofdifferentpermutationsofnobjects,wheretherearen1indistinguishableobjectsoftype1,…,andnk

indistinguishableobjectsoftypek,is设类型1相同物体有n1个，类型2相同物体有n2个，…，类型k相同物体有nk个，那么n个物体不一样排数是

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

第72页Proof:为确定排列数，首先能够用C(n,n1)种方式在n个位置中放置类型1n1个物体，剩下n-n1个空位。然后用C(n-n1，n2)种方式放类型2物体，剩下n-n1-n2个空位。继续放类型3物体,...,类型k-1物体，直到最终可用C(n-n1-n2-…-nk-1,nk)种方式放类型k物体。所以由乘积法则，不一样排列总数是第73页【example】假设一个大家庭有14个孩子，包含2组三胞胎、3组双胞胎以及2个单胞胎。这些孩子坐在一排椅子上，假如相同三胞胎或双胞胎孩子不能相互区分，那么有多少种方式？第74页Solution：

因为这些孩子中有些孩子是不能相互区分，答案并不是14个孩子排列数。这些孩子中包含2组三胞胎、3组双胞胎已近2个单胞胎。为确定排列这些孩子能组成多少个不一样排列，首先注意到一组三胞胎能够用C(14,3)中不一样方式放在14个位置中，剩下11个空位。然后能够用C(11,3)中可能方式放另一组三胞胎，留下8个空位又能够用C(8,2)中方式将一组双胞胎放在8个位置中。依次类推，将剩下孩子放入方式数分别为C(6,2)、C(4,2)、C(2,1)、C(1,1)。由乘积法则，产生不一样排列数是

第75页Solution：若要求3个字母A必须连续，不妨将3个A看做是一个元素，则总元素数为6，其中有2个字母R。对于两个字母R我们能够用C(6,2)种方式放在6个位置中，剩下4个字母分别有C(4,1)C(3,1)C(2,1)C(1,1)中方式放入排列中。由乘积法则，产生不一样串数是C(6,2)C(4,1)C(3,1)C(2,1)C(1,1)=6!/2!=360【example】使用AARDVARK中全部字母且全部3个A必须连续，能够结构多少个不一样串？第76页【example】使用SEERESS中字母能够结构多少个最少含5个字符串？Solution：我们需要使用定理3对长度为5、6、7字符串分别进行考虑。字符串长度为7时，全部可能字符串数是7!/(3!3!1!)=140字符串个数长度为6时，我们删去字母R时，全部可能字符串数是6!/(3!3!)=20删去字母S时，全部可能字符串数是

6!/(3!2!1!)=60删去字母E时，全部可能字符串数是

6!/(3!2!1!)=60第77页

由此我们能够得到字符串长度为6时，总可能字符串数20+60+60=140

字符串长度为5时，存在情况分别为：删去2个字符E或者2个字符S时，每一个可能存在字符串数为5!/(3!1!1!)=20删除字符E和S时，可能存在字符串数为5!/(2!2!1!)=30

删除字符R和E或者是删除字符R和S时，可能存在字符串数都为5!/(3!2!)=10由此我们能够得到字符串长度为5时，总可能字符串数为20+20+30+10+10=90第78页【example】有多少种不一样方法在xyzw空间上从原点（0，0，0，0）抵达（4，3，5，4）点？这个旅行每一步是在x、y、z或w正方向移动一个单位。Solution：我们使用一个包含4个x，3个y，5个z和4个w序列来表示任何一次旅行。由定理3，存在全部不一样方法数是16!/(4!3!5!4!)=50450400第79页对于有些计数问题能够经过枚举把不一样物体放入不一样盒子方式数来求解。Example9有多少种方式把52张标准扑克牌发给4个人似每个人5张牌？把物体放入盒子问题Solution：

第一个人得到5张牌能够有C(52,5)种方式，剩下47张牌。第二个人得到5张牌可能有C(47,5)种方式。第三个人得5张牌有C(42,5)种方式，第四个人得5张牌有C(37,5)种方式。所以发给4个人每人5张牌方式总数是第80页由前面例子能够得到以下定理用于求解把不一样物体分配到不一样盒子计数问题。【

Theorem4】Thenumberofwaystodistributen

distinguishableobjectsintokdistinguishableboxessothatniobjectsareplaceintoboxi,i=1,2,…,k,equals把n个不一样物体分配到k个不一样盒子使得ni个物体放入盒子方式数等于

n!/(n1!n2!…nk!)第81页Proof:

首先，在第1个盒子中放入n1个物体，能够有C(n,n1)种方式，然后剩下物体有n-n1个，对第2个盒子中放入n2个物体方式有C(n-n1,n2)类似地能够得到放n3个物体到第3个盒子方式数为C(n-n1-n2,n3),依次进行，直到放nk个物体到第k个盒子中可能方式数为C(n-n1-n2-…-nk-1,nk),因为存在n1+n2+…+nk=n,得到

C(n-n1-n2-…-nk-1,nk)=C(nk,nk)=1现在依据乘积法则，完成整个任务方式数为第82页Solution：把12个相同物体放到6个不一样盒子方式数是含有6类元素集合12组合数。由定理2，这等于C(12+6-1,12)=C(17,12)因为C(17,12)=C(17,5)=6188所以，把12个相同求放到6个不一样箱子方式数为6188。【example】把12个相同球放到6个不一样箱子里有多少种方法？第83页Solution：假设5个盒子是相同。使用乘积法则计算以下：首先对第一个盒子中放入1个物体能够有C(15,1)种方式，对第二个盒子放入2个物体能够有C(14,2)中方式，第三个盒子得到3个物体方式数为C(12,3)种，第四个盒子得到4个物体方式数是C(9,4)种，第五个盒子得到5个物体方式数是C(5,5).

而在题目中要求盒子是不一样，5个不一样盒子排列数是5！则可知全部符合题意可能方式数为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个不一样物体放到5个不一样盒子里而且这些盒子分别有1个、2个、3个、4个和5个物体，有多少种方法？第84页【example】一个教授把40本数学期刊放入4个盒子，每盒10本，分配这些期刊有多少种方式？

a)假如每个盒子被编号使得它们是可区分。

b)这些盒子是相同，使得它们是不可区分。第85页Solution：

a)因为4个盒子被编上号码彼此之间不一样，也是能够区分。由定理4，我们把40本数学期刊放入4个不一样盒子，而且每个盒子10本书方式数为C(40,10)C(30,10)C(20,10)C(10,10)=40!/(10!10!10!10!)=40!/(10!)4

b)因为4个不一样盒子排列数是4！，所以我们能够得到将a)中将49本书放入4个不一样盒子方式数40!/（10!）除以4个不一样盒子排列数4！即为将40本书放入4个相同盒子可能方式数。则得到符合题意全部方式数为

40!/(10!)4/4!

第86页

PermutationsandCombinations排列与组合

Generalized

PermutationsandCombinations

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

排列与组合

PermutationsandCombinations第87页生成排列和组合Generating

PermutationsandCombinationsGeneratingPermutations

生成排列Problem:Listthepermutationsofanysetofnelements.

列出n个元素集合全部排列Solution:任何n元素集合能够与集合{1,2,…,n}建立一一对应生成n个最小正整数排列，然后用对应元素替换这些整数.Introduce:lexicographicorderingforpermutation字典次序排列

第88页假如对于某个k,1

k

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

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

前边。换句话说，假如在n个最小正整数集合两个排列不等第一个位置，一个排列数小于第二个排列数，那么这个排列按照字典次序排在第二个排列前边。

以{1,2,…,n}排列集合为基础字典次序算法Forexample:123478124635第89页Example1

集合{1,2,3,4,5}排列23415在排列23514前边。因为这些排列在前两位相同，但第一排列在第三位置中数是4，小于第二排列在第三位置中数5.类似地，排列41532在排列52143前边。第90页生成{1,2,…,n}排列算法基础是从一个给定排列a1a2…an按照字典次序结构下一个排列过程。给定排列a1a2…an,按字典次序找到下一个最大排列算法以下:

(1)找到整数即在这个排列中最终一对相邻整数，使这个正确第一个整数小于第二个整数。(2)把中大于最小整数放到第j个位置(3)按照递增次序排列以下整数

第91页Solution：

使得aj<aj+1最终一对整数aj和aj+1是a3=2和a4=5。排列在2右边大于2最小整数是a5=4,所以4被放在第三位置。然后整数2，5和1依次递增次序放到最终3个位置，即这个排列最终3个位置是125.于是下一个最大排列是364125Example2

在362541后面按照字典次序下一个最大排列是什么？第92页Solution：

从123开始，由交换3和2得到下一个排列132，下一步，因为3>2,和1<3,排列在132中3个整数，把3和2中较小放到第一个位置，然后按递增次序把1和3放到位置2和3而得到213.跟着213是231，它是由交换1和3得到，因为1<3。下一个最大排列把3放在第一位置，然后是1和2按递增次序排列，即312.最终，交换1和2得到最终一个排列321。Example3

按字典次序生成整数1,2,3排列。第93页【Example】

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

Thenextlargestpermutationof124653inlexicographicorderis125346第94页算法1显示了在给定排列不是最大排列nn-1n-2…21时，在它后面按照字典次序找到下一个最大排列过程。第95页Solution:一个组合就是一个子集。

需要列出有限集全部子集。使用n位二进位串表示n元素集合一个子集。

需要列出全部长度为n二进制串。按照一个n位二进制串二进制展开式中整数递增次序能够列出这2n个二进制串。GeneratingCombinations

生成组合

Problem1

:Generateallcombinationsoftheelementsofafiniteset.

生成一个有穷集元素全部组合

第96页在每一步找下一个最大二进制展开式时先确定从右边起第一个不是1位置.然后把这个位置右边全部1变成0，而且将这第一个0（从右边数）变为1。Algorithmofproducingallbitstrings产生全部二进位串算法

从含有n个0二进位串00…00开始.

然后，继续找下一个最大展开式，直到得到

111…11为止.寻找下一个最大二进制展开式方法：第97页Example4

找出1000100111后面下一个最大二进位串。Solution：这个串从右边数不是1第1位是从右边起第4位。把这一位变成1，而且将它后面全部位变成0.这就生成了下一个最大二进位串1000101000第98页下面以算法形式给出生成bn-1bn-2…b1b0后面下一个最大二进位串过程。第99页Problem2:Generateallr-combinationsoftheset{1,2,…,n}Thealgorithmforgeneratingther-combinationoftheset{1,2,…,n}(1)S1={1,2,…,r}

(2)Ifhasfound,thenthenextcombinationcanbeobtainedusingthefollowingrules.First,locatethelastelementinthesequencesuchthat.Thenreplacewithandwith第100页Solution：在含有a1=1,a2=2,a3=5,a4=6项中使得最终项是a2=2。为得到下一个最大4组合，把a2加1得a2=3。然后，置a3=3+1=4且a4=3+2=5。从而下一个最大4组合是{1，3，4，5}Example5找出集合{1,2,3,4,5,6}在{1,2,5,6}后面下一个最大4组合。第101页算法3中给出了按字典次序生成集合{1，2，3,…,n}下一个r组合伪代码。第102页【example】找出按照字典次序跟在下面每一个排列后面下一个最大排列。

a)1342b)45321c)13245d)612345e)1623547f)23587416第103页Solution:a)使得aj<aj+1最终一对整数aj和aj+1是a2=3,a3=4。排列在3右边大于3最小整数是a3=4,则将4放在第三位.然后整数2，3依递增次序放入最终2个位置。于是下一个最大排列是1423.

同理能够计算出

b)51234c)13254

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

首先，我们先排列首个数字是1排列，则有165432和156423，因为这两个排列中第二位上数字是6和5，因为5<6,所以排列在最前面排列数是156423，第二个是165432。其次对以数字2开头排列进行排序，有231456，231465，234561。以数字3开头只有314562。

依次类推后面能够得到432561，435612，541236，543216，654312，654321。则对着12个排列按照字典次序排列后次序为

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

第106页Solution：首先第一个子集对应于字符串0000，即空集。下一个子集对应于字符串0001，为集合{4}。字符串0010对应于子集{3}，0011对应于子集{3，4},…继续这种方式能够得到其余子集:{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页【练习】1.令S={1，2，3，4，5},a)列出S全部3排列。b)列出S全部3组合。2.求出下面每个值。

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页3.多少个12位二进制串包含

a)恰好3个1？

b)至多3个1？

c)最少3个1？

d)0个数和1个数相等？第109页4.一个硬币被掷8次，每次可能出现头像或非头像。有多少种可能结果

a)包含各种可能情况？

b)包含恰好3个头像？

c)包含最少3个头像？

d)头像和非头像数目相等？第110页5.一个俱乐部有25个组员。

a)有多少种方式从中选择4个人作为董事会组员。

b)有多少种方式从中选出俱乐部主席、副主席、书记和司库。第111页、6.一个教授写了40道离散数学真假判断题。在这些题中有17个语句为真。假如能够按照任意次序排列这些题，可能有多少种不一样答案？第112页7.一个小猪储钱罐包含100个相同1美分和80个相同5美分硬币，从中选8个硬币有多少种方式？8.有多少20位十进制数字包含有2个0、4个1、3个2、1个3、2个4、3个5、2个7和3个9？第113页9.方程有多少个解？其中