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

组合恒等式参考博客 :

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

一、组合恒等式 ( 积之和 ) 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}

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

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

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

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

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

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

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

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

A = { a 1 , a 2 , ⋯   , a m } A = \{ a_1, a_2 , \cdots , a_m \} A={a1​,a2​,⋯,am​}

B = { b 1 , b 2 , ⋯   , b n } B = \{ b_1, b_2 , \cdots , b_n \} B={b1​,b2​,⋯,bn​}

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

( m + n r ) \dbinom{m + n }{r} (rm+n​) 代表 如下计数 :

从这 两个集合的 m + n m + n m+n 个元素中 , 选取 r r r 个元素 , 这样就构造了一个选取问题 ;

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

等号左边的 组合数 ∑ k = 0 r ( m k ) ( n r − k ) \sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} k=0∑r​(km​)(r−kn​) 计数分析 :

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

按照 从两个集合中 选出的 r r r 个子集中 , 含有多少个 A = { a 1 , a 2 , ⋯   , a m } A = \{ a_1, a_2 , \cdots , a_m \} A={a1​,a2​,⋯,am​} 集合中的元素进行分类 ,

含有 A A A 中的元素 k k k 个 ,

剩下的 r − k r-k r−k 元素取自 B = { b 1 , b 2 , ⋯   , b n } B = \{ b_1, b_2 , \cdots , b_n \} B={b1​,b2​,⋯,bn​} 集合 ;

分步处理的逻辑是 : 先在 A A A 集合中选择 k k k 个元素 , 然后在 B B B 集合中选择 r − k r-k r−k 个元素 ;

因此 k k k 最多取 r r r 个 ( 全部从 A A A 集合中取 ) , 最少取 0 0 0 个 ( 全部从 B B B 集合中取 ) ;

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

三、组合恒等式 ( 积之和 ) 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​)

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

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

证明了上述 “组合恒等式 ( 积之和 ) 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}

中 , 令 r = n r=n r=n , 就变成公式

∑ k = 0 n ( m k ) ( n n − k ) = ( m + n n ) \sum\limits_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{n-k} = \dbinom{m + n }{n} k=0∑n​(km​)(n−kn​)=(nm+n​)

( n n − k ) \dbinom{n}{n-k} (n−kn​) 与 ( n k ) \dbinom{n}{k} (kn​) 是等价的 , 因此公式可以变成 :

∑ k = 0 n ( m k ) ( n k ) = ( m + n n ) = ( m + n n ) \sum\limits_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{n} =\dbinom{m + n }{n} k=0∑n​(km​)(kn​)=(nm+n​)=(nm+n​)

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