（江苏专用）2020版高考数学一轮复习 第十九章 计数原理 19.1 计数原理与排列组合课件

第十九章计数原理§19.1计数原理与排列组合高考数学(江苏省专用)五年高考A组自主命题·江苏卷题组1.(2018江苏,23,10分)设n∈N*,对1,2,…,n的一个排列i1i2…in,如果当st时,有isit,则称(is,it)是排列i1i2…in的一个逆序,排列i1i2…in的所有逆序的总个数称为其逆序数,例如:对1,2,3的一个排列231,只有两个逆序(2,1),(3,1),则排列231的逆序数为2.记fn(k)为1,2,…,n的所有排列中逆序数为k的全部排列的个数.(1)求f3(2),f4(2)的值;(2)求fn(2)(n≥5)的表达式(用n表示).解析本题主要考查计数原理、排列等基础知识,考查求解能力和推理论证能力.(1)解法一:记τ(abc)为排列abc的逆序数,对1,2,3的所有排列,有τ(123)=0,τ(132)=1,τ(213)=1,τ(231)=2,τ(312)=2,τ(321)=3,所以f3(0)=1,f3(1)=f3(2)=2.对1,2,3,4的排列,利用已有的1,2,3的排列,将数字4添加进去,4在新排列中的位置只能是最后三个位置.因此f4(2)=f3(2)+f3(1)+f3(0)=5.解法二:记τ(abc)为排列abc的逆序数,对1,2,3的所有排列,有τ(123)=0,τ(132)=1,τ(213)=1,τ(231)=2,τ(312)=2,τ(321)=3,所以f3(0)=1,f3(1)=f3(2)=2.对1,2,3,4的排列,若1在首位,则2,3,4的排列逆序数为2,τ(1342)=2,τ(1423)=2.若1在第二个位置,则首位只能是2,3,如果首位是2,则只能是τ(2143)=2,如果首位是3,则只能是τ(3124)=2.若1在第三个位置,则只能是τ(2314)=2,因此,f4(2)=2+1+1+1=5.(2)解法一:对一般的n(n≥4)的情形,逆序数为0的排列只有一个:12…n,所以fn(0)=1.逆序数为1的排列只能是将排列12…n中的任意相邻两个数字调换位置得到的排列,所以fn(1)=n-1.为计算fn+1(2),当1,2,…,n的排列及其逆序数确定后,将n+1添加进原排列,n+1在新排列中的位置只能是最后三个位置.因此,fn+1(2)=fn(2)+fn(1)+fn(0)=fn(2)+n.当n≥5时,fn(2)=[fn(2)-fn-1(2)]+[fn-1(2)-fn-2(2)]+…+[f5(2)-f4(2)]+f4(2)=(n-1)+(n-2)+…+4+f4(2)= .因此,当n≥5时,fn(2)= .解法二:对一般的n(n≥4)的情形,逆序数为0的排列只有一个:12…n,所以fn(0)=1.逆序数为1的排列只能是将排列12…n中的任意相邻两个数字调换位置得到的排列,所以fn(1)=n-1.为计算fn+1(2),若1在首位,则2,3,…,n的排列逆序数为2的排列必有fn(2)个.若1在第二个位置,则首位只能是2或3,如果首位是2,则3,4,…,n的排列逆序数为1的排列必有fn-1(1)=(n-2)个,如果首位是3,则2,4,…,n的排列逆序数为0的排列必有fn-1(0)=1个.若1在第三个位置,则只有τ(2314…n)=2,因此,fn+1(2)=fn(2)+fn+1(1)+fn-1(0)+1=fn(2)+n.当n≥5时,fn(2)=[fn(2)-fn-1(2)]+[fn-1(2)-fn-2(2)]+…+[f5(2)-f4(2)]+f4(2)=(n-1)+(n-2)+…+4+f4(2)=222nn222nn .因此,当n≥5时,fn(2)= .222nn222nn2.(2016江苏,23,10分)(1)求7 -4 的值;(2)设m,n∈N*,n≥m,求证:(m+1) +(m+2) +(m+3) +…+n +(n+1) =(m+1) .36C47CCmm1Cmm2Cmm1CmnCmn22Cmn解析本题主要考查组合数及其性质等基础知识,考查运算求解能力和推理论证能力.(1)7 -4 =7× -4× =0.(2)证法一:当n=m时,结论显然成立.当nm时,(k+1) = =(m+1)· =(m+1) ,k=m+1,m+2,…,n.又因为 + = ,所以(k+1) =(m+1)( - ),k=m+1,m+2,…,n.因此,(m+1) +(m+2) +(m+3) +…+(n+1) =(m+1) +[(m+2) +(m+3) +…+(n+1) ]=(m+1) +(m+1)[( - )+( - )+…+( - )]=(m+1) .证法二:因为(k+1) =(m+1) ,所以(m+1) +(m+2) +(m+3) +…+n +(n+1) 36C47C65432176544321Cmk(1)!!()!kkmkm(1)!(1)![(1)(1)]!kmkm11Cmk11Cmk21Cmk22CmkCmk22Cmk21CmkCmm1Cmm2CmmCmnCmm1Cmm2CmmCmn22Cmm23Cmm22Cmm24Cmm23Cmm22Cmn21Cmn22CmnCmk11CmkCmm1Cmm2Cmm1CmnCmn=(m+1) +(m+1) +…+(m+1) =(m+1)( + + +…+ ).又因为 + = ,所以 + + +…+ = + + +…+ = + +…+ =…= ,所以(m+1) +(m+2) +(m+3) +…+n +(n+1) =(m+1) .证法三:(数学归纳法)对任意的m∈N*,①当n=m时,左边=(m+1)= =m+1,右边=(m+1) =m+1,等式成立.②假设n=k(k≥m)时等式成立,即(m+1) +(m+2) +(m+3) +…+k +(k+1) =(m+1) .则当n=k+1时,左边=(m+1) +(m+2) +(m+3) +…+k +(k+1)· +(k+2) =(m+1) +(k+2) .因为(k+1) =(m+1) , + = ,所以(m+1) +(k+2) =(m+1) +(m+1) =(m+1)( + )=(m+1) .11Cmm12Cmm11Cmn11Cmm12Cmm13Cmm11CmnCkn1Ckn1Ckn11Cmm12Cmm13Cmm11Cmn22Cmm12Cmm13Cmm11Cmn23Cmm13Cmm11Cmn21CmnCmm1Cmm2Cmm1CmnCmn22CmnCmm22CmmCmm1Cmm2Cmm1CmkCmk22CmkCmm1Cmm2Cmm1CmkCmk1Cmk22Cmk1CmkCmk11CmkCkn1Ckn1Ckn22Cmk1Cmk22Cmk12Cmk22Cmk12Cmk23Cmk因此左边=右边,即n=k+1时等式也成立.综合①②可得等式对任意n≥m均成立.证法四:记f(x)=(1+x)m+1+(1+x)m+2+…+(1+x)n+1,其中m,n∈N*,且m≤n,1+x≠1,则f'(x)=(m+1)(1+x)m+(m+2)(1+x)m+1+…+(n+1)(1+x)n,其中xm项的系数为(m+1) +(m+2) +(m+3) +…+n +(n+1) .又f(x)=(1+x)m+1· = ,所以f'(x)= ,其中xm项的系数为(n+2) - .因为(k+1) =(m+1) ,所以(n+2) - =(m+2) - =(m+1) .所以(m+1) +(m+2) +(m+3) +…+n +(n+1) =(m+1) .Cmm1Cmm2Cmm1CmnCmn11(1)1(1)nmxx21(1)(1)nmxxx1212[(2)(1)(1)(1)](1)(1)nmnmnxmxxxxx11Cmn22CmnCmk11Cmk11Cmn22Cmn22Cmn22Cmn22CmnCmm1Cmm2Cmm1CmnCmn22CmnB组统一命题、省(区、市)卷题组考点计数原理与排列组合1.(2018课标全国Ⅰ理,15,5分)从2位女生,4位男生中选3人参加科技比赛,且至少有1位女生入选,则不同的选法共有种.(用数字填写答案)答案16解析本题主要考查组合问题.解法一:从2位女生,4位男生中选3人,且至少有1位女生入选的情况有以下2种:①2女1男:有  =4种选法;②1女2男:有  =12种选法,故至少有1位女生入选的选法有4+12=16种.解法二:从2位女生,4位男生中选3人有 =20种选法,其中选出的3人都是男生的选法有 =4种,所以至少有1位女生入选的选法有20-4=16种.22C14C12C24C36C34C2.(2018浙江,16,4分)从1,3,5,7,9中任取2个数字,从0,2,4,6中任取2个数字,一共可以组成个没有重复数字的四位数.(用数字作答)答案1260解析本题考查排列、组合及其运用,考查分类讨论思想.含有数字0的没有重复数字的四位数共有    =540个,不含有数字0的没有重复数字的四位数共有   =720个,故一共可以组成540+720=1260个没有重复数字的四位数.25C13C13A33A25C23C44A易错警示数字排成数时,容易出错的地方:(1)数字是否可以重复;(2)数字0不能排首位.3.(2017课标全国Ⅱ理改编,6,5分)安排3名志愿者完成4项工作,每人至少完成1项,每项工作由1人完成,则不同的安排方式共有种.答案36解析本题主要考查排列、组合.第一步:将4项工作分成3组,共有 种分法.第二步:将3组工作分配给3名志愿者,共有 种分配方法,故共有 · =36种安排方式.24C33A24C33A方法总结分组、分配问题是排列组合的综合问题,解题思想是先分组后分配.(1)分组问题属于“组合”问题,常见的分组方法有三种:①完全均匀分组,每组元素的个数都相等;②部分均匀分组,应注意不要重复;③完全非均匀分组,这种分组不考虑重复现象.(2)分配问题属于“排列”问题,常见的分配方法有三种:①相同元素的分配问题,常用“挡板法”;②不同元素的分配问题,利用分步乘法计数原理,先分组,后分配;③有限制条件的分配问题,采用分类法求解.4.(2017浙江,16,4分)从6男2女共8名学生中选出队长1人,副队长1人,普通队员2人组成4人服务队,要求服务队中至少有1名女生,共有种不同的选法.(用数字作答)答案660解析本题考查计数原理、排列、组合,排列数、组合数计算,利用间接法解决“至少”类的组合问题,考查推理运算能力.从8人中选出4人,且至少有1名女学生的选法种数为 - =55.从4人中选出队长1人,副队长1人,普通队员2人的选法为 =12种.故总共有55×12=660种选法.48C46C24A5.(2017天津理,14,5分)用数字1,2,3,4,5,6,7,8,9组成没有重复数字,且至多有一个数字是偶数的四位数,这样的四位数一共有个.(用数字作答)答案1080解析本题主要考查计数原理及排列组合的应用.(1)有一个数字是偶数的四位数有   =960个.(2)没有偶数的四位数有 =120个.故这样的四位数一共有960+120=1080个.14C35C44A45A思路分析分两种情况:①有一个数字是偶数的四位数;②没有偶数的四位数.6.(2016课标全国Ⅱ理改编,5,5分)如图,小明从街道的E处出发,先到F处与小红会合,再一起到位于G处的老年公寓参加志愿者活动,则小明到老年公寓可以选择的最短路径条数为. 答案18解析分两步,第一步,从E→F,有6条可以选择的最短路径;第二步,从F→G,有3条可以选择的最短路径.由分步乘法计数原理可知有6×3=18条可以选择的最短路径.7.(2016课标全国