由于现在CSP的排列组合题越来越多了,平均一份都有2题,临近考试,我来讲一下排列组合的题目
应该大部分人都知道排列数A和组合数C,不过我还是讲一下
ANM=N!(N−M)!A_N^M = \FRAC{N!}{(N-M)!}ANM =(N−M)!N!
***=N!M!(N−M)!C_N^M = \FRAC{N!}{M!(N-M)!}*** =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种
9.相同元素分组:将N个相同元素放入M个不同的盒内,且每盒不空,则不同的方法共有CN−1M−1C_{N-1}^{M-1}CN−1M−1 种。对应问题是一次不定方程X1+X2+...+XN=R的非负整数解的个数等于CN+R−1RC_{N+R-1}^{R}CN+R−1R (或CN+R−1N−1C_{N+R-1}^{N-1}CN+R−1N−1 ),正整数解的个数等于CR−1R−NC_{R-1}^{R-N}CR−1R−N
解决此类问题的方法是“挡板法”,因为元素相同,所以只需考虑每个盒子里所含元素个数,则可将这N个元素排成一列,共有(N-1)个空,使用(M-1)个挡板进入空挡处,则可将这N个元素划分为M个区域,刚好对应那M个盒子
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
制作不易,希望对你们有帮助
分享一则笑话(洛谷神图)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有什么问题可以加我QQ2967188932