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

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

文章目录

  • 一、组合恒等式 ( 变上项求和 1 )
  • 二、组合恒等式证明方法 ( 三种 )
  • 三、组合恒等式 ( 变上项求和 1 ) 证明

组合恒等式参考博客 :

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

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

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}

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

变上项求和 1 :

sumlimits_{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 : 等号右侧代表的计数问题 ;

参考 : 【组合数学】二项式定理与组合恒等式 ( 二项式定理 | 三个组合恒等式 递推式 | 递推式 1 | 递推式 2 | 递推式 3 帕斯卡/杨辉三角公式 | 组合分析方法 | 递推式组合恒等式特点 ) 五、组合分析方法

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

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

现在开始构造选取问题 :

1 . 指定集合 : 假定有

n 1

个元素的集合 , 记作

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

,

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

S

中 , 选取

k 1

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

dbinom{n 1}{k 1}

个 ;

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

sumlimits_{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

个元素 ;

博客 集合 数学 原理

0 人点赞