IDEA激活码
文章目录
- 一、组合恒等式 ( 递推式 )
- 二、组合恒等式 ( 变下项求和 ) 简单和
- 二、组合恒等式 ( 变下项求和 ) 交错和
一、组合恒等式 ( 递推式 )
组合恒等式 ( 递推式 ) :
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×⋯×2n个=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. 应用场景 : 在序列求和场景使用 ;
