IDEA激活码
文章目录
- 一、二项式定理
- 二、组合恒等式 ( 递推式 1 )
- 三、组合恒等式 ( 递推式 2 )
- 四、组合恒等式 ( 递推式 3 ) 帕斯卡 / 杨辉三角公式
- 五、组合分析方法
- 六、递推式组合恒等式特点
一、二项式定理
二项式定理 :
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)
二、组合恒等式 ( 递推式 1 )
(
n
k
)
=
(
n
n
−
k
)
\dbinom{n}{k} = \dbinom{n}{n-k}
(kn)=(n−kn)
组合分析方法 :
(
n
k
)
\dbinom{n}{k}
(kn) 是求
k
k
k 个子集选取方法 ,
(
n
n
−
k
)
\dbinom{n}{n-k}
(n−kn) 是求
n
−
k
n-k
n−k 个子集的选取方法 , 二者是一一对应的 ;
一般情况下 ,
(
n
k
)
\dbinom{n}{k}
(kn) 的下项 , 不超过上项的一半 ;
如果出现
(
10
8
)
\dbinom{10}{8}
(810) , 就可以写成
(
10
2
)
\dbinom{10}{2}
(210)
三、组合恒等式 ( 递推式 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)
代入组合数的公式 , 可以得到 等号
=
=
= 两侧的值是相等的 ;
该公式用于消去系数的 , 示例如下 :
计算
∑
k
=
0
n
k
(
n
k
)
\sum\limits_{k=0}^n k\dbinom{n}{k}
k=0∑nk(kn) 组合式 :
此时需要消去
k
k
k 系数 ;
使用
n
k
(
n
−
1
k
−
1
)
\dfrac{n}{k} \dbinom{n - 1}{k - 1}
kn(k−1n−1) 代替
(
n
k
)
\dbinom{n}{k}
(kn) , 有以下计算过程 :
∑
k
=
0
n
k
(
n
k
)
=
∑
k
=
0
n
k
n
k
(
n
−
1
k
−
1
)
\begin{array}{lcl} \sum\limits_{k=0}^n k\dbinom{n}{k} = \sum\limits_{k=0}^n k \dfrac{n}{k} \dbinom{n - 1}{k - 1} \end{array}
k=0∑nk(kn)=k=0∑nkkn(k−1n−1)
可以将加和式中的
k
k
k 约掉 , 此时
n
n
n 就与求和变量无关了 , 此时可以将
n
n
n 提取到加和符号
∑
\sum
∑ 外面 ,
∑
k
=
0
n
k
(
n
k
)
=
∑
k
=
0
n
k
n
k
(
n
−
1
k
−
1
)
=
n
∑
k
=
0
n
(
n
−
1
k
−
1
)
\begin{array}{lcl} \sum\limits_{k=0}^n k\dbinom{n}{k} &=& \sum\limits_{k=0}^n k \dfrac{n}{k} \dbinom{n - 1}{k - 1} \\\\ &=& n \sum\limits_{k=0}^n \dbinom{n - 1}{k - 1} \end{array}
k=0∑nk(kn)==k=0∑nkkn(k−1n−1)nk=0∑n(k−1n−1)
然后计算
∑
k
=
0
n
(
n
−
1
k
−
1
)
\sum\limits_{k=0}^n \dbinom{n - 1}{k - 1}
k=0∑n(k−1n−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=0∑n(kn)xkyn−k
根据二项式定理 , 可以得到
(
1
+
1
)
n
=
∑
k
=
0
n
(
n
k
)
(1 + 1)^{n} = \sum\limits_{k=0}^n \dbinom{n}{k}
(1+1)n=k=0∑n(kn)
推导 :
(
1
+
1
)
n
−
1
=
∑
k
=
0
n
−
1
(
n
−
1
k
−
1
)
=
2
n
−
1
(1 + 1)^{n-1} = \sum\limits_{k=0}^{n-1} \dbinom{n-1}{k-1} = 2^{n-1}
(1+1)n−1=k=0∑n−1(k−1n−1)=2n−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)
该递推式 , 用于拆项 :
可以将
(
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
)
\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) 之差;
在一堆求和的组合数中 , 拆分成两个数之差 , 可以抵消很多组合数 ;
经常在大的求和公式中进行化简时使用 ;
使用组合分析的办法证明该公式 :
取
n
n
n 元集中选取
k
k
k 子集 , 这是集合组合数 ;
指定其中某个元素
a
a
a ;
① 包含
a
a
a 元素 :
k
k
k 子集中包含
a
a
a 元素的情况组合数 为
(
n
−
1
k
−
1
)
\dbinom{n - 1}{k - 1}
(k−1n−1) ,
k
k
k 子集中包含
a
a
a , 只需要在除
a
a
a 元素外 , 剩下的
n
−
1
n-1
n−1 个元素中 , 选出
k
−
1
k-1
k−1 个元素即可 ;
② 不包含
a
a
a 元素 :
k
k
k 子集中不包含
a
a
a 元素的情况组合数 为
(
n
−
1
k
)
\dbinom{n - 1}{k}
(kn−1) ,
k
k
k 子集中不包含
a
a
a , 只需要在除
a
a
a 元素外 , 剩下的
n
−
1
n-1
n−1 个元素中 , 选出
k
k
k 个元素即可 ;
五、组合分析方法
以上面证明 帕斯卡 / 杨辉三角 公式为例
组合分析方法使用 : 使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;
- 指定集合 :
n
n
n 元集 - 指定元素 : 某个特定元素
a
a
a - 指定计数问题 :
- ① 问题 1 :
n
n
n 元集k
k
k 组合数 ; - ② 问题 2 :
n
n
n 元集中k
k
k 组合数 , 组合中含有元素a
a
a , 不含有元素a
a
a 的两种组合计数 ;
- ① 问题 1 :
六、递推式组合恒等式特点
使用 比较小的组合数 表示 比较大的组合数 , 称为递推式组合恒等式 ;
