IDEA激活码
文章目录
- 一、十一个组合恒等式
- 二、组合恒等式 证明方法
- 三、组合数 求和
∑
\sum
∑ 方法
组合恒等式参考博客 :
- 【组合数学】二项式定理与组合恒等式 ( 二项式定理 | 三个组合恒等式 递推式 | 递推式 1 | 递推式 2 | 递推式 3 帕斯卡/杨辉三角公式 | 组合分析方法 | 递推式组合恒等式特点 )
- 【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )
- 【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )
- 【组合数学】组合恒等式 ( 八个组合恒等式回顾 | 组合恒等式 积 1 | 证明 | 使用场景 )
- 【组合数学】组合恒等式 ( 组合恒等式 积之和 1 | 积之和 1 证明 | 组合恒等式 积之和 2 | 积之和 2 证明 )
一、十一个组合恒等式
1 . 组合恒等式 ( 递推式 ) :
( 1 ) 递推式 1 :
(
n
k
)
=
(
n
n
−
k
)
\dbinom{n}{k} = \dbinom{n}{n-k}
(kn)=(n−kn) ①
( 2 ) 递推式 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 ) 递推式 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) ③
2 . 回顾四个变下项求和的组合恒等式 : 之前介绍的组合恒等式 中的组合数
(
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 ⑦
3 . 变上项求和 :
∑
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) ⑧
4 . 积 :
∑
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) ⑨
5 . 积之和 :
( 1 ) 组合恒等式 ( 积之和 ) 1 :
∑
k
=
0
r
(
m
k
)
(
n
r
−
k
)
=
(
m
+
n
r
)
,
r
=
min
{
m
,
n
}
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}
k=0∑r(km)(r−kn)=(rm+n), r=min{m,n} ⑩
( 2 ) 组合恒等式 ( 积之和 ) 2 :
∑
k
=
0
r
(
m
k
)
(
n
k
)
=
(
m
+
n
m
)
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}
k=0∑r(km)(kn)=(mm+n) ⑪
二、组合恒等式 证明方法
1 . 已知组合恒等式代入 : 已知的
11
11
11 个组合恒等式代入
2 . 二项式定理
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)
3 . 幂级数求导、积分
幂函数求导 : ( 很重要 )
- 原函数 :
y
=
x
n
y = x^n
y=xn - 对应导数 :
y
′
=
n
x
n
−
1
y' = nx^{n-1}
y′=nxn−1
常数的导数是
0
0
0 ;
导数四则运算 :
(
u
±
v
)
′
=
u
′
±
v
′
(u \pm v)' = u' \pm v'
(u±v)′=u′±v′
参考 :
- 导数 - 百度百科
- 组合恒等式 ( 变下项求和 ) 变系数求和 1 证明 ( 二项式定理 + 求导 )
4 . 归纳法
数学归纳法 描述 一个与自然数相关的命题
P
(
n
)
P(n)
P(n) ,
根据不同的问题 , 设定
n
n
n 最小的值 , 一般情况下从
0
0
0 开始 ,
( 1 ) 证明时分为以下两个步骤 :
① 归纳基础 : 先证明 归纳基础 , 如证明
P
(
0
)
P(0)
P(0) 为真 ;
② 归纳步骤 : 根据 数学归纳法的种类 , 进行不同方式的证明 , 这里有 第一数学归纳法 和 第二数学归纳法 两种归纳法 ;
( 1 ) 数学归纳法 :
① 第一数学归纳法 : 从
P
(
n
)
P(n)
P(n) 推导
P
(
n
+
1
)
P(n + 1)
P(n+1)
P
(
0
)
P(0)
P(0) 为真
假设
P
(
n
)
P(n)
P(n) 为真 , 证明
P
(
n
+
1
)
P(n + 1)
P(n+1) 也为真
② 第二数学归纳法 : 所有小于
n
n
n 的
P
(
0
)
,
P
(
1
)
,
⋯
,
P
(
n
−
1
)
P(0) , P(1), \cdots , P(n-1)
P(0),P(1),⋯,P(n−1) 都为真 , 推导
P
(
n
)
P(n)
P(n) 为真 ;
P
(
0
)
P(0)
P(0) 为真
假设所有小于
n
n
n 的自然数
k
k
k , 命题
P
(
k
)
P(k)
P(k) 都为真 , 即
P
(
0
)
,
P
(
1
)
,
⋯
,
P
(
n
−
1
)
P(0) , P(1), \cdots , P(n-1)
P(0),P(1),⋯,P(n−1) 都为真 , 推导
P
(
n
)
P(n)
P(n) 为真 ;
符号化表示为 :
P
(
0
)
∧
P
(
1
)
∧
⋯
∧
P
(
n
−
1
)
→
P
(
n
)
P(0) \land P(1) \land \cdots \land P(n-1) \to P(n)
P(0)∧P(1)∧⋯∧P(n−1)→P(n)
参考 : 【组合数学】组合数学简介 ( 组合思想 2 : 数学归纳法 | 数学归纳法推广 | 多重归纳思想 )
5 . 组合分析
使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;
( 1 ) 指定集合 : 指定计数是在什么样的集合中产生的 ;
( 2 ) 指定计数问题 : 下面两个计数问题都是同一个问题的计数 ;
- ① 问题 1 : 等号左侧代表的计数问题 ;
- ② 问题 2 : 等号右侧代表的计数问题 ;
( 3 ) 等价说明 : 说明两个计数问题是同一个问题 ;
参考 :
- 【组合数学】组合恒等式 ( 组合恒等式 积之和 1 | 积之和 1 证明 | 组合恒等式 积之和 2 | 积之和 2 证明 ) 二、组合恒等式 ( 积之和 ) 1 证明
上述证明方法 , 可以根据具体的证明要求 , 选择合适的证明方法 ;
三、组合数 求和
∑
\sum
∑ 方法
针对含有组合数的式子的 求和
∑
\sum
∑ 方法
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) ③
( 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) 之和 ;
( 2 ) 该递推式 , 用于拆项 :
可以将
(
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
)
+
(
n
−
1
k
−
1
)
\dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}
(kn−1)+(k−1n−1) 形式的组合数 , 可以合并成一项
(
n
k
)
\dbinom{n}{k}
(kn) ;
( 3 ) 也可以变形使用 , 将其中的一项 , 变成其中两项的差 ;
将
(
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) 之差;
在一堆求和的组合数中 , 拆分成两个数之差 , 可以抵消很多组合数 ;
经常在大的求和公式中进行化简时使用 ;
2 . 级数求和 :
3 . 观察和的结果 , 使用数学归纳法证明 :
猜想一个和的结果 , 然后使用归纳法证明 ;
4 . 利用已知公式求和 :
