单墫老师教你学数学 组合数学的问题与方法

《单墫老师教你学数学 组合数学的问题与方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、!!!!$目!录总序!0前言!00!!计数问题!0#!!存在问题!#$!!!图论问题!!":!!灵活多样的问题!20习题!1#解答!11!!!!!!计数问题!我赴圣地爱弗西"!"#$#$途遇妇女数有七$每人七袋手中提$一袋七猫数整齐$一猫七崽紧相依!妇与布袋猫与崽$几何"多少#同时赴圣地%&这是一首古老的英国童谣!假设它说的是事实的话!我们很怀疑每位妇女手中能提那么多的猫咪"#不难算出妇!女!!!!!!!!!%!名布!袋!!!!!%&"!’(!!个!!猫!!!!!!!%)")’)只崽!!!!!!!%’"&’*+只!总!数!!!!!!!!&,

2、**有很多问题与这首童谣类似!例如$一个军有三个师#一个师有三个旅#一个旅有三个团#一个团有三个营#一个营有三个连#一个连有三个排#一个排有三个班#一个军有多少个班!显然#答案是!!!!"%)#)#)#)#)#)#)")"&+,%!即使问题中出现的数不一定全部相同!全是%或全是)"#但计算的方法也是一样的$采用乘法!下面的例+便是如此!例"!#####################从甲地到乙地有三条路#从乙地到丙地有四条路!如图+-+"#问从甲地到乙地再到丙地有多少种不同的走法!图+-+走法共有)#’"+&种!我们可以把这+&种走法全部列

3、举出来#即!$#!%#!&#!’#####"$"%"&"’#$##%##&##’!其中!$表示先经路!到乙#再经路$到丙!例+与下面的问题实质上是一样的$%如果一棵树有三个枝#一个枝有四朵花#那么一棵树有几朵花!&从这些简单的问题可以总结出一个重要的原理#即乘法原理!如果做第一件事有!种方法!第一件事做完后做第二件事有"种方法!第一"二件事做完后做第三件事有#种方法!#$那么先做第一件事!再做第二件事!然后再做第三件!!!!#事!#!就有(#)#*##种方法$这个原理看来简单#却极为重要#有着广泛的应用!例""!##############

4、#######一项比赛有.名运动员参加#要定出第一名’第二名’第三名#有多少种不同的结果!首先选第一名#有.种可能$每位运动员都有可能当第一名!第一名选好后再选第二名#有/种可能!第一’二名选好后再选第三名#有’种可能!因此!根据乘法原理"#选出前三名有.#/#’"+&*种不同的结果!用完全同样的推理#可以知道从*个不同的元素中选出+个元素排成一列#不同的排列数为*#!*,+"#!*,&"#(#!*,+-+"!选排在第一位的有*种方法#再选排在第二位的有*0+种方法#(#最后选排在第+位的有*0+1+种方法"!如果用2+来表示从*个不同的元

5、素中选出+个元素的排*列数#就有公式$%#&#’$#(!%’$#("%’#’$#(%)!%$如果+"*#就得到*个元素的全排列公式!即将*个元素排成一列的不同排列的种数"#%&#’$#(!%’$#("%’$#$即$##’"’!&#&$!!!!%*"!读做*的阶乘"就是*#!*,+"#!*,&"#(#&#+的缩写!为了方便起见#规定&&&!$上面的排列公式也可改写成%#&$#&$$#(%%&例"#!#####################五个人排成一列照相#有多少种不同的排法!答案是!/""/#’#)#&#+"+&*!例"$!#######

6、##############用+#&#/#.#,这五个数字组成三位数#如果$!+"三位数中数字不重复出现)!&"数字可以重复出现!可以组成多少种不同的三位数!第一个小问题的答案是)2/"/#’#)".*!第二个小问题的答案是/#/#/"+&/!理由与本节开始的童谣相同$第一位数字有/种选法#第二位数字也有/种选法!允许第一位数字重复出现"#第三位数字也有/种选法#因而根据乘法原理#共有/3/3/种选法!更一般地#从*个元素中选出+个排成一列#如果每个元素都可以重复选取#那么排列数为+*#*#(#*"*!%$&+个!!!!’这是允许重复的排列

7、公式!不过#重要的不是死背公式#而是如何去运用乘法原理!例’的两个问题都可以用乘法原理解决#请读者体会这两个问题的差别"!例"%!#####################用数字*#+#&#’#/可以组成多少个没有重复数字的三位数!先考虑百位数字#有’种选法!*不能在首位"#再考虑十位数字与个位数字#可知答案是’#’#)!!或’#2&""’,!’例"&!#####################将字母.#.#.#/#0#1#2排成一列#有多少种不同的排法!如果是%个不同的字母.+#.&#.)#/#0#1#2#那么排成一列的排法!全排列"是%

8、""%#.#/#’#)#&#+!现在的问题是%个字母中有三个是相同的.!为了解决这个问题#我们运用一个非常重要的思想$对应!对%个不同的字母.+#.&#.)#/#0#1#2的一种