• 周六. 8月 20th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

二项式定理与组合恒等式

admin

11月 28, 2021

本文版权归Azazel与博客园共有,欢迎转载,但需保留此声明,并给出原文地址,谢谢合作。

原文地址:https://www.cnblogs.com/Azazel/p/15151448.html

二项式定理

表述

[large (x+y)^n=sum_{k=0}^n egin{pmatrix} n\k end{pmatrix} x^ky^{n-k}
]

(~~~~) 其中 (n) 为正整数。

组合意义证明

(~~~~) 考虑暴力展开 ((x+y)^n)(n)((x+y)) 的积,则凑出 (k)(x) (即 (x^k) )的方案数为 (egin{pmatrix} n\k end{pmatrix}) ,同时剩下的 (n-k)(y) 自动凑成 (y^{n-k}),故 (x^k y^{n-k}) 的系数为 (egin{pmatrix} n\k end{pmatrix}) ,将所有项求和即为展开式。

数学归纳法

(~~~~)(n=1) 时,二项式定理经带入成立。

(~~~~) 考虑当二项式定理对 (n) 成立时是否也对 (n+1) 成立。

[large (x+y)^{n+1}
\ large =(x+y)(x+y)^n
\ large =(x+y)sum_{k=0}^n egin{pmatrix} n\k end{pmatrix} x^ky^{n-k}
\ large =sum_{k=0}^n egin{pmatrix} n\k end{pmatrix} x^{k+1}y^{n-k}+sum_{k=0}^n egin{pmatrix} n\k end{pmatrix} x^ky^{n-k+1}
\ large =x^{n+1}+sum_{k=0}^{n-1} egin{pmatrix} n\k end{pmatrix} x^{k+1}y^{n-k}+y^{n+1}+sum_{k=1}^n egin{pmatrix} n\k end{pmatrix} x^ky^{n-k+1}
]

(~~~~) 将第一个 (sum) 里面的 (k)(k-1) 来替换,以统一两个 (sum) 的上下限以及统一 (x)(y) 的次数:

[large sum_{k=0}^{n-1} egin{pmatrix} n\k end{pmatrix} x^{k+1}y^{n-k}= sum_{k=1}^n egin{pmatrix} n\k-1 end{pmatrix} x^ky^{n-k+1}
]

(~~~~) 代入:

[\ large =x^{n+1}+sum_{k=1}^n egin{pmatrix} n\k-1 end{pmatrix} x^ky^{n-k+1}+y^{n+1}+sum_{k=1}^n egin{pmatrix} n\k end{pmatrix} x^ky^{n-k+1}
\ large =x^{n+1}+y^{n+1}+sum_{k=1}^n (egin{pmatrix} n\k-1 end{pmatrix}+egin{pmatrix}n\k end{pmatrix})x^ky^{n-k+1}
]

(~~~~) 利用 ( ext{Pascal}) 公式((egin{pmatrix} n\k end{pmatrix}=egin{pmatrix} n-1\k end{pmatrix}+egin{pmatrix} n-1\k-1 end{pmatrix})):

[\ large =x^{n+1}+y^{n+1}+sum_{k=1}^n (egin{pmatrix} n\k-1 end{pmatrix}+egin{pmatrix}n\k end{pmatrix})x^ky^{n-k+1}
\ large =x^{n+1}+y^{n+1}+sum_{k=1}^n egin{pmatrix} n+1\k end{pmatrix} x^ky^{n-k+1}
\ large =sum_{k=0}^{n+1} egin{pmatrix}n+1\kend{pmatrix}x^ky^{n-k+1}
]

(~~~~) 综上:

[large (x+y)^{n+1}=sum_{k=0}^{n+1} egin{pmatrix}n+1\kend{pmatrix}x^ky^{n-k+1}
]

(~~~~) (mathcal{Q.E.D.})

组合恒等式 #1

表述

[large egin{pmatrix} n\k end{pmatrix}=egin{pmatrix} n\n-k end{pmatrix}
]

组合意义证明

(~~~~)(n) 个物品当中选 (k) 个的方案数,即在 (n) 个物品中有 (n-k) 个不选的方案数。

公式证明

[large egin{pmatrix} n\k end{pmatrix}=dfrac{n!}{k!(n-k)!}=egin{pmatrix} n\n-k end{pmatrix}
]

组合恒等式 #2

表述

[large egin{pmatrix} n\k end{pmatrix}=dfrac{n}{k}egin{pmatrix} n-1\k-1 end{pmatrix}
]

公式证明

[large egin{pmatrix} n\k end{pmatrix}=dfrac{n!}{k!(n-k)!}=dfrac{n imes (n-1)!}{k imes (k-1)![n-1-(k-1)]!}=dfrac{n}{k}egin{pmatrix} n-1\k-1 end{pmatrix}
]

组合恒等式 #3

表述

[large egin{pmatrix} n\k end{pmatrix}=egin{pmatrix} n-1\k end{pmatrix}+egin{pmatrix} n-1\k-1 end{pmatrix}
]

组合意义证明

(~~~~)(n) 个物品中取 (k) 个物品,方案数为 (egin{pmatrix} n\k end{pmatrix}) 。同时考虑其中某一个物品:

  • 选择该物品,则还需从剩下 (n-1) 个物品中选择 (k) 个,方案数 (egin{pmatrix} n-1\k end{pmatrix})
  • 不选该物品,则还需从剩下 (n-1) 个物品中选择 (k-1) 个,方案数 (egin{pmatrix} n-1\k -1end{pmatrix})

(~~~~) 以上两种情况相互独立,故 (egin{pmatrix} n\k end{pmatrix}=egin{pmatrix} n-1\k end{pmatrix}+egin{pmatrix} n-1\k -1end{pmatrix})

公式证明

[large egin{pmatrix} n-1\k end{pmatrix}+egin{pmatrix} n-1\k-1 end{pmatrix}
\ large =dfrac{(n-1)!}{k!(n-1-k)!}+dfrac{(n-1)!}{(k-1)!(n-k)!}
\ large =dfrac{(n-1)! imes (n-k)}{k!(n-k)!}+dfrac{(n-1)! imes k}{k!(n-k)!}
\ large =dfrac{(n-1)! imes n}{k!(n-k)!}=dfrac{n!}{k!(n-k)!}=egin{pmatrix} n\k end{pmatrix}
]

组合恒等式 #4

表述

[large sum_{k=0}^n egin{pmatrix} n\k end{pmatrix}=2^n
]

组合意义证明

(~~~~) 左边的意义即从 (n) 个物品中任意取若干个的方案数,则每个物品有取或不取两种选择,总方案数即为 (2^n)

二项式定理证明

(~~~~) 逆用二项式定理:

[large sum_{k=0}^n egin{pmatrix} n\k end{pmatrix}=sum_{k=0}^n egin{pmatrix} n\k end{pmatrix}1^k imes 1^{n-k}=(1+1)^n=2^n
]

组合恒等式 #5

表述

[large sum_{k=0}^n (-1)^k egin{pmatrix} n\k end{pmatrix}=0
]

组合数性质证明

  • (n) 为奇数时,该级数共有偶数项,同时绝对值相同的数刚好正负一一对应抵消;

  • (n) 为偶数时,用 ( ext{Pascal}) 公式拆开每一项后亦可正负一一抵消。

二项式定理证明

[large sum_{k=0}^n egin{pmatrix} n\k end{pmatrix} (-1)^k1^{n-k}=(1-1)^n=0^n=0
]

组合恒等式 #6

表述

[large sum_{k=0}^n kegin{pmatrix} n\k end{pmatrix}=n2^{n-1}
]

求导+二项式定理证明

(~~~~) 先写出一个二项式定理:

[large (x+1)^n=sum_{k=0}^n egin{pmatrix} n\k end{pmatrix}x^k
]

(~~~~) 为了凑出系数 (k) 我们对两边求导:

[large n(x+1)^{n-1}=sum_{k=0}^n kegin{pmatrix} n\k end{pmatrix}x^{k-1}
]

(~~~~)(x=1)

[large n2^{n-1}=sum_{k=0}^n kegin{pmatrix} n\k end{pmatrix}
]

推式子证明

[large sum_{k=0}^n kegin{pmatrix} n\k end{pmatrix}=sum_{k=0}^n (n-k) egin{pmatrix} n\k end{pmatrix}
]

左右相加得:

[large sum_{k=0}^n negin{pmatrix} n\k end{pmatrix}=n imes 2^n
]

则原式的值即为 (dfrac{n imes 2^n}{2}=n imes 2^{n-1})

组合恒等式 #7

表述

[large sum_{k=0}^n k^2 egin{pmatrix} n\k end{pmatrix}=n(n+1)2^{n-2}
]

推式子证明

(~~~~) 利用第二个组合恒等式:

[large sum_{k=0}^n k^2 egin{pmatrix} n\k end{pmatrix}\
large =sum_{k=0}^n k^2 dfrac{n}{k}egin{pmatrix} n-1\k-1 end{pmatrix}\
large =sum_{k=0}^n kn egin{pmatrix} n-1\k-1 end{pmatrix}\
]

(~~~~) 拆分 (k) ,方便利用第六个组合恒等式:

[large =sum_{k=0}^n n[(k-1)+1]egin{pmatrix} n-1\k-1 end{pmatrix}\
large =nsum_{k=0}^n (k-1)egin{pmatrix} n-1\k-1 end{pmatrix}+nsum_{k=0}^n egin{pmatrix} n-1\k-1 end{pmatrix}\
large =nsum_{k=1}^n (k-1)egin{pmatrix} n-1\k-1 end{pmatrix}+nsum_{k=1}^n egin{pmatrix} n-1\k-1 end{pmatrix}\
]

(~~~~) 变限使得其变为标准的组合恒等式:

[large =n sum_{k=0}^{n-1} k egin{pmatrix} n-1\k end{pmatrix}+n sum_{k=0}^{n-1} egin{pmatrix} n-1\kend{pmatrix}\
large =n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n-2}
]

组合恒等式 #8

表述

[large sum_{l=0}^n egin{pmatrix} l\k end{pmatrix}=egin{pmatrix} n+1\k+1 end{pmatrix}
]

组合意义证明

(~~~~)(n+1) 个物品里面选择 (k+1) 个,假设最后一个被选择的物品的位置为 (l+1) ,则剩下物品的选择方案为 (egin{pmatrix} l\k end{pmatrix}) ,枚举所有 (l) 并求和即为右式的意义。

组合恒等式 #9

[large egin{pmatrix} n\r end{pmatrix}egin{pmatrix} r\k end{pmatrix}=egin{pmatrix} n\k end{pmatrix}egin{pmatrix} n-k\r-k end{pmatrix}
]

组合意义证明

(~~~~) 左边为先在 (n) 个物品里选 (r) 个,再在选出的 (r) 个物品中选择 (k) 个的方案数。

(~~~~) 本质上为从 (n) 个物品里选 (k) 个,但是左边可能选出来的 (k) 个可能在不同的选 (r) 个物品的方案下相同,而相同的情况即为从剩下的 (n-k) 个物品中随便选 (r-k) 个得方案数。

组合恒等式 #10

表述

[large sum_{k=0}^r egin{pmatrix} m\k end{pmatrix} egin{pmatrix} n\r-k end{pmatrix}=egin{pmatrix} m+n\r end{pmatrix}
]

组合意义证明

(~~~~) 左式的意义为先从 (m) 个物品中选择 (k) 个,再从 (n) 个物品中选择 (r-k) 个。则相当于从 (m+n) 个物品中选择 (r) 个。由于 (kin[0,r]) ,故任何情况都可以视作上述情况中某一个 (k)

组合恒等式 #11

表述

[large sum_{k=0}^m egin{pmatrix} m\k end{pmatrix} egin{pmatrix} n\k end{pmatrix}=egin{pmatrix} m+n\m end{pmatrix}
]

组合恒等式证明

由第一个组合恒等式:

[large sum_{k=0}^m egin{pmatrix} m\k end{pmatrix} egin{pmatrix} n\k end{pmatrix}\
large =sum_{k=0}^n egin{pmatrix} m\m-k end{pmatrix} egin{pmatrix} n\k end{pmatrix}
]

再由第十个组合恒等式:

[large =egin{pmatrix} m+n\m end{pmatrix}
]

发表回复

您的电子邮箱地址不会被公开。