组合数学复习课.ppt

《组合数学复习课.ppt》由会员分享，可在线阅读，更多相关《组合数学复习课.ppt（35页珍藏版）》请在三一文库上搜索。

1、组合数学,http:/ Mathematics),Contents,例 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？ 解 一种常见的思路是按轮计场，费事。 各轮场数502512632199 剩余选手数目:25, 13, 7, 4, 2, 1 另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。,全排列的生成算法 1序数法,由序数2，0，1 ，求十进制m13 m=23！02！11！13 由十进制m13，求序数2，0，1,序数 n!个，对应n元的n!个序列。 规则(序列序数)：序列(p)= 是(p)中数字i+1后面比i+1小的数的

2、个数 如 (p)=(4213) 对应 =(301) n4 (p)=(3412) 对应 =(220) 规则(序数序列)： 如其中的序列(220)所对应的排列: 先由 =2决定4的位置 x4xx 再由 =2决定3的位置 34xx 再由 =0决定2的位置 34x2 则 3412,2字典序法,例 设有排列(p) =2763541, 按照字典式排序, 它的下一个排列是谁? (q) =2764135. (1) 2763541 找最后一个正序35 (2) 2763541 找3后面比3大的最后一个数4 (3) 2764531 交换3,4的位置 (4) 2764135 把4后面的531反序排列为135 即得到最

3、后的排列(q),例 求839647521的下一个排列 找出比右边数字小的第一个数4 在后缀7521中找出比4大的最小数 5 4 ,5 对换成为 839657421 将此后缀7421翻转成为 1247 接上前缀83965得到839651247 即839647521的下一个。,3邻位对换法,活动数是箭头所指相邻数比自己小的数。 对换规则： 活动数中最大的数m，交换箭头所指相邻数。 同时，比m大的数，改变方向。,4 组合的生成,设1,2,3,4,5,6中取3个的组合，20个， 按照字典序排列。 123，124，125，126，134， 135，136，145，146，156， 234，235，236

4、，245，246， 256，345，346，356，456。 第1位1到4，第2位2到5，第3位3到6。,每个组合C1C2C3满足条件1C1 C2 C36. C3最大可以到6, C2最大可以到5, C1最大可以到4. 如果每个数都已经达到最大, 那就结束了. 如果没有, 就找最右边一个还没有达到最大值的数, 给这个数加1，(并依次写出后续各数)，得到下一个组合. 重复这个过程就可以得到整个组合.,如256，345，346，356，456。 256中，5和6到最大。 2加1为3，后接4，5等。为345。 如156，234，235，236，245， 156中，5和6到最大。 1加1为2，后接3，4

5、等。为234。 236中，6到最大。 3加1为4，后接5等。为245。,组合意义的解释,例 选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委 选常委,再选非常委政治局委员 两种选法都无遗漏,无重复地给出可能的方案，应该相等。,线性常系数齐次递推关系,(1)若特征多项式 有n个不同零点 则递推关系的解,其中 是待定系数，有初始条件 来确定。,(2)若特征多项式 有不同的复根，可依照(1)的办法处理。不过任意复数 可写为 形式，设 是 的一个零点，其共轭复根为,和 仍然是待定常数。即 有一对共轭复根 和 时，递推关系的解有对应的项,其中A，B是待定常数。,(3)若 k重根。

6、不妨设 是k的重根。则递推关系(2-5-1)的解对应于的项为 其中 是k个待定常数。,关于线性常系数非齐次递推关系,线性常系数齐次递推关系解决得比较彻底，而非齐次的只限于某些特殊情况：,其中s是一参数，对应的齐次递推关系为,(1)假定所讨论的非齐次递推关系为,若序列,是非齐次递推关系的解，则序列,是齐次递推关系的解。,例3,代入非齐次递推关系,令 则,满足齐次递推关系,特征方程,由初始条件,关于线性常系数非齐次递推关系,其中b(n)是n的p次多项式，r是特征方程,(2)若非齐次递推关系,的m重根,则特解的形式有,其中,是待定常数，由非齐次递推关系确定。,若r不是C(x)=0的根，则令m=0。,

7、例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理、化学的22人；同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？,令A、B、C分别为修数学、物理、化学的学生集合。,即学校共有336名学生。,容斥原理的推广,例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理、化学的22人；同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？,若把问题改为“单

8、修一门数学的学生有多少？” “只修一门课的学生有多少？”“只修两门课的学生有多少？”呢？,仍然用A、B、C分别表示修数学、物理、化学的学生的集合。,类似有,因此,例 求方程x1+x2+x3=15的非负整数解的数目。,这个问题相当于15个相同的球放入3个不同的盒子的不同方案数，为C(15+3-1,15)=C(17,2)。,令U为全体非负整数解，A1为其中x15的整数解，A2为其中x26的整数解，A3为其中x37的整数解。,则|U|=C(17,2)。A1相当于求线性方程,(x1+6)+x2+x3=15,类似有：|A2|=C(8+3-1,8)=C(10,2)，,但如果加上条件 呢？,的非负整数解，其

9、个数为|A1|=C(9+3-1,9)=C(11,2)。,|A3|=C(7+3-1,8)=C(9,2)。,A1A2相当于求线性方程,(x1+6)+(x2+7)+x3=15,类似有：|A1A3|=C(3,2)， |A2A3|=C(2,2)。,因此方程满足条件 的非负整数解数目为：,的非负整数解，| A1A2 |=C(2+3-1,2)=C(4,2)。,A1A2A3相当于求线性方程,(x1+6)+(x2+7)+(x3+8)=15,的非负整数解，|A1A2A3 |=0。,例1 欧拉函数(n)，是指小于n且与n互素的正整数的个数。,令Ai (i=1,2,k)分别表示1到n这n个整数中pi的倍数组成的集合。

10、,则显然有|U|=n，|Ai|=n/pi。,注意到所有的素数互不相同，所以|AiAj|=n/(pi pj)。,类似有：|AiAjAk|=n/(pi pj pk)。,设n的因数分解为：,其中p1,pk是互不相同的素数。,其他的都可以依此类推。,因此小于n且与n互素的正整数的个数为：,例如60=2235，所以,即比60小且与60互素的数有16个： 1，7，11，13，17, 19, 23，29，31，37，41，43，47，49，53，59。,例4 在边长为1的等边三角形内任意取5个点，则至少存在两个点，其距离不超过1/2。,等边三角形三边的中点把等边三角形分成四个边长为1/2的等边三角形。,每个

11、小等边三角形内的点之间的距离不超过1/2。,由鸽巢原理，任取5个点中至少有两个落入同一个小等边三角形内，它们的距离不超过1/2。,例5 设a1,a2,am是正整数序列，则至少存在一个k和l，1klm，使得和ak+1+al是m的倍数。,构造序列Si=a1+ai，i=1,2,m。,设Si除以m的余数为ri。下面来讨论ri。,(1) 若有某个ri=0，则命题已成立。,(2) 若所有的ri都不为零，则ri只可能是1到m-1。,不妨设rk=rl，其中l k，则Sl -Sk是m的倍数。,根据Si的定义，,但是共有m个ri，根据鸽巢原理，至少有2个相同。,Sl -Sk= ak+1+al，,故命题成立。,Thank You !,http:/