组合数的恒等式

本讲将涉及到组合学的一个重要内容：组合恒等式.从组合数和二项式定理开始，可以得到很多有趣的恒等式.事实上，历史上出现过数以千计的组合恒等式，直到现在仍然有新的恒等式出现.在中科大小丛书《组合恒等式》中，史济怀教授给出了两百多个组合恒等式.

由于现在各级竞赛中对组合恒等式要求大为降低，因此本讲只涉及比较简单的恒等式，以及利用这些恒等式来解决问题

以下给出一些基础知识：

1．二项式定理

*0()()nnknkknkabCabnN

2．二项展开式的通项

1(0)rnrrrnTCabrn它是展开式的第r+1项.

3．二项式系数

(0)rnCrn

4．二项式系数的性质

⑴ (0)knknnCCkn

⑵ 111(01)kkknnnCCCkn

⑶ 若n是偶数，有01122,nnnnnnnnnnCCCCCC，即中间一项的二项式系数2nnC最大.

若n是奇数，有1101122nnnnnnnnnnCCCCCC，即中项二项的二项式系数12nnC和12nnC相等且最大.

⑷ 0122nnnnnnCCCC

⑸ 02413512nnnnnnnCCCCCC

⑹ 11kknnkCnC和11kknnnCCk 本讲概述 第3讲 组合恒等式 ⑺ ()kmmkmkmmnknnmnnkmCCCCCCmkn

⑻ 1121nnnnnnnnnknkCCCCC

以上组合恒等式（是指组合数mnC满足的恒等式）是证明一些较复杂的组合恒等式的基本工具.

5．证明组合恒等式的方法常用的有

⑴ 公式法，利用上述基本组合恒等式进行证明

⑵ 利用二项式定理，通过赋值法或构造法用二项式定理于解题中

⑶ 利用数学归纳法

⑷ 构造组合问题模型，将证明方法划归为组合应用问题的解决方法

【原创】关于第二类组合数相乘求和的恒等式

在组合数学中，关于组合数序列相乘求和的类型，存在两种组合数序列（C(i,n)，C(m,i+m)），分别对应杨辉三角（PASCAL Triangle）的横向与斜向。

二项式公式及朱世杰恒等式

不依顺序只有三大基本类型｛第一类组合数对应相乘求和、第一类与第二类组合数对应相乘求和以及第二类组合数对应相乘求和｝；

①朱世杰-范得蒙恒等式

②双组合二项式

③三角乘积垛公式

若k=m，则 b 为李善兰恒等式（三角自乘垛公式）；

若k=0，则 a b 皆为朱世杰恒等式。

第二类组合数相乘求和的部分证明（推导过程略，主要是数学归纳法证明）这个恒等式包括了朱世杰恒等式与李善兰恒等式以及其它一些垛积术公式，只要对它作适当变形，就成为大家熟悉的垛积公式，下图中有例子

上传后的图片效果差得要命

百度文邮-让每个人平零地捉升口我

4（

2

1引言

组合恒等式是组合数学的一个重要部份•它在数学的各个分支中都有普遍

应用,而且它的证明方式多种多样，具有很强的灵活性•下面通过几个实例具体讲

述一下，几种证法在组合恒等式中的运用.

2代数法

通常利用组合恒等式的一些性质进行讣算或化简，使得等式两边相等， 或利用二项式定理（x+y）ll= 'Yjc：txryn r在展开式中令％和y为某个特定的 r=0

值，也可以先对二项式定理利用幕级数的微商或积分后再代值，得出所需要的 恒等式.

例 1 C；,+, + C；-1 + 2C； = n > m .

分析：这个等式两边都很简单，咱们可以利用一些常常利用的组合恒等 式去求证.

证明:W+CJ+2C： =C 鷲

• “ ■ 111 +1 八“

亠 j fl Ifl … •••左边=c （—- + —-— + 2） m+1 n+1 m

二⑴（"+加+ 2 * 加 ） m + 1 〃 +1 — m

/ （it + m + 2）（/1 +1 一 m） + m2 + m、

（in + l）（n +1 - m）

n2 +3n + 2

（〃?+ l）（n +1— 〃?）

（〃 + 2）（〃 +1）

（加+ 1）（" +1—〃7）

右边二 = G + 2)! = s + 2)(n + l)川

心(n + \—m) !(加 +1)! (m +1)(〃 +1-m)(n 一 m)!m! VC：

m

c：（ 百度文库•让每个人平等地捉升口我

3

=J G + l)S + 2)

"(〃 + 1—加)(〃？ + 1)

左侧二右边

即证.

例2 求证:3” + C：3”" + C; 3心 + …+ C；J 31 + C；； 3° = 22n .

分析：看到上式，很容易想到二项式的展开式，尝试利用二项式定理去 做.

证明：

山二项式定理成立恒等式，

(3 + ”)" = 3” + C* 3”" x + C： 3,,_2 F + …+ C：；“ 3xn~l + xH

组合数定理

1. 引言

组合数定理是组合数学中的一项重要理论。在计算组合问题时，我们经常需要计算从n个元素中选取k个元素的组合数。而组合数定理提供了一种便捷的方法来计算这些组合数。

2. 组合数的定义

在介绍组合数定理之前，我们先来回顾一下组合数的定义。

定义1： 从n个元素中选取k个元素的组合数，记作C(n,k)，表示从n个元素中选取k个元素的不同方式的数量。其中，n和k都是非负整数，并且满足0 <= k

<= n。

根据定义，我们可以得到以下公式来计算组合数：

公式1： C(n,k) = n! / (k! * (n-k)!)

其中，“!”表示阶乘运算。

3. 组合数定理

在实际应用中，我们经常需要计算大量的组合数。直接使用公式1进行计算可能会导致复杂度较高，并且容易出现溢出等问题。为了解决这些问题，我们引入了组合数定理。

定理1（二项式定理）： 对于任意非负整数n和整数m，有以下等式成立：

(1 + x)^n = C(n,0) * x^0 + C(n,1) * x^1 + C(n,2) * x^2 + … + C(n,n) *

x^n

该等式被称为二项式定理，其中(1 + x)^n表示一个多项式的展开形式。

根据定理1，我们可以通过展开(1 + x)^n来计算组合数C(n,k)。具体方法如下：

方法1： 展开(1 + x)n，并观察xk的系数，即可得到C(n,k)的值。

例如，当n=4时，展开(1+x)^4可以得到：

(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4

观察上述展开式中x的指数和系数，可以得到C(4,0)=1、C(4,1)=4、C(4,2)=6、C(4,3)=4和C(4,4)=1。

通过这种方法，我们可以快速计算出较小规模的组合数。 4. 组合数定理的应用

组合数定理在实际问题中有广泛的应用。下面我们介绍一些常见的应用场景。

4.1. 排列组合问题

在排列组合问题中，我们经常需要计算从一组元素中选取若干个元素进行排列或组合的方式数量。通过使用组合数定理，我们可以方便地计算出这些数量。