建立组合数数学建模例子.docVIP

对五个球的排序问题 摘要： 现ABCDE5个球构成的排列组合可重复抽取最多取到16个共有多少种组合方式？现ABCDE5个球构成的排列组合可重复抽取最多取到16个共有多少种组方式？取1个球可以构成的组合有 A B C D E 共5种取2个球可以构成的组合有 5+4+3+2+1=15种 （BA 和 AB 这种重复的排列 算成一种） AA AB AC AD AE BB BC BD BE CC CD CE DD DE EE取 3 个球可以构成的组合是 （5+4+3+2+1）+（4+3+2+1）+（3+2+1）+（2+1）+1= 35种AAA AAB AAC AAD AAE ABB ABC ABD ABE ACC ACD ACE ADD ADE AEE BBB BBC BBD BBE BCC BCD BCE BDD BDE BEE CCC CCD CCE CDD CDE CEE DDD DDE DEE EEE 取四个球的方法： AAAA AAAB AAAC AAAD AAAE AABA AACA AADA AAEA AABB AABC AABD AABE AACB AADB AAEB AACC AACD AACE AADC AAEC AADD AADE AAED AAEE BBBB BBBC BBBD BBBE BBCB BBEB BBCC BBCD BBCE BBDC BBEC BBDD BBDE BBED BBEE CCCC CCCD CCCE CCDC CCEC CCDD CCDE CCED CCEE DDDD DDDE DDED DDEE EEEE 以上都可以采用树枝法来计算。 从上述的排列可以看出此次题目可以运用数学排序问题来解决 如取一次球时可得到：5！/1！*4！=5种方法； 再有取两次球可得到：两次的取法都有5！/1！*4！=5种；从两次中分别去取一个球。得到C(5,2)=15; 可以推出一下的结论： 从ABCDE这5个球里,重复抽取N个, 有C(n,n+5-1)=C(n,n+4)=C(4,n+4)个组合.取1个球的组合有C(1,5)=5种 取2个球的组合有C(2,6)=15种 取3个球的组合有C(3,7)=35种 取4个球的组合有C(4,8)=70种 取5个球的组合有C(5,9)=15种 取6个球的组合有C(4,n+4)=C(4,10)种 最多能取16个=C(4,20)种取1-16个的过程中 总计有: C(4,5)+C(4,6)+...+C(4,20)在组合的定义中,C二表示从。个不同元素中取出R个元素的组合数。这里n、R满足条件, (1):R, (2)n、R都是自然数。 在解一些含有组合符号的题目时,常常要考虑这两个条件组合数学中的著名问题 地图着色问题：对世界地图着色，每一种国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。 四色定理指出每个可以画出来的地图都可以至多用4种颜色来上色，而且没有两个相接的区域会是相同的颜色。被称为相接的两个区域是指他们共有一段边界，而不是一个点。 这一定理最初是由Francis Guthrie在1853年提出的猜想。很明显，3种颜色不会满足条件，而且也不难证明5种颜色满足条件且绰绰有余。但是，直到1977年四色猜想才最终由Kenneth Appel 和Wolfgang Haken证明。他们得到了J. Koch在算法工作上的支持。证明方法将地图上的无限种可能情况减少为1,936种状态（稍后减少为1,476种），这些状态由计算机一个挨一个的进行检查。这一工作由不同的程序和计算机独立的进行了复检。在1996年，Neil Robertson、Daniel Sanders、Paul Seymour和Robin Thomas使用了一种类似的证明方法，检查了633种特殊的情况。这一新证明也使用了计算机，如果由人工来检查的话是不切实际的。四色定理是第一个主要由计算机证明的理论，这一证明并不被所有的数学家接受，因为它不能由人工直接验证。最终，人们必须对计算机编译的正确性以及运行这一程序的硬件设备充分信任。参见实验数学。缺乏数学应有的规范成为了另一个方面；以至于有人这样评论“一个好的数学证明应当像一首诗——而这纯粹是一本电话簿！”船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。