组合数学基础
- 格式：doc
- 大小：368.00 KB
- 文档页数：23
边界条件：f(0,0)=1;
如果有马，则需要标记那些点被马控制，所以需要设置一个二维数组horse[x][y]，表示棋盘，将马控制点标记，在计算到标记点的时候，将气方法数直接记为0。
程序，请自行完成。
(4)
◆分类时用加法原理，分步时用乘法原理。
◆分类时要求各类办法彼此之间相互排斥；分步时要求各步是相互独立的。
解法二：从六个元素中先取出一个元素作为一个组有 种选法，再从余下的五个元素中取出一个元素作为一个组有 种选法，最后余下的四个元素自然作为一个组，由于第一步和第二步各选取出一个元素分别作为一个组有先后之分，产生了重复计算，应除以
所以共有 ＝15种不同的分组方法
第二类（１－２－３）分法，这是一类整体和局部均不等分的问题，首先从六个不同的元素中选取出一个元素作为一个组有 种不同的选法，再从余下的五个不同元素中选取出两个不同的元素作为一个组有 种不同的选法，余下的最后三个元素自然作为一个组，根据乘法原理共有 ＝60种不同的分组方法
第1类办法是从3本不同数学书中任取1本，有3种方法；
第2类办法是从5本不同的语文书中任取1本，有5种方法；
第3类办法是从6本不同的英语书中任取一本，有6种方法。
根据加法原理，得到的取法种数是：N＝m1＋m2＋m3＝3＋5＋6＝14。
(2)从书架上任取数学书、语文书、英语书各1本，需要分成三个步骤完成：
计算公式：＝＝＝
组合恒等式：
①
②
③
④
⑤
3.高中数学知识补充：
n个人围着一张圆桌坐在一起，共有(n－1)!种坐法。
把r个相同的球放到n个不同颜色的盒子中去，共有种方法。
从n个排成一排的数中取m个数，且数字之间互不相邻，共有种取法。
Catalan数列，其数列为1，2，5，14，42，132，429……，通项公式为hn＝。
◆
(5)
1．在所有的两位数中，个位数字小于十位数字的共有多少个？
2．某学生填报高考志愿，有m个不同的志愿可供选择，若只能按第一、二、三志愿依次填写3个不同的志愿，求该生填写志愿的方式的种数．
3．在所有的三位数中，有且只有两个数字相同的三位数共有多少个？
4．某小组有10人，每人至少会英语和日语中的一门，其中8人会英语，5人会日语：
第十单元 组合数学基础
10.1
(
计算机科学与数学密不可分。组合数学在信息学竞赛运用广泛，特别大多数的搜索类问题，动态规划类问题（运筹学）、递推计数类问题，都可以归结到组合数学的应用问题。组合数学是以两个计数原理为基础的。
1)加法原理
【问题1】从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船．一天中，火车有4个班次，汽车有2个班次，轮船有3个班次．那么一天中乘坐这些交通工具从甲地到乙地，共有多少种不同的走法？
第三步将第二步“捆绑”的这个整体“插入”到第一步所排的四个不同数字的五个“间隙”(包括两端的两个位置)中的其中一个位置上,有 种不同的“插入”方法
根据乘法原理共有 ＝720种不同的排法 所以共有720个符合条件的七位数
解（2）：因为三个偶数２、４、６互不相邻，所以要得到符合条件的七位数可以分为如下两步：
它们的区别是：一个与分类有关，一个与分步有关。
(2)
【问题1】找1～10这10个数中的所有合数。
【解答】第1类办法是找含因数2的合数，共有4个；
第2类办法是找含因数3的合数，共有2个；
第3类办法是找含因数5的合数，共有1个，
所以，1～10中一共有N=4＋2＋1=7个合数。
【问题2】在前面的问题2中，步行从A村到B村的北路需要8时，中路需要4时，南路需要6时，B村到C村的北路需要5时，南路需要3时，要求步行从A村到C村的总时数不超过12时，共有多少种不同的走法？
二、解题思路：
解排列组合问题，首先要弄清一件事是“分类”还是“分步”完成，对于元素之间的关系，还要考虑“是有序”的还是“无序的”，也就是会正确使用分类计数原理和分步计数原理、排列定义和组合定义，其次，对一些复杂的带有附加条件的问题，需掌握以下几种常用的解题方法：
特殊优先法 对于存在特殊元素或者特殊位置的排列组合问题，我们可以从这些特殊的东西入手，先解决特殊元素或特殊位置，再去解决其它元素或位置，这种解法叫做特殊优先法.例如：用0、1、2、3、4这5个数字，组成没有重复数字的三位数，其中偶数共有________个.（答案：30个）
【分析】因为一天中乘火车有4种走法，乘汽车有2种走法，乘轮船有3种走法，每种走法都可以完成由甲地到乙地这件事情．所以，一天中乘坐这些交通工具从甲地到乙地共有4+2+3=9种不同的走法。解答树如下:
【总结】将这类型的问题总结为一个基本原理——加法原理：做一件事，完成它可以有几类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，…，在第n类办法中有mn种不同的方法．那么，完成这件事共有N=m1+m2+…+mn种不同的方法。
第1步取1本数学书，有3种方法；
第2步取1本语文书，有5种方法；
第3步取1本英语书，有6种方法．
根据乘法原理，得到不同的取法种数是N=m1×m2×m3=3×5×6=90．
(3)从书架上任取不同科目的书两本，可以有3类办法：
第1类办法是数学书、语文书各取1本，需要分两个步骤，有3×5种方法；
第2类办法是数学书、英语书各取1本，需要分两个步骤，有3×6种方法；
【总结】进行分类时，要求各类办法彼此之间是相互排斥的，不论哪一类办法中的哪一种方法，都能单独完成这件事。只有满足这个条件，才能直接用加法原理，否则不可以。
如果完成一件事需要分成几个步骤，各步骤都不可缺少，需要依次完成所有步骤才能完成这件事，而各步要求相互独立，即相对于前一步的每一种方法，下一步都有m种不同的方法，那么计算完成这件事的方法数时，就可以直接应用乘法原理。
计算公式：＝n(n－1)(n－2)……(n－m＋1)＝
以前排列会记为P。下面一些例题是P的表明也是排列。
2.组合
概念：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。
组合数：从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数，用符号表示。
解答树如下：
2)、乘法原理
【问题2】由A村去B村的道路有3条，由B村去C村的道路有2条（见图9－1），从A村经B村去C村，共有多少种不同的走法？
【分析】从A村到B村，有3种不同的走法，按这3种走法中的每一种走法到达B村后，再从B村到C村又各有2种不同的走法，因此，从A村经B村去C村共有3×2=6种不同的走法。解答树如下：
【总结】将着类型的问题总结为一个基本原理——乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，…，做第n步有mn种不同的方法．那么，完成这件事共有N＝m1×m2×…×mn种不同的方法．
解答树如下：
3)加法原理和乘法原理的浅释
它们的作用是：是用于计算完成一件事的所有不同的方法种数。
三、讲解范例：
例1由数字１、２、３、４、５、６、７组成无重复数字的七位数
(1）求三个偶数必相邻的七位数的个数；（2）求三个偶数互不相邻的七位数的个数
解(1)：因为三个偶数２、４、６必须相邻，所以要得到一个符合条件的七位数可以分为如下三步：
第一步将１、３、５、７四个数字排好有 种不同的排法；
第二步将２、４、６三个数字“捆绑”在一起）(1<=n,m<=20)，同样马的位置坐标是需要给出的（约定: C<>A，同时C<>B）。现在要求你计算出卒从A点能够到达B点的路径的条数。
【输入】B点的坐标（n,m）以及对方马的坐标(X,Y)
【输出】一个整数（路径的条数）。
【样例】
single.in
single.out
也就是说：类类互斥，步步独立。
(3)
例1：书架上放有3本不同的数学书，5本不同的语文书，6本不同的英语书．
（1）若从这些书中任取一本，有多少种不同的取法？
（2）若从这些书中，取数学书、语文书、英语书各一本，有多少种不同的取法？
（3）若从这些书中取不同的科目的书两本，有多少种不同的取法？
【分析】
(1)从书架上任取一本书，可以有3类办法：
6 6 3 2
17
【分析】
在不考虑有马的棋盘中:
设函数f(x,y)=从出发点(0,0)走到(x,y)的路径条数。则走到(x,y)的方法有两类：
第1类是从上边点(x-1,y)走下来，这类的方法数为：f(x-1,y)
第2类是从左边点(x,y-1)走过来，这类的方法数为：f(x,y-1)
根据加法原理有，f(x,y)=f(x-1,y)+f(x,y-1)
（1）从中任选一个会外语的人，有多少种选法？
（2）从中选出会英语与会日语的各1人，有多少种不同的选法？
10.
(
1.排列
概念：从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。
排列数：从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号表示。
科学分类法 对于较复杂的排列组合问题，由于情况繁多，因此要对各种不同情况，进行科学分类，以便有条不紊地进行解答，避免重复或遗漏现象发生 例如：从6台原装计算机和5台组装计算机中任取5台，其中至少有原装与组装计算机各两台，则不同的选取法有_______种.（答案：350）
插空法 解决一些不相邻问题时，可以先排一些元素然后插入其余元素，使问题得以解决 例如：7人站成一行，如果甲乙两人不相邻，则不同排法种数是______.(答案:3600)
捆绑法 相邻元素的排列，可以采用“整体到局部”的排法，即将相邻的元素当成“一个”元素进行排列，然后再局部排列 例如：6名同学坐成一排，其中甲、乙必须坐在一起的不同坐法是________种.（答案：240）
如果有马，则需要标记那些点被马控制，所以需要设置一个二维数组horse[x][y]，表示棋盘，将马控制点标记，在计算到标记点的时候，将气方法数直接记为0。
程序，请自行完成。
(4)
◆分类时用加法原理，分步时用乘法原理。
◆分类时要求各类办法彼此之间相互排斥；分步时要求各步是相互独立的。
解法二：从六个元素中先取出一个元素作为一个组有 种选法，再从余下的五个元素中取出一个元素作为一个组有 种选法，最后余下的四个元素自然作为一个组，由于第一步和第二步各选取出一个元素分别作为一个组有先后之分，产生了重复计算，应除以
所以共有 ＝15种不同的分组方法
第二类（１－２－３）分法，这是一类整体和局部均不等分的问题，首先从六个不同的元素中选取出一个元素作为一个组有 种不同的选法，再从余下的五个不同元素中选取出两个不同的元素作为一个组有 种不同的选法，余下的最后三个元素自然作为一个组，根据乘法原理共有 ＝60种不同的分组方法
第1类办法是从3本不同数学书中任取1本，有3种方法；
第2类办法是从5本不同的语文书中任取1本，有5种方法；
第3类办法是从6本不同的英语书中任取一本，有6种方法。
根据加法原理，得到的取法种数是：N＝m1＋m2＋m3＝3＋5＋6＝14。
(2)从书架上任取数学书、语文书、英语书各1本，需要分成三个步骤完成：
计算公式：＝＝＝
组合恒等式：
①
②
③
④
⑤
3.高中数学知识补充：
n个人围着一张圆桌坐在一起，共有(n－1)!种坐法。
把r个相同的球放到n个不同颜色的盒子中去，共有种方法。
从n个排成一排的数中取m个数，且数字之间互不相邻，共有种取法。
Catalan数列，其数列为1，2，5，14，42，132，429……，通项公式为hn＝。
◆
(5)
1．在所有的两位数中，个位数字小于十位数字的共有多少个？
2．某学生填报高考志愿，有m个不同的志愿可供选择，若只能按第一、二、三志愿依次填写3个不同的志愿，求该生填写志愿的方式的种数．
3．在所有的三位数中，有且只有两个数字相同的三位数共有多少个？
4．某小组有10人，每人至少会英语和日语中的一门，其中8人会英语，5人会日语：
第十单元 组合数学基础
10.1
(
计算机科学与数学密不可分。组合数学在信息学竞赛运用广泛，特别大多数的搜索类问题，动态规划类问题（运筹学）、递推计数类问题，都可以归结到组合数学的应用问题。组合数学是以两个计数原理为基础的。
1)加法原理
【问题1】从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船．一天中，火车有4个班次，汽车有2个班次，轮船有3个班次．那么一天中乘坐这些交通工具从甲地到乙地，共有多少种不同的走法？
第三步将第二步“捆绑”的这个整体“插入”到第一步所排的四个不同数字的五个“间隙”(包括两端的两个位置)中的其中一个位置上,有 种不同的“插入”方法
根据乘法原理共有 ＝720种不同的排法 所以共有720个符合条件的七位数
解（2）：因为三个偶数２、４、６互不相邻，所以要得到符合条件的七位数可以分为如下两步：
它们的区别是：一个与分类有关，一个与分步有关。
(2)
【问题1】找1～10这10个数中的所有合数。
【解答】第1类办法是找含因数2的合数，共有4个；
第2类办法是找含因数3的合数，共有2个；
第3类办法是找含因数5的合数，共有1个，
所以，1～10中一共有N=4＋2＋1=7个合数。
【问题2】在前面的问题2中，步行从A村到B村的北路需要8时，中路需要4时，南路需要6时，B村到C村的北路需要5时，南路需要3时，要求步行从A村到C村的总时数不超过12时，共有多少种不同的走法？
二、解题思路：
解排列组合问题，首先要弄清一件事是“分类”还是“分步”完成，对于元素之间的关系，还要考虑“是有序”的还是“无序的”，也就是会正确使用分类计数原理和分步计数原理、排列定义和组合定义，其次，对一些复杂的带有附加条件的问题，需掌握以下几种常用的解题方法：
特殊优先法 对于存在特殊元素或者特殊位置的排列组合问题，我们可以从这些特殊的东西入手，先解决特殊元素或特殊位置，再去解决其它元素或位置，这种解法叫做特殊优先法.例如：用0、1、2、3、4这5个数字，组成没有重复数字的三位数，其中偶数共有________个.（答案：30个）
【分析】因为一天中乘火车有4种走法，乘汽车有2种走法，乘轮船有3种走法，每种走法都可以完成由甲地到乙地这件事情．所以，一天中乘坐这些交通工具从甲地到乙地共有4+2+3=9种不同的走法。解答树如下:
【总结】将这类型的问题总结为一个基本原理——加法原理：做一件事，完成它可以有几类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，…，在第n类办法中有mn种不同的方法．那么，完成这件事共有N=m1+m2+…+mn种不同的方法。
第1步取1本数学书，有3种方法；
第2步取1本语文书，有5种方法；
第3步取1本英语书，有6种方法．
根据乘法原理，得到不同的取法种数是N=m1×m2×m3=3×5×6=90．
(3)从书架上任取不同科目的书两本，可以有3类办法：
第1类办法是数学书、语文书各取1本，需要分两个步骤，有3×5种方法；
第2类办法是数学书、英语书各取1本，需要分两个步骤，有3×6种方法；
【总结】进行分类时，要求各类办法彼此之间是相互排斥的，不论哪一类办法中的哪一种方法，都能单独完成这件事。只有满足这个条件，才能直接用加法原理，否则不可以。
如果完成一件事需要分成几个步骤，各步骤都不可缺少，需要依次完成所有步骤才能完成这件事，而各步要求相互独立，即相对于前一步的每一种方法，下一步都有m种不同的方法，那么计算完成这件事的方法数时，就可以直接应用乘法原理。
计算公式：＝n(n－1)(n－2)……(n－m＋1)＝
以前排列会记为P。下面一些例题是P的表明也是排列。
2.组合
概念：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。
组合数：从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数，用符号表示。
解答树如下：
2)、乘法原理
【问题2】由A村去B村的道路有3条，由B村去C村的道路有2条（见图9－1），从A村经B村去C村，共有多少种不同的走法？
【分析】从A村到B村，有3种不同的走法，按这3种走法中的每一种走法到达B村后，再从B村到C村又各有2种不同的走法，因此，从A村经B村去C村共有3×2=6种不同的走法。解答树如下：
【总结】将着类型的问题总结为一个基本原理——乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，…，做第n步有mn种不同的方法．那么，完成这件事共有N＝m1×m2×…×mn种不同的方法．
解答树如下：
3)加法原理和乘法原理的浅释
它们的作用是：是用于计算完成一件事的所有不同的方法种数。
三、讲解范例：
例1由数字１、２、３、４、５、６、７组成无重复数字的七位数
(1）求三个偶数必相邻的七位数的个数；（2）求三个偶数互不相邻的七位数的个数
解(1)：因为三个偶数２、４、６必须相邻，所以要得到一个符合条件的七位数可以分为如下三步：
第一步将１、３、５、７四个数字排好有 种不同的排法；
第二步将２、４、６三个数字“捆绑”在一起）(1<=n,m<=20)，同样马的位置坐标是需要给出的（约定: C<>A，同时C<>B）。现在要求你计算出卒从A点能够到达B点的路径的条数。
【输入】B点的坐标（n,m）以及对方马的坐标(X,Y)
【输出】一个整数（路径的条数）。
【样例】
single.in
single.out
也就是说：类类互斥，步步独立。
(3)
例1：书架上放有3本不同的数学书，5本不同的语文书，6本不同的英语书．
（1）若从这些书中任取一本，有多少种不同的取法？
（2）若从这些书中，取数学书、语文书、英语书各一本，有多少种不同的取法？
（3）若从这些书中取不同的科目的书两本，有多少种不同的取法？
【分析】
(1)从书架上任取一本书，可以有3类办法：
6 6 3 2
17
【分析】
在不考虑有马的棋盘中:
设函数f(x,y)=从出发点(0,0)走到(x,y)的路径条数。则走到(x,y)的方法有两类：
第1类是从上边点(x-1,y)走下来，这类的方法数为：f(x-1,y)
第2类是从左边点(x,y-1)走过来，这类的方法数为：f(x,y-1)
根据加法原理有，f(x,y)=f(x-1,y)+f(x,y-1)
（1）从中任选一个会外语的人，有多少种选法？
（2）从中选出会英语与会日语的各1人，有多少种不同的选法？
10.
(
1.排列
概念：从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。
排列数：从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号表示。
科学分类法 对于较复杂的排列组合问题，由于情况繁多，因此要对各种不同情况，进行科学分类，以便有条不紊地进行解答，避免重复或遗漏现象发生 例如：从6台原装计算机和5台组装计算机中任取5台，其中至少有原装与组装计算机各两台，则不同的选取法有_______种.（答案：350）
插空法 解决一些不相邻问题时，可以先排一些元素然后插入其余元素，使问题得以解决 例如：7人站成一行，如果甲乙两人不相邻，则不同排法种数是______.(答案:3600)
捆绑法 相邻元素的排列，可以采用“整体到局部”的排法，即将相邻的元素当成“一个”元素进行排列，然后再局部排列 例如：6名同学坐成一排，其中甲、乙必须坐在一起的不同坐法是________种.（答案：240）
