组合数学算法(二)

组合数学算法(二)

ID:39627457

大小:318.50 KB

页数:14页

时间:2019-07-07

组合数学算法(二)_第1页
组合数学算法(二)_第2页
组合数学算法(二)_第3页
组合数学算法(二)_第4页
组合数学算法(二)_第5页
资源描述:

《组合数学算法(二)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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个,不

3、妨设为红色点。设这些红点中,纵坐标y=j的点有mj个(1≤j≤12),则。又由y=j的红点连得条不同的线段。于是知由这些红点至少可以连得应用二次平均与算术平均不等式得(条)不同的平行于x轴的线段。这些线段在x轴上投影均落在1≤x≤12中。但该区间中,由坐标为整数的点所连成的线段一共只有=½x12x11=66条。由此可知,上述平行于x轴的线段的投影中必有一些相互重合,而投影重合的两线段的四个端点恰构成一个长方形的点。它们都是红色的,且长方形的边分别平行于二个坐标轴。*例4在平面上给定5个点,已知连结这些点的直线

4、互不平行,互不垂直,也不重合。通过每一个点向其余4点的各条连线作垂线,这些垂线的交点最多有几个?(不包括原来的5个点)解:由给定的5个点可两两连成=10条线段,由其中每4点可两两连成=6条直线。因此,由每个点都应引出6条垂线,一共有5x6=30条,如果这些垂线中每两条都相交,则一共可交得=435个交点。但这些垂线是分别向10条连线引出的,每一条连线上都有3条垂线(5点中除自连的两点外还剩3点,可向这条连线引垂线),这三条垂线互相平行没有交点,因此要减去10x3=30条。又由于由给定的5个点可构成=10个三角形

5、,上述30条垂线恰好是这些三角形的全部高,每个三角形中的三条高线相交于同一点,因而还要减去10x3-10=20。最后,由于经过每个原来的点的垂线都有6条,所以还要减去=75。因此得这些垂线的交点最多只能有435-30-20-75=310个。435:是5个点中每点可引6条垂线()共30条垂线,其中每二条交于一点共30:原来5点两两连接共10条线,每条线上有3条平行垂线没有交点共10x3=3020:每个三角形中三条高交于一点,不是一般的3点,所以要(多出来的)75:原来从每点向其他4点所成连线的垂线交于该点不算在

6、内,故例5有两位高一学生参加高二年级的象棋比赛,比赛时每二个棋手都要对弈一局,胜者得1分,败者得0分,平局每人½分。现知两位高一学生共得8分,每位高二选手得分相等,而且都是整数。问高二有几位选手参赛?解:设高二有n位选手参赛,这样全部选手有n+2个,故赛局有,其中8局分数为高一生所得,其余为高二生所得,并平分。故有=非负整数即=非负整数如果n为奇数,则应为整数,从而n=7或1。但n=1不合题意,舍去。故取n=7。如果n为偶数,则应为整数,故应为分母为2的约分数,故知n=14。重组合从n个不同的元素中取r个允许

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

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

9、OOO

10、O

11、

12、O

13、OOOO

14、OOO

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。