组合恒等式

组合恒等式

㈠、二项式定理

k k n −k k k k 定理1： x +y n = n ,特别的 (1+x) n = n 0C n y x 0C n x ,其中n 为正整数, Cn =

n n −1 … n −k+1

k ! 0=1. 1≤k ≤n , C n

（二）、基本组合恒等式

n =C m −n （1）C m m

n n +C n −1 （2）C m+1=C m m

k k −1k −1 （3）kC n =nC n −1=（n −k +1）C n

k C m =C m C k −m =C k −m C m （4）C n n n −m n k n −k+m

1n （5）1+C n +⋯C n =2n

1+C 2−⋯+（−1）C n =0 （6）1−C n n n

1（7）C n 3+C n 2 +1C n 2n n +⋯+=1+2C n +⋯2 +C n 2n =2n −1

01k k （8）C n +C n +1+⋯+C n+k=C n+k+1

n n n n+1（9）C n +C n+1+⋯+C n+m=C n+m+1

0C k +C 1C k −1+C 2C k −2+⋯+C k C 0=C k （10）（范德蒙恒等式）C m n m n m n m n m+n

0）（11）（C n 2+1）（C n 2+n ）⋯+（C n 2n =C 2n

k n −1 （12） n k=0kC n =n ∙2

2k n −2（13） n k=0k C n =n （n +1）2

k m n −m C m （14） n n k=mC n C k =2

n =2C 2+n 2 （15）C 2n n

k （16）C −n k n k

k ！=（−1）i C j =C r （17） i+j=rC m m+n n

i C j =C n+r （18） i −j =rC m m+nn

k m m （19） m k=0（−1）C n =(−1) C n −1

k 2n −1+C n （20） n k=0C 2n =222n

k C m =C m 2n −m （21） k C n n k 1k

（22） k ≥0（−1）k 2k C n =2cos

n n 2n π4 2k+1=22sin n π （23） k ≥0（−1）C n 4

r s r+s+1（24） k ≥0C m −k C k =C m+1

k k n −k n n （25）（李善兰恒等式） n k=0C x C y C x+y+n−k =C x+nC y+n k

k k n k k n 命题1：若P （x ）是次数＜n 的多项式, 则 n k=0−1C n p k =0，k=0−1C n k =

（−1）n ！

（三）、组合恒等式基本证明方法

恒等变形、求和换序、数学归纳法、微积分方法、母函数方法、应用递归关系、运用组合解释、复数法、差分法、网络路径数、WZ 方法、算子方法、利用组合互逆公式等

1. 母函数方法

应用母函数方法证明组合恒等式时，常常是适当选择一个母函数，用两种不同的方法将它展开成两个幂级数，则由同次幂的系数相等便得到要证明的组合恒等式.

2. 算子方法

n 设p x 表示如下形状的形式幂级数组成的集合：f x = ∞n=0a n x . 特别，如果

a 0，a 1，……，a n ，……中只有有限个数不等于0，那么f x 为多项.

n ∞n 对任意f x = ∞n=0a n x ，g （x ） n=0b n x ，我们定义：

n （1）k f x = ∞n=0（ka n ）x （k 为常数）

n （2）f x ±g x = ∞n=0（a n ±b n ）x

n ∞（3）f x g x = ∞n=0C n x ，其中C n = k=0a k b n −k . n

对任意f x ∈p x ，我们定义算子：C k f x =a ，即C k f x 为f x 展开式中x k 的系数. 由此定义我们易知算子C k f x 有下列性质成立：

（1）对任意f x ∈p x 及常数a ，C k af x =aC k f x .

（2）对任意f （x ），g （x ）∈p x ，C k f x ±g （x ） =C k f x ±C k g x ；

C k f x g （x ） = k i=0C i f x C k −i g x .

（3）对任意正整数n,k 及f （x ），g （x ）

∈p x ，当n ＞k 时，C k f x =C n x n −k f x ，C k f x =C k f x +x n g （x ） .

k a n −k b （当k k =0）公式I:当n,k 为正整数，a,b 为常数时，C k （a +bx ） =C n n ＜k 时，约定C n .

m −1a k =C k k 公式II:设m,k 为正整数时，a 为常数，则C k 1−ax −m =C k+m−1k+m−1a x ＜ . n

公式III ：设m,n 为非负整数，a,b 为常数，则C k

（a −b ）x ） . m （1+ax）m （1+bx）=C k （1−bx ）n −m+k（1+

3. 差分方法

设f （x ）为任意函数，Δ为差分算子，其定义为Δf x =f x +1 −f x ，Δk f x =Δ Δk −1f x k =2，3，… ，以算子Δ作成的差分多项式P （Δ）=