【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )

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

文章目录

  • 一、组合恒等式 ( 递推式 )
  • 二、组合恒等式 ( 变下项求和 ) 简单和
  • 二、组合恒等式 ( 变下项求和 ) 交错和

一、组合恒等式 ( 递推式 )

组合恒等式 ( 递推式 ) :

1 .

dbinom{n}{k} = dbinom{n}{n-k}

, 作用 : 化简

2 .

dbinom{n}{k} = dfrac{n}{k} dbinom{n - 1}{k - 1}

, 作用 : 求和时消去变系数 ;

3 .

dbinom{n}{k} = dbinom{n - 1}{k} dbinom{n - 1}{k - 1}

, 作用 : 求和时拆项 , 将一个组合数拆分成两项之和 , 或两项之差 , 然后合并 ;

二、组合恒等式 ( 变下项求和 ) 简单和

简单和 :

sum_{k=0}^{n}dbinom{n}{k} = 2^n

1. 证明 ( 二项式定理 ) : 通过二项式定理可以证明 ,

(x y)^n = sumlimits_{k=0}^n dbinom{n}{k}x^k y^{n-k}

中 , 使

x=y=1

, 即可得到上面的 简单和 组合恒等式 ;

2. 证明 ( 组合分析 ) : 将等号 左边 和 右边 各看做某个 组合计数问题的解 ,

( 1 ) 左侧 组合计数问题 :

sumlimits_{k=0}^{n}dbinom{n}{k}

可以看做

n

个元素的所有子集个数 ; ( 这也是集合中的幂集个数 ) ;

这是分类计数 , 最后将所有的类个数相加 , 即包含

0

个元素个数 , 包含

1

个元素子集个数 ,

cdots

, 包含

n

个元素子集个数 ;

( 2 ) 右侧 组合计数问题 :

n

个元素中 , 每个元素都有 放入子集中 , 不放入子集中 , 两种选择 , 那么所有元素的选择有 ,

begin{matrix} underbrace{ 2 times 2 times cdots times 2 } \ n 个end{matrix} = 2^n

个选择 , 这是 分步计数的乘法法则 ,

这是分步计数 , 最后将所有的分步结果相乘 , 即第

1

个元素选择个数 , 第

2

个元素选择个数 ,

cdots

, 第

n

个元素选择个数 ;

3. 应用场景 : 在序列求和场景使用 ;

二、组合恒等式 ( 变下项求和 ) 交错和

交错和 :

sum_{k=0}^{n} (-1)^k dbinom{n}{k} = 0

1. 证明 ( 二项式定理 ) : 通过二项式定理可以证明 ,

(x y)^n = sum_{k=0}^n dbinom{n}{k}x^k y^{n-k}

中 , 使

x= -1 , y=1

, 即可得到上面的 交错和 组合恒等式 ;

2. 证明 ( 组合分析 ) : 将等号 左边 和 右边 各看做某个 组合计数问题的解 , 完全展开上述组合数 , 这里需要先移项 , 将

k

为奇数的情况下 ,

(-1)^k

为

-1

, 将这种情况的分项移到右边 , 就有了如下公式 :

sum_{k=0}^{偶数} dbinom{n}{k} = sum_{k=1}^{奇数} dbinom{n}{k}

( 1 ) 左侧 组合计数问题 :

sum_{k=0}^{偶数} dbinom{n}{k}

可以看做

n

个元素的所有 偶数个 子集个数 ;

( 2 ) 右侧 组合计数问题 :

sum_{k=1}^{奇数} dbinom{n}{k}

可以看做

n

个元素的所有 奇数个 子集个数 ;

上述 奇数子集个数 与 偶数子集个数 是相等的 ;

3. 应用场景 : 在序列求和场景使用 ;

集合 数学

0 人点赞