《组合数学算法》PPT课件

《《组合数学算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二、组合与排列不同，组合是研究无次序的选取问题。定义：从n个不同元素中无次序地选取k个，叫做从n个元素中选k个的一个组合。记或其中中C是Combination的第一个字母，而是AndreasVonEttingelausen(1796—1876)发明的排列与组合的关系：∴（1）由（1）可推出组合数的两个基本恒等式：(i)(ii)另外，还约定：当k>n及k<0时，都有，，例1印度人早已了解组合规律，大约在公元前六世纪的一本书就记载了如下问题：“甜、酸、咸、辣、苦、涩六味可以调出多少种味道？”书上所附答案是：“六种单味，十五种双味，二十种三味，十五种四味，六种五味，一种六味。”这就是组合数例2公

2、元628年写的一本书中还有这样一道题：“一位有经验的建筑师为国王建造一座雄伟的宫殿，这座宫殿有八个门，每次开一个门，或二，三，…，共有多少种不同的开门方式？”答：255种*例3在一平面直角坐标系中考虑格点（x，y），其中x，yєZ满足1≤x≤12，1≤y≤12。将这144个格点分别染成红、白、蓝三色。证明：存在一个长方形，它的边平行于坐标轴，它的顶点具有相同的颜色。证：首先这三种颜色的点中，至少有一种不少于144/3=48个，不妨设为红色点。设这些红点中，纵坐标y=j的点有mj个（1≤j≤12），则。又由y=j的红点连得条不同的线段。于是知由这些红点至少可以连得应用二次平均与算术平均不等式

3、得（条）不同的平行于x轴的线段。这些线段在x轴上投影均落在1≤x≤12中。但该区间中，由坐标为整数的点所连成的线段一共只有=½x12x11=66条。由此可知，上述平行于x轴的线段的投影中必有一些相互重合，而投影重合的两线段的四个端点恰构成一个长方形的点。它们都是红色的，且长方形的边分别平行于二个坐标轴。*例4在平面上给定5个点，已知连结这些点的直线互不平行，互不垂直，也不重合。通过每一个点向其余4点的各条连线作垂线，这些垂线的交点最多有几个？（不包括原来的5个点）解：由给定的5个点可两两连成=10条线段，由其中每4点可两两连成=6条直线。因此，由每个点都应引出6条垂线，一共有5x6=30条

4、，如果这些垂线中每两条都相交，则一共可交得=435个交点。但这些垂线是分别向10条连线引出的，每一条连线上都有3条垂线（5点中除自连的两点外还剩3点，可向这条连线引垂线），这三条垂线互相平行没有交点，因此要减去10x3=30条。又由于由给定的5个点可构成=10个三角形，上述30条垂线恰好是这些三角形的全部高，每个三角形中的三条高线相交于同一点，因而还要减去10x3-10=20。最后，由于经过每个原来的点的垂线都有6条，所以还要减去=75。因此得这些垂线的交点最多只能有435-30-20-75=310个。435：是5个点中每点可引6条垂线（）共30条垂线，其中每二条交于一点共30：原来5点两

5、两连接共10条线，每条线上有3条平行垂线没有交点共10x3=3020：每个三角形中三条高交于一点，不是一般的3点，所以要（多出来的）75：原来从每点向其他4点所成连线的垂线交于该点不算在内，故例5有两位高一学生参加高二年级的象棋比赛，比赛时每二个棋手都要对弈一局，胜者得1分，败者得0分，平局每人½分。现知两位高一学生共得8分，每位高二选手得分相等，而且都是整数。问高二有几位选手参赛？解：设高二有n位选手参赛，这样全部选手有n+2个，故赛局有，其中8局分数为高一生所得，其余为高二生所得，并平分。故有=非负整数即=非负整数如果n为奇数，则应为整数，从而n=7或1。但n=1不合题意，舍去。故取n

6、=7。如果n为偶数，则应为整数，故应为分母为2的约分数，故知n=14。重组合从n个不同的元素中取r个允许重复的元素而不考虑其次序时，称为从n个中取r个允许重复的组合，简称重组合。记H(n,r)orC(n+r-1)其实这是一类放球入盒的问题。这类占位问题在统计物理和古典概率中具有特别的兴趣，被称为波瑟—爱因斯坦(Bossel-Einstein)统计模型。对它处理需要一点特别的技巧。这类统计模型可归为：“球不可区分，盒子可区分，每盒容量不限，也就是：要将k个相同的球放入n个不同的盒子，每盒所放球数不限，有多少种不同的放法？”下面推导它的计算公式。既然球是相同的，所以关键的区别就在各个盒子中所放

7、的球数上面。即对不同的放法，各个盒子中所分的球数不会全部相同的，当然，一旦各个盒子所摊得的球数确定下来，那么一种放法也就确定下来了。因此，现在的问题就归结为任何把一字排开的k个相同的小球分成n段，然后以各段中的球数作为相应的盒子可摊得的球数就可以了。那么怎样才能把排成一列的k个小球分开成n段呢？我们可设想有n-1块隔板，只要把它们分别插入到小球的行列中，如图，OO

8、OOO

9、O

10、

11、O

12、OOOO

13、OOO

14、O则小球就自然地被分