多项式系数及其妙用

目录

1 多项式系数

一个有意思的问题：把\(n\)个不同的元素分成\(r\)组，每组分别有\(n_{1},\ldots ,n_{r}\)个元素，\(\sum_{i=1}^{r}n_{i} = n\)，一共有多少种方法？

要解决这个问题，我们可以把这个问题分成多个步骤：

  1. 在\(n\)个元素中选择\(n_{1}\)个作为第一组，一共有\(\binom{n}{n_{1}}\)中选择方法；
  2. 在剩下的\(n-n_{1}\)个元素中选择\(n_2\)个作为第二组，一共有\(\binom{n-n_{1}}{n_{2}}\)中选择方法；
  3. 在剩下的\(n-n_{1}-n_{2}\)个元素中选择\(n_{3}\)个作为第三组，一共有\(\binom{n-n_{1}-n_{2}}{n_{3}}\)中选择方法；
  4. 依次类推，经过了\(n_{r}-1\)步，从剩下的\(n-n_{1} - \ldots n-n_{r-1}\)个元素中选取\(n_{r}\)个元素作为第\(n_{r}\)组，一共有\(\binom{n- n_{1} - \ldots - n_{r-1}}{n_{r}}\)

综上，可能的分法一共有：

\begin{eqnarray} \label{eq:3} && \binom{n}{n_{1}}\binom{n-n_{1}}{n_{2}}\binom{n-n_{1}-n_{2}}{n_{3}} \ldots \binom{n- n_{1} - \ldots - n_{r-1}}{n_{r}}\\ &=& \frac{n!}{(n-n_{1})!n_{1}!} \cdot \frac{(n-n_{1})!}{(n-n_{1}- n_{2})!n_{2}!} \ldots \frac{(n-n_{1} - \ldots - n_{r-1})!}{0!n_{r}!}\\ &=& \frac{n!}{n_{1}!n_{2}!\ldots n_{r}!} \end{eqnarray}

从上面的计算过程我们可以看到，这个式子和 排列组合分析一文 中的式1完全一样。因此我们可以考虑：

排列 假设有\(n\)个互不相同的元素，则一共有\(n!\)个排列结果。如果这\(n\)个元素，其中\(n_{1}\)个彼此相同，另\(n_{2}\)个彼此相同，依次类推，\(n_{r}\)个也彼此相同，那么一共排列的个数为：

\begin{equation} \label{eq:4} \frac{n!}{n_{1}!n_{2}!\ldots n_{r}!} \end{equation}

如此，我们可以把这\(n\)个元素都打上标记，其中有\(n_{1}\)个\(1\)，有\(n_{2}\)个\(2\)，等等等等，有\(n_{r}\)个\(r\)，则我们把这些标记做个排列，每次排列后，把标记为\(1\)位置上的\(n_{1}\)个元素归类为\(n_{1}\)，把标记\(2\)对应的\(n_{2}\)个元素归类为第二组，依次类推把标记\(r\)对应的元素归类为第\(r\)组。那么将\(n\)个元素分成大小为\(n_{1},n_{2},\ldots ,n_{r}\)这样不同\(r\)组的分法数量，与\(n\)个值中，\(n_{1}\)相同，\(n_{2}\)相同，等等，\(n_{r}\)相同的排列数是相等的，这等于：\[\frac{n!}{n_{1}!n_{2}!n_{3}!\ldots n_{r}!} \]

如果\(n_{1} + n_{2} + \ldots + n_{r} = n\)，则定义：\(\binom{n}{n_{1},n_{2},\ldots ,n_{r}}\)为：\[\binom{n}{n_{1},\ldots ,n_{r}} = \frac{n!}{n_{1}!\ldots n_{r}!}\] 因此，\(\binom{n}{n_{1},n_{2},\ldots ,n_{r}}\) 表示吧\(n\)个不同的元素分成大小为\(n_{1},\ldots ,n_{r}\)的\(r\)个不同组的组合数。

2 多项式定理

\begin{equation} \label{eq:5} (x_{1} + \ldots + x_{r})^{n} = \sum_{\substack{ (n_{1},\ldots ,n_{r}) \\ n_{1} + \ldots + n_{r} = n }} \binom{n}{n_{1},n_{2},\ldots ,n_{r}} x_{1}^{n_{1}}x_{2}^{n_{2}}\ldots x_{r}^{n_{r}} \end{equation}

上式的求和号是对满足\(n_{1}+ \ldots + n_{r} = n\)的所有非负整数向量\((n_{1},\ldots ,n_{r})\)求和。

我们知道\((x_{1} + \ldots + x_{r})^{n}\)结果是\(k\)个元素之和，\(k\)是\(n_{1}+\ldots +n_{r} = 0\)具有非负整数解的个数。每个元素的是\(n\)次项。每一个\(n\)次项中的\(x_{1},x_{2},\ldots ,x_{r}\)的幂次之和是\(n\)，因此上述定理成立。

3 淘汰赛场次问题

假设有\(n\)名选手进行淘汰赛，\(n\)是\(2^{m}\)。这\(n\)名选手被分成\(n/2\)组，每组都要相互比赛，每一场比赛的失败者将被淘汰而胜者进入下一轮，这个过程持续到只有一名选手留下。假设我们有一场淘汰赛，其中有\(8\)名选手。

  1. 第一轮之后有多少种可能的结果？
  2. 这场淘汰赛有多少种可能的结果？其中每个结果包含了所有轮次的完整信息。

首先，对于第一个问题，我们把\(8\)个人分为\(4\)组，每组\(2\)个这样的分法有\(\binom{8}{2,2,2,2}= \frac{8!}{2^{4}}\)种分法，然后，当这四组没有顺序的差别时，\(\frac{8!}{2^{4}\times 4!}\)种分法。对于比赛结果每一组都有两种所以一共有\(\frac{8!\times 2^{4}}{2^{4} \times 4!} = \frac{8!}{4!}\)

对于第一个问题，我们还有另外的解法。首先选出\(4\)名胜利者一共有\(\binom{8}{4}\)种方法，然后为这四名胜利者配对一个失败者，一共有\(4!\)种方法。所以结合这两步，一共有\(\binom{8}{4}\times 4! =\frac{8!}{4!}\)种方法。

第二种方法是第一种方法的扩展，则有：第二轮的结果有\(\frac{4!}{2!}\)，第三轮的结果有\(\frac{2!}{1!}\)，所以一共有\(\frac{8!}{4!}\times \frac{4!}{2!} \times \frac{2!}{1!} = 8!\)

我们可以进一步考虑，是不是淘汰赛的结果和\(1,\ldots ,n\)排列之间存在一一对应的关系，所以结果才是\(n!\). 我们可以这样理解，对于淘汰赛而言其结果有一个排名，从第\(n\)名到第\(n\)名，所以一共有\(n!\)种排名。

4 方程整数解个数

在上面多项式定理中，对于多项式展开的和中元素个数\(K\)，我们没有给出一个解析解。现在我们尝试推出\(K\)的闭式解。假设\(n=n_{1} + \ldots + n_{r}\)，则要计算可能的非负整数向量\((n_{1},\ldots ,n_{r})\)，我们考虑有\(n\)个连续的\(0\)排成一行： \[0\quad 0\quad \cdots \quad 0\] 从\(n-1\)个相邻的\(0\)的间隔中选出\(r-1\)个间隔的每一个方式对应等式：\[n=n_{1} + \ldots + n_{r}\]一个正整数解：令\(n_{1}\)等于第一个被选择的间隔之前的\(0\)的个数，\(x_{2}\)等于第一个和第二被选择的间隔之间的\(0\)的个数，依次类推，\(n_{r}\)等于最后一个被选的间隔后面的\(0\)的个数。于是：

共有\(\binom{n-1}{r-1}\)个不同的正整数向量\((n_{1},n_{2},\ldots ,n_{r})\)满足：

\begin{equation} \label{eq:6} n_{1} + n_{2} + \ldots n_{r} = n, n_{i} > 0, i = 1,\ldots ,r \end{equation}

为了得到非负整数解的个数，注意\(x_{1} + \ldots +x_{r} = n\)的非负整数解的个数和\(y_{1}+ \ldots y_{r} = n+r\)的正整数解的个数是相同的(令\(y_{i} = x_{i} + 1,i = 1,\ldots ,r\))，于是：

共有\(\binom{n+r-1}{r-1}\)个不同的非负整数向量\((x_{1},\ldots ,x_{r})\)满足：

\begin{equation} \label{eq:7} x_{1} + x_{2} +\ldots + x_{r} = n \end{equation}

5 一个应用

我们再来讨论天线有效问题：有\(n\)个天线，其中\(m\)个是不可分辨的失效天线，令\(n-m\)个天线也是不可分辨但是有效的。现在要求排成一排且没有相邻的两个失效天线的可能排列数。

我们可以假设\(n-m\)个有效的天线排成一排，一共有\(n-m+1\)个间隔，根据题目要求每个间隔中最多放一根失效天线，所以问题就变成从\(n-m+1\)个间隔中找出\(m\)个位置放置失效天线。即有\(\binom{n-m+1}{m-1}\)种天线排列方法。

另外我们还可以先把\(m\)个失效的天线排成一排，一共有\(m+1\)个间隔，我们要把这\(n-m\)个有效天线放到\(m+1\)个间隔中。因此放置的天线排列数是\[n_{1} + \ldots + n_{m+1} = n-m\]的解的个数，满足\(n_{1} \leq 0, n_{i} > 0, i=2,\ldots ,m;\) \(x_{m+1} \leq 0\)。令\(y_{1} = x_{1} + 1;y_{i} = x_{i},i=2,\ldots ,m;y_{m+1} = x_{m+1} + 1\)，所以这个问题等于：

\begin{equation} \label{eq:8} y_{1} + \ldots + y_{m+1} = n-m+2 \end{equation}

的正整数向量的个数，因此一共有\(\binom{n-m+1}{m}\)中方法，和我们之前得出的结果一样。

现在来考虑每两个失效天线之间至少有\(2\)个有效天线这种情况的排列数，结果为如下方程的解的个数： \[x_{1} + \ldots + x_{m+1} = n-m,x_{1}\leq 0 ;x_{m+1}\leq 0 ;x_{i}\geq 2,i=2,\ldots ,m\] 令\(y_{1} = x_{1} + 1,y_{m+1} = x_{m+1} + 1;y_{i} = x_{i}-1,i=2,\ldots ,m\)，则问题变为： \[y_{1} + \ldots + y_{m+1} = n-m +2 - (m-1)\] 有正整数解的个数。所以一共有\(\binom{n-2m +2}{m}\)个天线配置方式。