【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )

一、组合恒等式 ( 递推式 )

组合恒等式 ( 递推式 ) :

1 . ( n k ) = ( n n − k ) \dbinom{n}{k} = \dbinom{n}{n-k} (kn​)=(n−kn​) , 作用 : 化简

2 . ( n k ) = n k ( n − 1 k − 1 ) \dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1} (kn​)=kn​(k−1n−1​) , 作用 : 求和时消去变系数 ;

3 . ( 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​) , 作用 : 求和时拆项 , 将一个组合数拆分成两项之和 , 或两项之差 , 然后合并 ;

二、组合恒等式 ( 变下项求和 ) 简单和

简单和 :

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

1. 证明 ( 二项式定理 ) : 通过二项式定理可以证明 , ( x + y ) n = ∑ k = 0 n ( n k ) x k y n − k (x + y)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k y^{n-k} (x+y)n=k=0∑n​(kn​)xkyn−k 中 , 使 x = y = 1 x=y=1 x=y=1 , 即可得到上面的 简单和 组合恒等式 ;

2. 证明 ( 组合分析 ) : 将等号 左边 和 右边 各看做某个 组合计数问题的解 ,

( 1 ) 左侧 组合计数问题 : ∑ k = 0 n ( n k ) \sum\limits_{k=0}^{n}\dbinom{n}{k} k=0∑n​(kn​) 可以看做 n n n 个元素的所有子集个数 ; ( 这也是集合中的幂集个数 ) ;

这是分类计数 , 最后将所有的类个数相加 , 即包含 0 0 0 个元素个数 , 包含 1 1 1 个元素子集个数 , ⋯ \cdots ⋯ , 包含 n n n 个元素子集个数 ;

( 2 ) 右侧 组合计数问题 : n n n 个元素中 , 每个元素都有 放入子集中 , 不放入子集中 , 两种选择 , 那么所有元素的选择有 , 2 × 2 × ⋯ × 2 ⏟ n 个 = 2 n \begin{matrix} \underbrace{ 2 \times 2 \times \cdots \times 2 } \\ n 个\end{matrix} = 2^n 2×2×⋯×2​n个​=2n 个选择 , 这是 分步计数的乘法法则 ,

这是分步计数 , 最后将所有的分步结果相乘 , 即第 1 1 1 个元素选择个数 , 第 2 2 2 个元素选择个数 , ⋯ \cdots ⋯ , 第 n n n 个元素选择个数 ;

3. 应用场景 : 在序列求和场景使用 ;

二、组合恒等式 ( 变下项求和 ) 交错和

交错和 :

∑ k = 0 n ( − 1 ) k ( n k ) = 0 \sum_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0 k=0∑n​(−1)k(kn​)=0

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=0n​(kn​)xkyn−k 中 , 使 x = − 1 , y = 1 x= -1 , y=1 x=−1,y=1 , 即可得到上面的 交错和 组合恒等式 ;

2. 证明 ( 组合分析 ) : 将等号 左边 和 右边 各看做某个 组合计数问题的解 , 完全展开上述组合数 , 这里需要先移项 , 将 k k k 为奇数的情况下 , ( − 1 ) k (-1)^k (−1)k 为 − 1 -1 −1 , 将这种情况的分项移到右边 , 就有了如下公式 :

∑ k = 0 偶 数 ( n k ) = ∑ k = 1 奇 数 ( n k ) \sum_{k=0}^{偶数} \dbinom{n}{k} = \sum_{k=1}^{奇数} \dbinom{n}{k} k=0∑偶数​(kn​)=k=1∑奇数​(kn​)

( 1 ) 左侧 组合计数问题 : ∑ k = 0 偶 数 ( n k ) \sum_{k=0}^{偶数} \dbinom{n}{k} ∑k=0偶数​(kn​) 可以看做 n n n 个元素的所有 偶数个 子集个数 ;

( 2 ) 右侧 组合计数问题 : ∑ k = 1 奇 数 ( n k ) \sum_{k=1}^{奇数} \dbinom{n}{k} ∑k=1奇数​(kn​) 可以看做 n n n 个元素的所有 奇数个 子集个数 ;

上述 奇数子集个数 与 偶数子集个数 是相等的 ;

3. 应用场景 : 在序列求和场景使用 ;