儿子学奥竞。在过春节期间，重新学习了下高中的排列组合，以便与儿子能沟通。以下是学习笔记。
一、计数原理基础概念
- 分类加法原理：完成一件事有两类不同方案，在第1种方案中有m种不同的方法，在第2种方案中有n种不同的方法，那么完成这件事共有
种不同的方法。要点在2种方案中的方法互不相同。
问题：如果2个方案中方法有相同项呢？ - 分步乘法原理：完成一件事需要两个步骤，做第1步有m种不同的方法，做第2步有n种不同的方法，那么完成这件事有
种不同的方法。要点是2步中的方法互不影响。
问题：如果两步中方法相互影响呢？ - 排列：从n个不同元素中取出m（m<=n）个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。排列公式为：
。
- 组合：从n个不同元素中取出m（m<=n）个元素合成一组，叫做从n个不同元素中取出m个元素的一个组合。组合公式为：
。
- +分组：把n个相同元素中分成m组（m<=n），共有
分法。
- +分配：把n个不同元素分配给n个不同的对象，共有
分法，与全排列思路相似。
（注）：
1. 排列与组合实际上是分步乘法原理的两种应用而已。
2. 而组合的本质只是选取不进行排列。
3. 排列的本质是选取加上全排列。
+4. 分组是多次选取的结果。1次选取相当于分成两组，相当于组合。
+5. 排列的结果是数列，而组合的结果是集合，而分组的结果是多个集合。
+6. 分配的本质是分组加上全排列。 分配是现实世界的要求与规则。
二、乘法在排列与组合中的意义的不同
举个例子：
有什么意义？是排列还是组合？
这个问题重要吗？
这个很重要，如果不知道当前式子是排列还是组合，就无法进行正确计算。
排列的结果是数列，而组合的结果是集合。
上面式子的可以有两种意义：
- 第一种：从五个人选出两人当正副班长，选法几何？
。这明显是一个排列问题。因为选出后按正副班长这个排列顺序，如果是选出两个人打扫卫生，结果就变成
了。
- 第二种：从5个男生与4个女生中，分别选出一个人去参加乒乓双打。
大多数情况下：
三、从元素的相异性来看计数
（一）无重复元素（不同元素集合，我们主要学的）
- 元素模型常见有：同学、甲乙丙丁、球队、课程等。
- 排列应用：
，从n个不同元素中选取m个元素的排列。
- 全排列应用：
，从n个不同元素中选取n个元素的排列，或对n个不同元素直接排列
- 圆排列应用：
，n个不同元素围成一个圆的全排列。
- 项链排列应用：
，n个不同珠子串成一个项链的全排列。
- 组合应用：
，从n个不同元素中选择m个元素的组合。
- 全组合应用：
，从n个不同元素中任何选取的组合。
例：壹圆、贰圆、伍圆、拾圆各一张，一共可组成多少币值（至少取一张）？
答：
- 分组排列：
（n=n1+n2+...+nk，将n个不同元素分成k个按一顺序排列的组）
例：将10个人分别分成1人组、2人组、3人组、4人组，共有分法？
答：
-
平均分组排列：
（n=m*k 将n个不同元素平均分成k个按一顺序排列的组，每组m个元素）
例：将6个同学分成3组分别命名为1号组,2号组,3号组，然后去打双打比赛，有几种分法？
答：
析：不同元素的平均分组排列，也是分配。
-
平均分组组合：
（n=m*k 将n个不同元素平均分成k个组，每组m个元素）
例：将6个同学分成3组，去打双打比赛，有几种分法？
答：
-
分组组合：
（n=n1+n2+...+nk，将n个不同元素分成k个组）
例1：4个同学分成3个组去玩游戏，有几种分法？
答：
析：第一个是有一组是2人，第二个
注：???表示情况比较复杂，需要具体应对。往往这地方也是可以拓展的知识边界。
-
+分配问题：？？？，（n个不同元素全部分配给m个不同对象时，n>m）
例1：n+1个不同礼物，全部发给n个同学，每人至少一件，则发放方法数为 ____
答：。先将n+1个元素分成n组，然后将不同的n组派发给n个同学。
答：。通过先n+1个元素分成无序组，再进行分配。
例2：10个不同礼物，全部发放给四个同学，每个同学最少2件，最多3件，有多少发放法？
答：
（二）无限重复元素（可重复元素，扩展，人的直觉不能识别的元素）
- 元素常见模型有：银行中的纸币、数字、乒乓球、不同颜色的球、颜色
- 排列：
（从n种可重复元素中选出m个元素的排列）
例：用0、1、2、3四个数字，能构成多少个3位数（可有重复数字）？
答：或
，首位不能为0，故先取首位。
- 组合：
（从n种可重复元素中选出m的组合）
例：在银行中从五角、一元、二元、五元、十元、五十元、一百元7种纸币中任取10张，有多少种组合方式？
答：
（三）有限重复元素（扩展）
- 元素常见模型举例：红蓝白球各10个、36的质因数（2个数字2, 3个数字3）
- 排列：？？？
注：目前没有发现这方面的发现与研究。
- 组合：？？？（n=n1+n2+...+nk，分别有k种不同元素，每种元素有n1,n2,...,nk个，从所有元素中取出m个元素的组合，其中
）
例：红、黑、白球各10个，取出16个球，有多少取法？
答：
析：当m>n/2时，可转化成n-m; 当m<max(n1,n2,...,nk)，比m大的颜色，对于m来说是无限取法，也需要调到m。
注1：对做法有疑问者可以留言，仔细询问。这里通用作法是分类讨论。
注2：???表示情况比较复杂，需要具体应对。往往这地方也是可以拓展研究的知识边界。
- 全排列：
例：红旗2面，蓝旗3面，白旗4面，在杆上进行排列，可排列出多少标志？
答：
- 全组合：
（其中n1个元素1，n2个元素2，nk个元素k，任意两元素的组合结果都不同，有多少组合方法？）
例：，问x,y有多少组正整数解？
答：
析：，因为3与2皆为质数，故满足任何两元素的乘积结果都不同。
（四）无差异元素（相同元素集合，扩展）
- 元素常见模型：相同的球、几何图形或几何体的顶点、边长等。无差异元素的排列与组合没有意义。
- 全组合：
（n个相同的元素，随意取出，共有多少取法？）
- 析：取出个固定数量的组合没有意义
- 分组排列：
例：七个相同的球分给5个班，每个班至少有一个，如何分？
答：
- 分组排列：
（将n个相同元素分成m个可空组的排列）
例：10个完全相同的球分给甲乙丙丁4人，可以有人没有球，但球必须发完，有多少分法？
答：
析：无差别元素的分组排列，其实就是无差别元素的分配。
- 分组组合：??? （将n个相同元素分成m个组）
例：不定方程x1+x2+x3=200, x1,x2,x3皆为正整数,且均不相等,且保证x1<x2<x3，问有x1,x2,x3多少组解？
答：
析：为所有x1,x2,x3的解，为总集合；而
是其中有两数相等的情况；6是
，指当3数皆不相等时的所有排列。
注：???表示情况比较复杂，需要具体应对。往往这地方也是可以拓展研究的知识边界。
四、总结
- 排列组合比较容易出错，往往无法检验。最好的检验办法是用多种思路，得到同一结果。
- 对于复杂的排列组合解题，最好的办法从小规模的数去演绎算法。
- 排列组合最容易出错的原因是漏算与重复算。
- 排列组合主要应用场景有：排列、组合、分组、+分配、集合、不定方程、质因数、约数和等。
- 排列组合的本质是现实世界事物与时间空间的对应与分配问题。
n 个不同元素到m个不同位置的对应问题。
(1) 如果n=1，就是组合；
(2) 如果n>m，要求1个位置放1个元素，就是排列；
+(3) 如果n=m，要求1个位置放1个元素，就是全排列，或者是直接分配；
+(4) 如果n>m，要求必须分配完，每个位置必须有，就是分配问题； - 排列组合的本质是集合与数列的转换问题。
(1)排列的过程，是集合向数列的转换。排列的对象是集合，而结果是数列。
(2)组合的过程，是集合向集合的转换。组合的对象是集合，而结果也是集合。
+(3)分组的对象是集合，而结果可以是数列，也可以是集合，视情况而定。
+(4)分配的过程，是集合向集合的分配，分配的对象集合，分配的目标也是集合。
+(5)分组排列的过程 ，是集合先转成大集合，大集合又向数列的转换
+(6)分组组合的过程 ，是集合向大集合的转换。
网友评论