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

韩曙亮

发布于 2023-03-28 18:25:45

1.1K0

发布于 2023-03-28 18:25:45

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

组合恒等式参考博客 :

一、组合恒等式回顾 ( 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

一直在累加改变 , 具有

\sum\limits_{k=0}^{n}

累加性质 , 上项

n

是不变的 ;

( 1 ) 简单和 :

\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n

( 2 ) 交错和 :

\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0

( 3 ) 变下项求和 3 :

\sum\limits_{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 . 变上项求和 :

\sum\limits_{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

求和的话 , 即

\sum\limits_{r=0}^{n}

, 如下 :

对

\sum\limits_{r=k}^{n}\dbinom{n}{r}\dbinom{r}{k}

求和 ;

对

r

求和 ,

r

是从

k

一直到

n

,

前面的项

\dbinom{n}{r}

下项是变量 ,

后面的项

\dbinom{r}{k}

上项是变量 ,

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

\sum

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

\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n

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

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

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

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

\sum\limits_{r=k}^{n}\dbinom{n}{r}\dbinom{r}{k} = \sum\limits_{r=k}^{n} \dbinom{n }{k}\dbinom{n-k}{r-k}

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

\sum\limits_{r=k}^{n} \dbinom{n }{k}\dbinom{n-k}{r-k}

,

前面的

\dbinom{n }{k}

项与求和变量

r

无关 ,

后面的

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

下项与求和变量

r