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

韩曙亮

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

5800

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

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

文章目录

组合恒等式参考博客 :

一、组合恒等式 ( 积之和 ) 1

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

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}

二、组合恒等式 ( 积之和 ) 1 证明

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

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

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

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

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

2 . 使用组合分析的方法进行证明 :

( 1 ) 指定集合 : 定义两个集合 ,

A = \{ a_1, a_2 , \cdots , a_m \}

B = \{ b_1, b_2 , \cdots , b_n \}

( 2 ) 指定等号右边的计数 :

\dbinom{m + n }{r}

代表如下计数 :

从这两个集合的

m + n

个元素中 , 选取

r

个元素 , 这样就构造了一个选取问题 ;

( 3 ) 指定等号左边的计数 :

等号左边的组合数

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

计数分析 :

先分类后分步 : 上述式子中 , 有乘积 , 有求和 , 说明这是先分类 ( 加法法则 ) , 每个分类中使用分步 ( 乘法法则 ) 计算 ;

按照从两个集合中选出的

r

个子集中 , 含有多少个

A = \{ a_1, a_2 , \cdots , a_m \}

集合中的元素进行分类 ,

含有

A

中的元素

k

个 ,

剩下的

r-k

元素取自

B = \{ b_1, b_2 , \cdots , b_n \}

集合 ;

分步处理的逻辑是 : 先在

A

集合中选择

k

个元素 , 然后在

B

集合中选择

r-k

个元素 ;

因此

k

最多取

r

个 ( 全部从

A

集合中取 ) , 最少取

0

个 ( 全部从

B

集合中取 ) ;

( 4 ) 上述等式左右两边的计数是同一个计数 , 都是在两个集合中取

r

个元素的方案数 ;

三、组合恒等式 ( 积之和 ) 2

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

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}

四、组合恒等式 ( 积之和 ) 2 证明

该公式是 “组合恒等式 ( 积之和 ) 1” 的特例情况 ,

证明了上述 “组合恒等式 ( 积之和 ) 1” 公式后 , 本公式是上述公式的推论 ;

在 “组合恒等式 ( 积之和 ) 1” 公式

\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}

中 , 令

r=n

, 就变成公式

\sum\limits_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{n-k} = \dbinom{m + n }{n}

\dbinom{n}{n-k}

与

\dbinom{n}{k}

是等价的 , 因此公式可以变成 :

\sum\limits_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{n} =\dbinom{m + n }{n}

因此 “组合恒等式 ( 积之和 ) 2” 是 “组合恒等式 ( 积之和 ) 1” 的一个特例情况 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-20，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

集合

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

博客

集合

数学

登录后参与评论

0 条评论

热度