【组合数学】组合恒等式总结 ( 十一个组合恒等式 | 组合恒等式证明方法 | 求和方法 ) ★

2023-03-28 18:26:14 浏览数 (1)

文章目录

  • 一、十一个组合恒等式
  • 二、组合恒等式 证明方法
  • 三、组合数 求和
sum

方法

组合恒等式参考博客 :

  • 【组合数学】二项式定理与组合恒等式 ( 二项式定理 | 三个组合恒等式 递推式 | 递推式 1 | 递推式 2 | 递推式 3 帕斯卡/杨辉三角公式 | 组合分析方法 | 递推式组合恒等式特点 )
  • 【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )
  • 【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )
  • 【组合数学】组合恒等式 ( 八个组合恒等式回顾 | 组合恒等式 积 1 | 证明 | 使用场景 )
  • 【组合数学】组合恒等式 ( 组合恒等式 积之和 1 | 积之和 1 证明 | 组合恒等式 积之和 2 | 积之和 2 证明 )

一、十一个组合恒等式

1 . 组合恒等式 ( 递推式 ) :

( 1 ) 递推式 1 :

dbinom{n}{k} = dbinom{n}{n-k}

①

( 2 ) 递推式 2 :

dbinom{n}{k} = dfrac{n}{k} dbinom{n - 1}{k - 1}

②

( 3 ) 递推式 3 ( 帕斯卡 / 杨辉三角公式 ) :

dbinom{n}{k} = dbinom{n - 1}{k} dbinom{n - 1}{k - 1}

③

2 . 回顾四个变下项求和的组合恒等式 : 之前介绍的组合恒等式 中的组合数

dbinom{n}{k}

, 是下项

k

一直在累加改变 , 具有

sumlimits_{k=0}^{n}

累加性质 , 上项

n

是不变的 ;

( 1 ) 简单和 :

sumlimits_{k=0}^{n}dbinom{n}{k} = 2^n

④

( 2 ) 交错和 :

sumlimits_{k=0}^{n} (-1)^k dbinom{n}{k} = 0

⑤

( 3 ) 变下项求和 3 :

sumlimits_{k=0}^{n} k dbinom{n}{k} = n 2^{n-1}

⑥

( 4 ) 变下项求和 4 :

sum_{k=0}^{n} k^2 dbinom{n}{k} = n ( n 1 ) 2^{n-2}

⑦

3 . 变上项求和 :

sumlimits_{l=0}^{n} dbinom{l}{k} = dbinom{n 1}{k 1}

⑧

4 . 积 :

sumlimits_{l=0}^{n} dbinom{l}{k} = dbinom{n 1}{k 1}

⑨

5 . 积之和 :

( 1 ) 组合恒等式 ( 积之和 ) 1 :

sumlimits_{k=0}^{r}dbinom{m}{k}dbinom{n}{r-k} = dbinom{m n }{r} , r= min { m, n }

⑩

( 2 ) 组合恒等式 ( 积之和 ) 2 :

sumlimits_{k=0}^{r}dbinom{m}{k}dbinom{n}{k} = dbinom{m n }{m}

⑪

二、组合恒等式 证明方法

1 . 已知组合恒等式代入 : 已知的

11

个组合恒等式代入

2 . 二项式定理

n

是正整数 , 对于一切

x

和

y

, 有以下定理 :

(x y)^n = sum_{k=0}^n dbinom{n}{k}x^k y^{n-k}
dbinom{n}{k}

表示

n

元集中取

k

个元素的组合数 , 是 集合组合数

C(n,k)

的另一种写法 ;

另一个常用形式 (

y = 1

) :

(1 x)^n = sum_{k=0}^n dbinom{n}{k}x^k

基本求和公式 (

x = y =1

) :

2^n = sum_{k=0}^n dbinom{n}{k}

3 . 幂级数求导、积分

幂函数求导 : ( 很重要 )

  • 原函数 :
y = x^n
  • 对应导数 :
y' = nx^{n-1}

常数的导数是

0

;

导数四则运算 :

(u pm v)' = u' pm v'

参考 :

  • 导数 - 百度百科
  • 组合恒等式 ( 变下项求和 ) 变系数求和 1 证明 ( 二项式定理 求导 )

4 . 归纳法

数学归纳法 描述 一个与自然数相关的命题

P(n)

,

根据不同的问题 , 设定

n

最小的值 , 一般情况下从

0

开始 ,

( 1 ) 证明时分为以下两个步骤 :

① 归纳基础 : 先证明 归纳基础 , 如证明

P(0)

为真 ;

② 归纳步骤 : 根据 数学归纳法的种类 , 进行不同方式的证明 , 这里有 第一数学归纳法 和 第二数学归纳法 两种归纳法 ;

( 1 ) 数学归纳法 :

① 第一数学归纳法 : 从

P(n)

推导

P(n 1)
P(0)

为真

假设

P(n)

为真 , 证明

P(n 1)

也为真

② 第二数学归纳法 : 所有小于

n

的

P(0) , P(1), cdots , P(n-1)

都为真 , 推导

P(n)

为真 ;

P(0)

为真

假设所有小于

n

的自然数

k

, 命题

P(k)

都为真 , 即

P(0) , P(1), cdots , P(n-1)

都为真 , 推导

P(n)

为真 ;

符号化表示为 :

P(0) land P(1) land cdots land P(n-1) to P(n)

参考 : 【组合数学】组合数学简介 ( 组合思想 2 : 数学归纳法 | 数学归纳法推广 | 多重归纳思想 )

5 . 组合分析

使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;

( 1 ) 指定集合 : 指定计数是在什么样的集合中产生的 ;

( 2 ) 指定计数问题 : 下面两个计数问题都是同一个问题的计数 ;

  • ① 问题 1 : 等号左侧代表的计数问题 ;
  • ② 问题 2 : 等号右侧代表的计数问题 ;

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

参考 :

  • 【组合数学】组合恒等式 ( 组合恒等式 积之和 1 | 积之和 1 证明 | 组合恒等式 积之和 2 | 积之和 2 证明 ) 二、组合恒等式 ( 积之和 ) 1 证明

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

三、组合数 求和

sum

方法

针对含有组合数的式子的 求和

sum

方法

1 . 使用帕斯卡公式 :

递推式 3 ( 帕斯卡 / 杨辉三角公式 ) :

dbinom{n}{k} = dbinom{n - 1}{k} dbinom{n - 1}{k - 1}

③

( 1 ) 合并项 :

dbinom{n}{k}

可以规约成

dbinom{n - 1}{k} dbinom{n - 1}{k - 1}

之和 ;

( 2 ) 该递推式 , 用于拆项 :

可以将

dbinom{n}{k}

拆成

dbinom{n - 1}{k} dbinom{n - 1}{k - 1}

之和 ; 在实际使用时 , 经常遇到某些项列出后 , 有

dbinom{n - 1}{k} dbinom{n - 1}{k - 1}

形式的组合数 , 可以合并成一项

dbinom{n}{k}

;

( 3 ) 也可以变形使用 , 将其中的一项 , 变成其中两项的差 ;

将

dbinom{n - 1}{k}

拆成

dbinom{n}{k} -dbinom{n - 1}{k - 1}

之差 ;

将 将

dbinom{n - 1}{k - 1}

拆成

dbinom{n}{k} -dbinom{n - 1}{k}

之差;

在一堆求和的组合数中 , 拆分成两个数之差 , 可以抵消很多组合数 ;

经常在大的求和公式中进行化简时使用 ;

2 . 级数求和 :

3 . 观察和的结果 , 使用数学归纳法证明 :

猜想一个和的结果 , 然后使用归纳法证明 ;

4 . 利用已知公式求和 :

百度 博客 基础 集合 数学

0 人点赞