前置知识点

排列数

\(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!\)

组合数

\(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^0=1\)，\(C_m^1=n\)，\(C_n^n=1\)，\(C_n^m=C_n^{n-m}\)

以下是一些题，主要是对于以上知识的运用

T1

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

答案：A

这题用捆绑法

把这两个元素看做整体，就变成了给4个小朋友进行排序

也就是给4个元素进行全排列

那么这两个元素之间还可以互换

所以最后的答案就是：

\(4!*2!=48\)

T2

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

A.84

B.72

C.56

D.504

答案：A

这题用插板法

RT，就是要把10分成7份

分成7份，要插多少块板？

你别告诉我不知道

6块呗

那么10个数，一共会有9个空

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

所以答案就是

\(C_9^6=C_9^3=84\)

T3

有5副不同颜色的手套（共10只手套，每副手套左右手各1只），一次性从中取6只手套，请问签好能配成两幅手套的不同取法有（）种。

A.120

B.180

C.150

D.30

答案：A

首先，一共有5副手套，要取出2副，那么现在有\(C_5^2\)种取法

因为是恰好2副，所以在剩下的3副中只能取出2只，而且凑不成一双，那么也就是从3组中选2组，每组拿出来一个，也就是\(C_3^2\)

因为每一副手套都有左右手，所以在选每副手套中的1只的时候，要区分左右手

第一副有2种选法，第二副有2种选法，所以还要\(*2*2\)

最后答案的就是\(C_5^2*C_3^2*2*2=120\)

T4

从一个4*4的棋盘中选取不在同一行也不在同一列上的两个方格，共有（）种方法。

A.60

B.72

C.86

D.64

答案：B

这题用间接法

如果取了o

那么就还可以再取*

一共有9种

因为一共有16个方格

所以一共有\(16*9\)种选法

但是因为取的时候会有重复

将结果除以2就是答案

也就是\(\frac{16*9}{2}=72\)

T5

把8个同样的球放在5个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（）
提示：如果8个球都放在一个袋子里，无论是哪个袋子，都只算同一种分法。

A. 22
 
B. 24
 
C. 18
    
D. 20

答案：C

emm……这题用暴力法

然后答案就是\(1+4+5+5+3=18\)

T6

—副纸牌除掉大小王有52张牌，四种花色，每种花色13张。
假设从这52张牌中随机抽取13张纸牌，则至少（）张牌的花色一致。

A. 4
 
B. 2

C. 3

D. 5

答案：A

直接做

因为3*4=12<13

所以就再加上4

也就是4*4=16>13

正好满足要求

所以答案就是4

T7

由数字1,1,2,4,8,8锁组成的不同的4位数的个数是（）。

A.104

B.102

C.98

D.100

答案：B

第一种：4个数都不相同

1,2,4,8

每一个枚举出来的数都不一样

所以一共有4！=24

第二种：4个数中有2个相同，另外2个不相同

1,1,2,4/1,1,2,8/1,1,4,8/1,2,8,8/1,4,8,8/2,4,8,8（共6种）

所以总共有\(\frac{4!}{2!}=12\)

第三种：4个数有2个相同，另外2个也相同

1,1,8,8

所以总共有\(\frac{4!}{2!*2!}=6\)

综上所述，一共有\(24+12*6+6=102\)

T8

—次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）。

A. 23
 
B. 21

C. 20

D. 22

答案：A

因为有4人语，数都是满分，所以我们在计算单科的时候要减去4

所以最终结果就是\(15+12-4=23\)

T9

10个人排队买票，票价为50元，其中5个人各手持一张50元钞票，5个人各手持一张100元钞票，除此之外大家身上没有任何其他的钱币，并且初始时候售票窗口没有钱，问有多少种排队的情况数能够让大家都买到票。

因为初始的时候窗口没有钱，所以就要让手持50元钞票的顾客先买票，这样才能将钱找给手持100元钞票的顾客

也就得出：在任意时刻，手持50元钞票的顾客的人数要大于等于手持100元钞票的顾客的人数

这就是传说中的卡特兰数(RT)

我们在这张图里面用横线表示手持50元钞票的顾客的人数，用竖线表示手持100元钞票的顾客的人数，那么我们就只能在下面这半部分进行计算

（这里的横线竖线可以理解为方格的一条边，是竖着的就称它是竖线，是横着的就称它为横线）

然后我们就可以发现1,2,5,14,42,……卡特兰数！

然后右上角的那个数表示从左下角出发，一直到右上角的所有路径总和，也就是符合题意的所有方案数：42

但是！这里的方案数指的只是站的方案，每5个人的站位还可以进行调换，一共有5！种

所以最后的答案应该是\(42*5!*5!=604800\)

卡特兰数的公式及推导

\(ans=C_{2n}^n-C_{2n}^{n-1}\)

RT（还是只能走下半部分的三角形）从A点走到B点总共需要走过n条横线，n条竖线（例如：绿色的那条边）

所以\(C_{2n}^n\)代表的就是从A点走到B点的总方案数

现在我们画一条不合法的线（紫色的，经过了上半部分的三角形）

emm……我们可以证明的是：

任意一条经过上半部分三角形的线，将不合法的点之后的横线竖线反着走，均能到达C点

当我们第一次经过不合法的点的时候，一定是竖线比横线多1

那么我们可以设：当前经过了a条竖线，a-1条横线

还需要走n-a条竖线，n-a+1条横线

反一反：还需要走n-a+1条竖线，n-a条横线

那么我们总共走了n+1条竖线，n-1条横线

走n+1条竖线，n-1条横线到哪呢？

到C点！

那么我们就把所有不合法的情况转化成了从A点到C点的总路径

而从A点到C点的总路径数为\(C_{2n}^{n-1}\)

将总路径数与不合法的路径数相减，得到的就是合法的方案数

错位排列（容斥原理）

错位排列：意思就是每个数都不在自己原来的位置上，求出满足这个条件的方案总数

设：{\(A_k\)}表示k号同学坐对位置的所有排列构成的集合

那么要求合法的方案数，我们可以用总数减掉不合法的方案数

总方案数就是\(n!\)，然后就求出不合法的方案数即可

至少有一个人坐对自己的位置的集合是

\(|{A_1 \bigcup A_2 \bigcup A_3 …… \bigcup A_n}|\)

\(=\sum_{k=1}^n{\\}|{A_k}|-\sum_{1≤i<j≤n}^n{\\}|{A_i\bigcap A_j}|+\sum_{1≤i<j<m≤n}^n|{A_i\bigcap A_j\bigcap A_m}|-……+……\)

emm……

这个式子，说起来就是把所有两两相交的部分减掉，然后再把三个三个相交的部分加上，然后再……

总之就是把重复减掉的地方再加上，然后不重复的进行计算

定义

如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。（A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）

咳咳……回到刚才那个式子

（直接接着刚才那个继续化简叭）

\(=n*(n-1)!-C_n^2*(n-2)!+C_n^3*(n-3)!-……+……\)

简单解释一下就是第一个式子是取出1个数的组合数，第二个十字因为选出了两个数，所以是两个数之间的组合数，以此类推，慢慢往后算就完了

\(=n!- \frac{n!}{2!}+\frac{n!}{3!}-……+……+(-1)^{n+1}\frac{n!}{n!}\)

然后错位排列，就是都没有做到自己的位置上去，那么就是我们刚才求的那个式子，用\(n!\)减掉，说白烈酒时用总共的方案数减去合法的方案数

T10

从数字0，1，2，3，4，5，6，7中任意取3个奇数和2个偶数，组成一个无重复数字且两个偶数不相邻的五位数，则此时满足条件的五位数的个数为____

方法1

如果说这五位数里面不包含0

因为这7个数里面有4个奇数，3个偶数

所以就会总共会有\(C_4^3*C_3^2\)

然后因为选3个奇数，不含0，所以用插孔法的话会有4个空可以插

就比如我们现在随便选择了三个奇数1,3,5

然后就会有4个空隙

像酱→_1_3_5_

然后因技术可以全排列的，就是\(A_3^3\)

然后再这4个空里面选择2个进行插空，有\(C_4^2\)种

一共就是\(C_4^3*C_3^2*A_3^3*4*3\)

那么含0的情况呢？

因为已经有一个偶数已经选好了

所以总共会有\(C_4^3*C_3^1\)种

奇数还是可以全排列的，\(A_3^3\)

因为0是不能放在第一个空里面的

所以0一共有3种放法

那么另外一个偶数也会有3种放法

总共就会有\(C_4^3*C_3^1*A_3^3*3*3\)

然后再把这两个式子进行累加

\(C_4^3*C_3^2*A_3^3*4*3+C_4^3*C_3^1*A_3^3*3*3=1512\)

方法二

就当做0也可以放在首位，不受0的影响

总共会有\(C_4^3*C_4^2*A_3^3*4*3\)种

然后把0放在首位的那种方案减掉

就是最后合法的方案

那么0放在首位的方案有多少呢？

\(C_4^3*C_3^1*A_3^3*3\)

因为0已经选了嘛

所以实在剩下的3个偶数里面选择1个偶数

然后每一种有3种选择

再然后用总共的减去不合法的就是最后的结果

即\(C_4^3*C_4^2*A_3^3*4*3-C_4^3*C_3^1*A_3^3*3=1512\)种

写了好几天……属实不容易

初赛（4）