计数原理与二项式定理A组——大题保分练1．设集合A，B是非空集合M的两个不同子集，满足：A不是B的子集，且B也不是A的子集．(1)若M＝{a1，a2，a3，a4}，直接写出所有不同的有序集合对(A，B)的个数；(2)若M＝{a1，a2，a3，…，an}，求所有不同的有序集合对(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)有(2k－1)＝2k－＝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，…，an的个数为f(n)(n≥2，n∈N*)．性质T：排列a1，a2，…，an中有且只有一个ai＞ai＋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}，使得ai＞ai＋1的排列有(1,3,2)，(2,1,3)，(2,3,1)，(3,1,2)，所以f(3)＝4.(2)在1,2，…，n的所有排列(a1，a2，…，an)中，若ai＝n(1≤i≤n－1)，从n－1个数1,2,3，…，n－1中选i－1个数按从小到大的顺序排列为a1，a2，…，ai－1，其余按从小到大的顺序排列在余下位置，于是满足题意的排列个数为C.若an＝n，则满足题意的排列个数为f(n－1)．综上，f(n)＝f(n－1)＋＝f(n－1)＋2n－1－1.从而f(n)＝－(n－3)＋f(3)＝2n－n－1.3．(2018·南京、盐城一模)已知n∈N*，nf(n)＝CC＋2CC＋…＋rCC＋…＋nCC.(1)求f(1)，f(2)，f(3)的值；(2)试猜想f(n)的表达式(用一个组合数表示)，并证明你的猜想．解：(1)由条件，nf(n)＝CC＋2CC＋…＋rCC＋…＋nCC，①在①中令n＝1，得f(1)＝CC＝1.在①中令n＝2，得2f(2)＝CC＋2CC＝6，得f(2)＝3.在①中令n＝3，得3f(3)＝CC＋2CC＋3CC＝30，得f(3)＝10.(2)猜想f(n)＝C(或f(n)＝C)．欲证猜想成立，只要证等式nC＝CC＋2CC＋…＋rCC＋…＋nCC成立．法一：(直接法)当n＝1时，等式显然成立．当n≥2时，因为rC＝＝＝n×＝nC，故rCC＝(rC)C＝nCC.故只需证明nC＝nCC＋nCC＋…＋nC·C＋…＋nCC.即证C＝CC＋CC＋…＋CC＋…＋CC.而C＝C，故即证C＝CC＋CC＋…＋CC＋…＋CC.②由等式(1＋x)2n－1＝(1＋x)n－1(1＋x)n可得，左边xn的系数为C.而右边(1＋x)n－1(1＋x)n＝(C＋Cx＋Cx2＋…＋Cxn－1)(C＋Cx＋Cx2＋…＋Cxn)，所以xn的系数为CC＋CC＋…＋C·C＋…＋CC.由(1＋x)2n－1＝(1＋x)n－1(1＋x)n恒成立可得②成立．综上，f(n)＝C成立．法二：(构造模型)构造一个组合模型，一个袋中装有(2n－1)个小球，其中n个是编号为1,2，…，n的白球，其余(n－1)个是编号为1,2，…，n－1的黑球．现从袋中任意摸出n个小球，一方面，由分步计数原理其中含有r个黑球((n－r)个白球)的n个小球的组合的个数为C·C，0≤r≤n－1，由分类计数原理有从袋中任意摸出n个小球的组合的总数为CC＋CC＋…＋CC＋…＋CC.另一方面，从袋中(2n－1)个小球中任意摸出n个小球的组合的个数为C.故C＝CC＋CC＋…＋CC＋…＋CC，余下同法一．法三：(利用导数)由二项式定理，得(1＋x)n＝C＋Cx＋Cx2＋…＋Cxn.③两边求导，得n(1＋x)n－1＝C＋2Cx＋…＋rCxr－1＋…＋nCxn－1.④③×④，得n(1＋x)2n－1＝(C＋Cx＋Cx2＋…＋Cxn)·(C＋2Cx＋…＋rCxr－1＋…＋nCxn－1)．⑤左边xn的系数为nC.右边xn的系数为CC＋2CC＋…＋rCC＋…＋nCC＝CC＋2CC＋…＋rCC＋…＋nCC＝CC＋2CC＋…＋rCC＋…＋nCC.由⑤恒成立，得nC＝CC＋2CC＋…＋rCC＋…＋nCC.故f(n)＝C成立．法四：(构造模型)由nf(n)＝CC＋2CC＋…＋rCC＋…＋nCC，得nf(n)＝nCC＋(n－1)CC＋…＋CC＝nCC＋(n－1)CC＋…＋CC，所以2nf(n)＝(n＋1)(CC＋CC＋…＋CC)＝(n＋1)(CC＋CC＋…＋CC)，构造一个组合模型，从2n个元素中选取(n＋1)个元素，则有C种选法，现将2n个元素分成两个部分n，n，若(n＋1)个元素中，从第一部分中取n个，第二部分中取1个，则有CC种选法，若从第一部分中取(n－1)个，第二部分中取2个，则有CC种选法，…，由分类计数原理可知C＝CC＋CC＋…＋CC.故2nf(n)＝(n＋1)C，所以f(n)＝·＝＝C....
