组合与图论-数学第一讲

前言组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前就观察到神龟背上的幻方…...幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486前言1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问题。包括安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排问题。前言

组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。第一章 排列与组合1.1加法法则与乘法法则.

[加法法则] 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言： 若|A|=m,|B|=n,AB=,则|AB|=m+n。第一章 排列与组合[例]某班选修企业管理的有18人，不选的有10人，则该班共有

18+10=28人。[例]北京每天直达上海的客车有5次，客机有3次，则每天由北京直达上海的旅行方式有5+3=8种。第一章 排列与组合[乘法法则] 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有m·n种产生方式。集合论语言：若|A|=m,|B|=n,AB={(a,b)|aA,bB},则|AB|=m·n。第一章 排列与组合[例]某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有53=15个。[例]从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6条道路。第一章 排列与组合例某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是44=16，而只有43=12种。在乘法法则中要注意事件A和事件B的相互相容性。第一章 排列与组合例1)求小于10000的含1的正整数的个数

2)求小于10000的含0的正整数的个数1)小于10000的不含1的正整数可看做4位数,但0000除外.

故有9×9×9×9－1＝6560个.

含1的有：9999－6560=3439个另:全部4位数有104

个,不含1的四位数有94个,含1的4位数为两个的差:104－94=3439个第一章 排列与组合2)“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。

不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个不含0小于10000的正整数有9+92+93+94=(95－1)/(9－1)=7380个含0小于10000的正整数有

9999－7380=2619个第一章 排列与组合1.2排列与组合定义：从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的排列。其排列的个数记为P(n,r)表示。nr

若取出r个元素而不考虑次序，则称从n个不同元中取r个元的组合。其组合的个数记为C(n,r)或（）第一章 排列与组合规定：从n个不同元中取n个的排列称为n的全排列第一章 排列与组合我们有下列排列与组合的计数公式：特别地，对于全排列有P(n,n)=n!。第一章 排列与组合从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，······，第r个有n-r+1种选择。故有P(n,r)=n(n-1)···(n-r+1)有时也用[n]r记P(n,r)第一章 排列与组合若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)·r!=P(n,r),nrn!———r!(n-r)!C(n,r)=P(n,r)/r!=[n]r/r!=()=第一章 排列与组合例有5本不同的日文书，7本不同的英文书，10本不同的中文书。

1)取2本不同文字的书；

2)取2本相同文字的书；

3)任取两本书请问有多少种不同的取法？解：1)5×7+5×10+7×10=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=()5+7+102第一章 排列与组合例从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解：将[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}.要满足条件，有四种解法：

1)3个数同属于A;2)3个数同属于B3)3个数同属于C;4)A,B,C各取一数.故共有3C(100,3)=1485100第一章 排列与组合定义：从n个不同元素中允许重复地取r个元素作排列，称为n元可重r-排列，其排列数为nr例：由数字1，2，3可组成多少个两位数？并写出这些两位数。解：这是三元可重2-排列问题。其排列数为32=9。这些两位数为11,12,13,21,22,23,31,32,33。n1个a1,n2个a2,…nk个ak的全排列的个数为:第一章 排列与组合定义：从n个不同元素中取r个元素围成一圈，称为从n个不同元中取r个元的圆排列，其排列数记为K(n,r)。我们有：123r-1r这是因为r个不同的线排列（即一般的排列）对应于一个圆排列。第一章 排列与组合例：4个女生和4个男生围圆桌相间而坐，试问有多少种不同的入座方式？解：先让女生入座，这是一个4的圆排列问题。有K（4，4）×4!=4！/4×4!=3！×4!。例:由四种颜色的珠子各一颗，可以做成多少种不同的项链？解：注意项链可以翻转。第一章 排列与组合定义：从n个不同元中允许重复地取r个元的组合，称为n元可重r-组合，其组合数记为F(n,r)。用集合描述为：重集{∞·a1,∞·a2,…∞·an}的r-组合数为F(n,r)。结论：F(n,r)=C(n+r-1,r)，其中n,r均为正整数。证明要点：设a1,a2,…ar是从1,2,…,n中任取的一个可重r-组合，不妨设：1≤a1≤a2≤…≤ar≤n从而有：1≤a1<a2+1

<a3+2<

…<ar+r-1

≤n+r-1第一章 排列与组合例:某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案有多少？[解]一进站方案表示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。第一章 排列与组合[解法1]标号可产生5!个14个元的全排列。故若设x为所求方案，则

x·5!=14!∴x=14!/5!=726485760[解法2]在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。故C(14,5)·9!即所求第一章 排列与组合[解法3]把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。以此类推，9号有14种选择。故所求方案为6×7×8×…×14种。第一章 排列与组合1.3模型转换“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与[1,n]元一一对应的关系.在组合计数时往往借助于一一对应实现模型转换。比如要对A集合计数，但直接计数有困难,于是可设法构造一易于计数的B，使得A与B一一对应。第一章 排列与组合例在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？解一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。第一章 排列与组合

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异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.第一章 排列与组合例简单格路问题|(0,0)→(m,n)|=().从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？m+nmy(m,n)...O...x第一章 排列与组合无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。则(0,0)→(m,n)的每一条路径可表示为m个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。第一章 排列与组合设所求方案数为P(m+n；m，n)则P(m+n；m，n)·m!·n!=(m+n)!故P(m+n;m,n)=———=()=()=C(m+n,m)(c,d)(a,b)(m+n)!m!n!m+nnm+nm(c-a)+(d-b)c-a设c≥a,d≥b,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=()第一章 排列与组合例：在上例的基础上若设m<n，求(0,1)点到(m,n)点不接触对角线x=y的格路的数目(“接触”包括“穿过”)从(0,1)点到(m,n)点的格路，有的接触x=y，有的不接触。对每一条接触x=y的格路，做(0,1)点到第一个接触点部分关于x=y的对称格路，这样得到一条从(1,0)到(m,n)的格路。第一章 排列与组合容易看出从(0,1)到(m,n)接触x=y的格路与(1,0)到(m,n)的格路(必穿过x=y)一一对应y

y=x(m,n)O(1,0)x(0,1)..故所求格路数为()－()。m+n-1m+n-1mm-1第一章 排列与组合若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得x－y=1，(0,0)关于x－y=1的对称点为(1,-1).格路也是一种常用模型m+nm+nmm-1(m+n)!(m+n)!m!n!(m-1)!(n+1)!m+nmn+1-mn+1所求格路数为

()－()=———

－————

=———()yx-y=1(m,n)x(0,0)(1,-1).....第一章 排列与组合例

CnH2n+2是碳氢化合物,随着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丙烷第一章 排列与组合1.4全排列的生成算法

就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。全排列的生成算法有许多种，我们仅介绍其中一种--序数法第一章 排列与组合1.4.1全排列的生成--序数法任一自然数n都可以唯一确定一个p进制数,反之也然。类似地，有第一章 排列与组合同理所以即第一章 排列与组合不难证明，从0到n!-1的任一个整数m都可唯一地表示为：所以从0到n!-1的n!个整数与满足上式的序列(an-1,an-2,…a2,a1)一一对应。然后我们再从(an-1,an-2,…a2,a1)建立与全排列的一一对应关系。第一章 排列与组合例：m＝4000，即n1＝4000第一章 排列与组合现从序列(an-1,an-2,…a2,a1)得到生成排列，为了方便起见,不妨今n个对象分别是1,2,…n.建立起对应的规则如下：设序列(an-1,an-2,…a2,a1)对应某个排列(p)=p1p2,…,pn，其中ai可以看作是排列(p)中数i+1所在位置后面比i+1小的数的个数，也就是排列(p)中从数i+1开始向右统计小于或等于i的数的个数。第一章 排列与组合以排列4213为例，4后面比它小的数的个数(即a3)为3;3后面比它小的数的个数(即a2)等于0;2后面比它小的数的个数(即a1)为1；排列中比1小的数是没有的．故得(p)=(4213)←→(a3a2a1)＝(301)我们称a3a2a1为中介数。第一章 排列与组合1.5组合的生成算法组合的生成不如排列生成困难．今以从1、2、3、4、5、6取3个的组合为例:(1)123，(2)124，(3)125，(4)126，

(5)134，(6)135，(7)136，(8)145，

(9)146，(10)156，(11)234，(12)235，(13)236，(14)245，(15)246，(16)256，(17)345，(18)346，(19)356，(20)456．第一章 排列与组合

从中可得规律：（1）最后一位数最大可达n，倒数第2位最大可达n-1，…，依此类推倒数第k位(k≤r)不得超过n-k+1．若r个元素的组合用c1c2…cr来表示，不妨假定c1<c2<…<cr

其中ck＜n-r+k

，k＝1,2,…,r。(2)当存在cj＜n-r+j时，其中下标的最大者设为i，即i＝max{j|cj

＜n-r+j}，则作ci←ci+1。与之相应地作ci+1←ci+1，ci+2←ci+1+1，…，cr←cr-1+1第一章 排列与组合于是我们可得到一般的算法：(1)求满足不等式ci＜n-r+i的最大的下标i，即i＝max{j|cj＜n-r+j}，(2)ci←ci+1。(3)从i+1位开始途径修改：cj←cj-1+1，j=i+1,i+2,…r大家可以思考，从n个不同元中选r个的可重组合的生成？第一章 排列与组合1.6若干等式及其组合意义组合意义或组合证明:含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。1.C(n,r)=C(n,n-r)

(1.6.1)※从[1,n]去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。第一章 排列与组合2.C(n,r)=C(n-1,r)+C(n-1,r-1)(1.6.2)※从[1,n]取a1,a2,…,ar.设1≤a1＜a2＜…＜ar≤n,对取法分类： a1=1,有C(n-1,r-1)种方案

a1>1,有C(n-1,r)种方案 共有C(n-1,r)+C(n-1,r-1)中方案，第一章 排列与组合3.(

)+()+()+…+()=()(1.6.3)nn+1n+2n+rn+r+1nnnnra1=2,a2…an+1取自[3,n+r+1]有()种取法n+r-1n………a1=r,a2…an+1取自[r+1,n+r+1]有()种取法n+1n也可看做按含1不含1，含2不含2,…,含r不含r的不断分类※[1]可从(6.2)推论，也可做一下组合证明从[1,n+r+1]取a1a2…anan+1，设a1＜a2＜…＜an

＜an+1，可按a1的取值分类：a1=1,2,3,…r,r+1.a1=r+1,a2…an+1取自[r+2,n+r+1]有()种取法nnn+rna1=1,a2…an+1取自[2,n+r+1]有()种取法第一章 排列与组合①选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委②选常委,再选非常委政治局委员两种选法都无遗漏,无重复地给出可能的方案，应该相等。nlnn-rlrrl-r4.()()=()()(1.6.4)第一章 排列与组合mkm-k

mmkk=0证1(x+y)

=∑(

)x

y,令x=y=1,得(1.6.5)5.()+()+…+()=2,m≥0,(1.6.5)mmmm01m组合证

[1,m]的所有方案.每一元素都可取或不取两种状态，由乘法原理可知所有状态数为2m.

而这些可分解为从m个元素中分别取0个,1个，2个，…，m个组合的总和。第一章 排列与组合例某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干钥匙。须４人到场，所备钥匙才能开锁。问①至少有多少把不同的钥匙？②每人至少持几把钥匙？解①每３人至少缺１把钥匙，且每３人所缺钥匙不同。故至少共有()=35把不同的钥匙。73任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁。故每人至少持(

)＝20把不同的钥匙。６３一般地某保密装置安装了一个电子锁.须同时使用若干把不同的钥匙才能打开。现有n人，每人有一把钥匙。必须m人(m<n)到场，才能用钥匙开锁。问怎么分配锁的特征和每个的钥匙上的特征?

既然锁比任意m-1把钥匙多一个特征，而任意两个m-1把钥匙组