2023届高三寒假数学二轮微专题45讲 43.排列组合

                       43排列组合与概率

5.1排列组合

5.1.1 含有相同元素的全排列

若个元素，有个元素相同，另有个元素也相同，一直到另有个元素相同，即

，这个元素的全排列数为

理解方式：方法1. 将个元素彼此之间种交换顺序的排列合并为一种.

          方法2. 只选位置.

注：此种理解方式其实完全等同于组合数的推导.

例1.  走上7级台阶，每次只能上一级或者两级，共有多少种不同的走法？

解：

分类，共有4种走法，故.

点评：本题亦可用递推公式斐波那契数列.

练习：1. 6×6的方格中停有三辆完全相同的红车和三辆完全相同的黑车，每一行每一列只有一辆车，每辆车占一格，则停放总数为_14400______.

2. 在一个4×4的方格中填入8个1，使得每一行每一列都有2个1，填法的总数为_90____.

5.1.2 容斥原理下的错位排列.

设集合，其所有元素的一个全排列满足，都有，则称这样的全排列为错位全排列.

例2.  证明：错位全排列数为：.

证明：记为满足的全排列的集合，则显然

由容斥原理，排列数为

，证毕.

5.1.3 不定方程 的非负整数解.

例3. 求证：

（1）方程 的正整数解为个.

（2）方程 的非负整数解为个.

证明：（1）挡板法：

（2） 的非负整数解一一对应的正整数解，

.

练习：两个实数集，若从到的映射使得中每个元素都有原象且，则这样的映射共有（   ）个.

.             .            .               .

5.1.4 二项式定理

恒等式：（1）         （2）

       （3）（范德蒙恒等式）

其他结论：

例4.求中的系数.

解法1. .

解法2.数列求和.

例5.  求的百万位上的数字.

解：.

由于则当时，百万位上均为0，故答案为.

点评：求形如某一指定位置数字时，常用二项展开式.

例6.将一个四棱锥的每个顶点染上一种颜色，并使同一条棱的两个端点异色，共有5种颜色可供使用，则不同的染色方法共有_420_种.

解：分类：用5种颜色时：，用4种颜色时：，

用5种颜色时：，故总的涂法.

练习：用4种不同的颜色涂在三棱台的6个顶点，要求同一条棱上的两点不同颜色，则不同的染色方法共有_264_种.

例7. 对于一个四位数，其各位数字至多有两个不相同，试求共有多少个这样的四位数？

解法1: ①4个，9种.②3个和1个，这种情形下，再分为1个0的情形，有种；3个0的情形，有种；没有0的情形，有种. ③2个和2个，这种情形下，再分为无0，有种；有0，有种.

故共计有种.

点评：其中②③亦可用排除法，比如②可用.

解法2：①全是，9种.

 ②有两个数字，. 第一步：千位，种情况；第二步：再选一个数字，种情况；第三步：百十个位填数字，，但不能都与千位相同，故要减1.

因此，总的方法为.

点评：解法2技巧性更强.

练习题

1. 解不等式. 
2. 的最后位数是.
3. 将凸五边形每个顶点染上五种颜色之一，使得每条对角线两个端点颜色不同的染色方法共有种.
4. 已知集合且，则符合条件的共有_______组.（顺序不同视为不同组）
5. 的展开式中，有理数有项.
6. 数列共有项，且，则满足条件的数列共有个.
7. 红蓝两色车，马，炮各一枚，将这六枚棋子排成一列，其中每对均是红在前，蓝在后，则共有种排法.
8. 数列为等差数列，从而中取出三个数，依然构成等差数列，则取法共有种.

注：，即.

9.   ，则.
10. ，若，则.

注：

11. 在平面直角坐标系中，，则以中点为顶点且位置不同的正方形个数为.
12. 设，其中，则在排列种，至少有两个相邻的排列的个数为.
13. 马路上有编号为的盏路灯，为节能关闭只，但不能关闭相邻，也不能关闭两端，则关灯方法共有种.
14. 已知集合满足，若中元素个数不是中元素，中元素个数不是中元素，则满足条件的集合的个数是.
15. 若四位数满足，就称其为好数，那么，好数的个数是.
16. 从数按从小到大的顺序取出，使得且，那么所有符合要求的取法共有种.
17. 记，则（    ）

18. 整数满足，则这样的有（   ）组.

19. 已知是的一个排列，且，则有（   ）种不同排列数.

20. 方程的非负整数解有（   ）组.

21. 若集合的三个子集满足，且，则称为的有序子集列，现，则有（ D ）个有序子集列.

22. 设，则（    ）

23. 为的一个排列，且，则排列共有______个.
24. 在圆周十等分点中取四个，可围成梯形个.
25. 将个数：个，个，个，个，填入一个矩阵，要求每行每列正好有个偶数，则共有______种填法.

26. 从中挑三个不同的数字组成五位数，其中有两个数字各用了两次，如，则这样的五位数共有（  ）个.

27. 从正边形所有顶点中选个，能构成（  ）个钝角三角形.

28. （   ）

            以上均不对

5.1.5 卡塔兰数：

例8. 已知，并且满足，，求有序数组的个数.

解：依题，中共有个，个，先不考虑记为（*）式，则共有种，接下来考虑排除法，若不符合（*）式，则一定存在一个的自然数，使得：

，现将全部改变符号，即有：

，对应后则有个，个，反之，对任一个个，个组成的有序数组，其必然存在一个最小的自然数，满足.

作对应，显然，与互为逆映射，从而不满足（*）式的个数，就是由个，个组成的有序数组的个数，从而.

点评：卡塔兰数在组合数学中常出现在各种计数问题中，其前几项为，其满足 或.

主要应用场景：（1）括号化：

             （2）出栈次序

             （3）凸多边形三角划分

             （4）给定节点组成二叉树

注：2016年三卷高考选择题12题即卡塔兰数的应用.

常见等价场景：

（1）个人进入剧场，票价元，有个人有元，个人有元，售票员不带钱，问有多少种方式使得只要带元的人买票，售票员就可以找零.

（2）圆上有个点，连成条线段且不相交

（3）个高矮不同的人排成两排，每排从左到右逐渐变高，且每列从前到后也逐渐变高.

5.2 概率统计

概率统计题型近几年主要考察递推关系.

例9.  几何分布期望与方差.

几何分布：伯努利实验中，记每次试验中事件发生的概率为，试验进行到事件出现时停止，此时所进行的试验次数为，其分布列为：，记为，因为此分布列是几何数列的一般项，故称几何分布.

若，则

，

故.

注：

①

② 以记第次成功出现时的试验次数，则亦是随机变量，称其概率分布为巴斯卡分布：，其中，记作，显然，的巴斯卡分布即几何分布.

③ 以记第次成功出现时所经历的失败次数，则，有些资料上把这个称为巴斯卡分布，几何分布亦是如此定义，

例10. 投掷一枚质量均匀的硬币，若出现两次正面向上即停止，问总投掷次数的数学期望.

（2017年清华大学暑期学校）

解法1. 显然，本题是的巴斯卡分布，记投掷次数为，则

那么

由于，故当时，.

解法2. 采用递推关系

，其中表示第一次不成功，表示第一次成功，为从第次开始，成功一次所需次数的随机变量，显然满足几何分布，故，则解得.

点评：（1）解法1中，可处理为，因为的二级导数为，不影响式子的值. ，此处先取极限再求导，因为这两者顺序可交换. 显然，这样处理计算量小得多，此手法使用母函数.

     （2）巴斯卡分布本身就可以分拆为个集合分布的叠加，其期望自然就是几何分布相加，即.

     （3）解法2中这样的递推公式竞赛和自招都比较喜欢考察，也很好用，比如几何分布的期望.

练习：（1）设一个袋子里有红，黄，蓝色小球各一个，现每次从袋子里取出一个小球（取出某色球概率均相同），确定颜色后放回，直到连续两次取出红色球为止，记此时取出球的次数为，则______.

     （2）甲，乙两个赌徒赌博，约定先胜七局者赢得全部赌注，但进行到甲胜局，乙胜局时，因故不得不中止，试问如何分配赌注才公平？

     （3）数学家左，右口袋中各有根火柴的一个火柴盒，每次任取一盒用一根，求发现一盒用光时，另一盒有根火柴的概率.

     （4）四人传球，首次甲传球，问传了次后，球回到甲的概率.

例11.某人上台阶走格的概率是，走格的概率为，问他能走到第格的概率.

解：设走到第格的概率为，则.

点评：典型的递推.

练习.

1. 将长为的线段分成三段，能构成三角形的概率是多少？
2. 上台阶走一格或者两格，现需要走格，请问有多少种走法？
3. 将一枚均匀的硬币连续投掷次，以表示未出现连续次证明的概率.

（1）求；

（2）探究的递推公式并证明；

（3）讨论的单调性及极限，并阐述该极限的概率意义.

4. 均匀正四面体上写有，每轮投掷两个正四面体，若底面数字之和大于则获胜且游戏结束，否则轮到其他玩家，则甲乙两人轮流投掷，由甲开始，问甲能获胜的概率？游戏进行轮数的数学期望？
5. 一袋中有个白球和个黑球，从中任取一个球，取出白球则放回，黑球则不再放回且另补一个白球到袋中，次操作后，袋中白球个数记为.

（1）求的数学期望；

（2）设，求；

（3）证明：的数学期望.

6. 如图，一点从出发，掷一枚骰子，若大于等于点，则沿平行于方向(正反方向均可)移动一步，若小于等于点，则沿平行于方向(正反方向均可)移动一步，投掷次骰子后，回到点的概率为，回到点的概率为.

（1）求；

（2）投掷次骰子经过点次数为，求的分布列；

（3）比较三者大小.