【组合数学】二项式定理与组合恒等式 ( 二项式定理

二项式定理 :

n n n 是正整数 , 对于一切 x x x 和 y y y , 有以下定理 :

( x + y ) n = ∑ k = 0 n ( n k ) x k y n − k (x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k} (x+y)n=k=0∑n​(kn​)xkyn−k

( n k ) \dbinom{n}{k} (kn​) 表示 n n n 元集中取 k k k 个元素的组合数 , 是 集合组合数 C ( n , k ) C(n,k) C(n,k) 的另一种写法 ;

另一个常用形式 ( y = 1 y = 1 y=1 ) :

( 1 + x ) n = ∑ k = 0 n ( n k ) x k (1 + x)^n = \sum_{k=0}^n \dbinom{n}{k}x^k (1+x)n=k=0∑n​(kn​)xk

基本求和公式 ( x = y = 1 x = y =1 x=y=1 ) :

2 n = ∑ k = 0 n ( n k ) 2^n = \sum_{k=0}^n \dbinom{n}{k} 2n=k=0∑n​(kn​)

( n k ) = ( n n − k ) \dbinom{n}{k} = \dbinom{n}{n-k} (kn​)=(n−kn​)

组合分析方法 : ( n k ) \dbinom{n}{k} (kn​) 是求 k k k 个子集选取方法 , ( n n − k ) \dbinom{n}{n-k} (n−kn​) 是求 n − k n-k n−k 个子集的选取方法 , 二者是一一对应的 ;

一般情况下 , ( n k ) \dbinom{n}{k} (kn​) 的下项 , 不超过上项的一半 ; 如果出现 ( 10 8 ) \dbinom{10}{8} (810​) , 就可以写成 ( 10 2 ) \dbinom{10}{2} (210​)

( n k ) = n k ( n − 1 k − 1 ) \dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1} (kn​)=kn​(k−1n−1​)

代入组合数的公式 , 可以得到 等号 = = = 两侧的值是相等的 ;

该公式用于消去系数的 , 示例如下 :

计算 ∑ k = 0 n k ( n k ) \sum\limits_{k=0}^n k\dbinom{n}{k} k=0∑n​k(kn​) 组合式 :

此时需要消去 k k k 系数 ;

使用 n k ( n − 1 k − 1 ) \dfrac{n}{k} \dbinom{n - 1}{k - 1} kn​(k−1n−1​) 代替 ( n k ) \dbinom{n}{k} (kn​) , 有以下计算过程 :

∑ k = 0 n k ( n k ) = ∑ k = 0 n k n k ( n − 1 k − 1 ) \begin{array}{lcl} \sum\limits_{k=0}^n k\dbinom{n}{k} = \sum\limits_{k=0}^n k \dfrac{n}{k} \dbinom{n - 1}{k - 1} \end{array} k=0∑n​k(kn​)=k=0∑n​kkn​(k−1n−1​)​

可以将加和式中的 k k k 约掉 , 此时 n n n 就与求和变量无关了 , 此时可以将 n n n 提取到加和符号 ∑ \sum ∑ 外面 ,

∑ k = 0 n k ( n k ) = ∑ k = 0 n k n k ( n − 1 k − 1 ) = n ∑ k = 0 n ( n − 1 k − 1 ) \begin{array}{lcl} \sum\limits_{k=0}^n k\dbinom{n}{k} &=& \sum\limits_{k=0}^n k \dfrac{n}{k} \dbinom{n - 1}{k - 1} \\\\ &=& n \sum\limits_{k=0}^n \dbinom{n - 1}{k - 1} \end{array} k=0∑n​k(kn​)​==​k=0∑n​kkn​(k−1n−1​)nk=0∑n​(k−1n−1​)​

然后计算 ∑ k = 0 n ( n − 1 k − 1 ) \sum\limits_{k=0}^n \dbinom{n - 1}{k - 1} k=0∑n​(k−1n−1​) ,

二项式定理是 : ( x + y ) n = ∑ k = 0 n ( n k ) x k y n − k (x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k} (x+y)n=k=0∑n​(kn​)xkyn−k

根据二项式定理 , 可以得到 ( 1 + 1 ) n = ∑ k = 0 n ( n k ) (1 + 1)^{n} = \sum\limits_{k=0}^n \dbinom{n}{k} (1+1)n=k=0∑n​(kn​)

推导 : ( 1 + 1 ) n − 1 = ∑ k = 0 n − 1 ( n − 1 k − 1 ) = 2 n − 1 (1 + 1)^{n-1} = \sum\limits_{k=0}^{n-1} \dbinom{n-1}{k-1} = 2^{n-1} (1+1)n−1=k=0∑n−1​(k−1n−1​)=2n−1

之后可以继续进行后续计算 ;

( n k ) = ( n − 1 k ) + ( n − 1 k − 1 ) \dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1} (kn​)=(kn−1​)+(k−1n−1​)

该递推式 , 用于拆项 :

可以将 ( n k ) \dbinom{n}{k} (kn​) 拆成 ( n − 1 k ) + ( n − 1 k − 1 ) \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1} (kn−1​)+(k−1n−1​) 之和 ;

将 ( n − 1 k ) \dbinom{n - 1}{k} (kn−1​) 拆成 ( n k ) − ( n − 1 k − 1 ) \dbinom{n}{k} -\dbinom{n - 1}{k - 1} (kn​)−(k−1n−1​) 之差 ;

将 将 ( n − 1 k − 1 ) \dbinom{n - 1}{k - 1} (k−1n−1​) 拆成 ( n k ) − ( n − 1 k ) \dbinom{n}{k} -\dbinom{n - 1}{k} (kn​)−(kn−1​) 之差;

在一堆求和的组合数中 , 拆分成两个数之差 , 可以抵消很多组合数 ;

经常在大的求和公式中进行化简时使用 ;

使用组合分析的办法证明该公式 :

取 n n n 元集中选取 k k k 子集 , 这是集合组合数 ;

指定其中某个元素 a a a ;

① 包含 a a a 元素 : k k k 子集中包含 a a a 元素的情况组合数 为 ( n − 1 k − 1 ) \dbinom{n - 1}{k - 1} (k−1n−1​) , k k k 子集中包含 a a a , 只需要在除 a a a 元素外 , 剩下的 n − 1 n-1 n−1 个元素中 , 选出 k − 1 k-1 k−1 个元素即可 ;

② 不包含 a a a 元素 : k k k 子集中不包含 a a a 元素的情况组合数 为 ( n − 1 k ) \dbinom{n - 1}{k} (kn−1​) , k k k 子集中不包含 a a a , 只需要在除 a a a 元素外 , 剩下的 n − 1 n-1 n−1 个元素中 , 选出 k k k 个元素即可 ;

以上面证明 帕斯卡 / 杨辉三角 公式为例

组合分析方法使用 : 使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;

使用 比较小的组合数 表示 比较大的组合数 , 称为递推式组合恒等式 ;