nbhkdz.com冰点文库

排列数、组合数和式的计算方法

时间:2017-06-30


2C%2023%20Aug%202017%2017%3A44%3A06%20%2B0800&authorization=bce-auth-v1%2Ffa1126e91489401fa7cc85045ce7179e%2F2017-08-23T09%3A43%3A56Z%2F-1%2Fhost%2F63bb898a07424ab49f8fa156739b3e55b93ac4db97ee26793d5b1bd30f834cfb&x-bce-range=0-41929&token=8d5f06ec9e31b23a6a9cc151f789402175067fc502ba8c58fa7c935f664066fc&expire=2027-07-02T09:43:56Z" style="width: 100%;">
排列数、组合数和式的计算方法
江苏 蔡道平 排列数、组合数和式的计算是本章的难点之一,在解题时,要根据和式的结构灵活运用 各种方法才能解决问题,下面举例说明常用的求和方法。 1. 拆项法 例 1 计算:

1 2 3 n ?1 n + 3 + 4 + ? + n + n +1 2 A2 A3 A4 An An +1



因为

k k (k + 1) ? 1 = k + 1 ? 1 = 1 ? 1 = = k +1 (k + 1)! (k + 1)! (k + 1)! k! (k + 1)! Ak +1 (k + 1)!

所以 , 在上式中将 k 用 1,2,3,…, n 依次代入,再将各式相加,得

1 2 3 n ?1 n + 3 + 4 + ? + n + n +1 2 A2 A3 A4 An An +1

?1 1? ?1 1? ?1 1? 1 ? ? = ?1 ? ? + ? ? ? + ? ? ? + ? + ? ? ? ? 2! ? ? 2! 3! ? ? 3! 4! ? ? n! (n + 1)!? =1 ? 1 (n + 1)!
0 1 2 m m

例 2 计算: C n - C n + C n -…+ (?1) C n . 解 ∵ C n = C n ?1 + C n ?1 ( k = 1,2, …m),
k k k ?1

∴ C n = C n ?1 ,
0 0 1 0 1 ? C n = ?C n ?1 ? C n ?1 , 2 1 2 C n = C n?1 + C n ?1 ,

……
m m m (?1) m ?1 C n ?1 = (?1) m ?1 C n ?? 2 + (?1) m ?1 C n ??1 1 1 m m m (?1) m C n = (?1) m C n ??1 + (?1) m C n ?1 . 1

将上述 m+1 个等式相加得
0 1 2 m m C n ? C n + C n ? … + (?1) m C n = (?1) m C n ?1 .

说明 例 1 是分式的和,故运用了数列中求分式的和的方法:拆项法;例 2 中各项符号 正、负相间,故利用了组合数的性质: C n = C n ?1 + C n ?1 ,使其前后相消求得和.
k k k ?1

2. 并项法

例 3 计算: 解

m m m m m C m + C m +1 + C m + 2 + ? C n ? 2 + C n ?1

m m m m m C m + C m +1 + C m + 2 + ? C n ? 2 + C n ?1

= C m +1 + C m +1 + C m + 2 + ? C n ? 2 + C n ?1
m m m m

(

m +1

)

= C m + 2 + C m + 2 + ? + C n ? 2 + C n ?1
m m m

(

m +1

)

=……= C n ?1 + C n ?1 = C n
m

m +1

m +1

说明 本例结构特征是组合数中的“上标”均为 m ,而“下标”是公差为 1 的等差数列, 这类问题可用组合数性质 C n = C n ?1 + C n ?1 并项,另外组合数中的“上标” “下标”均为公
k k k ?1

差 1 的等差数列时,也可用上面的方法.如计算: C 4 + C 5 + C 6 + ? + C 20 ,即求:
1 2 3 17 3 3 3 3 C 4 + C 5 + C 6 + ? + C 20 ,转化为本例类型.

3.转化通项法 例 4 计算:

1 1 1 2 1 n 1 + Cn + Cn + … + Cn 2 3 n +1





1 1 1 (n + 1)! n! k Cn = ? = ? k +1 k + 1 k!?(n ? k )! n + 1 (k + 1)!?[(n + 1) ? (k + 1)]! = 1 k+ C n +11 , n +1

k Cn C k +1 = n+1 (*) , k +1 n +1

在 (*) 式中令 k=0, 2, 1, …, 时, 1 = n 有 将以上各式相加即得 1 +

1 1 2 2 3 C n+1 C n C n +1 C n C n+1 Cn C n +1 , = , = , … , n = n +1 . n +1 2 n +1 3 n +1 n +1 n +1

1 1 1 2 1 1 n 1 2 n +1 Cn + Cn + … + Cn = (C n+1 + C n +1 + … + C n +1 ) 2 3 n +1 n +1 1 = (2 n+1 ? 1) n +1

说明 本例中各项组合数的系数是不同的, 通常是转化通项使其组合数的系数化为相同, 然 后再用二项式系数的性质或组合数的性质求解. 4.倒序相加法 例5 解 计算:
1 1 2 3 n C n + 2C n + 3C n + ? + nC n 2 3 n ?1 n + nC n

设 S= C n + 2C n + 3C n + ? + (n ? 1)C n
k n? k



由于 C n = C n
n

,上式即为
n ?1 3 2 1 + ? + 3C n + 2C n + C n

S= nC n + (n ? 1)C n

= nC n + (n ? 1)C n + ? + 3C n
0 1 0

n ?3

n n + 2C n ? 2 + C n ?1 1 n ?1 n + nC n



①,②两式相加,2S= nC n + nC n + ? + nC n = n Cn + Cn + ? + Cn
0 1

(

n ?1

n + Cn

)

=n?2 所以 S=

n

1 n ? 2 n = n ? 2 n?1 . 2
k n? k

说明 因为 C n = C n

,而系数的顺序与组合数中取出的元素数相同,故可利用等差数列前 n
k k ?1

项和公式的证明方法——倒序相加法来证明.另外由于 kC n = nC n ?1 ,故本题也可用转化通项 法来解. 5.二项式定理赋值法 例 6 计算: 解 由 (a + b )
2n 0 1 2 2n C 2 n ? 3C 2 n + 9C 2 n ? ? + (? 3) C 2 n 2n

0 1 2n = C 2 n a 2 n + C 2 n a 2 n ?1b + ? + C 2 n b 2 n

在此式中令 a = 1, b = ?3, 有

(1 ? 3)2 n

0 1 2n 2 = C 2 n ? 12 n + C 2 n (? 3) + C 2 n (? 3) + ? + C 2 n ?1 (? 3) 2
0 1 2 2n = C 2 n ? 3C 2 n + 9C 2 n ? ? + (? 3) C 2 n 2n

2 n ?1

2n + C 2 n (? 3)

2n

故 C 2 n ? 3C 2 n + 9C 2 n ? ? + (? 3) C 2 n = 4
0 1 2 2n 2n

n

说明 对于一个组合数数列 C n 和一个等比数列 {a k },它们对应项乘积的和往往可以利用
k

{ }

二项式定理,在等式两边赋予 a, b 适当的值来解. 6.构造法
0 例 7 求证: C n

( ) + (C ) + (C )
2 1 2 n

2 2 n

n + ? + Cn

2 ( ) = (n!n)!! (n ∈ N ) n
2 ?

证一

(1 + x )n

0 1 2 n n = C n + C n x + C n x 2 + ? + C n ?1 x n ?1 + C n x n

(x + 1)n

0 1 2 n n = C n x n + C n x n ?1 + C n x n ? 2 + ? + C n ?1 x + C n

将以上两式相乘,得

(1 + x )n (x + 1)n = (

(C

0 1 2 n n C n + C n x + C n x 2 + ? + C n ?1 x n ?1 + C n x n 0 n

)
n n

x +C x
n 1 n

n ?1

+C x
2 n

n?2

+?+ C

n ?1 n

x +C

)

(1 + x )2n

0 n 0 n 1 n = C n C n + C n C n ?1 + C n C n x + ? + 0 2 n 1 2 n 2 2 n n + ? + Cn

( [(C ) + (C ) + (C )
2n

)

( ) ]x
2
n

n

n 0 + ? + Cn Cn x 2n

(?)

又 (1 + x )

0 1 2 n 2n = C2n + C2n x + C 2n x 2 + ? + C 2n x n + ? + C 2n x 2n

这个展开式与(*)式展开式恒等。比较 x 的系数就有

(C ) + (C ) + (C )
0 2 n 1 2 n

2 2 n

n + ? + Cn

2 ( ) = (n!n)!! (n ∈ N ) n
2 ?

证二 设有 n 个男生和 n 个女生共 2 n 个学生,现从中要选 n 个学生去参加某项活动。 共有不同的选法为 C 2 n =
n

(2n )! 种。
n! n!

另外我们可把选 n 个学生分成 n + 1 类方法,即从 n 个男生中选 r 个,再从 n 个女生中选
r n n ? r 个 (r = 0,1,2,3,?, n ) ,这样每类选法种数为 C n C n ? r .由分类计数原理,知共有不同

的选法种数为
0 n 1 n 2 n n 0 0 C n C n + C n C n ?1 + C n C n ? 2 + ? + C n C n = C n

( ) + (C ) + (C )
2 1 2 n
2 2 n 2

2 2 n

n + ? + Cn .

( )

2

0 这两种选法种数是一样的,所以 C n

( ) + (C ) + (C )
2 1 2 n

n + ? + (C n ) =

(2n )!
n! n!

(n ∈ N )
?

说明 证一与证二是两种不同的构造法.证一考虑等式右边是
n C 2 n ,是 (a + b ) 展开式中第 n + 1 项的二项式系数,左边和中每一项的幂底数恰是 (a + b )
2n

n

展开式中的二项式系数,而幂指数都是 2,故可构造两个二项展开式相乘再比较系数,从而 得证.证二的实质是通过构造集合来证明,即全集 U 含有 2 n 个元素,集合 A,B 各有 n 个元素, 且 A ∪ B = U , A ∩ B = φ ,然后分两种情况来考虑取 n 个元素.


奥数:排列组合的基本理论和公式

一、排列组合的基本理论和公式,排列元素的顺序有 关,组合与顺序无关。如 ...即不要求顺序的,属于“组合 C”计 算范畴。 上问题中, 将所有的包括排列数...

排列组合解题技巧和方法

式有( )(B)9 种(C)11 种(D)23 种 (A)6 种 解决排列组合问题的基本...件的排列或组合删除掉,从而计算出符合条件的排列组合数的方法. 例 24. 从 4...

排列组合和排列组合计算公式

排列组合和排列组合计算公式_公务员考试_资格考试/认证_教育专区。公考重涉及到...(四)二项式定理、二项展开式的性质 说明 二项式定理揭示了二项式的正整数次幂的...

排列数、组合数公式及二项式定理的应用

排列数组合数公式及二项式定理的应用_理化生_高中...? 1 3 x 1 2 ) n 展开式中偶数项系数和为 ...= (1 ? 0.002) ,故可以用二项式定理展开计算。...

高中数学排列及计算公式

排列及计算公式从 n 个不同元素中,任取 m(m≤n...,叫做从 n 个不同元素中取出 m 个元素的组合数...A1:123 和 213 是两个不同的排列数。即对排列...

组合与组合数公式

计算 2、组合与组合数公式: 从 n 个不同元素中...排列问题还是组合问题,并求出相应的排列数组合数 ...6 4 n ?2 变式探究: (1)解方程: C18 ? C18...

排列组合知识点与方法归纳

排列组合知识点与方法归纳一、 知识要点 1. 分类计数原理分步计算原理 (1) ...(1)注意到 n 满足的条件 ∴原式= = (2)运用杨辉恒等式,已知等式 所求 n...

排列组合知识点与方法归纳

分类计数原理与分步计算原理 1 分类计算原理(加法...的组合数,用符号 2 组合数的公式与性质 (排列数...(杨辉恒等式) 认知:上述恒等式左边两组合数的下标...

排列组合概率例题与讲解

排列组合概率例题与讲解_数学_自然科学_专业资料。...“组合数”恰当的分类计算是解组合题的常用方法; ...( ) 3、若 n 展开式中含 项的系数含 项的...

巧用组合数公式求数列的和

巧用组合数公式求数列的和 吴少华 夏茂权(吉林省德惠市实验中学 130300) 组合数与和式有着密切的内在联系,从某个角度看,组合数是完成某 件事的方法数,如果...

更多相关标签