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

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

文章目录

  • 一、二项式定理
  • 二、组合恒等式 ( 递推式 1 )
  • 三、组合恒等式 ( 递推式 2 )
  • 四、组合恒等式 ( 递推式 3 ) 帕斯卡 / 杨辉三角公式
  • 五、组合分析方法
  • 六、递推式组合恒等式特点

一、二项式定理

二项式定理 :

n

是正整数 , 对于一切

x

和

y

, 有以下定理 :

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

表示

n

元集中取

k

个元素的组合数 , 是 集合组合数

C(n,k)

的另一种写法 ;

另一个常用形式 (

y = 1

) :

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

基本求和公式 (

x = y =1

) :

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

二、组合恒等式 ( 递推式 1 )

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

组合分析方法 :

dbinom{n}{k}

是求

k

个子集选取方法 ,

dbinom{n}{n-k}

是求

n-k

个子集的选取方法 , 二者是一一对应的 ;

一般情况下 ,

dbinom{n}{k}

的下项 , 不超过上项的一半 ; 如果出现

dbinom{10}{8}

, 就可以写成

dbinom{10}{2}

三、组合恒等式 ( 递推式 2 )

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

代入组合数的公式 , 可以得到 等号

=

两侧的值是相等的 ;

该公式用于消去系数的 , 示例如下 :

计算

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

组合式 :

此时需要消去

k

系数 ;

使用

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

代替

dbinom{n}{k}

, 有以下计算过程 :

begin{array}{lcl} sumlimits_{k=0}^n kdbinom{n}{k} = sumlimits_{k=0}^n k dfrac{n}{k} dbinom{n - 1}{k - 1} end{array}

可以将加和式中的

k

约掉 , 此时

n

就与求和变量无关了 , 此时可以将

n

提取到加和符号

sum

外面 ,

begin{array}{lcl} sumlimits_{k=0}^n kdbinom{n}{k} &=& sumlimits_{k=0}^n k dfrac{n}{k} dbinom{n - 1}{k - 1} \\ &=& n sumlimits_{k=0}^n dbinom{n - 1}{k - 1} end{array}

然后计算

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

,

二项式定理是 :

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

根据二项式定理 , 可以得到

(1 1)^{n} = sumlimits_{k=0}^n dbinom{n}{k}

推导 :

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

之后可以继续进行后续计算 ;

四、组合恒等式 ( 递推式 3 ) 帕斯卡 / 杨辉三角公式

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

该递推式 , 用于拆项 :

可以将

dbinom{n}{k}

拆成

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

之和 ;

将

dbinom{n - 1}{k}

拆成

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

之差 ;

将 将

dbinom{n - 1}{k - 1}

拆成

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

之差;

在一堆求和的组合数中 , 拆分成两个数之差 , 可以抵消很多组合数 ;

经常在大的求和公式中进行化简时使用 ;

使用组合分析的办法证明该公式 :

取

n

元集中选取

k

子集 , 这是集合组合数 ;

指定其中某个元素

a

;

① 包含

a

元素 :

k

子集中包含

a

元素的情况组合数 为

dbinom{n - 1}{k - 1}

,

k

子集中包含

a

, 只需要在除

a

元素外 , 剩下的

n-1

个元素中 , 选出

k-1

个元素即可 ;

② 不包含

a

元素 :

k

子集中不包含

a

元素的情况组合数 为

dbinom{n - 1}{k}

,

k

子集中不包含

a

, 只需要在除

a

元素外 , 剩下的

n-1

个元素中 , 选出

k

个元素即可 ;

五、组合分析方法

以上面证明 帕斯卡 / 杨辉三角 公式为例

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

  • 指定集合 :
n

元集

  • 指定元素 : 某个特定元素
a
  • 指定计数问题 :
    • ① 问题 1 :
    n

    元集

    k

    组合数 ;

    • ② 问题 2 :
    n

    元集中

    k

    组合数 , 组合中含有元素

    a

    , 不含有元素

    a

    的两种组合计数 ;

六、递推式组合恒等式特点

使用 比较小的组合数 表示 比较大的组合数 , 称为递推式组合恒等式 ;

变量 集合 数学

0 人点赞