构造组合模型巧证组合恒等式范文大全

第一篇：构造组合模型巧证组合恒等式

证明组合恒等式，一般是利用组合数的性质、数学归纳法、二项式定理等，通过一些适当的计算或化简来完成．但是，很多组合恒等式，也可直接利用组合数的意义来证明．即构造一个组合问题的模型，把等式两边看成同一组问题的两种计算方法，由解的唯一性，即可证明组合恒等式．例１证明Ｃｎｍ＝Ｃｎｍ－１＋Ｃｎ－１ｍ－１．

分析：原式左端为ｍ个元素中取

ｎ个的组合数．原式右端可看成是同一问题的另一种算法：把满足条件的组合分为两类，一类为不取某个元素ａ１，有Ｃｎｍ－１种取法．一类为必取ａ１有Ｃｎ－１ｍ－１种取法．由加法原理可知原式成立．

例２证明Ｃｎｍ·Ｃｐｎ＝Ｃｐｍ·Ｃｎ－ｐｍ－ｐ．

分析：原式左端可看成一个班有ｍ个人，从中选出ｎ个人打扫卫生，在选出的ｎ个人中，ｐ人打扫教室，余下的ｎ－ｐ人打扫环境卫生的选法数．原式右端可看成直接在ｍ人中选出ｐ人打扫教室，在余下的ｍ－ｐ人中再选出ｎ－ｐ人打扫环境卫生．显然，两种算法计算的是同一个问题，结果当然是一致的．

以上两例虽然简单，但它揭示了用组合数的意义证明组合恒等式的一般思路：先由恒等式中意义比较明显的一边构造一个组合问题的模型，再根据加法原理或乘法原理对另一边进行分析．若是几个数（组合数）相加的形式，可以把构造的组合问题进行适当分类，如例１，若是几个数（组合数）相乘的形式，则应进行适当的分步计算，如例２，当然，很多情况下是两者结合使用的．

例３证明Ｃｋｍ＋ｎ＝Ｃ０ｍＣｋｎ＋Ｃ１ｍＣｋ－１ｎ＋Ｃ２ｍＣｋ－２ｎ＋…＋ＣｋｍＣ０ｎ，其中当ｐ＞ｑ时Ｃｐｑ＝０．

证明：原式左边为ｍ＋ｎ个元素中选ｋ个元素的组合数．今将这ｍ＋ｎ个元素分成两组，第一组为ｍ个元素，剩下的ｎ个元素为第二组，把取出的ｋ个元素，按在第一组取出的元素个数ｉ（ｉ＝０，１，２，…，ｋ）进行分类，这一类的取法数为ＣｉｍＣｋ－ｉｎ．于是，在ｍ＋ｎ个元素中取ｋ个元素的取法数又可写成ｋｉ＝０ＣｉｍＣｋ－ｉｎ．故原式成立．

例４证明

Ｃｎｎ＋Ｃｎｎ＋１＋Ｃｎｎ＋２＋…＋Ｃｎｎ＋ｍ＝Ｃｎ＋１ｎ＋ｍ＋１．

证明：原式右边为ｍ＋ｎ＋１个元素中取ｎ＋１个，元素的组合数，不失一般性，可以认为是在１，２，３，…，ｍ＋ｎ，ｍ＋ｎ＋１，共ｍ＋ｎ＋１个数中取ｎ＋１个数．将取出的ｎ＋１个数ａ１，ａ２…，ａｎ＋１由小到大排列，即设ａ１＜ａ２＜ａｎ＋１，按取出的最大数ａｎ＋１＝ｋ＋１分类，显然ｋ＝ｎ，ｎ＋１，…，ｎ＋ｍ．当ｋ＝ｎ＋ｉ时（ｉ＝０，１，２，…，ｍ），这一类取法数为Ｃｎｎ＋ｉ，所以取法总数又等于ｍｉ＝０Ｃｎｎ＋ｉ．原式成立．

对于某些组合恒等式，有时其左右两边所表示的意义都不易看出，但是如果根据组合数的特点仔细分析，或对原式进行一些适当的变形，往往可以巧妙地构造一个组合问题做为模型，证明就可化难为易．

例５证明Ｃ１ｎ＋２Ｃ２ｎ＋３Ｃ３ｎ＋…＋ｎＣｎｎ＝ｎ２ｎ－１．

分析：注意，原式左端等价于Ｃ１１Ｃ１ｎ＋Ｃ１２Ｃ２ｎ＋…＋Ｃ１ｎＣｎｎ，这里Ｃ１ｉＣｉｎ可表示先在ｎ个元素里选ｉ个，再在这ｉ个元素里选一个的组合数，可设一个班有ｎ个同学，选出若干人（至少１人）组成一个代表团，并指定一人为团长．把这种选法按取到的人数ｉ分类（ｉ＝１，２，…，ｎ），则选法总数即为原式左端．今换一种选法，先选团长，有ｎ种选法，再决定剩下的ｎ－１人是否参加，每人都有两种可能，所以团员的选法有２ｎ－１种．即选法总数为ｎ２ｎ－１种．显然两种选法是一致的．

这里应注意２ｎ的意义，并能用组合意义证明ｎｉ＝０Ｃｉｎ＝２ｎ．

例６证明

Ｃ１ｎ＋２２Ｃ２ｎ＋３２Ｃ３ｎ＋…＋ｎ２Ｃｎｎ＝ｎ（ｎ＋１）２ｎ－２．

分析：本题左边与例５左边类似，不同的是例５左边为ｎｉ＝１ｉＣｉｎ，而本题为ｎｉ＝１ｉ２Ｃｉｎ．只要在例５构造的模型中加上同时还要选一个干事，并且干事和团长可以是同一个人，即可符合原式左边．对原式右边我们可分为团长和干事是否是同一个人两类情况．若团长和干事是同一个人，则有ｎ２ｎ－１种选法；若团长和干事不是同一个人，则有ｎ（ｎ－１）２ｎ－１种选法．所以，共有ｎ２ｎ－１＋ｎ（ｎ－１）２ｎ－２＝ｎ（ｎ＋１）２ｎ－２种选法．

例７证明

（Ｃ１ｎ）２＋２（Ｃ２ｎ）２＋３（Ｃ３ｎ）２＋…＋ｎ（Ｃｎｎ）２＝ｎＣｎ－１２ｎ－１．

分析：注意到（Ｃｉｎ）２＝ＣｉｎＣｎ－ｉｎ，可设一个班有ｎ个男生与ｎ个女生，在这２ｎ个学生中选ｎ个同学（至少有１名男生）组成一个代表团，并指定其中一名男生为团长，按选出的男生人数ｉ（ｉ＝１，２，…，ｎ）分类，这一类有ｉＣｉｎＣｎ－ｉｎ＝ｉ（Ｃｉｎ）２种选法，总的选法有ｎｉ＝１ｉ（Ｃｉｎ）２种．原式右边的组合意义是明显的，即直接在ｎ个男生中选一名团长，有ｎ种选法，再从剩下的２ｎ－１人中选出ｎ－１

人为团员，共有ｎＣｎ－１２ｎ－１种选法．

掌握了用组合意义证明组合恒等式这种方法后，还可通过构造一个组合问题的模型，编拟组合恒等式习题．如在例５中除了要选一名团长外，还要选一名干事和一名联络员（可以兼职）便可得ｎｉ＝１ｉ３Ｃｉｎ＝ｎ２（ｎ＋３）·２ｎ－３．具体证法可参照例５与例６．又如，在例７中除了在２ｎ个同学中选出ｎ个团

员及指定一名男生为团长外，还要有一名男生担任联络员（可以兼职），则可得组合恒等式：ｎｉ＝１ｉ２（Ｃｉｎ）２＝ｎＣｎ－１２ｎ－１＋ｎ（ｎ－１）Ｃｎ－２２ｎ－２．若在例７中要求，留下的女生中再选一名负责人，则有组合恒等式ｎｉ＝１ｉ２（Ｃｉｎ）２＝ｎ２Ｃｎ－１２ｎ－２．具体证明读者可自己完成．实际上习题的编拟过程就是用组合意义证明恒等式的过程．

若把恒等式中较简单的一边去掉，变为化简组合式，用此法同样能完成化简，读者可自己体会．

用组合数的意义证明组合恒等式，除了对提高学生的智力及观察分析问题的能力有帮助外，还有它独到的好处，那就是把抽象的组合数还原为实际问题，能提高学生应用数学知识解决实际问题的能力，把枯燥的公式还原为有趣的实例，能提高学生的学习兴趣．所以，老师在教学过程中适当介绍一些这方面的内容，将是大有益处的．

第二篇：算两次在证明组合恒等式中的应用

“算两次”思想在证明组合恒等式中的应用

mnm1.Cn，取走和剩下的一一对应； Cn

n

2.C

k0kn2n

122nn我们可令等式(1x)n1CnxCnxCnx中的x等于1，得到该式。

另外，我们可考察集合{b1,,bn}的子集的个数：

一方面，采取加法原理，根据子集中元素个数分类：C

k0nkn；

另一方面，采取乘法原理，设其子集为S，我们逐一考察bi,i1,2,,n是否在S内，每个元素都有两种可能，考察完毕，子集S确定，或者我没把子集看成一个排列，如

n；b11,0,0,,0。共2。0,0,,0

nn1

所以得证。

mmm1mm13.Cn，从{a,b1,,bn}取m个有Cn，一类不含a：1CnCn1种：一类含a：Cnm。Cn

mmm1推广①： An 1AnmAn

mm1m从{a,b1,,bn}取m个排成一排An，一类不含a：An。1：一类含a：mAn

n1nnnnn推广②：CnCCC

CCm1mnmn1mn2n1n

解释：有m+n+1不同小球，其中黑球m+1个，白球n个。从中选取n+1个小球，n1选法共：Cnm1种，n考虑另外一种算法：若有黑1则在剩余小球中选n个，即Cnm，若无黑1，则考虑是否有

n黑2，若有则从剩余n+m-1个小球中取n个，即Cnm1，依次考虑下去，到考虑是否有黑

nm，若有，则在剩余n个小球取n个，即Cn1，若无黑m。则必有黑m+1，最后剩下的m

个白球全取。总共CmnCmn1Cmn2Cn1Cn。所以得证。nnnnn

rr1

本公式另一种表现形式：CrrCrr1Crr2Cn本公式也可从杨辉三角1Cn。

观察可得。还可考察等式(1x)(1x)

rr1

(1r)

n1

(1x)n(1x)x

两端

x

xr的系数相同。

推广③： C

rnm

krk

CmCnk0r

r

从{a1,am,b1,,bn}取r(rm)个元素Cn：从这n+m个元素中取k个a系，r-k个bm

r

系的方法CC

k

mrkn

种，k0,1,2,,r，所以C

rnm

krk

。（Vandermonde恒等式）CmCnk0

rrr1

特例，当m1时，即CnCC1nn。

n

当nmr时，CnkC2nn

k0

2n!。

（人教B选修2-3教材P35T17，此题

n!n!

n

还可以通过考察等式(1x)n(1x)n(1x)2n左右两边含x项的系数相等得到；同样考察(1x)n(1x)m(1x)nm左右两边含x项的系数相等得到Vandermonde恒等式）

1222n2n1推广④：(Cn)2(Cn)n(Cn)nC2n1。

r

r

证明：由C

r

nm

krkkk1，令rmn1结合kCnCmCnnCn1可得。k0

nC

n1

2n1

knk1

nCn1Cn

k0

n1

knk1

nCn1Cnk0n1

k1nk1(k1)CnCnk0n1

n1

(k1)C

k0n

k1

n



kC

k0

kn



得证。

解释：a系{a1,a2,,an}选一个作为主元素，从剩余的2n-1中再选n-1个；再有对于k=1，2,3„„，n从n个a系中选k个，再从中选一主元素，再从n个b系{b1,b2,,bn}中选n-k

knk

个（不做主元素），即kCn。Cn

另一种证明方法：

00nn因为：(1x)nCnCnxCnx，(1

1n001n1)CnCnCn两展开式右

xxxn

1222n2

(Cn)2(Cn)n(Cn)，而

边乘积中的常数项恰好等于

(1x)n(1

1n1n)n(1x)2n，(1x)2n中含xn的系数是C2

n。

xx

krk，当nm时，即是上式。kCmCn

k1m

推广：mC

r1

nm1

rr1

4.rCn（可直接用组合数公式证明）nCn1，r

解释：从n个元素中选出r个元素并把其中之一作为主元素rCn，另一方法，先从n个r1元素中选出一个主元素，再从剩余的n-1个元素中选取r-1个元素nCn1。123n用之可证明人教B版选修2-3P32T6：Cn2Cn3CnnCnn2n1。

0n1（证明一：倒序相加；证明二：从左往右结合2n1Cn1Cn1；证明三：122nn

x1）(1+x)n=C0nCnxCnxCnx两端求导并令123n

Cn2Cn3CnnCnn2n1的推广：

nmk0

mkmnmmnm时，Cn。CmCnk2

解释：考虑从n人中选出m名正式代表及若干名列席代表的选法（列席代表不限人数，可以为0）.m

一方面，先选定正式代表，有Cn种方法，然后从nm个人选列席代表，有2

nm

种方法，共有2

nm

m

种。Cn

另一方面，可以先选出mk人（k0,1,2,,nm），然后再从中选出m名正式代表，其余的k人为列席代表。对于每个k,这样的选法有Cn

mk

m

Cmk种，从而，总选法的种数为

nmk0

C

mknmCmk。从而得证。

rr1rmmrmrr1

另：rCn的推广：，m=1时即为nCnCCCCrCnC1nrnnmnn1。

第三篇：材料巧组合(教学设计)

第十课题：材料巧组合

单元主题：体验版画艺术 课题名称：材料巧组合 教学类别：版画

课时建议：约1～2课时 隐性渗透：

体验版画的艺术魅力，体味巧妙运用材料的乐趣，通过巧妙的设计，制作出有独特的并富有美感的作品。

教学准备学具：收集各种材料、剪刀、糨糊等 教具：各种综合材料、剪刀、胶水、油墨、滚筒等 作业内容：综合版画制作 知识要素：肌理的搭配与组合 技能要求：制版与拓印技巧

教学重点：巧妙的运用不同的材料，创作出独特的作品 教学难点：掌握熟练的制作和印制过程

要注意的问题：粘贴要牢固，否则无法印制。注意画面的节奏感，合理运用构图原理

一、教学目标：

体验与发现：发现生活中的各种材料，感受其肌理效果 创意与表现：通过不同的材料和丰富的想象，组合画面 欣赏与评议：发现他人作品中的巧妙之处

二、作业要求：

基础层面：挖掘各种材料，制作出不同的肌理效果 拓展层面：发挥想象，巧妙运用材料，使造型富有创意 探究层面：印制出独特的富有美感的作品

三、教学环节与指导要点

（一）欣赏与感受：

1．出示次序打乱的版画制作步骤图。2．请学生讨论并整理有序。3．教师小结版画制作步骤。

4．欣赏各种版画，讨论它们的制作材料。5．出示课题。

（二）体验与讨论：

1．出示不同材料，感受他们的不同肌理，激发起制作的愿望。2．小组讨论想象，进行巧妙的构思。确立制作内容。3．讨论、了解制作步骤以及相关要求。①设计草图

②选择材料

③粘贴组合，固定在底版上

④印制完成

（三）想象与实践：

1．创意制作

材料与构思巧妙结合 块面线条组合有节奏变化 印制清晰美观

2．可进行小组合作作业 3．“印版”可以再做修改反复印制

（四）展示与评论：

1．展示作品

2．交流独特的设计思路 3．互评、教师评议

是否产生了各种有趣的肌理效果？

巧妙的构思使其成为了一幅独特的版画。印制清晰，画面效果美观。

四、教学研究

（一）儿童经验

1．学生对版画这一形式不是很熟悉，三年级时有过接触。版画的制作过程较为复杂，所花费的时间也较多。但由于动手操作的部分相当多，所以会产生许多意想不到的效果。

2．运用实物制作版画，会使学生相当感兴趣，它打破了平时课上较为单一的材料应用。一下子可以用这么多平时想也没想到可以用来作画的材料，那是相当激动的。

（二）相关背景

版画是一种以制作为主的作画形式。它种类繁多，效果各异，有很强的装饰性。采用最多的是纸版画、吹塑纸版画、木版画和综合版画。印制时，可以用水粉颜料或者油墨，（三）讨论与探究

1．教学思路（指引）

1）建议课前让学生做些准备工作，收集一些树叶、纱布、粗线、纽扣等材料。

2）版画制作步骤复杂，但工艺简单、易学。在学生已有的基础上只要稍加提示就可以明白。所以导入部分可以通过让学生排列次序，来搞清版画的整个制作过程。

3）综合版画的重点在对材料的巧妙组合上，可以是较为抽象的具有形式美感的作品，也可以是较为巧妙的具象构思作品。所以在制作过程中可以着力于一方面来进行。

4）教学展示时，可以发现巧妙运用的散光点。通过对比可以感受到画面整体布局的协调性和构图原理的合理运用。2．操作技能（提示）

1）构思在本课中显得由为重要，因此操作之前小组的讨论要落到实处，扑捉到每个同学脑中的闪光点。

2）先将实物摆放到适合的位置，如果不理想可以进行修改调整。调整满意后可以进行粘贴固定，要使它有足够的牢固度。

3）印制时，教师可以提供单独的场所，避免和制作时的材料混在一起，造成不必要的麻烦。

（四）教学渗透

1．培养学生的动手能力以及眼、手、脑的协调能力。2．培养学生挖掘生活中的各种材料，运用头脑将其美化。

（五）评价内容参考

1）是否产生了各种有趣的肌理效果？

2）巧妙的构思使其成为了一幅独特的版画。3）印制清晰，画面效果美观。

第四篇：第2课 图画复制巧组合-教案

第2课 图画复制巧组合

【教学目标与要求】 1．知识与技能

(1)学会使用“编辑”菜单中“复制”和“粘贴”命令复制、粘贴图形的方法。

(2)使用“选定”“任意形状的裁剪”工具选定图形和移动图形的方法。(3)掌握图形剪贴、复制的技巧。2．过程与方法

通过对“选定”、“复制”、“粘贴”等命令进行尝试操作，掌握复制、粘贴图形的操作方法和过程，领悟其中的操作技巧，培养学生的自学能力和发现问题、解决问题的能力。3．情感态度与价值观

体验计算机画图的优越性，激发学生学习信息技术的兴趣，渗透环境教育，培养学生对大自然的情感，促进其个性发展。4．行为与创新

增强学生独立思考的能力和协作学习的意识，养成主动探究、勤于实践的学习习惯。

【教学重点与难点】

教学重点：使用“编辑”菜单中“复制”和“粘贴”命令复制、粘贴图形。

教学难点：应用“透明背景”和“不透明背景”。【教学方法与手段】

以学生自主学习、探究学习为主，教师指导评价。【比较区别】

1.“选定”工具和“任意形状的裁剪”工具，“应用不透明背景”和“应用透明背景”；

2.“剪切”和“粘贴”与“复制”和“粘贴”

【教学过程】

1．复习导入，提出任务

复习“多边形”工具的使用，展示“一盘橘子”作品（出示优秀学生作品）。同学们都画得很好，但是画这幅画都花了不少时间，现在老师想画一盘橘子，怎么样能节省时间，减少重复劳动呢？

（引入新的思路，以“节省时间，减少重复劳动”，激发学生学习新知识的兴趣，让学生体会计算机画图的优越性。）要解决这个问题，今天我们就来学习第2课“图画复制巧组合”。

引入课题：第2课 图画复制巧组合

（教学设想：联系前一课的内容，既能复习前一课的内容的知识，又能对前一课的内容做评价展示，同时能过渡到本课画多个盆花怎么办的问题上；既是对上节课任务的总结，又提出了新的任务，同时激发学习学习本课的兴趣。）2．探究学习(1)选定

我们要复制、粘贴首先要选定要复制的对象。请学生对照课本，学习“选定”工具的使用。

小组交流选定方法。展示操作较好的学生。

结合探究屋，小组讨论相互交错的图形怎样选取，并完成讨论卡。

（教学设想：以学生自主学习课本为主要教学方法，既充分利用了课本，又培养学生的自主探究和学习能力，同时提高了教学效果。）(2)复制与粘贴

选定了对象，我们就可以复制了。请学生对照课本上的步骤，学习“编辑”菜单中“复制”和“粘贴”命令的使用。

学生实践：复制与粘贴操作。

小组交流“应用不透明背景”和“应用透明背景”的区别和优劣，完成讨论卡。

(3)合作探究

在编辑菜单中除了“复制”和“粘贴”还有“剪切”命令，它和“粘贴”结合使用，会产生什么结果呢？

学生自主探究“剪切”和“粘贴”与“复制”和“粘贴”有何不同。

完成讨论卡。

（教学设想：结合课本上的6个步骤，学生很容易完成复制花盆的操作，在完成之余，让学生自主探究“应用不透明背景”和“应用透明背景”的区别，以及“剪切”和“粘贴”与“复制”和“粘贴”有何不同，充实和拓展教学内容。）3．展示和总结

展示优秀作品。

利用今天的知识能够提高画图的速度，体现计算机画图的优越性。希望同学们能学习好、利用好今天的知识。

【教学反思】

本课的教学处于画图教学单元的后期教学，要达到本课的教学目标和要求，要注意以下几个问题。

(1)学生的前期知识准备良好，如工具箱工具的使用、填充颜色、菜单栏、拖动操作等。

(2)学生在自主学习和探究的过程中要注意学生学习的差距，教师及时指导。(3)完成讨论卡的填写，深化和拓展本课的知识内容。

第五篇：组合数学论文

生活中的组合数学

摘 要:组合数学在基础理论方面和生活应用方面都发挥着越来越重要的作用, 组合数学不仅在基础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。如果说微积分和近代数学的发展为近代的工业革命奠定了基础，那么组合数学的发展则是奠定了21世纪计算机革命的基础。因此随着计算机科学和其它许多新兴应用学科的发展,组合数学在基础理论方面和生活应用方面都发挥着越来越重要的作用,进而需要我们对其进行更加深层次的研究.关键词:组合数学;鸽巢原理;数学游戏

引言

随着计算机的普及推广,组合数学这门古老的学科焕发出蓬勃的生机.组合数学是一门研究内容丰富、应用广泛的学科,同时它也是一门讲究方法,讲究技巧的学科.组合数学的魅力在于找到巧妙的解法来完善的解决一个组合数学问题,计算机强大的计算能力为寻求组合数学问题的巧妙解法提供了无限的可能,同时组合数学也反过来有效地推动了计算机科学的发展.组合数学在国外已有较快发展,在很多大学已设立组合数学与优化理论专业来培养专门人才.我国对组合数学的研究具有一定的基础,特别是图论研究和区组设计等方面已取得一定的成果.组合数学的发展显然已经改变了传统数学中分析和代数占统治地位的局面,奠定了本世纪的计算机革命的基础.因此需要对其进行更加深入的理论探讨和实践.本文正是基于这种思想,希望借以简单的阐述引起人们对组合数学的更深层次的理解,并能够将其灵活应用于生活中.所以我想通过一些实例和数学史上的一些故事和难题,介绍了组合数学是如何在生活中应用的.在研究了一些典型的例子和趣味性的故事的基础上,系统的查阅了相关文献，并结合生活中涉及组合数学的相关知识进行阐述,具体说明了组合数学的基本方法及其在生活中的应用.这样就使得晦涩的组合数学显得更加形象,也使抽象的理论概念变得浅显具体,更易被初学者理解和接受,以至于可以激发人们在生活中应用组合数学的意识.1.组合数学的基本内容

1.1概念

伴随着计算机科学的高速发展,近年来,组合数学已渐渐成为一门新兴起来的边缘性、综合性学科.关于组合数学到底是什么,数学界有许多种的看法.Richard A.Brualdi在其所著的《Introductory Combinatorics》一书中提到组合数学研究的是事物按照一定的规则安排,其中包括:对已知安排问题的研究，计数性问题,存在性问题.在《Basic Techniques of Combinatorial Theory》中有如此描述: 组合数学即为对已给定描述事物的研究有多少种或者是对某事物发生的途径有多少种.综上所述,组合数学主要研究的就是事物安排中所涉及的有关数学问题1.组合数学是研究任意一组离散性事物按照一定规则安排或配置的数学.特别是当指定的规则较简单时,计算一切可能的安排或配置的方法数,就成为它研究的主要问题.现代组合数学有两个主要特点:其一,它大量应用了抽象代数学工具和矩阵工具促使问题的提法和处理方法表现出极大的普遍性;其二,为了适应计算机科学的发展,它很注重对方法的能行性和程序化问题进行研究.这样,它又派生出算法组合学和组合算法等新的亚分支学科.1.2主要内容

组合数学最早是同数论和概率论交叉在一起的.本世纪五十年代以来,特别是由于计算机科学的巨大发展,促使组合数学成为一支富有生命力的新兴数学分支.与传统的数学课程相比,组合数学研究的主要是一些离散事物之间所存在的某些数学关系,包括计数性问题、存在性问题、最优化问题以及构造性问题等,其内容主要是枚举和计数.组合学中研究最多的主要是计数问题,该问题通常出现在所有的数学分支之中.计算机科学通常需要研究有关算法的内容,就必须估计出算法所需的存储单元和运算量,即分析算法的空间复杂性和时间复杂性2.综上,组合数学主要研究:排列组合、递推关系和生成函数、鸽巢原理和容斥原理、贝恩赛特引理与波利亚定理以及区组设计与编码等等.2.组合数学的基本解题方法

组合数学是离散数学的一个分支,其内容零散,思想方法繁多,对于长期接受

连续性数学学习的我们来说,通常感到很难抓住其要领,无从下手,尤其是对新颖繁多的各种组合方法感到有些茫然.组合数学的方法很多,如加乘法则,抽屉法则,母函数法,逐步淘汰法等等,了解这些方法有助于培养我们学生的组合思维。

3.组合数学在生活中的应用举例

组合数学是十分贴近于人们的生活的，因此组合问题在生活中非常常见。例如，求n个球队参加比赛，每队只和其他队比赛一次的总比赛场数。例如，在纸上画一个网络，用铅笔沿着网络的线路揍，在笔不离开纸面而且不重复线路的条件下，一笔画出网络图。又例如这样一个简单的组合数学问题：一个船夫要把一只狼，一只羊和一棵白菜运过河。而当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个，问人怎样才能把三者都运过河。下面介绍几种组合数学中的著名问题。

1.地图着色为题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？四色定理是一个著名的数学定理。它指出，如果将平面分成一些邻接的区域，那么可以用不多于四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样。另一个通俗的说法是：每个（无飞地的）地图都可以用不多于四种颜色来染色，而且没有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界，而不仅仅是一个公共的交点。例如右图左下角的四色圆盘中，红色部分和绿色部分是邻接的区域，而黄色部分和红色部分则不是临界区域。

尽管四色定理最初提出是和地图染色工作有关，但四色定理本身对地图着色工作并没有特别的意义。据凯尼斯·梅在一篇文章中所言：“（实际中）用四种颜色着色的地图是不多见的，而且这些地图往往最少只需要三种颜色来染色。制图学和地图制图史相关的书籍也没有四色定理的记载。”

一些简单的地图只需要三种颜色就够了，但有时候第四种颜色也是必须的。比如说当一个区域被三个区域包围，而这三个区域又两两相邻时，就得用四种颜色才行了。“是否只用四种颜色就能为所有地图染色”的问题最早是由一位英国制图员在1852年提出的，被称为“四色问题”。人们发现，要证明宽松一点的“五定理”（即“只用五种颜色就能为所有地图染色”）很容易，但四色问题却出人意料地异常困难。曾经有许多人发表了四色问题的证明或反例，但都被证实是错误的。

1977年，数学家凯尼斯·阿佩尔（英语：Kenneth Appl）和沃夫冈·哈肯（英语：Wolfgang Haken）借助电子计算机首次得到了一个完全的证明，四色问题也终于成为了四色定理。这是首个主要由计算机证明的定理。这个证明一开始并不为许多数学家接受，因为不少人认为这个证明无法用人手直接验证。尽管随着计算机的普及，数学界对计算机辅助证明更能接受，但仍有数学家对四色定理的证明存疑。

船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。

中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。

河洛图：我国古代的河洛图上记载了三阶幻方，即把从一到九这九个数按三行三列的队行排列，使得每行，每列，以及两条对角线上的三个数之和都是一十五。组合数学中有许多象幻方这样精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。

装箱问题：当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。

是否存在稳定婚姻的问题：假如能找到两对夫妇（如张（男）--李（女）和赵（男）--王（女）），如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。组合数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然这只是理论上的结论）。这种组合数学的方法却有 一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的 次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。实际上，高考学生的最后录取方案也可以用这种方法。

管理调度问题：我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是组合数学典型例子。又比如，假日饭店的管理中，也严格规定了有关的工序，如清洁工的第一步是换什么，清洗什么，第二步又做什么，总之，他进出房间的次数应该最少。既然，这样一个简单的工作都需要讲究工序，那么一个复杂的工程就更不用说了。

铺地砖问题：我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非方型的砖块来铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题，也涉及到很深的组合数学问题。

组合数学还可用于金融分析：组合数学还可用于金融分析，投资方案的确定，怎样找出好的投资组合以降低投资风险。南开大学组合数学研究中心开发出了“

金沙股市风险分析系统”现已投放市场，为短线投资者提供了有效的风险防范工具。

总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。

3.1 乘法原则与加法原则的应用举例

下面看看组合数学在生活中的实际应用.（以下假设A和B是两类互不关联、互不相同的事件.）组合数学问题在生活中非常常见。例如，求n个球队参加比赛，每队只和其他队比赛一次的总比赛场数。例如，在纸上画一个网络，用铅笔沿着网络的线路揍，在笔不离开纸面而且不重复线路的条件下，一笔画出网络图。又例如这样一个简单的组合数学问题：一个船夫要把一只狼，一只羊和一棵白菜运过河。而当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个，问人怎样才能把三者都运过河。

加法原则可定义为:设事件A有m种选择方式,事件B有n种选择方式,则选A或B共有mn种方式.例如,大于1小于9的的奇数有3个,分别为3,5,7,9;大于1小于9的偶数有4个,分别为2,4,6,8.则大于1小于9的整数有7个,即2,3,4,5,6,7,8.这里事件A为大于1小于9的奇数,事件B为大于1小于9的偶数.而大于1小于9的整数即是属于A或者属于B.乘法原则可以定义为:设事件A有m种选取方式,事件B有n种选取方式,那么选取A以后再选取B共有mn种方式.例如,从3个黑人、5个白人、9个黄种人中各选出1位的方式有359135种方式.而从中共选出一人的方式有35917种方式.下面再用一个实例看看这两个法则是如何应用的.例5 某旅行社开辟了从北京去长白山和天山2条旅游线路,称为北线；从北京去西湖、黄山、峨眉山3条旅游线路,称为南线.问该社共有多少条不同的线路？如某人选定了从北京去四川,先要在西安中转,北京到西安有3种航班可选,西安到四川又有2种航班可选,问共有多少种不同的航班配置方式？

分析

由所学的概率知识可知,互不相容事件A1、A2,则其和的概率等于各自

概率之和,即P(A1A2)PA1PA2;同理,二个独立事件同时发生的概率PA1A2PA1PA2.解

由加法原理可知,该社共有的线路条数P1235条.由乘法原理可知,共有的航班配置方式P2326种.3.2 Ramsey定理的应用举例

首先是抽屉原理,大家也许早就听说过这样的智力问题“:从10双鞋子中随便拿几只能保证有一双相配的鞋?”答案显然是至少3只.大家不难根据同样的原理编造出许多新问题.这个原理本身可以很形象的表述为:“把多于n个东西任意放进n个抽屉,那么一定有一个抽屉放进了不止一个东西”.因为19世纪德国数学家狄利克雷曾用这个原理证明过数学命题,所以把它叫做狄氏抽屉原理,或简称抽屉原理.它虽然简单,但利用它可以证明不少并不简单的结论.其次是鸽巢原理.鸽巢原理是组合数学中最简单最基本的原理,和抽屉原理其实是异曲同工.鸽巢原理可简单的描述为:“若有n个鸽巢,而鸽子多余n只,若每只鸽子必须进巢,则至少有一个鸽巢内的鸽子多于一只.”

下面简要举一个用鸽巢原理解决实际问题的例子.例6

一间屋内有10个人,他们当中没有人超过60岁（年龄只以整数给出）但又至少不低于1岁.试证明:总能找出两组人（两组不含相同的人）,各组的年龄和是相同的.解

设Yy1,y2,,y10为屋内10个人的年龄构成的集合,集合Y的所有k个

121010kC10C1021种,不同元素之和共有C10,则所有可能的不同元素之和有C10记这些和为Ss1,s2,,s1023,由题设条件可知:

1si60,i1,2,,1023.因此,由鸽巢原理原理可知S中至少有两个元素是相同的,设为sisj.如果年龄和si和sj的人中有相同的人,则把这些相同的人去掉,即为要找的两组年龄和相同的人.最后就是集会问题.这也是一个广为流传的趣味数学问题:“证明在至少有6个人参加的集会上,与会者中或者有3个人以前互相认识,或者有3个人以前彼此都不认识.”因为6人集会中成员间的情况共有21532728种.下面就针对这个问题给予简单证明.例77

试证明6个人中一定有3个人相互认识或相互不认识.证明

先考虑6个人中的任意一个人,不妨把这个人称作p.则其他的5个人可以分为下面的两个集合F和S.其中F表示与p相识的人的集合,S表示与p不相识的人的集合.由鸽巢原理知,这两个集合中至少有一个集合包含有3个人.若F包含有3个人,则这3个人或者彼此不相识,或者有两个人彼此相识.如果F中有3个人彼此不相识,则结论成立.如果F中有2人相识,则由于这两个人都与p相识,因此有3人彼此相识,故定理结论成立.类似的,如果S包含3个人,则这3个人或者彼此相识,或者有两个人彼此不相识.如果这3个人彼此相识,则结论成立.如果有两个人彼此不相识,则由于这两个人都与p也不相识,因此有3个人彼此不相识,故定理结论成立.3.3 线性规划法的应用实例

线性规划是最简单,应用最广泛的一种数学规划方法,也是使用最早的一种 优化方法.在组合数学中,线性规划问题可以归结为一类条件极值问题.例8 某电视机厂有100台彩电的订单要在三周内交货,在第一,第一和第三周生产x台彩电的费用分别是120x,1.2x2,1.5x2.求每周生产彩电的数目的最优策略.解

假设xii1,2,3表示在第i周生产的彩电数,fixi表示第i周生产xi台彩电的费用,则此问题的数学模型为

min yf1x1f2x2f3x3120x11.2x221.5x32，s.t.x1x2x3100，xi0,i1,2,3.假设Fkx表示在前k周生产x台彩电所得到的最小费用,则由最优原理可得出如下的递归方程

F1xf1x，Fkxmin0xkxfkxkFk1xxk,k0x100.2,3, 原问题的解就是F.（100）3由上式可知

F1xf1x=120x，F2xmin0x2xf2x2F1xx2, f3x3Fxx3.F3xmin0x3x解上面的递归方程,可得当x110,x250,x340时有最小值

F31006600.即第一周生产10台彩电,第二周生产50台彩电,第三周生产40台彩电,可获得最小费用6600.3.4 游戏中的组合数学 3.4.1哥尼斯堡七桥问题

18世纪初在东普鲁土有这样一个问题:某条河上有两个岛屿,城市中的四部分可以由七个桥来连接起来．那么可否经过每个桥并且每个桥只能走一次？（如图1上图所示）．

图1 在18世纪中期,欧拉成功论证了该问题,也即是合适的方案并没有,不可能每座桥走过且仅走过一次．欧拉把该实际问题形象地简化成同一平面上线与点的组合问题,将每一座桥看成一条线,每座桥所连接的地方看作点.因此,从某一点出发再回

到这一点的问题,可转化成一个一笔画的问题8.欧拉采用概念映像法来解决该类问题,亦即抽象分析法.将七桥问题中的桥与陆地之间的关系结构用S表示,用x表示一次可否同时走过此七座桥的问题.欧拉使用了一种方法,即用概念映像将桥视为几何线,将连接的地点视为几何点,则在映像下可得到(S;x)→(Sn;xn).如此,Sn则可表示如图1下图的点线图.之前的问题x便对应变成能否一笔画出如图1下图所示的平面图问题xn.也即xn就是关于上述点线图的一笔画问题.欧拉的这种方法就是组合数学中后来的关系映像反演方法的最早体现．

3.4.2“三同六变”的问题

中国的王文紊在其所著的《算学宝鉴》一书中详细记载了一个名为“三同六变”的题目:

“假令二十四老人,长者寿高一百,次者递减一岁,止于七十七．共积总寿二千一百二十有四．卜(疑为‘赴’)会三社,八老相会,七百八岁,盖因人情逸顺,散而复会,共换六次,其积(即和)仍均七百有八,屯(疑为‘求’)见连用之道．”8

它的意思也即是说:有24位老人,每8人一起,分三处赴会,每处年龄之和均为708岁,并且年龄从100岁到77岁,依次递减1岁．那么如何分配,分配方法有多少种?

在该书当中共列出了6种解答,并且作了注释,“其变尤多,不及备述”．

对这个问题加以推广,便可得到一类 “n同k聚”的问题:在自然数集合N内,任意选取nk(k=2,3,4, „)个连续自然数作为集合M,将M任意划分为n个互不相交子集M1,M2,M3,,Mn,而每个子集均有k个元素,并且各个子集元素之和相等,求M1,M2,M3,,Mn．这个问题为中国传统数学中的浑圆图给出了另一解释.结束语

这篇论文只是介绍了组合数学在生活中的应用的一小部分,希望借此论文可以激起我们对组合数学的关注,学会在生活中运用组合数学来解决具体的问题.组合数学这个富有生命力的数学分支,涉及生活中的各个领域, 作为计算机专业的学生，我们必须把组合数学的学习放在一个重要的位置上来，掌握基本的组合数学原理，培养专业的数学思维，这样才能在以后的工作学习中掌握主动和先机。才能在将来为中国的计算机软件事业做出自己的贡献。

参考资料

百度知道：http://zhidao.baidu.com 百度百科：http://baike.baidu.com/view/44868.htm http://zhidao.baidu.com/question/33561976.html 百度文库；http://wenku.baidu.com/view/b7d3f019f18583d0496459e9.html http://wenku.baidu.com/view/41879a15cc7931b764ce1507.html http://wenku.baidu.com/view/d0bc7b1dc281e53a5802ffeb.html http://wenku.baidu.com/view/a42acc270722192e4536f63b.html http://wenku.baidu.com/view/9bacf1f9f705cc1755270986.html http://wenku.baidu.com/view/33e0ad3143323968011c9213.html 维基百科：http://zh.wikipedia.org/wiki/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6