【组合数学】组合恒等式 ( 变上项求和 1 组合恒等式 | 三种组合恒等式证明方法总结 | 证明变上项求和 1 组合恒等式 )

韩曙亮

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

7960

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

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

文章目录

组合恒等式参考博客 :

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

\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}

一、组合恒等式 ( 变上项求和 1 )

变上项求和 1 :

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

上述公式中 , 组合数

\dbinom{l}{k}

中 , 下项

k

是不变的 , 上项

l

一直是改变的 , 其取值范围是

0

~

n

;

该表达式中有若干项都是

0

:

当

l < k

时 ,

\dbinom{l}{k} = 0

, 从

l

个元素中选取

k

个元素 , 没有方案 ;

当

l = k

时 ,

\dbinom{l}{k} = 1

;

当

l > k

时 ,

\dbinom{l}{k}

才为大于

1

的值 ;

二、组合恒等式证明方法 ( 三种 )

1 . 证明方法 : 之前使用过两种证明方法 , ① 二项式定理 + 求导 , ② 使用现有组合恒等式推导 ;

在这里使用第三类证明方法 , ③ 组合分析 , 组合分析方法是要构造一个组合计数问题 , 左边和右边都是同一个计数问题的解 ;

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

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

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

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

三、组合恒等式 ( 变上项求和 1 ) 证明

现在开始构造选取问题 :

1 . 指定集合 : 假定有

n+1

个元素的集合 , 记作

S = \{ a_1 , a_2 , \cdots , a_{n+1} \}

,

2 . 指定等号右侧的计数问题 : 从上述集合

S

中 , 选取

k+1

个元素的子集 , 选择方法的个数是

\dbinom{n + 1}{k+1}

个 ;

3 . 指定等号左侧的计数问题 : 等号左侧是

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

;

计数问题类型确定 ( 分类选取 ) : 组合式中存在和号

\sum

, 说明该计数问题采用了分类计数原理 , 对应加法法则 ; 该计数问题肯定是分类选取 ;

S

集合 , 从

n+1

个元素中选取

k+1

个元素 ;

( 1 ) 第

1

类 , 指定某个特定元素

a_1

, 在子集中必须含有

a_1

, 则只能从剩余的

n

个元素中选取

k

个 , 方案数是

\dbinom{n}{k}

;

( 2 ) 第

2

类 , 与第

1

类不重叠 ,

不含

a_1

, 但是必须含有

a_2

,

不含

a_1

那就要从

n

个元素中选取 ( 从

n+1

个元素中去掉一个 ) ,

必须含有

a_2

( 从

n

个元素中再去掉一个, 即

n - 1

个 ) , 那么就要从

n-1

个元素中选取

k

个元素 ,

最终结果是

\dbinom{n-1}{k}

( 3 ) 第

3

类 , 与第

1,2

类不重叠 ,

不含

a_1, a_2

, 但是必须含有

a_3

,

不含

a_1, a_2

那就要从

n-1

个元素中选取 ( 从

n+1

个元素中去掉

2

个 , 即

n-1

) ,

必须含有

a_3

( 从

n-1

个元素中再去掉一个, 即

n - 2

个 ) , 那么就要从

n-2

个元素中选取

k

个元素 ,

最终结果是

\dbinom{n-2}{k}

\vdots

( 4 ) 第

n + 1

类 , 与第

1,2, \cdots , n

类不重叠 ,

不含

a_1, a_2 , a_3 , \cdots , a_n

, 但是必须含有

a_{n+1}

,

不含

a_1, a_2 , a_3 , \cdots , a_n

那就要从

1

个元素中选取 ( 从

n+1

个元素中去掉

n

个 , 即

1

) ,

必须含有

a_{n+1}

( 从

1

个元素中再去掉一个, 即

0

个 ) , 那么就要从

0

个元素中选取

k

个元素 ,

最终结果是

\dbinom{0}{k}

5 . 在上述两个计数问题都是同一个计数问题 , 都是从

n+1

个元素中选取

k+1

个元素 ;

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

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

博客

集合

数学

原理

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

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

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

登录后参与评论

0 条评论

热度