排列组合

一只姜（AAAAAA级遗址）

2024-08-23 09:55:33

发布于：浙江

223阅读

0回复

0点赞

由于现在CSP的排列组合题越来越多了，平均一份都有2题，临近考试，我来讲一下排列组合的题目

应该大部分人都知道排列数A和组合数C，不过我还是讲一下

$A_n^m = \frac{n!}{(n-m)!}$

$C_n^m = \frac{n!}{m!(n-m)!}$

A的原理就是在n个人中m个人排序的种类数

C的原理就是在n个人中挑m个人的种类数

先看一道很简单的例题（来源：CSP-J2019）

这道题大家应该都会吧，只需要考虑最坏情况：3 3 3 4就好了

所以答案选A

这就是最基础的排列组合

再看（来源：CSP-J2020）

此题首先把10个三好学生分为7份，所以使用插板法，在9个空格选6个插板，所以有 $C_9^6=84$ 种分配方案

再看（来源：CSP-J2021）

此题很简单，先在6个人中选2个，然后在剩下4个人中选2个,然后除 $A_3^3$ 判重

$\frac{C_6^2 \times C_4^2}{A_3^3}=15$

再看例题（来源：CSP-J2020）

这是一道经典的捆绑法的题目

首先我们把这对双胞胎看做一个整体

所以可以看做有4个人，但是双胞胎最后还要排序

所以列出式子：

$A_4^4 \times A_2^2=48$

这也是一道很基础的题目

再看（来源：SJZ08提供的CSP-J模拟卷）

这道题目要分两种情况考虑

有4个空位，要填入0、1、2、3，首位不能为0，必须包含1、2、3

第一种：先找3个位置，但是包含一号位，所以有 $C_3^2$ 种位子选择，然后1、2、3排序，所以再乘 $A_3^3$ ，剩下的位置选1、2、3，所以再乘上 $C_3^1$ ，最后再手动判重(比如1 2 3 2和1 2 3 2）

$C_3^2 \times A_3^3 \times C_3^1=54$

手动判重，1开头有四个：1 2 3 2、1 3 2 3、1 2 2 3、1 3 3 2

所以54-4*3=42种

第二种：和第一种一样，但是剩下的位置填0，不用判重，所以

$C_3^2 \times A_3^3=18$

答案：42+18=60

再看（非CSP，仅排列组合练习题）

2位男生和3位女生共5位同学站成一排，若男生甲不站两端，3位女生中有且只有两位女生相邻，则不同排法的种数是（）
A.60    B.48    C.42    D.36

此题首先选出2个相邻的女生共 $C_3^2$ 种，然后2个相邻女生排序 $A_2^2$ ，相邻女生的整体和单独女生排序 $A_2^2$

接着就是4个整体的排序

我们把男生甲看做A，另一个男生看做B，两个相邻女生看做C，单独女生看做D

有由于左右调换不同，CD顺序已考虑不用管，所以有四种排法：

C A B D
C B A D
B C A D
D A C B

所以列出：

$C_3^2 \times A_2^2 \times A_2^2 \times 4=48$

看了那么多例题，我讲一下常用思路

1.特殊优先：对于题目中有特殊要求的元素，在考虑步骤时优先安排，然后再去处理无要求的元素

2.寻找对立事件：如果一件事从正面入手，考虑的情况较多，则可以考虑该事的对立面，再用全部可能的总数减去对立面的个数即可

3.先取再排（先分组再排列）：有时会出现所需排列的元素并非前一步选出的元素，所以此时就要将过程拆分成两个阶段，可先将所需元素取出，然后再进行排列

4.捆绑法：当题目中有“相邻元素”时，则可将相邻元素视为一个整体，与其他元素进行排列，然后再考虑相邻元素之间的顺序即可

5.插空法：当题目中有“不相邻元素”时，则可考虑将剩余元素排好“搭台”，不相邻元素进行“插空”，然后再进行各自的排序

6.错位排列问题：设集合I={1,2,...,n}，所有元素的一种全排列t1,t2,...,tn，满足ti不等于i(i=1,2,...,n)，则称这样的排列t1,t2,...,tn为错位全排列。用Dn表示I={1,2,...,n}的错位全排列总数，则

$D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n \times \frac{1}{n!})$

极限为 $\frac{1}{e}$

7.依次插空：如果在n个元素的排列中有m个元素保持相对位置不变，则可以考虑先将这m个元素排好位置，再将n-m哥元素一个个插入到队伍当中（注意每插入一个元素，下一个元素可选择的空+1）

8.不同元素分组：将n个元素放入m个不同的盒中有 $m^n$ 种

9.相同元素分组：将n个相同元素放入m个不同的盒内，且每盒不空，则不同的方法共有 $C_{n-1}^{m-1}$ 种。对应问题是一次不定方程x1+x2+...+xn=r的非负整数解的个数等于 $C_{n+r-1}^{r}$ （或 $C_{n+r-1}^{n-1}$ ）,正整数解的个数等于 $C_{r-1}^{r-n}$

解决此类问题的方法是“挡板法”，因为元素相同，所以只需考虑每个盒子里所含元素个数，则可将这n个元素排成一列，共有（n-1）个空，使用（m-1）个挡板进入空挡处，则可将这n个元素划分为m个区域，刚好对应那m个盒子

制作不易，希望对你们有帮助

分享一则笑话（洛谷神图）

有什么问题可以加我QQ2967188932

有帮助，赞一个

去预览

0/2000

全部评论 5

坤·燃.
大佬为什么被禁言了？？（第一眼：有人被禁言了，活该！，第二眼：一只姜被禁言了，一定是有人冒充！第三眼：是真的一只姜，咋干啥了？！下一步：看站务违规公示，没有一只姜，一看就是AC君搞得鬼。~~想到举报申诉哪里举报AC君~~）

2024-08-22 来自北京
2
- 一只姜（AAAAAA级遗址）
  回复坤·燃.
  ……
  
  2024-08-23 来自浙江
  0
- SJZ08
  回复一只姜（AAAAAA级遗址）
  恭喜解禁！
  
  2024-08-23 来自广东
  0
- 花似雪jacxi
  回复一只姜（AAAAAA级遗址）
  之前那个登录框吧
  
  2024-08-23 来自广东
  0
李总
顶顶顶顶顶！

2024-08-22 来自四川
1
一只姜（AAAAAA级遗址）
顶

2024-08-22 来自浙江
1
‮队团加不）ด้้童帅_者仇复
大佬我对星号过敏，能不能改成\times？（

2024-08-23 来自广东
0
- 一只姜（AAAAAA级遗址）
  回复‮队团加不）ด้้童帅_者仇复
  改了.
  
  2024-08-23 来自浙江
  0
暗夜
<style> body{ background: linear-gradient(90deg,#EE82EE 0%,#00D1FF 100%); } </style>
改颜色~

2024-08-22 来自上海
0

由于现在CSP的排列组合题越来越多了，平均一份都有2题，临近考试，我来讲一下排列组合的题目

应该大部分人都知道排列数A和组合数C，不过我还是讲一下

Anm=n!(n−m)!A_n^m = \frac{n!}{(n-m)!}Anm​=(n−m)!n!​

Cnm=n!m!(n−m)!C_n^m = \frac{n!}{m!(n-m)!}Cnm​=m!(n−m)!n!​

A的原理就是在n个人中m个人排序的种类数

C的原理就是在n个人中挑m个人的种类数

先看一道很简单的例题（来源：CSP-J2019）

这道题大家应该都会吧，只需要考虑最坏情况：3 3 3 4就好了

所以答案选A

这就是最基础的排列组合

再看（来源：CSP-J2020）

此题首先把10个三好学生分为7份，所以使用插板法，在9个空格选6个插板，所以有C96=84C_9^6=84C96​=84种分配方案

再看（来源：CSP-J2021）

此题很简单，先在6个人中选2个，然后在剩下4个人中选2个,然后除A33A_3^3A33​判重

C62×C42A33=15\frac{C_6^2 \times C_4^2}{A_3^3}=15A33​C62​×C42​​=15

再看例题（来源：CSP-J2020）

这是一道经典的捆绑法的题目

首先我们把这对双胞胎看做一个整体

所以可以看做有4个人，但是双胞胎最后还要排序

所以列出式子：

A44×A22=48A_4^4 \times A_2^2=48A44​×A22​=48

这也是一道很基础的题目

再看（来源：SJZ08提供的CSP-J模拟卷）

这道题目要分两种情况考虑

有4个空位，要填入0、1、2、3，首位不能为0，必须包含1、2、3

第一种：先找3个位置，但是包含一号位，所以有C32C_3^2C32​种位子选择，然后1、2、3排序，所以再乘A33A_3^3A33​，剩下的位置选1、2、3，所以再乘上C31C_3^1C31​，最后再手动判重(比如1 2 3 2和1 2 3 2）

C32×A33×C31=54C_3^2 \times A_3^3 \times C_3^1=54C32​×A33​×C31​=54

手动判重，1开头有四个：1 2 3 2、1 3 2 3、1 2 2 3、1 3 3 2

所以54-4*3=42种

第二种：和第一种一样，但是剩下的位置填0，不用判重，所以

C32×A33=18C_3^2 \times A_3^3=18C32​×A33​=18

答案：42+18=60

再看（非CSP，仅排列组合练习题）

此题首先选出2个相邻的女生共C32C_3^2C32​种，然后2个相邻女生排序A22A_2^2A22​，相邻女生的整体和单独女生排序A22A_2^2A22​

接着就是4个整体的排序

我们把男生甲看做A，另一个男生看做B，两个相邻女生看做C，单独女生看做D

有由于左右调换不同，CD顺序已考虑不用管，所以有四种排法：

所以列出：

C32×A22×A22×4=48C_3^2 \times A_2^2 \times A_2^2 \times 4=48C32​×A22​×A22​×4=48

看了那么多例题，我讲一下常用思路

1.特殊优先：对于题目中有特殊要求的元素，在考虑步骤时优先安排，然后再去处理无要求的元素

2.寻找对立事件：如果一件事从正面入手，考虑的情况较多，则可以考虑该事的对立面，再用全部可能的总数减去对立面的个数即可

3.先取再排（先分组再排列）：有时会出现所需排列的元素并非前一步选出的元素，所以此时就要将过程拆分成两个阶段，可先将所需元素取出，然后再进行排列

4.捆绑法：当题目中有“相邻元素”时，则可将相邻元素视为一个整体，与其他元素进行排列，然后再考虑相邻元素之间的顺序即可

5.插空法：当题目中有“不相邻元素”时，则可考虑将剩余元素排好“搭台”，不相邻元素进行“插空”，然后再进行各自的排序

6.错位排列问题：设集合I={1,2,...,n}，所有元素的一种全排列t1,t2,...,tn，满足ti不等于i(i=1,2,...,n)，则称这样的排列t1,t2,...,tn为错位全排列。用Dn表示I={1,2,...,n}的错位全排列总数，则

Dn=n!(1−11!+12!−13!+...+(−1)n×1n!)D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n \times \frac{1}{n!})Dn​=n!(1−1!1​+2!1​−3!1​+...+(−1)n×n!1​)

极限为1e\frac{1}{e}e1​

7.依次插空：如果在n个元素的排列中有m个元素保持相对位置不变，则可以考虑先将这m个元素排好位置，再将n-m哥元素一个个插入到队伍当中（注意每插入一个元素，下一个元素可选择的空+1）

8.不同元素分组：将n个元素放入m个不同的盒中有mnm^nmn种

解决此类问题的方法是“挡板法”，因为元素相同，所以只需考虑每个盒子里所含元素个数，则可将这n个元素排成一列，共有（n-1）个空，使用（m-1）个挡板进入空挡处，则可将这n个元素划分为m个区域，刚好对应那m个盒子

制作不易，希望对你们有帮助

分享一则笑话（洛谷神图）

有什么问题可以加我QQ2967188932

全部评论 5

恭喜解禁！

顶顶顶顶顶！

热门讨论

$A_n^m = \frac{n!}{(n-m)!}$

$C_n^m = \frac{n!}{m!(n-m)!}$

此题首先把10个三好学生分为7份，所以使用插板法，在9个空格选6个插板，所以有 $C_9^6=84$ 种分配方案

此题很简单，先在6个人中选2个，然后在剩下4个人中选2个,然后除 $A_3^3$ 判重

$\frac{C_6^2 \times C_4^2}{A_3^3}=15$

$A_4^4 \times A_2^2=48$

第一种：先找3个位置，但是包含一号位，所以有 $C_3^2$ 种位子选择，然后1、2、3排序，所以再乘 $A_3^3$ ，剩下的位置选1、2、3，所以再乘上 $C_3^1$ ，最后再手动判重(比如1 2 3 2和1 2 3 2）

$C_3^2 \times A_3^3 \times C_3^1=54$

$C_3^2 \times A_3^3=18$

此题首先选出2个相邻的女生共 $C_3^2$ 种，然后2个相邻女生排序 $A_2^2$ ，相邻女生的整体和单独女生排序 $A_2^2$

$C_3^2 \times A_2^2 \times A_2^2 \times 4=48$

$D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n \times \frac{1}{n!})$

极限为 $\frac{1}{e}$

8.不同元素分组：将n个元素放入m个不同的盒中有 $m^n$ 种