【组合数学】组合恒等式 ( 变上项求和 1 组合恒等式 | 三种组合恒等式证明方法总结 | 证明变上项求和 1 组合恒等式 )

组合恒等式参考博客 :

• 【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )
• 【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )

回顾四个变下项求和的组合恒等式 : 之前介绍的组合恒等式 中的组合数 ( n k ) \dbinom{n}{k} (kn​) , 是下项 k k k 一直在累加改变 , 具有 ∑ k = 0 n \sum\limits_{k=0}^{n} k=0∑n​ 累加性质 , 上项 n n n 是不变的 ;

( 1 ) 简单和 : ∑ k = 0 n ( n k ) = 2 n \sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n k=0∑n​(kn​)=2n

( 2 ) 交错和 : ∑ k = 0 n ( − 1 ) k ( n k ) = 0 \sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0 k=0∑n​(−1)k(kn​)=0

( 3 ) 变下项求和 3 : ∑ k = 0 n k ( n k ) = n 2 n − 1 \sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1} k=0∑n​k(kn​)=n2n−1

( 4 ) 变下项求和 4 : ∑ k = 0 n k 2 ( n k ) = n ( n + 1 ) 2 n − 2 \sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2} ∑k=0n​k2(kn​)=n(n+1)2n−2

一、组合恒等式 ( 变上项求和 1 )

变上项求和 1 :

∑ l = 0 n ( l k ) = ( n + 1 k + 1 ) \sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1} l=0∑n​(kl​)=(k+1n+1​)

上述公式中 , 组合数 ( l k ) \dbinom{l}{k} (kl​) 中 , 下项 k k k 是不变的 , 上项 l l l 一直是改变的 , 其取值范围是 0 0 0 ~ n n n ;

该表达式中有若干项都是 0 0 0 :

• 当 l < k l < k l k l > k l>k 时 , ( l k ) \dbinom{l}{k} (kl​) 才为大于 1 1 1 的值 ;

二、组合恒等式证明方法 ( 三种 )

1 . 证明方法 : 之前使用过两种证明方法 , ① 二项式定理 + 求导 , ② 使用现有组合恒等式推导 ;

在这里使用第三类证明方法 , ③ 组合分析 , 组合分析方法是要构造一个组合计数问题 , 左边和右边都是同一个计数问题的解 ;

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

指定计数问题 : 下面两个计数问题都是同一个问题的计数 ;

• ① 问题 1 : 等号左侧代表的计数问题 ;
• ② 问题 2 : 等号右侧代表的计数问题 ;

参考 : 【组合数学】二项式定理与组合恒等式 ( 二项式定理 | 三个组合恒等式 递推式 | 递推式 1 | 递推式 2 | 递推式 3 帕斯卡/杨辉三角公式 | 组合分析方法 | 递推式组合恒等式特点 ) 五、组合分析方法

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

三、组合恒等式 ( 变上项求和 1 ) 证明

现在开始构造选取问题 :

1 . 指定集合 : 假定有 n + 1 n+1 n+1 个元素的集合 , 记作 S = { a 1 , a 2 , ⋯   , a n + 1 } S = \{ a_1 , a_2 , \cdots , a_{n+1} \} S={a1​,a2​,⋯,an+1​} ,

2 . 指定等号右侧的计数问题 : 从上述集合 S S S 中 , 选取 k + 1 k+1 k+1 个元素的子集 , 选择方法的个数是 ( n + 1 k + 1 ) \dbinom{n + 1}{k+1} (k+1n+1​) 个 ;

3 . 指定等号左侧的计数问题 : 等号左侧是 ∑ l = 0 n ( l k ) \sum\limits_{l=0}^{n} \dbinom{l}{k} l=0∑n​(kl​) ;

计数问题类型确定 ( 分类选取 ) : 组合式中存在 和号 ∑ \sum ∑ , 说明该计数问题采用了 分类计数原理 , 对应加法法则 ; 该计数问题肯定是分类选取 ;

S S S 集合 , 从 n + 1 n+1 n+1 个元素中选取 k + 1 k+1 k+1 个元素 ;

( 1 ) 第 1 1 1 类 , 指定某个特定元素 a 1 a_1 a1​ , 在子集中必须含有 a 1 a_1 a1​ , 则只能从剩余的 n n n 个元素中选取 k k k 个 , 方案数是 ( n k ) \dbinom{n}{k} (kn​) ;

( 2 ) 第 2 2 2 类 , 与 第 1 1 1 类不重叠 , 不含 a 1 a_1 a1​ , 但是必须含有 a 2 a_2 a2​ , 不含 a 1 a_1 a1​ 那就要从 n n n 个元素中选取 ( 从 n + 1 n+1 n+1 个元素中去掉一个 ) , 必须含有 a 2 a_2 a2​ ( 从 n n n 个元素中再去掉一个, 即 n − 1 n - 1 n−1 个 ) , 那么就要从 n − 1 n-1 n−1 个元素中选取 k k k 个元素 , 最终结果是 ( n − 1 k ) \dbinom{n-1}{k} (kn−1​)

( 3 ) 第 3 3 3 类 , 与 第 1 , 2 1,2 1,2 类不重叠 , 不含 a 1 , a 2 a_1, a_2 a1​,a2​ , 但是必须含有 a 3 a_3 a3​ , 不含 a 1 , a 2 a_1, a_2 a1​,a2​ 那就要从 n − 1 n-1 n−1 个元素中选取 ( 从 n + 1 n+1 n+1 个元素中去掉 2 2 2 个 , 即 n − 1 n-1 n−1 ) , 必须含有 a 3 a_3 a3​ ( 从 n − 1 n-1 n−1 个元素中再去掉一个, 即 n − 2 n - 2 n−2 个 ) , 那么就要从 n − 2 n-2 n−2 个元素中选取 k k k 个元素 , 最终结果是 ( n − 2 k ) \dbinom{n-2}{k} (kn−2​)

⋮ \vdots ⋮

( 4 ) 第 n + 1 n + 1 n+1 类 , 与 第 1 , 2 , ⋯   , n 1,2, \cdots , n 1,2,⋯,n 类不重叠 , 不含 a 1 , a 2 , a 3 , ⋯   , a n a_1, a_2 , a_3 , \cdots , a_n a1​,a2​,a3​,⋯,an​ , 但是必须含有 a n + 1 a_{n+1} an+1​ , 不含 a 1 , a 2 , a 3 , ⋯   , a n a_1, a_2 , a_3 , \cdots , a_n a1​,a2​,a3​,⋯,an​ 那就要从 1 1 1 个元素中选取 ( 从 n + 1 n+1 n+1 个元素中去掉 n n n 个 , 即 1 1 1 ) , 必须含有 a n + 1 a_{n+1} an+1​ ( 从 1 1 1 个元素中再去掉一个, 即 0 0 0 个 ) , 那么就要从 0 0 0 个元素中选取 k k k 个元素 , 最终结果是 ( 0 k ) \dbinom{0}{k} (k0​)

5 . 在上述两个计数问题都是同一个计数问题 , 都是从 n + 1 n+1 n+1 个元素中选取 k + 1 k+1 k+1 个元素 ;