组合恒等式
㈠、二项式定理
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 （Δ）=
组合恒等式
㈠、二项式定理
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 （Δ）=