组合数

默认会组合数基础内容，二项式定理

广义组合数定义

(\binom{n}{m}) = \frac{n^{\underset{―}{m}}}{m!}

n^{\underset{―}{m}} = n \times (n - 1) \times (n - 2) \times . . . \times (n - m + 1)

组合数常用公式及证明

这里的证明主要分为 3 种

1.用组合意义证明

2.用定义证明(拆成阶乘形式)

3.用前面的公式推导

不带求和

1.吸收公式（Absorption Identity）：

(\binom{n}{k}) = \frac{n}{k} (\binom{n - 1}{k - 1})

定义证明：

(\binom{n}{k}) = \frac{n!}{(k - n)! \times k!}

\frac{n}{k} (\binom{n - 1}{k - 1}) = \frac{n}{k} \frac{(n - 1)!}{(n - k)! \times (k - 1)!} = \frac{n!}{(k - n)! \times k!}

推广：

k (\binom{n}{k}) = n (\binom{n - 1}{k - 1}), (n - k) (\binom{n}{k}) = n (\binom{n - 1}{k})

均可用定义证明，不再赘述。

2.上指标反转（Negating the Upper Index）：

(\binom{n}{k}) = (- 1)^{k} (\binom{k - n - 1}{k})

定义证明：

（这里运用组合数广义定义）

(\binom{k - n - 1}{k}) = \frac{(k - n - 1)^{\underset{―}{k}}}{k!} \begin{aligned} (k - n - 1)^{\underset{―}{k}} & = (k - n - 1) \times (k - n - 2) \times . . . \times (- n) \\ = (- 1)^{k} \times n \times (n + (k - 1) - k) \times . . . \times (n + 1 - k) \\ = (- 1)^{k} n^{\underset{―}{k}} \end{aligned}

把这个带入就可以了。

3.三项式系数恒等式：

(\binom{n}{m}) (\binom{m}{k}) = (\binom{n}{k}) (\binom{n - k}{m - k})

组合意义证明：

从 $n$ 个小球中选 $m$ 个染成红色，再从 $m$ 个红色小球中选 $k$ 个染成蓝色。

从 $n$ 个小球中选 $k$ 个染成蓝色，再从 $n - k$ 个无色小球中选 $m - k$ 个染成红色。

两种方法得到的最终结果等价。

定义证明：

(\binom{n}{m}) (\binom{m}{k}) = \frac{n!}{m! \times (n - m)!} \times \frac{m!}{k! \times (m - k)!} = \frac{n!}{k! \times (n - m)! \times (m - k)!}

(\binom{n}{k}) (\binom{n - k}{m - k}) = \frac{n!}{k! \times (n - k)!} \times \frac{(n - k)!}{(n - m)! \times (m - k)!} = \frac{n!}{k! \times (n - m)! \times (m - k)!}

4.帕斯卡公式

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

组合意义证明

从 $n$ 个小球中选 $k$ 个，一定是最后一个小球不选然后从 $n - 1$ 个里面选 $k$ 个和最后一个小球要选然后从 $n - 1$ 个里面选 $k - 1$ 个的方案数加起来。

定义证明

\begin{aligned} (\binom{n}{k}) & = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) \\ \frac{n!}{k! \times (n - k)!} & = \frac{(n - 1)!}{(n - k)! \times (k - 1)!} + \frac{(n - 1)!}{(n - k - 1)! \times (k)!} \\ \frac{n!}{k! \times (n - k)!} & = \frac{(n - 1)! \times (k)! \times (n - 1 - k)! + (n - k)! \times (n - 1)! \times (k - 1)!}{(n - k)! \times (k - 1)! \times k! \times (n - 1 - k)!} \\ n! & = \frac{(n - 1)! \times [(k)! \times (n - 1 - k)! + (n - k)! \times (k - 1)!]}{(k - 1)! \times (n - 1 - k)!} \\ n & = \frac{k! \times (n - 1 - k)!}{(k - 1)! \times (n - 1 - k)!} + \frac{(n - k)! \times (k - 1)!}{(k - 1)! \times (n - 1 - k)!} \\ n & = k + n - k \\ n & = n \end{aligned}

求和

接下来才是真正有用的东西

1.上指标求和（Summation on the Upper Index）：

公式1

\sum_{k = 0}^{n} (\binom{k}{m}) = (\binom{n + 1}{m + 1})

组合证明

有 $m + 1$ 个球，选 $n + 1$ 个，枚举最后一个选的位置在 $k + 1$ 则前 $k$ 个要选 $n$ 个。

推导证明

根据4.帕斯卡公式得

\begin{aligned} (\binom{n + 1}{m + 1}) & = (\binom{n}{m}) + (\binom{n}{m + 1}) \\ = (\binom{n}{m}) + (\binom{n - 1}{m}) + (\binom{n - 1}{m + 1}) \\ = (\binom{n}{m}) + (\binom{n - 1}{m}) + (\binom{n - 2}{m}) + (\binom{n - 2}{m + 1}) \\ = . . . . . . \\ = \sum_{k = 0}^{n} (\binom{k}{m}) \end{aligned}

公式2

\sum_{k = 0}^{m} (\binom{n + k}{k}) = (\binom{n + m + 1}{m})

推导证明

\begin{aligned} \sum_{k = 0}^{m} (\binom{n + k}{k}) & = \sum_{k = 0}^{m} (\binom{n + k}{n}) = \sum_{k = n}^{n + m} (\binom{k}{n}) \\ = \sum_{k = 0}^{n + m} (\binom{k}{n}) - \sum_{k = 0}^{n - 1} (\binom{k}{n}) \\ = (\binom{m + n + 1}{n + 1}) - (\binom{n}{n + 1}) \\ = (\binom{m + n + 1}{m}) \end{aligned}

第 3 行运用了上指标求和的公式1 ， $(\binom{n}{n + 1}) = 0$

2.范德蒙德卷积

\sum_{k = 0}^{k <= n} (\binom{r}{k}) (\binom{s}{n - k}) = (\binom{r + s}{n})

组合证明

有 $r + s$ 个小球选 $n$ 个小球，枚举在前 $r$ 个中选 $k$ 个，在后 $s$ 个中选 $n - k$ 个。

推导证明

\begin{aligned} \sum_{k = 0}^{n + m} (\binom{n + m}{k}) x^{k} & = (x + 1)^{n + m} \\ = (x + 1)^{n} (x + 1)^{m} \\ = \sum_{r = 0}^{n} (\binom{n}{r}) x^{r} + \sum_{r = 0}^{m} (\binom{m}{s}) x^{s} \\ = \sum_{k = 0}^{n + m} \sum_{r = 0}^{k} (\binom{n}{k}) (\binom{m}{k - r}) x^{k} \end{aligned} \Rightarrow (\binom{n + m}{k}) = \sum_{r = 0}^{k} (\binom{n}{k}) (\binom{m}{k - r})

3.交错和

__EOF__

本文作者： h f j h

本文链接： https://www.cnblogs.com/hfjh/p/17519646.html

关于博主： I am a Code Talker

声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。

文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。

THE END

博客文章
# 组合数学