《组合数学第一讲教学案例》由会员分享，可在线阅读，更多相关《组合数学第一讲教学案例（59页珍藏版）》请在金锄头文库上搜索。
1、前言,组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方.,幻方可以看作是一个 3阶方阵，其元素是1 到9的正整数，每行、 每列以及两条对角线 的和都是15。,5,1,9,3,7,2,4,8,6,前言,1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。 组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问
2、题。包括安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排问题。,前言,组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。 但是，要学好组合数学并非易事，既需要 一定的数学修养，也要进行相当的训练。,第一章排列与组合, 例 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18 + 10 = 28 人。, 例 北京每天直达上海的客车有 5 次，客机有 3 次， 则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。,第一章排列与组合, 乘法法则 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m n种产生方式。
3、,集合论语言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。,第一章排列与组合,例 某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有5 3 = 15 个。,例 从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6 条道路。,第一章排列与组合,例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42 = 8种着色方案。 若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是4 4 = 16，
4、而只有 4 3 = 12 种。 在乘法法则中要注意事件 A 和 事件 B 的相互相容性。,第一章排列与组合,例 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数,1)小于10000的不含1的正整数可看做4位数,但0000除外. 故有999916560个. 含1的有：99996560=3439个,另: 全部4位数有104 个,不含1的四位数有94个,含1的4位数为两个的差: 10494 = 3439个,第一章排列与组合,2)“含0”和“含1”不可直接套用。0019 含1但不含0。 在组合的习题中有许多类似的隐含的 规定，要特别留神。,不含0的1位数有9个，2位数
5、有92个，3位数有93个，4位数有94个,不含0小于10000的正整数有 9+92+93+94=(951)/(91)=7380个,含0小于10000的正整数有 99997380=2619个,第一章排列与组合,1.2排列与组合,定义：从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的排列。其排列的个数记为P(n,r)表示。,第一章排列与组合,规定：,从n个不同元中取n个的排列称为n的全排列,第一章排列与组合,我们有下列排列与组合的计数公式：,特别地，对于全排列有P(n, n)=n!。,第一章排列与组合,从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同
6、的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，第r个有n-r+1种选择。 故有P(n,r)=n(n-1) (n-r+1) 有时也用nr记P(n,r),第一章排列与组合,若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。,故有 C(n,r)r!=P(n,r),第一章排列与组合,例 有5本不同的日文书，7本不同的英文书，10本不同的中文书。 1)取2本不同文字的书； 2)取2本相同文字的书； 3)任取两本书 请问有多少种不同的取法？,解：1)57+510+710=155; 2)C(5,2)+C(7,2
7、)+C(10,2)=10+21+45=76;,第一章排列与组合,例 从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？,解：将1,300分成3类： A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)=3,6,9,300. 要满足条件，有四种解法： 1)3个数同属于A; 2)3个数同属于B 3)3个数同属于C; 4)A,B,C各取一数.,故共有3C(100,3)+1003 =1485100,第一章排列与组合,定义：从n个不同元素中允许重复地取r个元素作排列，称为n元可重r-排列，其排列数为nr 例：由
8、数字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)。我们有：,这是因为r个不同的线排列（即一般的排列）对应于一个圆排列。,第一章排列与组合,例：4个女生和4个男生围圆桌相间而坐，试问有多少种不同的入座方式？ 解：先让女生入座，这是一个4的圆排列问题。有K（4，4）4!=4！/44!=3！4!。 例:由
9、四种颜色的珠子各一颗，可以做成多少种不同的项链？ 解：注意项链可以翻转。,第一章排列与组合,定义：从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-组合，不妨设： 1a1 a2 ar n 从而有： 1a1 a2+1 a3+2 ar+r-1 n+r-1,第一章排列与组合,例:某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案有多少？,解一进站方案
10、表示成：00011001010100 其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。,第一章排列与组合,解法1标号可产生5!个14个元的全排列。 故若设x为所求方案，则 x5!=14! x=14!/5!=726485760,解法2在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。 故C(14,5)9!即所求,第一章排列与组合,解法3把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须
11、）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。 以此类推，9号有14种选择。 故所求方案为67 814种。,第一章排列与组合,1.3模型转换,“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。 如我们说A集合有n个元素 |A|=n，无非是建立了将A中元与1,n元一一对应的关系. 在组合计数时往往借助于一一对应实现模型转换。 比如要对A集合计数，但直接计数有困难,于是可设法构造一易于计数的B，使得A与B一一对应。,第一章排列与组合,例 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举
12、行几场比赛？ 解 一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。,第一章排列与组合,例,第一章排列与组合,无论怎样走法，在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),(m+n)!
13、m!n!,m+n n,m+n m,第一章排列与组合,例：在上例的基础上若设mn，求(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)一一对应,第一章排列与组合,若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得xy=1，(0,0)关于xy=1的对称点为(
14、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 | H,n=1甲烷 n=2 乙烷 n=3 丙烷,第一章排列与组合,H | H C H | H C H | H C H | H C H | H,H | H H C H | | H C C H | | H C H | H H,n=4 丁烷 n=4异丁烷,这说明对应CnH2n+2的 枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶
15、点是叶子。对于这样结构的每一棵树，就对应有一种特定的化,合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.,第一章排列与组合,1.4全排列的生成算法,就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。,全排列的生成算法有许多种，我们仅介绍其中一种-序数法,第一章排列与组合,1.4.1全排列的生成-序数法,任一自然数n都可以唯一确定一个p进制数,反之也然。,类似地，有,第一章排列与组合,同理,所以,即,第一章排列与组合,不难证明，从0到n!-1的任一个整数m都可唯一地表示为：,所以从0到n!-1的n!个整数与满足上式的序列(an-1,an-2,a
16、2,a1)一一对应。 然后我们再从(an-1,an-2,a2,a1)建立与全排列的一一对应关系。,第一章排列与组合,例 ：m4000，即n14000,第一章排列与组合,现从序列 (an-1,an-2,a2,a1)得到生成排列，为 了方便起见,不妨今n个对象分别是1,2, n.,建立起对应的规则如下： 设序列(an-1,an-2,a2,a1) 对应某个排列(p)=p1 p2,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为中介数。,第一
