论文部分内容阅读
摘 要： 本文引入了排列组合中的一些典型例题，通过分析其一题多解思想方法，加深了对
组合数学中的一些重要原理的理解，开拓了我们的解题思路，增强了我们的解题能力。
关键词： 排列；组合；一题多解
【中图分类号】G620
一、引言
1.何谓组合数学？
组合数学，为离散数学的一个重要分支，主要研究某组离散对象满足一定条件的安排（或组态）的存在性、构造、计数及优化计算等问题，是一门研究安排问题的学科。中学数学里学习的排列、组合问题及其推广——重复排列和重复组合问题、分派问题、染色问题、中国邮路问题等都是安排问题的例子。组合数学是计算机出现以后迅速发展起来的一门数学分支，为本世纪计算机革命奠定了坚实的基础，推动了软件技术和信息技术快速发展。组合数学不仅在软件、信息技术中有重要的应用价值，在企业管理、交通规划、战争指挥、金融分析等领域都有重要的应用。组合数学无论在应用上和理论上都具有越来越重要的位置，在应用科学项目有更广阔的发展前景，为我国的社会主义建设事业做出更大的贡献。
2.一题多解思想及其在数学学习中的重要性
所谓一题多解，主要体现在解题时没有唯一的固定模式，而是以其多样化答案为明显的特征，可以通过纵横发散，知识串联，综合沟通，达到举一反三，融会贯通的目的。一题多解是培养学生发散思维的好方法，对于一道题从问题的不同角度出发，根据所给的条件，突破固有的解题思想和思维定势，去寻求不同的解题方法，以此达到预期的效果。
一题多解思想是一重要的数学思想，它对数学思维的训练起着重要作用。数学思想方法是数学的精髓，是知识转化为能力的桥梁，具有普遍的应用意义。在分析和解决问题时，它能指导我们探索揭示问题的本质，抓住解决问题的关键，进一步开拓我们的解题思路。通过一题多解能培养思维的发散性、灵活性、敏捷性；对题目的灵活变通，引申推广，培养思维的深刻性、抽象性；对题目解法的简捷性的反思评估，不断优化思想品质，培养思维的严谨性、批判性。对同一数学问题多角度审视引发的不同联想，是一题多解的思想本源，丰富的合理的联想，是对知识的深刻理解、类比、转化、数形结合、函数及方程等数学思想的灵活运用。数学思想方法的运用往往使我们运算简捷明白，推理机敏，是提高数学能力的必由之路。素质教育的核心问题是能力的培养，其中思维能力的训练培养是教与学的主要方面，利用一题多解更好地训练我们的发散思维、创造思维、灵感思维、逆向思维等。
二、排列组合中一题多解例题解析
设某二年制学校已有连续八届毕业生。现欲从毕业生中选出三名代表参加校友会，要求三名代表互不认识（假如相邻的两届毕业生相互认识），问有多少种选法？
（1）方法一：穷举法（分类穷举）
含1：{1，3，5}{1，3，6}{1，3，7}{1，3，8}{1，4，6}
{1，4，7}{1，4，8}[1，5，7]{1，5，8}{1，6，8}
不含1：{2，4，6}{2，4，7}{2，4，8}{2，5，7}{2，5，8}{2，6，8}
不含1，2：{3，5，7}{3，5，8}{3，6，8}
不含1，2，3：{4，6，8}
故共有20种选法。
穷举法讲求技巧，避免重复列举。穷举法是排列组合中常用的一种解题方法，尤其是对于计算复杂度不大的计数。
（2）方法二：用不相邻组合公式求解。
不相邻组合：从个元素中取出r个而不考虑它的顺序，称为从n中取r个组合，其组合数为Cnr。而不相邻组合指的是从序列A={1，2，3 ，…，n}中取r个，其中不存在i，i+1两个相邻的数同时出现于一个组合中的组合，其计数公式组合数为Cn-r+1r。
解：在图论中我们学习了一种特殊的简单图：路pn。若用1，2，3，…，8来表示8届毕业生，相互认识的两届毕业生用线相连，可得如下图：
p8：——————————————
故问题就转化为求p8的有三个顶点的独立集的个数。
求路pn中由r个点组成的独立集的个数，问题实际上是从{1，2，3，...，n}中取r个不相邻的组合问题，此时n=8，r=3，则所求独立集的个数为：
N=
（3）方法三：插入法
考虑从{1，2，3，…8}中选出3个数不相邻的，则可以转化为从8-3个位置的中间插入3个数。若这5个位置用“○”作标记，可插入的位置用“*”标记，则
* ○ * ○ * ○ * ○ * ○ *
即任意“*”位置选3个形成的组合都是不相邻的，共有C63=20种。
（4）方法四：可以用筛法（容斥原理）
2.容斥原理：容斥原理也称为逐步淘汰原理，是计数的一种基本方法，是组合数学中的重要原理。容斥原理的基本原理如下：
定理：设具有性质p1、p2的S中元素的集合为A1、A2，则S中性质p1、p2都不具备的元素个数是 |∣=∣S|-（|A1|+|A2|）+|A1∩A2|
本题求不相邻组合数，只需考虑在C83的所有组合中筛掉有相邻的组合，即去掉其中存在i，i+1两个相邻的数同时出现在一个组合中的组合。
设对已经选好的组合进行从小到大排序，记a b c，设p1表示a=b-1这个性质，即a，b相邻其数集为A1，设p2表示b=c-1这个性质，具有p2的数集为A2，利用容斥原理得：
|∣= C83-（|A1|+|A2|）+|A1∩A2|
|A1|表示 { i，i+1，c} ，c>i+1 ，则| A1|=
| A2|表示{a，i，i+1}，a |A1·A2|表示a，b，c三者都相邻数集即为：{1，2，3}，{2，3，4}，{3，4，5}，{4，5，6}，{5，6，7}，{6，7，8}
故||=C83-21×2+6=20.
不相邻计数=||=C83-21×2+6=20
综合上面四种方法各有优劣之处，技巧性也很强，但对于一题多解开阔思路都大有益处。穷举虽然显得笨拙但是在大多数排列组合解题中都是行之有效的，这往往局限于运算复杂度不太大的情况下。插入排序这是一种很常见的题型，在计算机相关知识的一些算法中常用到，而且简易明了。不相邻组合看起来有些陌生，它在实际问题中比比皆是，只是我们运用得少些而已，而且这个知识点也很重要。然而容斥原理在数学解题中及许多实际问题中是重要的法宝，一个问题不好从正面入手，不妨从反面想想，养成逆向思考问题的习惯。灵活运用所学知识解题，从多方位剖析解题思路优化解题步骤可以达到培养数学思想的目的。
三、结论
一题多解是训练思维的好素材，通过一题多解，引导我们就多角度，多方位，多观点分析思考问题，从而扩充思维，不仅局限于固有的方法，力求标新立异，谋求创新；多样化的题型和解题方法，引导我们参与问题要有不同的广度和深度，通过一题多解促使我努力寻求不同的求解方法及其共同的本质，以及思考方式的共性，这最终上升到多解归一，多题归一的高度，使我们更好地掌握数学思想和方法；教育必须注重对学生素质的全面发展，数学教师在教学过程中重点应放在对学生思维和能力的培养和训练，通过一题多解，增强学生的分析、综合、推理、应用能力等，充分发挥各方面的积极主动性，提高教学效益，更好的培养学生综合运用知识的能力。
参考文献
[1]刁在筠，郑汉鼎.运筹学.北京：高等教育出版社，1996
[2]卢开澄.组合数学（计算机科学组合学丛书）.北京：清华大学出版社，1991
[3]彭波.数据结构教程.北京：清华大学出版社，2004
[4]叶上雄.中学教育学.北京：高等教育出版社，2005
[5]欧阳绛.思维的技巧.北京：当代中国出版社，2002
组合数学中的一些重要原理的理解，开拓了我们的解题思路，增强了我们的解题能力。
关键词： 排列；组合；一题多解
【中图分类号】G620
一、引言
1.何谓组合数学？
组合数学，为离散数学的一个重要分支，主要研究某组离散对象满足一定条件的安排（或组态）的存在性、构造、计数及优化计算等问题，是一门研究安排问题的学科。中学数学里学习的排列、组合问题及其推广——重复排列和重复组合问题、分派问题、染色问题、中国邮路问题等都是安排问题的例子。组合数学是计算机出现以后迅速发展起来的一门数学分支，为本世纪计算机革命奠定了坚实的基础，推动了软件技术和信息技术快速发展。组合数学不仅在软件、信息技术中有重要的应用价值，在企业管理、交通规划、战争指挥、金融分析等领域都有重要的应用。组合数学无论在应用上和理论上都具有越来越重要的位置，在应用科学项目有更广阔的发展前景，为我国的社会主义建设事业做出更大的贡献。
2.一题多解思想及其在数学学习中的重要性
所谓一题多解，主要体现在解题时没有唯一的固定模式，而是以其多样化答案为明显的特征，可以通过纵横发散，知识串联，综合沟通，达到举一反三，融会贯通的目的。一题多解是培养学生发散思维的好方法，对于一道题从问题的不同角度出发，根据所给的条件，突破固有的解题思想和思维定势，去寻求不同的解题方法，以此达到预期的效果。
一题多解思想是一重要的数学思想，它对数学思维的训练起着重要作用。数学思想方法是数学的精髓，是知识转化为能力的桥梁，具有普遍的应用意义。在分析和解决问题时，它能指导我们探索揭示问题的本质，抓住解决问题的关键，进一步开拓我们的解题思路。通过一题多解能培养思维的发散性、灵活性、敏捷性；对题目的灵活变通，引申推广，培养思维的深刻性、抽象性；对题目解法的简捷性的反思评估，不断优化思想品质，培养思维的严谨性、批判性。对同一数学问题多角度审视引发的不同联想，是一题多解的思想本源，丰富的合理的联想，是对知识的深刻理解、类比、转化、数形结合、函数及方程等数学思想的灵活运用。数学思想方法的运用往往使我们运算简捷明白，推理机敏，是提高数学能力的必由之路。素质教育的核心问题是能力的培养，其中思维能力的训练培养是教与学的主要方面，利用一题多解更好地训练我们的发散思维、创造思维、灵感思维、逆向思维等。
二、排列组合中一题多解例题解析
设某二年制学校已有连续八届毕业生。现欲从毕业生中选出三名代表参加校友会，要求三名代表互不认识（假如相邻的两届毕业生相互认识），问有多少种选法？
（1）方法一：穷举法（分类穷举）
含1：{1，3，5}{1，3，6}{1，3，7}{1，3，8}{1，4，6}
{1，4，7}{1，4，8}[1，5，7]{1，5，8}{1，6，8}
不含1：{2，4，6}{2，4，7}{2，4，8}{2，5，7}{2，5，8}{2，6，8}
不含1，2：{3，5，7}{3，5，8}{3，6，8}
不含1，2，3：{4，6，8}
故共有20种选法。
穷举法讲求技巧，避免重复列举。穷举法是排列组合中常用的一种解题方法，尤其是对于计算复杂度不大的计数。
（2）方法二：用不相邻组合公式求解。
不相邻组合：从个元素中取出r个而不考虑它的顺序，称为从n中取r个组合，其组合数为Cnr。而不相邻组合指的是从序列A={1，2，3 ，…，n}中取r个，其中不存在i，i+1两个相邻的数同时出现于一个组合中的组合，其计数公式组合数为Cn-r+1r。
解：在图论中我们学习了一种特殊的简单图：路pn。若用1，2，3，…，8来表示8届毕业生，相互认识的两届毕业生用线相连，可得如下图：
p8：——————————————
故问题就转化为求p8的有三个顶点的独立集的个数。
求路pn中由r个点组成的独立集的个数，问题实际上是从{1，2，3，...，n}中取r个不相邻的组合问题，此时n=8，r=3，则所求独立集的个数为：
N=
（3）方法三：插入法
考虑从{1，2，3，…8}中选出3个数不相邻的，则可以转化为从8-3个位置的中间插入3个数。若这5个位置用“○”作标记，可插入的位置用“*”标记，则
* ○ * ○ * ○ * ○ * ○ *
即任意“*”位置选3个形成的组合都是不相邻的，共有C63=20种。
（4）方法四：可以用筛法（容斥原理）
2.容斥原理：容斥原理也称为逐步淘汰原理，是计数的一种基本方法，是组合数学中的重要原理。容斥原理的基本原理如下：
定理：设具有性质p1、p2的S中元素的集合为A1、A2，则S中性质p1、p2都不具备的元素个数是 |∣=∣S|-（|A1|+|A2|）+|A1∩A2|
本题求不相邻组合数，只需考虑在C83的所有组合中筛掉有相邻的组合，即去掉其中存在i，i+1两个相邻的数同时出现在一个组合中的组合。
设对已经选好的组合进行从小到大排序，记a b c，设p1表示a=b-1这个性质，即a，b相邻其数集为A1，设p2表示b=c-1这个性质，具有p2的数集为A2，利用容斥原理得：
|∣= C83-（|A1|+|A2|）+|A1∩A2|
|A1|表示 { i，i+1，c} ，c>i+1 ，则| A1|=
| A2|表示{a，i，i+1}，a
故||=C83-21×2+6=20.
不相邻计数=||=C83-21×2+6=20
综合上面四种方法各有优劣之处，技巧性也很强，但对于一题多解开阔思路都大有益处。穷举虽然显得笨拙但是在大多数排列组合解题中都是行之有效的，这往往局限于运算复杂度不太大的情况下。插入排序这是一种很常见的题型，在计算机相关知识的一些算法中常用到，而且简易明了。不相邻组合看起来有些陌生，它在实际问题中比比皆是，只是我们运用得少些而已，而且这个知识点也很重要。然而容斥原理在数学解题中及许多实际问题中是重要的法宝，一个问题不好从正面入手，不妨从反面想想，养成逆向思考问题的习惯。灵活运用所学知识解题，从多方位剖析解题思路优化解题步骤可以达到培养数学思想的目的。
三、结论
一题多解是训练思维的好素材，通过一题多解，引导我们就多角度，多方位，多观点分析思考问题，从而扩充思维，不仅局限于固有的方法，力求标新立异，谋求创新；多样化的题型和解题方法，引导我们参与问题要有不同的广度和深度，通过一题多解促使我努力寻求不同的求解方法及其共同的本质，以及思考方式的共性，这最终上升到多解归一，多题归一的高度，使我们更好地掌握数学思想和方法；教育必须注重对学生素质的全面发展，数学教师在教学过程中重点应放在对学生思维和能力的培养和训练，通过一题多解，增强学生的分析、综合、推理、应用能力等，充分发挥各方面的积极主动性，提高教学效益，更好的培养学生综合运用知识的能力。
参考文献
[1]刁在筠，郑汉鼎.运筹学.北京：高等教育出版社，1996
[2]卢开澄.组合数学（计算机科学组合学丛书）.北京：清华大学出版社，1991
[3]彭波.数据结构教程.北京：清华大学出版社，2004
[4]叶上雄.中学教育学.北京：高等教育出版社，2005
[5]欧阳绛.思维的技巧.北京：当代中国出版社，2002