CSP-S初赛/排列组合

· · 个人记录

排列组合

参考一些巨佬的blog and 高中数学A版选择性必修三课本

感谢学妹的大力资瓷！

学妹のBlog

顺序可能有些许混乱，尽量修改排版，保证阅读质量。

定义

（参考百度百科）

分类加法计数原理：

完成一件事有n类不同的方案，在第一类方案中有m1种不同的方法，在第二类方法中有2种不同的方法...在第n类方法中有mn种不同的方法,那么完成这件事共有 N = m1+m2+...+mn 种不同的方法。

分类的要求：

1、每一类中的每一种方法都可以独立地完成此任务；

2、两类不同办法中的具体方法，互不相同（即分类不重）；

3、完成此任务的任何一种方法，都属于某一类（即分类不漏）。

分步乘法计数原理


完成一件事需要n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法...做第n步有mn种不同的方法，那么完成这件事共有 N = m1×m2×...×mn 种不同的方法。

分步的要求：


1、任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；

2、各步计数相互独立；

3、只要有一步中所采取的方法不同，则对应的完成此事的方法也不同。

应该还是很好理解的QAQ 只是一种思想？

进入正题啦

排列

定义

仍然参考百度百科QAQ


排列：

从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个不同的元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。

排列数：

从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数。

公式

排列数

A_n^m =n(n-1)(n-2)…[n-(m-1)] =n(n-1)(n-2)…(n-m+1) =\frac{n(n-1)(n-2)…(n-m+1)(n-m)(n-m-1)…2*1}{(n-m)(n-m-1)…2*1} =\frac{n!}{(n-m)!}

全排列数

A_n^n=n!

排列有顺序，组合没顺序！

组合

定义


组合：

从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。

组合数：

从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数

公式

组合数

C_n^m =\frac{A_n^m}{A_m^m} =\frac{n(n-1)(n-2)…[n-(m-1)]}{m(m-1)(m-2)…3*2*1} =\frac{n!}{(n-m)!m!}

其中

$C_n^m=C_n^{n-m}

一般初赛计算量不会太大，实在不会计算可以采用分类枚举，累加答案可以参照选项自行四舍五入，但分类一定要考虑全面（计算量稍大的话还是慎用)

以上是我的歪门邪道（千万慎用，好好学习以下方法）

穷举法适用于计算量较小或情况较少的题目中

将相邻元素放在一起，当作一个元素，参与排列，然后再对相邻元素进行排列。

捆绑法适用于“相邻”或“在一起”的排列组合问题

eg：

5个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个小朋友必须相邻，则有（）种不同排列方法？

A.48   B.36   C.24   D.72

答案：A

解析：

把两个元素看做整体，变成给4个小朋友进行排序，也就是给4个元素进行全排列，这两个元素之间还可以互换，

所以最后的答案就是：

4!*2!=48

可先把无位置要求的几个元素全排列，再把规定相离的几个元素插入上述几个元素间的空位（包含两端）

插空法适用于“不相邻”或“不在一起”的排列组合问题

eg：

5个小朋友并排站成一列，要求甲、乙、丙三人互不相邻，则有（）种不同排列方法？

A.12   B.6   C.20   D.24

答案：A

解析：

把没有要求的两个小朋友排列好，也就是A_2^2种

之后两个小朋友产生三个空，再把甲、乙、丙三人插在空隙中，也就是A_3^3种

所以最后的答案就是：

------------ - ### 隔板法 ### 将n个相同元素分成m份，（n,m为正整数）每份至少一个元素，可以用m-1块隔板，插入n个元素排成一排的n-1个空隙中，所有分法共有$C_{n-1}^{m-1}

隔板法适用于处理相同的东西分给不同的人，每人至少一个的排列组合问题。

eg：

10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有（）种不同的分配方案。

A.84  B.72  C.56  D.504

答案：A

把十个人分成7份，插（7 - 1）块板

10个数，一共会有9个空

也就是说，在这9个空里面选6个进行插板

所以最后的答案就是：

C_9^6=C_9^3=84

该方法看具体题目适用。

eg：

由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数。

答案：288

首位与末位有特殊要求

先排末位，末位为1,3,5，有C_3^1种

再排首位，首位不为0，有C_4^1种

再排其他位置共有A_4^3种

最后由乘法原理得：

C_3^1 * C_4^1 * A_4^3 = 288

还有别的方法但似乎不太会用到？

挂b乎文章！

排列组合解题方法1

排列组合解题方法2

卡特兰数（Catalan）

卡特兰数是一个在组合数学里经常出现的一个数列，它并没有一个具体的意义，却是一个十分常见的数学规律

公式

k=C_{2n}^n-C_{2n}^{n-1}

卡特兰数列（从第0项开始）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670...

挂一些Blog

才不是我懒得写QAQ（主要怕表述不清）

卡特兰数1

卡特兰数2

下课了QAQ 错位排序明天补！

排版问题明天再搞啦！