《组合数学算法二》PPT课件.ppt

二、组合 与排列不同，组合是研究无次序的选取问题。 定义：从n个不同元素中无次序地选取k个，叫做从n个元素中选k个的一个组合。记 或 其中 中C是Combination的第一个字母， 而 是Andreas Von Ettingelausen(17961876)发明的 排列与组合的关系： （1） 由（1）可推出组合数的两个基本恒等式： (i) (ii) 另外，还约定：当kn及k0时，都有 ， ，,例1 印度人早已了解组合规律，大约在公元前六世纪的一本书就记载了如下问题：“甜、酸、咸、辣、苦、涩六味可以调出多少种味道？” 书上所附答案是：“六种单味，十五种双味，二十种三味，十五种四味，六种五味，一种六味。” 这就是组合数 例2 公元628年写的一本书中还有这样一道题：“一位有经验的建筑师为国王建造一座雄伟的宫殿，这座宫殿有八个门，每次开一个门，或二，三， ，共有多少种不同的开门方式？” 答：255种,*例3 在一平面直角坐标系中考虑格点（x，y），其中x，y Z 满足1x12，1y12。将这144个格点分别染成红、白、蓝三色。证明：存在一个长方形，它的边平行于坐标轴，它的顶点具有相同的颜色。 证：首先这三种颜色的点中，至少有一种不少于144/3=48个，不妨设为红 色点。设这些红点中，纵坐标y=j的点有mj个（1j12），则 。 又由y=j的红点连得 条不同的线段。于是知由这些红点至 少可以连得 应用二次平均与 算术平均不等式得 （条）不同的平行于x轴的线段。 这些线段在x轴上投影均落在1x12中。但该区间中，由坐标为整数的 点所连成的线段一共只有 = x12x11=66条。由此可知，上述平行于x轴的线段的投影中必有一些相互重合，而投影重合的两线段的四个端点恰构成一个长方形的点。它们都是红色的，且长方形的边分别平行于二个坐标轴。,*例4 在平面上给定5个点，已知连结这些点的直线互不平行，互不垂直，也不重合。通过每一个点向其余4点的各条连线作垂线，这些垂线的交点最多有几个？（不包括原来的5个点） 解：由给定的5个点可两两连成 =10 条线段，由其中每4点可两两连成 =6 条直线。因此，由每个点都应引出6条垂线，一共有5x6=30条，如 果这些垂线中每两条都相交，则一共可交得 =435个交点。但这些垂线是分别向10条连线引出的，每一条连线上都有3条垂线（5点中除自连的两点外还剩3点，可向这条连线引垂线），这三条垂线互相平行没有交点，因此要减去10 x3=30条。又由于由给定的5个点可构成 =10个三角形，上述30条垂线恰好是这些三角形的全部高，每个三角形中的三条高线相交于同一点，因而还要减去10 x3-10=20。最后，由于经过每个原来的点的垂线都有6条，所以还要减去 =75 。因此得这些垂线的交点最多只能有435-30-20-75=310个。 435：是5个点中每点可引6条垂线（ ）共30条垂线，其中每二条交于一点共 30：原来5点两两连接共10条线，每条线上有3条平行垂线没有交点共10 x3=30 20：每个三角形中三条高交于一点，不是一般的3点，所以要 （多出来的） 75：原来从每点向其他4点所成连线的垂线交于该点不算在内，故,例5 有两位高一学生参加高二年级的象棋比赛，比赛时每二个棋手都要对弈一局，胜者得1分，败者得0分，平局每人分。现知两位高一学生共得8分，每位高二选手得分相等，而且都是整数。问高二有几位选手参赛？ 解：设高二有n位选手参赛，这样全部选手有n+2个，故赛局有 ，其中8局分数为高一生所得，其余 为高二生所得，并平分。 故有 =非负整数 即 =非负整数 如果n为奇数，则 应为整数，从而n=7或1。但n=1不合题意，舍去。故取n=7。 如果n为偶数，则 应为整数，故 应为分母为2的约分数，故知n=14。,重组合 从n个不同的元素中取r个允许重复的元素而不考虑其次序时，称为从n 个中取r个允许重复的组合，简称重组合。记H(n,r) or C(n+r-1) 其实这是一类放球入盒的问题。这类占位问题在统计物理和古典概率中 具有特别的兴趣，被称为波瑟爱因斯坦(Bossel-Einstein)统计模型。对 它处理需要一点特别的技巧。 这类统计模型可归为：“球不可区分，盒子可区分，每盒容量不限，也就 是：要将k个相同的球放入n个不同的盒子，每盒所放球数不限，有多少种 不同的放法？” 下面推导它的计算公式。 既然球是相同的，所以关键的区别就在各个盒子中所放的球数上面。即 对不同的放法，各个盒子中所分的球数不会全部相同的，当然，一旦各个 盒子所摊得的球数确定下来，那么一种放法也就确定下来了。因此，现在 的问题就归结为任何把一字排开的k个相同的小球分成n段，然后以各段中 的球数作为相应的盒子可摊得的球数就可以了。那么怎样才能把排成一列 的k个小球分开成n段呢？,我们可设想有n-1块隔板，只要把它们分别插入到小球的行列中，如图， O O | O O O | O | | O | O O O O | O O O | O 则小球就自然地被分成n段了。（这些段中可能是空的，就是不放球之盒）于是问题归结为：不尽相同的元素的排列k个相同的球和n-1块相同的隔板的排列所以知这一类占位问题中一共有 种不同的放法。 （吴文虎先生所著书中，将1作为盒子，0作为球，意思是一样的。）但 上述更直观一点。该书中有(x+y+z)1986共有几项？ 例 在(a1+a2+ +an)k 的展开式中有多少类不同的项？ 解：展开式中的每一项都具有 的形式，其中 反之，对于每组符合 的mi ， 均为展开式中的项。 所以有多少种将k折为非负m1，mn 的和的方式，展式中就有多少类不 同的项。这等价于将k个相同的球放入n个不同的容量不限的盒子的放法数 目，所以有 不同的项。,例 求x + y + z=1的整数解的数目，要求x，y，z都大于-6。 如无后面条件限制，则其解之数为 （1 0 0），（0 1 0），（0 0 1） 但加上条件后怎么办？ 要求x-6,y-6,z-6也就是相当于x+50, y+50, z+50. 即原方程化为 (x+5)+(y+5)+(z+5)=16 所以原问题化为 u + v + w=16 即 （个） 例 在1与106之间，有多少个整数的各位数字之和等于9？ 解：只要将问题设想为将9个无区别的球随意放入6个不同的盒子。即,鸽笼原理或抽屉原理（简介） 我们在讨论重排列时，如将问题化为：设盒子是有区别的，每个盒子的容量不限，而且球数k盒数n，现计算无空盒出现的情况数目。 假设要用n-1块隔板，将排成一行的k个球隔成n段，但任意两块隔板不能相邻，否则就要出现空盒，同理隔板也不能出现在两端。所以相当于要自k个球之间的k-1个间隔中选出n-1个来放置隔板，如图。O|OO|O|OOO|O|O|OOO|OO|O 所以是一个组合问题，知有 种不同情况。 例 x + y + z + w=23，有多少正整数解？ 解：与前面例子相似，但x、y、z、w不能等0。即知 有 个正整数解。 例 高三有8个班协商组成年级篮球队，共需10名队员，每班至少出1名。问有多少种组成方式？ 解：设有10个无区别的球与8个不同的盒子，不能出现空盒，即,补充例子 某市有n所中学，第i所中学派出ci名学生(1 ci 39，1in)来到体育 馆看球赛，全部学生总数为 ，看台上每一横排有199个座位， 要求同一学校的学生必须坐在同一横排，问体育馆最少要安排多少横排才 能保证全部学生都能坐下？ 解：首先证明，只要安排12个横排即可满足。 由于ci只有有限个， ci的有限和也是有限个，选取其中最接近199的有限 和，设为ci1 + ci2 + ci k ，即使 x1=199-(ci1 + ci2 + ci k) min 让这 些学生坐在第一排，则x1便是第一排中的空位数。于是对j i1， ik 的所有j均应有cj x1+1（否则第一排又可排下一个cj）。我们可断言必然 有x1 32。事实上，反证之，若x1 33，则对所有其余cj，应有cj 34， 从中任取5个学校，不妨设为c1，c2，c3，c4，c5则有 5x39=195 c1+c2+c3+c4+c5 5x34=170 =199-( c1+c2+c3+c4+c5 ) 199-170=2932 此与x1的最小性矛盾。,从所有其余的cj中选取 cj1+cj2+cj t 使其最接近199，让这些学生坐在第二排。 令x2=199 ( cj1+cj2+cj t ) 同理可证x2 32 对于第3排、第4排、第i排依次如此去做。 当安排好第 i 排后，令 x i 表示第 i 排的空位数，则只要剩下的学校不少于5所，便一定有x i 32，推理同前。 如果在安排完11排后，学生已坐完，则问题得证。 如果还未坐完，则可分为两种情况： 一是余下学校不足5所，由于4x39199，则其余学生可坐第12排； 如果余下的学校不少于5所，则仍有x11 32，这样前11排至少坐 11 x (199-32)=1837个学生，余下的学生不多于162个，自然可坐在第12 排上。,例 将边长为n的一个正方形分成n x n个个单位正方形，相当于画成一个围棋盘，棋盘中当然能数出许多矩形来。按惯例，称矩形的短边为宽，长边 为长，并把正方形也算作矩形。证明：棋盘中有23个宽n-1的矩形，33个宽 n-2的矩形，n3个宽1的矩形，并由此导出公式 证：数轴上以整数为端点，含于区间0，n中且长度是n-k的区间共有 k+1个，它们是0，n-k，1，n-k+1， ，k，n 。 因此，棋盘中以横向为宽，纵向为长，且宽n-k，长n-l (l k)的矩形有 (k+1)(l+1)个。对 l 求和，即知棋盘中以横向为宽，纵向为长，且宽n-k的矩形共有 同理，以纵向为宽，横向为长且宽为n-k的矩形也有 个。注意 到其中长宽均为n-k的正方形有(k+1)2个，它们同时被计了上述两个数字， 所以棋盘中宽为n-k的矩形共有(k+1)2(k+2)-(k+1)2=(k+1)3 k=1,2,n-1,另一方面，棋盘中任意两条横向直线和任意两条纵向直线都可以界得一个 矩形。于是由乘法原理知棋盘中共有 个矩形。综合两方面得： *例 n个人参加同一会议，其中每两个互不认识者都恰好有两个共同的熟 人，每两个熟人却都没有共同的认识者。证明：每一个与会者都有相同数 目的熟人。 解：设与会者甲有m位熟人a1，a2，am，由于他们都同甲熟悉，所以 他们互不认识。（为什么？）（因为其中任一个与甲为熟人，故没有共同 熟人，所以他们互不认识）既然他们都互不认识，所以他们中每两个人 (ai ，aj)除甲外都还有另一个共同的熟人，这些熟人当然都不认识甲（为什 么？因为如果有人认识甲，则甲的熟人为m+1，不是m了）。另外，对于 不同的(ai ，aj)，另一熟人也互不相同。于是,知与会者中不认识甲的人不会少于 。但另一方面，每个不认识甲的人 同甲一道都有两个共同的熟人，这些人既然都认识甲，所以都在 a1，a2，am之列，而且对于不同的不认识甲的人。这两个共同的熟人 (ai ，aj)也不会全然相同（为什么？如果有相同，则甲与不认识者就有多于 2个共同熟人）。因此可得，不认识甲的人不会多于 个。综上所述得， 与会者中恰有 个不认识甲的人。这样一来，参加的总人数n便应满足 等式 考察这个关于m的正整数二次方程，发现它只有唯一的正数根。所以对于 每个与会者，他的熟人数目m为常数。 （负值舍去） 唯一,