「 学习笔记 」二项式定理与组合恒等式

2021/11/17 23:13:59

本文主要是介绍「 学习笔记 」二项式定理与组合恒等式,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二项式定理与组合恒等式

前置知识

\[\dbinom {n} {k} = \mathrm{C} _ n ^ k = \dfrac {n!} {(n - k)! \times k!} \]

二项式定理

二项式定理:设 \(n\) 是正整数,对于一切 \(x\) 和 \(y\)

\[{(x + y)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k} \]

常用形式

\[{(x + 1)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k \]

等价形式

\[\begin{aligned} {(x + y)} ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k} \\ & = \sum \limits _ {k = 0} ^ n \dbinom {n} {n - k} x ^ k y ^{n - k} \\ & = \sum \limits _ {k = 0} ^ n \dbinom {n} {n - k} x ^ {n - k} y ^k \\ & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ {n - k} y ^k \\ \end{aligned} \]

证明 1 ( 组合意义 / 组合分析 / 算二次 )

\[{(x + y)} ^ n = (x + y) \times (x + y) \times \cdots \times (x + y) \]

对于每一项 \(x ^ k y ^ {n - k}\),其含义就是在 \(n\) 个 \((x + y)\) 中选择 \(k\) 个 \(x\)、\(n - k\) 个 \(y\),故有 \(\dbinom {n} {k}\) 中选法,即有 \(\dbinom {n} {k}\) 个 \(x ^ k y ^ {n - k}\)

证毕

证明 2 ( 数学归纳法 )

当 \(n = 1\) 时,公式显然成立
假设公式对于正整数 \(n\) 成立,即证明公式对于 \(n + 1\) 也成立
即证

\[{(x + y)} ^ {n + 1} = \sum \limits _ {k = 0} ^ {n + 1} \dbinom {n} {k} x ^ k y ^ {n + 1 - k} \]

  • 因为公式对于 \(n\) 成立,故有

\[\begin{aligned} {(x + y)} ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k} \\ {(x + y)} ^ {n + 1} & = (x + y) \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k} \\ & = x \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k} + y \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k} \\ & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ {k + 1} y ^{n - k} + \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 - k} \\ & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ {k + 1} y ^{(n + 1) - (k + 1)} + \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 - k} \\ & = \sum \limits _ {k + 1 = 1} ^ {n + 1} \dbinom {n} {(k + 1) - 1} x ^ {k + 1} y ^{(n + 1) - (k + 1)} + \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 - k} \\ & = \sum \limits _ {k = 1} ^ {n + 1} \dbinom {n} {k - 1} x ^ k y ^{n + 1 - k} + \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 - k} \\ & = \sum \limits _ {k = 1} ^ {n} \dbinom {n} {k - 1} x ^ k y ^{n + 1 - k} + x ^ {n + 1} + \sum \limits _ {k = 1} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 - k} + y ^ {n + 1} \\ & = \dbinom {n + 1} {0} x ^ {n + 1} + \sum \limits _ {k = 1} ^ {n} \dbinom {n} {k - 1} x ^ k y ^{n + 1 - k} + \sum \limits _ {k = 1} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 - k} + \dbinom {n + 1} {n + 1} y ^ {n + 1} \\ \end{aligned} \]

由 \(\mathrm{Pascal}\) 公式 \(\dbinom {n + 1} {k} = \dbinom {n} {k - 1} + \dbinom {n} {k}\)(后面会证明),就可以把 \(k\) 相等的项合并了

\[\begin{aligned} {(x + y)} ^ {n + 1} & = \dbinom {n + 1} {0} x ^ {n + 1} + \sum \limits _ {k = 1} ^ {n} \dbinom {n} {k - 1} x ^ k y ^{n + 1 - k} + \sum \limits _ {k = 1} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 - k} + \dbinom {n + 1} {n + 1} y ^ {n + 1} \\ & = \dbinom {n + 1} {0} x ^ {n + 1} y ^ 0 + \sum \limits _ {k = 1} ^ {n} \dbinom {n + 1} {k} x ^ k y ^{n + 1 - k} + \dbinom {n + 1} {n + 1} x ^ 0 y ^ {n + 1} \\ & = \sum \limits _ {k = 0} ^ {n + 1} \dbinom {n + 1} {k} x ^ k y ^{n + 1 - k} \\ \end{aligned} \]

证毕

组合恒等式

公式 1

\[\dbinom {n} {k} = \dbinom {n} {n - k} \]

证明 ( 组合意义 )

\(n\) 个小球选择 \(k\) 个留下,等价于选择 \(n - k\) 个不留下

证毕

公式 2

\[\dbinom {n} {k} = \dfrac {n} {k} \dbinom {n - 1} {k - 1} \]

证明 ( 公式法 )

\[\begin{aligned} \dbinom {n} {k} & = \dfrac {n!} {(n - k)! \times k!} \\ & = \dfrac {n} {k} \times \dfrac {(n - 1)!} {(n - k)! \times k!} \\ & = \dfrac {n} {k} \times \dfrac {(n - 1)!} {[(n - 1) - (k - 1)]! \times k!} \\ & = \dfrac {n} {k} \dbinom {n - 1} {k - 1} \\ \end{aligned} \]

证毕

公式 3 ( Pascal 公式 )

\[\dbinom {n} {k} = \dbinom {n - 1} {k} + \dbinom {n - 1} {k - 1} \]

证明 ( 组合意义 )

\(n\) 个小球中选择 \(k\) 个,等价于 ( 不选最后一个,前 \(n - 1\) 个中选择 \(k\) 个 ) 和 ( 选最后一个,前 \(n - 1\) 个中选择 \(k - 1\) 个 ) 的并集

公式 4

\[\sum \limits _ {k = 0} ^ {n} \dbinom {n} {k} = 2 ^ n \]

证明 ( 公式法 )

由二项式定理得 \({(x + y)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k}\),令 \(x = y = 1\),则等式变为

\[\begin{aligned} {(1 + 1)} ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} \times 1 ^ k \times 1 ^{n - k} \\ 2 ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} \\ \sum \limits _ {k = 0} ^ n \dbinom {n} {k} & = 2 ^ n \\ \end{aligned} \]

证毕

公式 5

\[\sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} = 0 \]

证明 ( 公式法 )

由二项式定理得 \({(x + y)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k}\),令 \(x = -1\)、\(y = 1\),则等式变为

\[\begin{aligned} {[(-1) + 1]} ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} \times {(-1)} ^ k \times 1 ^{n - k} \\ 0 ^ n & = \sum \limits _ {k = 0} ^ n {(-1)} ^ k \dbinom {n} {k} \\ \sum \limits _ {k = 0} ^ n {(-1)} ^ k \dbinom {n} {k} & = 0 \\ \end{aligned} \]

证毕

公式 6 ( 变下项求和 )

\[\sum \limits _ {k = 0} ^ {n} k \dbinom {n} {k} = n 2 ^ {n - 1} \]

证明 1 ( 组合意义 )

  • 公式含义:选择 \(n\) 个小球的所有选法中每个小球出现的次数和
  • 右式含义:\(n\) 个小球,每个小球被选择的次数是 \(2 ^ {n - 1}\)
  • 左式含义:对于所有选法中选择 \(k\) 个小球情况,其对答案的贡献是 \(k\),共有 \(\dbinom {n} {k}\) 种选法

显然,三种含义等价

证毕

证明 2 ( 公式法 )

公式 2 \(\dbinom {n} {k} = \dfrac {n} {k} \dbinom {n - 1} {k - 1}\) 得:

\[\begin {aligned} \sum \limits _ {k = 0} ^ {n} k \dbinom {n} {k} & = 0 \dbinom {n} {k} + \sum \limits _ {k = 1} ^ {n} k \times \dbinom {n} {k} \\ & = 0 + \sum \limits _ {k = 1} ^ {n} k \times \dfrac {n} {k} \dbinom {n - 1} {k - 1} \\ & = \sum \limits _ {k = 1} ^ {n} n \dbinom {n - 1} {k - 1} \\ & = n \sum \limits _ {k = 1} ^ {n} \dbinom {n - 1} {k - 1} \\ & = n \sum \limits _ {k = 0} ^ {n - 1} \dbinom {n - 1} {k} \\ \end{aligned} \]

公式 4 \(\sum \limits _ {k = 0} ^ {n} \dbinom {n} {k} = 2 ^ n\) 得 \(\sum \limits _ {k = 0} ^ {n - 1} \dbinom {n - 1} {k} = 2 ^ {n - 1}\),故

\[\begin {aligned} \sum \limits _ {k = 0} ^ {n} k \dbinom {n} {k} & = n \sum \limits _ {k = 0} ^ {n - 1} \dbinom {n - 1} {k} \\ & = n 2 ^ {n - 1} \\ \end{aligned} \]

证毕

公式 7

\[\sum \limits _ {k = 0} ^ {n} k ^ 2 \dbinom {n} {k} = n (n + 1) 2 ^ {n - 2} \]

证明 1 ( 组合意义 )

\[\begin {aligned} n (n + 1) 2 ^ {n - 2} & = n (n - 1) 2 ^ {n - 2} + n \times 2 \times 2 ^ {n - 2} \\ & = n (n - 1) 2 ^ {n - 2} + n \times 2 ^ {n - 1} \end {aligned} \]

  • 左式含义:有 \(n\) 个不同的数,对于选择 \(k\) 个不同的数的情况,可以组成 \(k ^ 2\) 种有序数对,每种有序数对 \((a, b)\) 对答案的贡献为 \(1\),一起对答案的贡献就是 \(k ^ 2\),选择 \(k\) 个不同的数有 \(\dbinom {n} {k}\) 种选法
  • 右式含义:考虑每种有序数对 \((a, b)\) 对答案的贡献;若 \(a \neq b\),对于其它 \(n - 2\) 个数的每种选法中,有 \(1\) 的贡献,有 \(2 ^ {n - 2}\) 种选法;若 \(a = b\),对于其它 \(n - 2\) 个数的每种选法中,有 \(1\) 的贡献,有 \(2 ^ {n - 1}\) 种选法

右式含义中的两种情况的并集等于左式含义中的情况,故两种含义等价

证毕

证明 2 ( 公式法 )

公式 2 \(\dbinom {n} {k} = \dfrac {n} {k} \dbinom {n - 1} {k - 1}\) 得:

\[\begin {aligned} \sum \limits _ {k = 0} ^ {n} k ^ 2 \dbinom {n} {k} & = 0 + \sum \limits _ {k = 1} ^ {n} k ^ 2 \times \dfrac {n} {k} \dbinom {n - 1} {k - 1} \\ & = \sum \limits _ {k = 1} ^ {n} k ^ 2 \times \dfrac {n} {k} \dbinom {n - 1} {k - 1} \\ & = \sum \limits _ {k = 1} ^ {n} k \times n \dbinom {n - 1} {k - 1} \\ & = n \sum \limits _ {k = 1} ^ {n} k \dbinom {n - 1} {k - 1} \\ & = n \sum \limits _ {k = 0} ^ {n - 1} (k + 1) \dbinom {n - 1} {k} \\ & = n \sum \limits _ {k = 0} ^ {n - 1} k \dbinom {n - 1} {k} + n \sum \limits _ {k = 0} ^ {n - 1} \dbinom {n - 1} {k} \\ \end{aligned} \]

公式 6 \(\sum \limits _ {k = 0} ^ {n} k \dbinom {n} {k} = n 2 ^ {n - 1}\) 得:\(\sum \limits _ {k = 0} ^ {n - 1} k \dbinom {n - 1} {k} = (n - 1) 2 ^ {n - 2}\)
公式 4 \(\sum \limits _ {k = 0} ^ {n} \dbinom {n} {k} = 2 ^ n\) 得:\(\sum \limits _ {k = 0} ^ {n - 1} \dbinom {n - 1} {k} = 2 ^ {n - 1}\)

故原式可化为:

\[\begin {aligned} \sum \limits _ {k = 0} ^ {n} k ^ 2 \dbinom {n} {k} & = n \sum \limits _ {k = 0} ^ {n - 1} k \dbinom {n - 1} {k} + n \sum \limits _ {k = 0} ^ {n - 1} \dbinom {n - 1} {k} \\ & = n (n - 1) 2 ^ {n - 2} + n 2 ^ {n - 1} \\ & = n (n - 1) 2 ^ {n - 2} + n \times 2 \times 2 ^ {n - 2} \\ & = n (n + 1) 2 ^ {n - 2} \\ \end{aligned} \]

证毕

公式 8 ( 变上项求和 )

\[\sum \limits _ {l = 0} ^ n \dbinom {l} {k} = \dbinom {n + 1} {k + 1} n, k \in N \]

证明 ( 组合意义 )

在 \(n + 1\) 个小球中选择 \(k + 1\) 个
对于所有选法中,考虑选择的最后一个小球的位置为 \(l + 1(0 \leq l \leq n)\) 时对答案的贡献,就是在前 \(l\) 个小球中选择 \(k\) 的方案数
因此,对于所有的 \(l\) 属于的集合的并集,就等于在 \(n + 1\) 个小球中选择 \(k + 1\) 个的集合

证毕

公式 9

\[\dbinom {n} {r} \dbinom {r} {k} = \dbinom {n} {k} \dbinom {n - k} {r - k} \]

证明 ( 组合意义 )

把 \(n\) 个球分成 \(3\) 堆,使得第 \(1\) 堆有 \(k\) 个球、第 \(2\) 堆有 \(r - k\) 个球、第 \(3\) 堆有 \(n - r\) 个球 的方案数

  • 左式含义:先从这 \(n\) 个球中选出 \(r\) 个球,把剩下的 \(n - r\) 个分到第 \(3\) 堆;再从这 \(r\) 个中选择 \(k\) 个分到第 \(1\) 堆,剩下的 \(r - k\) 给分到第 \(2\) 堆
  • 右式含义:先从这 \(n\) 个球中选出 \(k\) 个球分到第 \(1\) 堆;再从剩下的 \(n - k\) 个中选择 \(r - k\) 个分到第 \(2\) 堆,剩下的 \(n - r\) 给分到第 \(3\) 堆

显然,两种含义不会重复,并且两种含义等价

证毕

公式 10

\[\sum \limits _ {k = 0} ^ {r} \dbinom {m} {k} \dbinom {n} {r - k} = \dbinom {m + n} {r} \]

证明 ( 组合意义 )

  • 右式含义:从 \(m + n\) 个球中选出 \(r\) 个球
  • 左式含义:从前 \(m\) 个球中选出 \(k\) 个球和从后 \(n\) 个球中选出 \(r - k\) 个球的并集的并集(第一个并集对于每个 \(k\) 的方案数,第二个并集对于 \(\sum\))

显然,两种含义等价

证毕

公式 11

\[\sum \limits _ {k = 0} ^ {m} \dbinom {m} {k} \dbinom {n} {k} = \dbinom {m + n} {m} \]

证明 ( 公式法 )

\[\begin{aligned} \sum \limits _ {k = 0} ^ {m} \dbinom {m} {k} \dbinom {n} {k} & = \sum \limits _ {k = 0} ^ {m} \dbinom {m} {m - k} \dbinom {n} {k} \\ \end{aligned} \]

公式 10 \(\sum \limits _ {k = 0} ^ {r} \dbinom {m} {k} \dbinom {n} {r - k} = \dbinom {m + n} {r}\) 得 \(\sum \limits _ {k = 0} ^ {r} \dbinom {m} {r - k} \dbinom {n} {k} = \dbinom {n + m} {r}\),令 \(r = m\) 得:\(\sum \limits _ {k = 0} ^ {m} \dbinom {m} {m - k} \dbinom {n} {k} = \dbinom {m + n} {m}\),故

\[\begin{aligned} \sum \limits _ {k = 0} ^ {m} \dbinom {m} {k} \dbinom {n} {k} & = \sum \limits _ {k = 0} ^ {m} \dbinom {m} {m - k} \dbinom {n} {k} \\ & = \dbinom {m + n} {m} \\ \end{aligned} \]

证毕

课后习题

习题 1

\({(3x - 2y)} ^ {18}\) 的展开式中,\(x ^ 5 y ^ {13}\) 的系数是多少?\(x ^ 8 y ^ 9\) 的系数是多少?

答案

解:
\(x ^ 5 y ^ {13}\) 的系数为 \(\dbinom {18} {5} (3 ^ 5 + 2 ^ {13})\),\(x ^ 8 y ^ 9\) 的系数为 \(0\)

习题 2

  1. 用二项式定理证明:\(3 ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} 2 ^ k\)
  2. 对于任意实数 \(r\) 求 $ \sum \limits _ {k = 0} ^ n \dbinom {n} {k} r ^ k$

答案

  1. 证:
    二项式定理常用形式 得:\({(x + 1)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k\)
    令 \(x = 2\),则等式变为 \({(2 + 1)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} 2 ^ k\),即 \(3 ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} 2 ^ k\)
    证毕

  2. 解:
    二项式定理常用形式 得:$ \sum \limits _ {k = 0} ^ n \dbinom {n} {k} r ^ k = {(r + 1)} ^ n$

习题 3

二项式定理 证明:\(2 ^ n = \sum \limits _ {k = 0} ^ {n} {(- 1)} ^ k \dbinom {n} {k} 3 ^ {n - k}\)

答案

证:
二项式定理 得:\({(x + y)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k}\)
令 \(x = -1, y = 3\),则等式变为 \({[(-1) + 3]} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} {(-1)} ^ k 3 ^{n - k}\)
即 \(2 ^ n = \sum \limits _ {k = 0} ^ {n} {(- 1)} ^ k \dbinom {n} {k} 3 ^ {n - k}\)
证毕

习题 4

求 $ \sum \limits _ {k = 1} ^ n {(-1)} ^ k \dbinom {n} {k} {10} ^ k$

答案

解:
$ \sum \limits _ {k = 0} ^ n {(-1)} ^ k \dbinom {n} {k} {10} ^ k = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} {(-10)} ^ k$
二项式定理常用形式 得:\({(x + 1)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k\)
令 \(x = -10\),则等式变为 \({[(-10) + 1]} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} {(-10)} ^ k\)
故 $ \sum \limits _ {k = 0} ^ n \dbinom {n} {k} {(-10)} ^ k = {(-9)} ^ n$

习题 5

用组合意义证明 \(\dbinom {n} {k} - \dbinom {n - 3} {k} = \dbinom {n - 1} {k - 1} + \dbinom {n - 2} {k - 1} + \dbinom {n - 3} {k - 1}\)

答案

证:
选择 \(n\) 个小球中的 \(k\) 个

  • 左式含义:( 总方案数 ) \(-\) ( 前 \(3\) 个小球都不选的方案数 ),即表示至少选择前 \(3\) 个小球中的一个的方案数
  • 右式含义:( 选择第 \(1\) 个小球的方案数 ) \(+\) ( 不选择第 \(1\) 个小球,选择第 \(2\) 个小球的方案数 ) \(+\) ( 不选择第 \(1\) 个小球和第 \(2\) 个小球,选择第 \(3\) 个小球的方案数 )

显然,这两个含义是等价的
证毕

习题 6

设 \(n\) 是正整数,请证明:

\[ \sum \limits _ {k = 0} ^ n {(-1)} ^ k {\dbinom {n} {k}} ^ 2 = \begin{cases} 0, n = 2m + 1, m \in N_+ \\ {(-1)} ^ m \dbinom {2m} {m}, n = 2m, m \in N_+ \\ \end{cases} \]

答案

证:
如果 \(n\) 是奇数,则 \(k\) 和 \(n - k\) 是不同奇偶的
\(\therefore\) \({(-1)} ^ k\) 和 \({(-1)} ^ {n - k}\) 是一正一负的

\[\begin{aligned} \sum \limits _ {k = 0} ^ n {(-1)} ^ k {\dbinom {n} {k}} ^ 2 & = \sum \limits _ {k = 0} ^ {m} {(-1)} ^ k \dbinom {n} {k} + \sum \limits _ {k = m + 1} ^ {n} {(-1)} ^ k \dbinom {n} {k} \\ & = \sum \limits _ {k = 0} ^ {m} {(-1)} ^ k \dbinom {n} {k} - \sum \limits _ {k = m + 1} ^ {n} {(-1)} ^ {n - k} \dbinom {n} {n - k} \\ & = \sum \limits _ {k = 0} ^ {m} {(-1)} ^ k \dbinom {n} {k} - \sum \limits _ {k = 0} ^ {m} {(-1)} ^ k \dbinom {n} k \\ & = 0 \\ \end{aligned} \]

如果 \(n\) 是偶数,则 \(k\) 和 \(n - k\) 是同奇偶的
\(\therefore\) \({(-1)} ^ k = {(-1)} ^ {n - k}\)

二项式定理 得:

\[\begin{aligned} {(x + 1)} ^ n & = \sum \limits _ {k = 0} ^ {n} \dbinom {n} {k} x ^ k \\ {(x - 1)} ^ n & = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ {n - k} \dbinom {n} {k} x ^ k \\ & =\sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ k \\ {(x ^ 2 - 1)} ^ n & = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ {n - k} \dbinom {n} {k} {(x ^ 2)} ^ k \\ & = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} {(x ^ 2)} ^ k \\ & = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ {2k} \\ \end{aligned} \]

故可列等式 \({(x + 1)} ^ n {(x - 1)} ^ n = {(x ^ 2 - 1) ^ n}\)

\[\begin{aligned} {(x + 1)} ^ n {(x - 1)} ^ n & = {(x ^ 2 - 1) ^ n} \\ \sum \limits _ {k = 0} ^ {n} \dbinom {n} {k} x ^ k \times \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ k & = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ {2k} \\ \end{aligned} \]

\(\because\) 左右两边多项式相等
\(\therefore \forall i\),\(x ^ i\) 的系数相等
令 \(i = n = 2m\),即考虑 \(x ^ n\) 的系数

\[\begin{aligned} \sum \limits _ {k = 0} ^ {n} \dbinom {n} {n - k} x ^ {n - k} \times {(-1)} ^ k \dbinom {n} {k} x ^ k & = {(-1)} ^ m \dbinom {n} {m} x ^ n \\ \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ {n - k} \times \dbinom {n} {k} x ^ k & = {(-1)} ^ m \dbinom {n} {m} x ^ n \\ \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k {\dbinom {n} {k}} ^ 2 x ^ n & = {(-1)} ^ m \dbinom {n} {m} x ^ n \\ \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k {\dbinom {n} {k}} ^ 2 x ^ n & = {(-1)} ^ m \dbinom {2m} {m} x ^ n \\ \end{aligned} \]

同时约去 \(x ^ n\),得

\[\begin{aligned} \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k {\dbinom {n} {k}} ^ 2 & = {(-1)} ^ m \dbinom {2m} {m} \\ \end{aligned} \]

证毕

习题 7

化简 \(\dbinom {n} {k} + 3 \dbinom {n} {k - 1} + 3 \dbinom {n} {k - 2} + \dbinom {n} {k - 3}\)

答案

证:
$\dbinom {n} {k} + 3 \dbinom {n} {k - 1} + 3 \dbinom {n} {k - 2} + \dbinom {n} {k - 3} = \dbinom {3} {0} \dbinom {n} {k} + \dbinom {3} {1} \dbinom {n} {k - 1} + \dbinom {3} {2} \dbinom {n} {k - 2} + \dbinom {3} {3} \dbinom {n} {k - 3} = $
有 \(2\) 堆小球,第 \(1\) 堆有 \(3\) 个,第 \(2\) 堆有 \(n\) 个
在 \(n + 3\) 个小球中选择 \(k\) 个,等价于 ( 在第 \(1\) 堆选择 \(0\) 个,第 \(2\) 堆选择 \(k\) 个 ) + ( 在第 \(1\) 堆选择 \(1\) 个,第 \(2\) 堆选择 \(k - 1\) 个 ) + ( 在第 \(1\) 堆选择 \(2\) 个,第 \(2\) 堆选择 \(k - 2\) 个 ) + ( 在第 \(1\) 堆选择 \(3\) 个,第 \(2\) 堆选择 \(k - 3\) 个)
证毕

习题 8

证明 \(\dbinom {r} {k} = \dfrac {r} {r - k} \dbinom {r - 1} {k}\),其中 \(r \in R\),\(k \in Z\),\(r \neq k\)

答案

本题需要使用牛顿二项式,不符合本博客的讨论范围

习题 9

求:\(1 - \dfrac {1} {2} \dbinom {n} {1} + \dfrac {1} {3} \dbinom {n} {2} - \dfrac {1} {4} \dbinom {n} {3} + \cdots + {(-1)} ^ n \dfrac {1} {n + 1} \dbinom {n} {n}\)

答案

解:

\[\begin{aligned} 1 - \dfrac {1} {2} \dbinom {n} {1} + \dfrac {1} {3} \dbinom {n} {2} - \dfrac {1} {4} \dbinom {n} {3} + \cdots + {(-1)} ^ n \dfrac {1} {n + 1} \dbinom {n} {n} & = \sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dfrac {1} {k + 1} \dbinom {n} {k} \\ \end{aligned} \]

公式 2 \(\dbinom {n + 1} {k + 1} = \dfrac {n + 1} {k + 1} \dbinom {n} {k}\) 得:\(\dbinom {n} {k} = \dfrac {k + 1} {n + 1} \dbinom {n + 1} {k + 1}\)

\[\begin{aligned} \sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dfrac {1} {k + 1} \dbinom {n} {k} & = \sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dfrac {1} {k + 1} \times \dfrac {k + 1} {n + 1} \dbinom {n + 1} {k + 1} \\ & = \sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dfrac {1} {n + 1} \dbinom {n + 1} {k + 1} \\ & = \dfrac { \sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dbinom {n + 1} {k + 1}} {n + 1} \\ & = -\dfrac { \sum \limits _ {k = 0} ^ n {(-1)} ^ {k + 1} \times \dbinom {n + 1} {k + 1}} {n + 1} \\ & = -\dfrac { \sum \limits _ {k = 1} ^ {n + 1} {(-1)} ^ k \times \dbinom {n + 1} {k}} {n + 1} \\ & = -\dfrac { \sum \limits _ {k = 0} ^ {n + 1} {(-1)} ^ k \times \dbinom {n + 1} {k} - {(-1)} ^ 0 \times \dbinom {n + 1} {0}} {n + 1} \\ & = -\dfrac { \sum \limits _ {k = 0} ^ {n + 1} {(-1)} ^ k \times \dbinom {n + 1} {k} - 1} {n + 1} \\ \end{aligned} \]

公式 5 $ \sum \limits _ {k = 0} ^ n {(-1)}^k \dbinom {n} {k} = 0$ 得:$ \sum \limits _ {k = 0} ^ {n + 1} {(-1)}^k \dbinom {n + 1} {k} = 0$

\[\begin{aligned} -\dfrac { \sum \limits _ {k = 0} ^ {n + 1} {(-1)} ^ k \times \dbinom {n + 1} {k} - 1} {n + 1} & = - \dfrac {0 - 1} {n + 1} \\ & = - \dfrac {-1} {n + 1} \\ & = \dfrac {1} {n + 1} \\ \end{aligned} \]

\(\therefore 1 - \dfrac {1} {2} \dbinom {n} {1} + \dfrac {1} {3} \dbinom {n} {2} - \dfrac {1} {4} \dbinom {n} {3} + \cdots + {(-1)} ^ n \dfrac {1} {n + 1} \dbinom {n} {n} = \dfrac {1} {n + 1}\)

习题 10

  1. 证明:\(\dbinom {n + 1} {k + 1} = \dbinom {0} {k} + \dbinom {1} {k} + \cdots + \dbinom {n - 1} {k} + \dbinom {n} {k}\)
  2. 证明:\(m ^ 2 = 2 \dbinom {m} {2} + \dbinom {m} {1}\)

答案

  1. 证:
    \(\dbinom {n + 1} {k + 1} = \dbinom {0} {k} + \dbinom {1} {k} + \cdots + \dbinom {n - 1} {k} + \dbinom {n} {k} = \sum \limits _ {i = 0} ^ {n} \dbinom {i} {k}\)
    在 \(n + 1\) 个小球中选择 \(k + 1\) 个的方案数,等价于 ( 枚举选择的最后一个小球的位置,在这个小球前选择 \(k\) 个小球 ) 的方案数之和
    证毕
  2. 证:
    ( 在 \(m\) 个不同的数中先后选择 \(2\) 个可以相同的数的方案数,组成一个有序数对 ),等价于 ( 选择不同的 \(2\) 个数组成 \(2\) 个有序数对 ) 和 ( 选择 \(1\) 个数组成 \(1\) 个有序数对 ) 的方案数之和
    证毕

习题 11

求整数 \(a, b, c\),使得对于所有的 \(m\),满足:\(m ^ 3 = a \dbinom {m} {3} + b \dbinom {m} {2} + c \dbinom {m} {1}\)

答案

解:
( 在 \(m\) 个不同的数中先后选择 \(3\) 个可以相同的数的方案数,组成一个有序数对 ),等价于 ( 选择不同的 \(3\) 个数组成 \(6\) 个有序数对 )、( 选择不同的 \(2\) 个数组成 \(6\) 个有序数对 )、( 选择 \(1\) 个数组成 \(1\) 个有序数对 ) 的方案数之和
\(\therefore m ^ 3 = 6 \times \dbinom {m} {3} + 6 \times \dbinom {m} {2} + 1 \times \dbinom {m} {1}\)
\(\therefore a = 6, b = 6, c = 1\)

习题 12

设 \(n\) 是整数,请证明 \(\sum \limits _ {k = 1} ^ {n} \dbinom {n} {k} \dbinom {n} {k - 1} = \dfrac {1} {2} \dbinom {2n + 2} {n + 1} - \dbinom {2n} {n}\)

答案

证:

\[\begin {aligned} \sum \limits _ {k = 1} ^ {n} \dbinom {n} {k} \dbinom {n} {k - 1} & = \sum \limits _ {k = 1} ^ {n} \dbinom {n} {n - k} \dbinom {n} {k - 1} \\ \dfrac {1} {2} \dbinom {2n + 2} {n + 1} - \dbinom {2n} {n} & = \dfrac {1} {2} \times \dfrac {2n + 2} {n + 1} \dbinom {2n + 1} {n} - \dbinom {2n} {n} \\ & = \dfrac {1} {2} \times 2 \dbinom {2n + 1} {n} - \dbinom {2n} {n} \\ & = \dbinom {2n + 1} {n} - \dbinom {2n} {n} \\ & = \dbinom {2n} {n - 1} \\ \end{aligned} \]

即证 \(\sum \limits _ {k = 1} ^ {n} \dbinom {n} {n - k} \dbinom {n} {k - 1} = \dbinom {2n} {n - 1}\)

  • 右式含义:在 \(2n\) 个小球中选择 \(n - 1\) 个的方案数
  • 左式含义:( 在前 \(n\) 个小球中选择 \(n - k\) 个 ) 和 ( 在后 \(n\) 个小球中选择 \(k - 1\) 个 ) 的方案数之和;\(\because 1 \leq k \leq n\),\(\therefore n - k, k - 1 \geq 0\),故此含义成立

显然,左右两式等价

证毕

习题 13

设 \(n\) 是整数,请用组合意义证明 \(\sum \limits _ {k = 1} ^ {n} k {\dbinom {n} {k}} ^ 2 = n \dbinom {2n - 1} {n - 1}\)

答案

证:

\[\begin {aligned} \sum \limits _ {k = 1} ^ {n} k {\dbinom {n} {k}} ^ 2 & = \sum \limits _ {k = 1} ^ {n} k \dbinom {n} {k} \dbinom {n} {n - k} \\ & = \sum \limits _ {k = 1} ^ {n} k \times \dfrac {n} {k} \dbinom {n - 1} {k - 1} \dbinom {n} {n - k} \\ & = \sum \limits _ {k = 1} ^ {n} n \dbinom {n - 1} {k - 1} \dbinom {n} {n - k} \\ & = n \sum \limits _ {k = 1} ^ {n} \dbinom {n - 1} {k - 1} \dbinom {n} {n - k} \\ & = n \sum \limits _ {k = 1} ^ {n} \dbinom {n} {n - k} \dbinom {n - 1} {k - 1} \\ \end{aligned} \]

即证 \(n \sum \limits _ {k = 1} ^ {n} \dbinom {n} {n - k} \dbinom {n - 1} {k - 1} = n \dbinom {2n - 1} {n - 1}\)
即证 \(\sum \limits _ {k = 1} ^ {n} \dbinom {n} {n - k} \dbinom {n - 1} {k - 1} = \dbinom {2n - 1} {n - 1}\)

  • 右式含义:在 \(2n - 1\) 个小球中选择 \(n - 1\) 个的方案数
  • 左式含义:( 在前 \(n\) 个小球中选择 \(n - k\) 个 ) 和 ( 在后 \(n - 1\) 个小球中选择 \(k - 1\) 个 ) 的方案数之和;\(\because 1 \leq k \leq n\),\(\therefore n - k, k - 1 \geq 0\),故此含义成立

显然,左右两式等价

证毕



这篇关于「 学习笔记 」二项式定理与组合恒等式的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程