【组合数学】组合恒等式 ( 八个组合恒等式回顾 | 组合恒等式 积 1 | 证明 | 使用场景 | 求组合数通用方法 )

2023-03-28 18:25:45 浏览数 (1)

文章目录

  • 一、组合恒等式回顾 ( 8个 )
  • 二、组合恒等式 ( 积 )
  • 三、组合恒等式 ( 积 ) 证明
  • 四、组合恒等式 ( 积 ) 用途 、求组合数通用方法

组合恒等式参考博客 :

  • 【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )
  • 【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )

一、组合恒等式回顾 ( 8个 )

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}

二、组合恒等式 ( 积 )

组合恒等式 ( 积 ) :

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

三、组合恒等式 ( 积 ) 证明

1 .

dbinom{n}{r}dbinom{r}{k}

组合数解析 : 这是两个组合数的乘法 , 使用的是 分步计数原理 , 对应乘法法则 ;

( 1 ) 第一步 :

dbinom{n}{r}

从

n

个元素中选择

r

个元素 ;

( 2 ) 第二步 :

dbinom{r}{k}

从

r

个元素中选择

k

个元素 ;

2 . 上述选择可能会存在重复的情况 , 以下反例可以证明 :

集合

S = { a, b, c, d, e }

, 从该集合

S

中选择

4

个元素 , 举两个栗子 :

①

{a, b, c, d}

, 有子集

{ b,c,d }

②

{ b,c,d,e }

, 有子集

{ b,c,d }

这样从

5

个元素中选择

4

个 , 然后从

4

个元素中选择

3

个 , 最后 出现了选择重复子集的情况 , 有两个重复的

{ b,c,d }

;

3 .

dbinom{n }{k}dbinom{n-k}{r-k}

组合数解析 :

dbinom{n }{k}

表示 从

n

个元素中 , 直接选出

k

个元素出来 , 查看有多少种方法 ; 栗子 : 上述

5

元集中直接选择

3

元素子集的个数 ;

dbinom{n-k}{r-k}

是 上述选择方法的重复度 , 每个选择方法会出现多少次 ; 栗子 : 计算上述每个

3

元素子集选择方案的重复次数 ;

4 . 下面开始研究上述

dbinom{n-k}{r-k}

重复度是如何计算出来的

以上面的栗子为例 ,

3

子集

{ b,c,d }

出现两次的原因是 ,

在

4

子集

{a, b, c, d}

和

{ b,c,d,e }

都包含同样的

3

子集

{ b,c,d }

,

在上述

4

子集中 , 除了

3

子集之外 , 有其它的添加元素 ,

  • 在
{a, b, c, d}

中 , 添加了

a

元素

  • 在
{b,c,d,e}

中 , 添加了

e

元素

在

3

子集中 , 添加不同的元素 , 就可以变成 不同的

4

子集 , 这里直接求该

3

子集有多少种添加方法 , 构成

4

子集的个数 ;

添加的元素是从 原有

S = { a, b, c, d, e }

集合中 , 除掉

{ b,c,d }
3

子集后的元素中选取的 ,

选取集合有

5-3 = 2

个元素 ( 相当于公式

n-k

) ,

选取的个数就是

4-3=1

个 ( 相当于公式

r-k

) ;

从

n-k

个元素中选择

r-k

个元素 , 方案数为

dbinom{n-k}{r-k}

;

5 .

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

的左右两边都是对同一个组合数的计数结果 , 因此是相等的

四、组合恒等式 ( 积 ) 用途 、求组合数通用方法

组合恒等式 ( 积 ) :

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

遇到

dbinom{n}{r}dbinom{r}{k}

先乘积 , 再求和的情况 , 如果求和是对

r

求和的话 , 即

sumlimits_{r=0}^{n}

, 如下 :

对

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

求和 ;

对

r

求和 ,

r

是从

k

一直到

n

,

前面的项

dbinom{n}{r}

下项是变量 ,

后面的项

dbinom{r}{k}

上项是变量 ,

之前的通用方法 : 这就无法使用之前的计算方法了 , 之前的计算方法是 , 常量向

sum

符号外面提取 , 剩下的转变成 基本求和式

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

, 或已知的 组合恒等式 , 组合公式 , 进行化简 ;

处理的情况 : 两个组合数 , 一个是下项是累加变量 , 一个是上项是累加变量 , 两个组合数相乘 的情况 ;

上述 积组合恒等式可以将上述情况改变成 下项 是累加变量的情况 ;

这里使用上述 积组合恒等式 , 转变为 :

sumlimits_{r=k}^{n}dbinom{n}{r}dbinom{r}{k} = sumlimits_{r=k}^{n} dbinom{n }{k}dbinom{n-k}{r-k}

得到上述公式后 , 分析得到的项

sumlimits_{r=k}^{n} dbinom{n }{k}dbinom{n-k}{r-k}

,

前面的

dbinom{n }{k}

项与 求和变量

r

无关 ,

后面的

dbinom{n-k}{r-k}

下项与 求和变量

r

相关 ;

因此

dbinom{n }{k}

项 可以提取到

sum

符号外面 ;

=dbinom{n }{k} sumlimits_{r=k}^{n} dbinom{n-k}{r-k}

上述式子就可以进行 变限 , 代换计算了 ; 使用

r' = r-k

替换

r

;

原来

r

的取值范围是

k

~

n

, 则

r' = r-k

的取值范围是

0

~

n-k

, 代换结果如下 :

=dbinom{n }{k} sumlimits_{r'=0}^{n - k} dbinom{n-k}{r'}

根据 基本求和式

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

, 计算

sumlimits_{r'=0}^{n - k} dbinom{n-k}{r'}

的结果为

2^{n-k}

; 最终的计算结果为 :

=dbinom{n }{k} sumlimits_{r'=0}^{n - k} dbinom{n-k}{r'} = 2 ^{n-k}dbinom{n }{k}
变量 博客 集合 数学 原理

0 人点赞