1、 43排列组合与概率5.1排列组合5.1.1 含有相同元素的全排列若个元素，有个元素相同，另有个元素也相同，一直到另有个元素相同，即，这个元素的全排列数为理解方式：方法1. 将个元素彼此之间种交换顺序的排列合并为一种. 方法2. 只选位置.注：此种理解方式其实完全等同于组合数的推导.例1. 走上7级台阶，每次只能上一级或者两级，共有多少种不同的走法？1级13572级0123解：分类，共有4种走法，故.点评：本题亦可用递推公式斐波那契数列.练习：1. 66的方格中停有三辆完全相同的红车和三辆完全相同的黑车，每一行每一列只有一辆车，每辆车占一格，则停放总数为_14400_.2. 在一个44的方格中
2、填入8个1，使得每一行每一列都有2个1，填法的总数为_90_.5.1.2 容斥原理下的错位排列.设集合，其所有元素的一个全排列满足，都有，则称这样的全排列为错位全排列.例2. 证明：错位全排列数为：.证明：记为满足的全排列的集合，则显然由容斥原理，排列数为，证毕.5.1.3 不定方程 的非负整数解.例3. 求证：（1）方程 的正整数解为个.（2）方程 的非负整数解为个.证明：（1）挡板法：（2） 的非负整数解一一对应的正整数解，.练习：两个实数集，若从到的映射使得中每个元素都有原象且，则这样的映射共有（ ）个. . . .5.1.4 二项式定理恒等式：（1） （2） （3）（范德蒙恒等式）其他
3、结论：例4.求中的系数.解法1. .解法2.数列求和.例5. 求的百万位上的数字.解：. 由于则当时，百万位上均为0，故答案为.点评：求形如某一指定位置数字时，常用二项展开式.例6.将一个四棱锥的每个顶点染上一种颜色，并使同一条棱的两个端点异色，共有5种颜色可供使用，则不同的染色方法共有_420_种.解：分类：用5种颜色时：，用4种颜色时：，用5种颜色时：，故总的涂法.练习：用4种不同的颜色涂在三棱台的6个顶点，要求同一条棱上的两点不同颜色，则不同的染色方法共有_264_种.例7. 对于一个四位数，其各位数字至多有两个不相同，试求共有多少个这样的四位数？解法1: 4个，9种.3个和1个，这种情
4、形下，再分为1个0的情形，有种；3个0的情形，有种；没有0的情形，有种. 2个和2个，这种情形下，再分为无0，有种；有0，有种.故共计有种.点评：其中亦可用排除法，比如可用.解法2：全是，9种. 有两个数字，. 第一步：千位，种情况；第二步：再选一个数字，种情况；第三步：百十个位填数字，但不能都与千位相同，故要减1.因此，总的方法为.点评：解法2技巧性更强.练习题1. 解不等式. 2. 的最后位数是.3. 将凸五边形每个顶点染上五种颜色之一，使得每条对角线两个端点颜色不同的染色方法共有种.4. 已知集合且，则符合条件的共有_组.（顺序不同视为不同组）5. 的展开式中，有理数有项.6. 数列共有
5、项，且，则满足条件的数列共有个.7. 红蓝两色车，马，炮各一枚，将这六枚棋子排成一列，其中每对均是红在前，蓝在后，则共有种排法.8. 数列为等差数列，从而中取出三个数，依然构成等差数列，则取法共有种. 注：，即.9. ，则.10. ，若，则.注：11. 在平面直角坐标系中，则以中点为顶点且位置不同的正方形个数为.12. 设，其中，则在排列种，至少有两个相邻的排列的个数为.13. 马路上有编号为的盏路灯，为节能关闭只，但不能关闭相邻，也不能关闭两端，则关灯方法共有种.14. 已知集合满足，若中元素个数不是中元素，中元素个数不是中元素，则满足条件的集合的个数是.15. 若四位数满足，就称其为好数，
6、那么，好数的个数是.16. 从数按从小到大的顺序取出，使得且，那么所有符合要求的取法共有种.17. 记，则（ ） 18. 整数满足，则这样的有（ ）组. 19. 已知是的一个排列，且，则有（ ）种不同排列数. 20. 方程的非负整数解有（ ）组. 21. 若集合的三个子集满足，且，则称为的有序子集列，现，则有（ D ）个有序子集列. 22. 设，则（ ） 23. 为的一个排列，且，则排列共有_个.24. 在圆周十等分点中取四个，可围成梯形个.25. 将个数：个，个，个，个，填入一个矩阵，要求每行每列正好有个偶数，则共有_种填法.26. 从中挑三个不同的数字组成五位数，其中有两个数字各用了两次，
7、如，则这样的五位数共有（ ）个. 27. 从正边形所有顶点中选个，能构成（ ）个钝角三角形. 28. （ ） 以上均不对5.1.5 卡塔兰数：例8. 已知，并且满足，求有序数组的个数.解：依题，中共有个，个，先不考虑记为（*）式，则共有种，接下来考虑排除法，若不符合（*）式，则一定存在一个的自然数，使得：，现将全部改变符号，即有：，对应后则有个，个，反之，对任一个个，个组成的有序数组，其必然存在一个最小的自然数，满足.作对应，显然，与互为逆映射，从而不满足（*）式的个数，就是由个，个组成的有序数组的个数，从而.点评：卡塔兰数在组合数学中常出现在各种计数问题中，其前几项为，其满足 或.主要应用场
8、景：（1）括号化： （2）出栈次序 （3）凸多边形三角划分 （4）给定节点组成二叉树注：2016年三卷高考选择题12题即卡塔兰数的应用.常见等价场景：（1） 个人进入剧场，票价元，有个人有元，个人有元，售票员不带钱，问有多少种方式使得只要带元的人买票，售票员就可以找零.（2） 圆上有个点，连成条线段且不相交（3） 个高矮不同的人排成两排，每排从左到右逐渐变高，且每列从前到后也逐渐变高.5.2 概率统计概率统计题型近几年主要考察递推关系.例9. 几何分布期望与方差.几何分布：伯努利实验中，记每次试验中事件发生的概率为，试验进行到事件出现时停止，此时所进行的试验次数为，其分布列为：，记为，因为此分
9、布列是几何数列的一般项，故称几何分布.若，则，故.注： 以记第次成功出现时的试验次数，则亦是随机变量，称其概率分布为巴斯卡分布：，其中，记作，显然，的巴斯卡分布即几何分布. 以记第次成功出现时所经历的失败次数，则，有些资料上把这个称为巴斯卡分布，几何分布亦是如此定义，例10. 投掷一枚质量均匀的硬币，若出现两次正面向上即停止，问总投掷次数的数学期望.（2017年清华大学暑期学校）解法1. 显然，本题是的巴斯卡分布，记投掷次数为，则那么由于，故当时，.解法2. 采用递推关系，其中表示第一次不成功，表示第一次成功，为从第次开始，成功一次所需次数的随机变量，显然满足几何分布，故，则解得.点评：（1）
10、解法1中，可处理为，因为的二级导数为，不影响式子的值. ，此处先取极限再求导，因为这两者顺序可交换. 显然，这样处理计算量小得多，此手法使用母函数. （2）巴斯卡分布本身就可以分拆为个集合分布的叠加，其期望自然就是几何分布相加，即. （3）解法2中这样的递推公式竞赛和自招都比较喜欢考察，也很好用，比如几何分布的期望.练习：（1）设一个袋子里有红，黄，蓝色小球各一个，现每次从袋子里取出一个小球（取出某色球概率均相同），确定颜色后放回，直到连续两次取出红色球为止，记此时取出球的次数为，则_. （2）甲，乙两个赌徒赌博，约定先胜七局者赢得全部赌注，但进行到甲胜局，乙胜局时，因故不得不中止，试问如何分
11、配赌注才公平？ （3）数学家左，右口袋中各有根火柴的一个火柴盒，每次任取一盒用一根，求发现一盒用光时，另一盒有根火柴的概率. （4）四人传球，首次甲传球，问传了次后，球回到甲的概率.例11.某人上台阶走格的概率是，走格的概率为，问他能走到第格的概率.解：设走到第格的概率为，则.点评：典型的递推.练习.1. 将长为的线段分成三段，能构成三角形的概率是多少？2. 上台阶走一格或者两格，现需要走格，请问有多少种走法？3. 将一枚均匀的硬币连续投掷次，以表示未出现连续次证明的概率.（1） 求；（2） 探究的递推公式并证明；（3） 讨论的单调性及极限，并阐述该极限的概率意义.4. 均匀正四面体上写有，每
12、轮投掷两个正四面体，若底面数字之和大于则获胜且游戏结束，否则轮到其他玩家，则甲乙两人轮流投掷，由甲开始，问甲能获胜的概率？游戏进行轮数的数学期望？5. 一袋中有个白球和个黑球，从中任取一个球，取出白球则放回，黑球则不再放回且另补一个白球到袋中，次操作后，袋中白球个数记为.（1） 求的数学期望；（2） 设，求；（3） 证明：的数学期望.6. 如图，一点从出发，掷一枚骰子，若大于等于点，则沿平行于方向(正反方向均可)移动一步，若小于等于点，则沿平行于方向(正反方向均可)移动一步，投掷次骰子后，回到点的概率为，回到点的概率为.（1） 求；（2） 投掷次骰子经过点次数为，求的分布列；（3） 比较三者大小.
