【组合数学】组合恒等式总结 ( 十一个组合恒等式

组合恒等式参考博客 :

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∑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 ⑦

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 . 幂级数求导、积分

幂函数求导 : ( 很重要 )

常数的导数是 0 0 0 ;

导数四则运算 : ( u ± v ) ′ = u ′ ± v ′ (u \pm v)' = u' \pm v' (u±v)′=u′±v′

参考 :

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 ) 指定计数问题 : 下面两个计数问题都是同一个问题的计数 ;

( 3 ) 等价说明 : 说明两个计数问题是同一个问题 ;

参考 :

上述证明方法 , 可以根据具体的证明要求 , 选择合适的证明方法 ;

针对含有组合数的式子的 求和 ∑ \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 . 利用已知公式求和 :