多项式系数及其妙用

1 多项式系数

一个有意思的问题：把个不同的元素分成组，每组分别有个元素，，一共有多少种方法？

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

在个元素中选择个作为第一组，一共有中选择方法；
在剩下的个元素中选择个作为第二组，一共有中选择方法；
在剩下的个元素中选择个作为第三组，一共有中选择方法；
依次类推，经过了步，从剩下的个元素中选取个元素作为第组，一共有

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

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

排列假设有个互不相同的元素，则一共有个排列结果。如果这个元素，其中个彼此相同，另个彼此相同，依次类推，个也彼此相同，那么一共排列的个数为：

如此，我们可以把这个元素都打上标记，其中有个，有个，等等等等，有个，则我们把这些标记做个排列，每次排列后，把标记为位置上的个元素归类为，把标记对应的个元素归类为第二组，依次类推把标记对应的元素归类为第组。那么将个元素分成大小为这样不同组的分法数量，与个值中，相同，相同，等等，相同的排列数是相等的，这等于：

如果，则定义：为：

因此，

表示吧

个不同的元素分成大小为

的

个不同组的组合数。

2 多项式定理

上式的求和号是对满足的所有非负整数向量求和。

我们知道结果是个元素之和，是具有非负整数解的个数。每个元素的是次项。每一个次项中的的幂次之和是，因此上述定理成立。

3 淘汰赛场次问题

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

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

首先，对于第一个问题，我们把个人分为组，每组个这样的分法有种分法，然后，当这四组没有顺序的差别时，种分法。对于比赛结果每一组都有两种所以一共有

对于第一个问题，我们还有另外的解法。首先选出名胜利者一共有种方法，然后为这四名胜利者配对一个失败者，一共有种方法。所以结合这两步，一共有种方法。

第二种方法是第一种方法的扩展，则有：第二轮的结果有，第三轮的结果有，所以一共有

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

4 方程整数解个数

在上面多项式定理中，对于多项式展开的和中元素个数，我们没有给出一个解析解。现在我们尝试推出的闭式解。假设，则要计算可能的非负整数向量，我们考虑有个连续的排成一行：

从

个相邻的

的间隔中选出

个间隔的每一个方式对应等式：

一个正整数解：令

等于第一个被选择的间隔之前的

的个数，

等于第一个和第二被选择的间隔之间的

的个数，依次类推，

等于最后一个被选的间隔后面的

的个数。于是：

共有个不同的正整数向量满足：

为了得到非负整数解的个数，注意的非负整数解的个数和的正整数解的个数是相同的(令)，于是：

共有个不同的非负整数向量满足：

5 一个应用

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

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

另外我们还可以先把个失效的天线排成一排，一共有个间隔，我们要把这个有效天线放到个间隔中。因此放置的天线排列数是

的解的个数，满足

。令

，所以这个问题等于：

的正整数向量的个数，因此一共有中方法，和我们之前得出的结果一样。

现在来考虑每两个失效天线之间至少有个有效天线这种情况的排列数，结果为如下方程的解的个数：

令

，则问题变为：

有正整数解的个数。所以一共有

个天线配置方式。