IDEA激活码
文章目录
- 一、组合恒等式 ( 变上项求和 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∑nk(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=0nk2(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
)
=
0
\dbinom{l}{k} = 0
(kl)=0 , 从l
l
l 个元素中选取k
k
k 个元素 , 没有方案 ; - 当
l
=
k
l = k
l=k 时 ,(
l
k
)
=
1
\dbinom{l}{k} = 1
(kl)=1 ; - 当
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 个元素 ;
