计数原理与二项式定理A组——大题保分练1．设集合A,B是非空集合M的两个不同子集,满足：A不是B的子集,且B也不是A的子集．(1)若M＝{a1,a2,a3,a4},直接写出所有不同的有序集合对(A,B)的个数；(2)若M＝{a1,a2,a3,…,a n},求所有不同的有序集合对(A,B)的个数．解：(1)110.(2)集合M有2n个子集,不同的有序集合对(A,B)有2n(2n－1)个．当A⊆B,并设B中含有k(1≤k≤n,k∈N*)个元素,则满足A⊆B的有序集合对(A,B)有n∑k＝1C k n(2k－1)＝n∑k＝0C k n2k－n∑k＝0C k n＝3n－2n个．同理,满足B⊆A的有序集合对(A,B)有3n－2n个．故满足条件的有序集合对(A,B)的个数为2n(2n－1)－2(3n－2n)＝4n＋2n－2×3n.2．记1,2,…,n满足下列性质T的排列a1,a2,…,a n的个数为f(n)(n≥2,n∈N*)．性质T：排列a1,a2,…,a n中有且只有一个a i＞a i＋1(i∈{1,2,…,n－1})．(1)求f(3)；(2)求f(n)．解：(1)当n＝3时,1,2,3的所有排列有(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2), (3,2,1),其中满足仅存在一个i∈{1,2,3},使得a i＞a i＋1的排列有(1,3,2),(2,1,3),(2,3,1), (3,1,2),所以f(3)＝4.(2)在1,2,…,n的所有排列(a1,a2,…,a n)中,若a i＝n(1≤i≤n－1),从n－1个数1,2,3,…,n－1中选i－1个数按从小到大的顺序排列为a1,a2,…,a i－1,其余按从小到大的顺序排列在余下位置,于是满足题意的排列个数为C i－1n－1.若a n＝n,则满足题意的排列个数为f(n－1)．综上,f(n)＝f(n－1)＋n－1∑i＝1C i－1n－1＝f(n－1)＋2n－1－1.从而f (n )＝23 1－2n －31－2－(n －3)＋f (3)＝2n －n －1.3．(2018·南京、盐城一模)已知n ∈N*,nf (n )＝C 0n C 1n ＋2C 1n C 2n ＋…＋r C r －1n C r n ＋…＋n C n －1n C n .(1)求f (1),f (2),f (3)的值；(2)试猜想f (n )的表达式(用一个组合数表示),并证明你的猜想．解：(1)由条件,nf (n )＝C 0n C 1n ＋2C 1n C 2n ＋…＋r C r －1n C r n ＋…＋n C n －1n C n ,①在①中令n ＝1,得f (1)＝C 01C 11＝1.在①中令n ＝2,得2f (2)＝C 02C 12＋2C 12C 22＝6,得f (2)＝3.在①中令n ＝3,得3f (3)＝C 03C 13＋2C 13C 23＋3C 23C 33＝30,得f (3)＝10.(2)猜想f (n )＝C n2n －1(或f (n )＝C n －12n －1)．欲证猜想成立,只要证等式n C n2n －1＝C 0n C 1n ＋2C C ＋…＋r C －C ＋…＋n C C n成立．法一：(直接法)当n ＝1时,等式显然成立．当n ≥2时,因为r C r n＝r ×n ！r ！ n －r ！＝n ！ r －1 ！ n －r ！＝n × n －1 ！ r －1 ！ n －r ！＝n C r －1n －1, 故r C r －1n C r n ＝(r C r n )C r －1n ＝n C r －1n －1C r －1n .故只需证明n C n2n －1＝n C 0n －1C 0n ＋n C 1n －1C 1n ＋…＋n C r －1n －1·C r －1n ＋…＋n C n －1C n －1n .即证C n2n －1＝C 0n －1C 0n ＋ C 1n －1C 1n ＋…＋ C r －1n －1C r －1n ＋…＋ C n －1C n －1n .而C r －1n ＝C n －r ＋1n ,故即证C n 2n －1＝C 0n －1C n n ＋ C 1n －1C n －1n ＋…＋ C r －1n －1C n －r ＋1n ＋…＋ C n －1n －1C 1n .②由等式(1＋x )2n －1＝(1＋x )n －1(1＋x )n 可得,左边x n 的系数为C n2n －1.而右边(1＋x )n －1(1＋x )n ＝(C 0n －1＋C 1n －1x ＋C 2n －1x 2＋…＋C n －1x n －1)(C 0n ＋C 1n x ＋C 2n x 2＋…＋C n x n ),所以x n 的系数为C 0n －1C n ＋ C 1n －1C n －1n ＋…＋ C r －1n －1·C n －r ＋1n ＋…＋ C n －1C 1n .由(1＋x )2n －1＝(1＋x )n －1(1＋x )n 恒成立可得②成立．综上,f(n)＝C n2n－1成立．法二：(构造模型)构造一个组合模型,一个袋中装有(2n－1)个小球,其中n个是编号为1,2,…,n的白球,其余(n－1)个是编号为1,2,…,n－1的黑球．现从袋中任意摸出n个小球,一方面,由分步计数原理其中含有r个黑球((n－r)个白球)的n个小球的组合的个数为C r n－1·C n－r n,0≤r≤n－1,由分类计数原理有从袋中任意摸出n个小球的组合的总数为C0n－1 C n＋C1n－1C n－1n＋…＋C r－1n＋…＋C n－1C1n.n－1C n－r＋1另一方面,从袋中(2n－1)个小球中任意摸出n个小球的组合的个数为C n2n－1.故C n2n－1＝C0n－1C n n＋ C1n－1C n－1n＋…＋ C r－1n＋…＋ C n－1n－1C1n,余下同法一．n－1C n－r＋1法三：(利用导数)由二项式定理,得(1＋x)n＝C0n＋C1n x＋C2n x2＋…＋C n x n.③两边求导,得n(1＋x)n－1＝C1n＋2C2n x＋…＋r C r n x r－1＋…＋n C n n x n－1.④③×④,得n(1＋x)2n－1＝(C0n＋C1n x＋C2n x2＋…＋C n n x n)·(C1n＋2C2n x＋…＋r C r n x r－1＋…＋n C n x n－1)．⑤左边x n的系数为n C n2n－1.右边x n的系数为C1n C n＋2C2n C n－1n＋…＋r C r n C n－r＋1n＋…＋n C n C1n＝C1n C0n＋2C2n C1n＋…＋r C r n C r－1n＋…＋n C n C n－1n＝C0n C1n＋2C1n C2n＋…＋r C r－1n C r n＋…＋n C n－1n C n.由⑤恒成立,得n C n2n－1＝C0n C1n＋2C1n C2n＋…＋r C r－1n C r n＋…＋n C n－1n C n n.故f(n)＝C n2n－1成立．法四：(构造模型)由nf(n)＝C0n C1n＋2C1n C2n＋…＋r C r－1n C r n＋…＋n C n－1n C n,得nf(n)＝n C n－1n C n＋(n－1)C n－2n C n－1n＋…＋C0n C1n＝n C0n C1n＋(n－1)C1n C2n＋…＋C n－1n C n,所以2nf(n)＝(n＋1)(C0n C1n＋C1n C2n＋…＋C n－1n C n n) ＝(n＋1)(C n n C1n＋C n－1n C2n＋…＋C1n C n n),构造一个组合模型,从2n个元素中选取(n＋1)个元素,则有C n＋12n种选法,现将2n个元素分成两个部分n,n,若(n＋1)个元素中,从第一部分中取n个,第二部分中取1个,则有C n n C1n种选法,若从第一部分中取(n－1)个,第二部分中取2个,则有C C种选法,…,由分类计数原理可知C n＋12n＝C n n C1n＋C n－1n C2n＋…＋C1n C n n.故2nf(n)＝(n＋1)C n＋12n,所以f (n )＝n ＋12n · 2n ！ n ＋1 ！ n －1 ！＝ 2n －1 ！n ！ n －1 ！＝C n 2n －1.4．(2018·苏锡常镇调研(二))已知函数f (x )＝(x ＋5)2n ＋1(n ∈N *,x ∈R )．(1)当n ＝2时,若f (2)＋f (－2)＝5A ,求实数A 的值；(2)若f (2)＝m ＋α(m ∈N *,0<α<1),求证：α(m ＋α)＝1.解：(1)当n ＝2时,f (x )＝(x ＋5)5＝C 05x 5＋C 15x 45＋C 25x 3(5)2＋C 35x 2(5)3＋C 45x (5)4＋C 5(5)5,所以f (2)＋f (－2)＝(2＋5)5＋(－2＋5)5＝2[C 15(5)124＋C 35(5)322＋C 5(5)5]＝2(5×165＋10×4×55＋255)＝6105,所以A ＝610.(2)证明：因为f (x )＝(x ＋5)2n ＋1＝C 02n ＋1x 2n ＋1＋C 12n ＋1x 2n 5＋C 22n ＋1x 2n －1(5)2＋…＋C 2n ＋1(5)2n ＋1,所以f (2)＝C 02n ＋122n ＋1＋C 12n ＋122n 5＋C 22n ＋122n －1(5)2＋…＋C 2n ＋1(5)2n ＋1,由题意知,f (2)＝(5＋2)2n ＋1＝m ＋α(m ∈N *,0<α<1),首先证明对于固定的n ∈N *,满足条件的m ,α是唯一的．假设f (2)＝(2＋5)2n ＋1＝m 1＋α1＝m 2＋α2(m 1,m 2∈N *,0<α1<1,0<α2<1,m 1≠m 2,α1≠α2),则m 1－m 2＝α2－α1≠0,而m 1－m 2∈Z ,α2－α1∈(－1,0)∪(0,1),矛盾．所以满足条件的m ,α是唯一的. 下面我们求m 及α的值：因为f (2)－f (－2)＝(2＋5)2n ＋1－(－2＋5)2n ＋1＝(2＋5)2n ＋1＋(2－5)2n ＋1＝2[C02n ＋122n ＋1＋C 22n ＋1·22n －1(5)2＋C 42n ＋122n －3(5)4＋…＋C 2n 2n ＋121(5)2n ],显然f (2)－f (－2)∈N *. 又因为5－2∈(0,1),故(5－2)2n ＋1∈(0,1),即f (－2)＝(－2＋5)2n ＋1＝(5－2)2n ＋1∈(0,1).所以令m ＝2[C 02n ＋122n ＋1＋C 22n ＋122n －1(5)2＋C 42n ＋1·22n －3(5)4＋…＋C 2n 2n ＋121(5)2n ],α＝(－2＋5)2n ＋1,则m ＝f (2)－f (－2),α＝f (－2),又m ＋α＝f (2),所以α(m ＋α)＝f (－2)·f (2)＝(2＋5)2n ＋1·(－2＋5)2n ＋1＝(5－4)2n ＋1＝1.B 组——大题增分练1．(2016·江苏高考)(1)求7C 36－4C 47的值；(2)设m ,n ∈N *,n ≥m ,求证：(m ＋1)C m m ＋(m ＋2)·C mm ＋1＋(m ＋3)C m m ＋2＋…＋n C m n －1＋(n ＋1)C mn ＝(m ＋1)C m ＋2n ＋2.解：(1)7C 36－4C 47＝7×6×5×43×2×1－4×7×6×5×44×3×2×1＝0.(2)证明：当n ＝m 时,结论显然成立．当n ＞m 时,(k ＋1)C mk ＝ k ＋1 ·k ！m ！· k －m ！＝(m ＋1)·k ＋1 ！m ＋1 ！·[ k ＋1 － m ＋1 ]！＝(m ＋1)C m＋1k ＋1,k ＝m ＋1,m ＋2,…,n .又因为C m＋1k ＋1＋C m ＋2k ＋1＝C m ＋2k ＋2,所以(k ＋1)C mk ＝(m ＋1)(C m ＋2k ＋2－C m ＋2k ＋1),k ＝m ＋1,m ＋2,…,n .因此,(m ＋1)C m m ＋(m ＋2)C m m ＋1＋(m ＋3)C m m ＋2＋…＋(n ＋1)C m n ＝(m ＋1)C m m ＋[(m ＋2)C m m ＋1＋(m ＋3)C m m ＋2＋…＋(n ＋1)C m n ]＝(m ＋1)C m ＋2＋(m ＋1)[(C 2m ＋3－C m ＋2)＋(C 2m ＋4－C 2m ＋3)＋…＋(C m ＋2n ＋2－C m ＋2n ＋1)]＝(m ＋1)C m＋2n ＋2.2．(2018·南京、盐城二模)现有n n ＋12(n ≥2,n ∈N *)个给定的不同的数随机排成一个下图所示的三角形数阵：******………………………………**…………**…………第1行…………第2行…………第3行…………第n 行设M k 是第k 行中的最大数,其中1≤k ≤n ,k ∈N *.记M 1<M 2<…<M n 的概率为p n.(1)求p 2的值；(2)证明：p n >C 2n ＋1n ＋1 ！.解：(1)由题意知p 2＝2A 2A 3＝23,即p 2的值为23.(2)证明：先排第n 行,则最大数在第n 行的概率为n n n ＋1 2＝2n ＋1；去掉第n 行已经排好的n 个数,则余下的n n ＋12－n ＝n n －12个数中最大数在第n －1行的概率为n －1n n －1 2＝2n；…故p n ＝2n ＋1×2n ×…×23＝2n －1 n ＋1 ×n ×…×3＝2nn ＋1 ！.由于2n ＝(1＋1)n ＝C 0n ＋C 1n ＋C 2n ＋…＋C n n ≥C 0n ＋C 1n ＋C 2n >C 1n ＋C 2n ＝C 2n ＋1,故2n n ＋1 ！>C 2n ＋2 n ＋1 ！,即p n >C 2n ＋1 n ＋1 ！.3．(2018·苏州暑假测试)设集合M ＝{－1,0,1},集合A n ＝{(x 1,x 2,…,x n )|x i ∈M ,i ＝1,2,…,n },集合A n 中满足条件“1≤|x 1|＋|x 2|＋…＋|x n |≤m ”的元素个数记为S n m .(1)求S 2和S 42的值；(2)当m <n 时,求证：S n m<3n ＋2m ＋1－2n ＋1.解：(1)S 2＝8,S 42＝32.(2)证明：设集合P ＝{0},Q ＝{－1,1}．若|x 1|＋|x 2|＋…＋|x n |＝1,即x 1,x 2,x 3,…,x n 中有n －1个取自集合P,1个取自集合Q ,故共有C n －1n 21种可能,即为C 1n 21,同理,|x 1|＋|x 2|＋…＋|x n |＝2,即x 1,x 2,x 3,…,x n 中有n －2个取自集合P,2个取自集合Q ,故共有C n －2n 22种可能,即为C 2n 22,若|x 1|＋|x 2|＋…＋|x n |＝m ,即x 1,x 2,x 3,…,x n 中有n －m 个取自集合P ,m 个取自集合Q ,故共有C n －m n 2m 种可能,即为C m n 2m ,所以S n m＝C 1n 21＋C 2n 22＋…＋C m n 2m ,。