从Parasprite说起：排列与组合数

####*本文将尽可能全面地向您展示排列组合的奥秘。为了让每位读者有一段美妙的体验，我们将会先讲解一些基础。有排列组合基础的同学可以选择性地跳过前三章节。

##0、一些铺垫：和式
想必大家小时候都听说过高斯的故事：
##### **1-100的整数加起来，和是多少？**
求和的传奇故事相信大家耳熟能详。但这里的问题是，如何写出从1一直加到100的表达式呢？？
这个式子如果直接展开来写的话，大概长成这样：$1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+61+62+63+64+65+66+67+68+69+70+71+72+73+74+75+76+77+78+79+80+81+82+83+84+85+86+87+88+89+90+91+92+93+94+95+96+97+98+99+100$

呼，没想到我有生之年还能写完。
不过数学家们可不会这么粗暴，数学工作者通常使用一种优雅的记录方法：$$\sum^{100}_{i=1}i$$。其中$\sum$读作**sigma**
$\sum$符号就代表了求和。有点懵？其实非常简单。我们想像手里有一个数，它每一秒会+1，直到加到大于100它就消失了。那么我们看它从第1秒到第100秒是不是变成过1-100内所有的数？那么每当他变成一个新的数，我们把他加起来，就表示了1-100的求和。
举一个简单的例子：
$$\sum^{3}_{i=1}i$$
第1秒i=1 答案加上了1，为1
第2秒i=2 答案加上了2，为3
第3秒i=3 答案加上了3，为6
第4秒i=4 超过了3，不加了
于是:$$\sum^{3}_{i=1}i = 1+2+3 = 6$$
那1-100求和是不是很好表示了？
如果表示50-100求和呢？我们让i一开始是50就好了。 $$\sum^{100}_{i=50}i$$
求积是一样的意思，只不过把加起来变为了乘起来，符号为$\prod$，读作**pai**：
$$\prod^{3}_{i=1}i = 1\times2\times3 = 6$$

但是我们后面将会用到的不仅仅是累加求和那么简单。上文中$i$我们暂且称作**枚举变量**，对于求和记号$\sum$来讲，一般情况下我们在它的下方书写枚举的变量需要满足的条件。
比如以下两个记号是等价的：
$$\sum^{100}_{i=1} i = \sum_{1 \leq i \leq 100} i$$
这样写有什么好处呢？我们可以有更多的枚举方式：
$$\sum_{1 \leq i, j \leq 100} i\cdot j$$
上式就可以表示$i$,$j$都从$1-100$中取，所有方案中两个数乘积的和。
甚至我们可以这样表示：$$\sum_{x_1+x_2=100, x_1, x_2 \geq 1}1$$
每有一种可以枚举的方案，和式就会$+1$，所以上式表示把$100$分成$2$个正整数有多少种方案。

##1、排列

Parasprite是一种奇妙的生物，它们色彩多变，喜爱成群结队地出没。虽然有着可爱的外表但是破坏力极强。这就是一只Parasprite：
![图片标题](https://leanote.com/api/file/getImage?fileId=5b249829ab64417ce7000668)

那么现在我们来考虑一个有趣的问题，有3只Parasprite排成一列出行，可能有多少种不同的排队顺序呢？

通过枚举，我们不难发现答案是6种：
<img src="https://leanote.com/api/file/getImage?fileId=5b249b2eab64417aee00068a" width="50%" height="50%" />

那么，这样$n$只Parasprite排成一列的方案数可以直接计算吗？
我们换个角度考虑，假设我们要把$n$只Parasprite依次排到队伍里面去，我们会怎么做？
假设我们先任选一个parasprite排到第一个，有$n$种方案。再任选一个parasprite排到第二个，因为我们已经排了一个parasprite，现在只剩下$n-1$个parasprite了...
我们发现，如果按照这样的顺序排，排到第$k$个位置会有$k-1$个parasprite被排了，这个位置只剩下$n-k+1$种parasprite可供选择。
这样我们相当于分$n$步，每一步选取了一个parasprite排到当前的位置。因为只要有一个parasprite排的不同就是不同的方案，根据乘法原理我们可以得到最终的方案数就是：$n\times (n-1) \times (n-2) ... \times 1$。从$n$一直乘到$1$也被称作$n$的阶乘，记作$n!$这样选$n$个排列成长度为$n$的排列也叫**全排列**

那么如果是$n$个parasprite要排成$k$个parasprite长的队伍呢？

同样的我们可以发现排到第$k$个位置有$k-1$个parasprite被排了，这个位置只剩下$n-k+1$种parasprite可供选择。那么哪里不同了呢？不同之处仅仅在于这一次我们队伍的长度为$k$，只用分$k$步拿就好啦~即
$n\times (n-1) \times (n-2) ... \times (n-k+1)$

这样的数就称作排列数，一般用$A^k_n$或$P^k_n$表示，读作$n$排列$k$。
也就是说$A^k_n = n\times (n-1) \times (n-2) ... \times (n-k+1)$

但是在这里，我们引入两个新的符号：

**下降幂**：
$n^{\underline k} = n \times (n-1) \times (n-2)\times ...\times (n-k+1)$

通俗的讲，下降幂就表示了$n$一直往下乘$k$个数，读作$n$的$k$阶下降幂。

同样的，有**上升幂**：
$n^{\overline k} = n \times (n + 1) \times (n + 2) \times ... \times (n + k - 1)$
读作$n$的$k$阶上升幂。

不难发现，排列数和下降幂不就是一回事嘛~
那为什么要用下降幂表示呢？一个原因是因为比较好写而且清晰容易理解，还有一个就是为后面的一些章节做铺垫。

**p.s.** 不难发现一个关系：
$$n^{\underline k} = (n-k+1)^{\overline k} = A^k_n = \frac{n!}{k!}$$

相信你已经知道排列数的含义和推导了。那么让我们来看看另一类问题吧。

##2、组合

我们来思考另一个有趣的问题：现在有3个parasprite，如果我们从中任意选出3个来组成一个特别小组有多少种方案呢？

哦，那不是和上面一样吗？分步选出parasprite，然后每一步的方案乘起来就行了！

如果按这个方法计算，那么这个问题的答案就是6。但实际上从常识出发，从三个parasprite里面选出三个，怎么选都只能全部选完，只有一种方案呀！这是怎么回事呢？

不难发现，上图的6种方案在这里都是一样的！因为选出来的parasprite的种类都是一个蓝色一个红色一个紫色。这也是两种计数的不同所在：有序和无序。

那么这样的$n$个中任选$k$个(不记顺序)的方案是多少呢？其实我们可以化有序为无序！

仔细思考一下，假如我们已经从$n$个parasprite中选出了$k$个来，那么这个方案会在排列中被计算多少次呢？由于在排列中$k$个数的任意一个顺序发生变化就成为一种新的方案，那么在排列中这个方案被计算的次数就是这$k$种数摆放顺序的种数了，这不就是$k$的全排列吗？

我们把这样$n$个中任选$k$个的方案数记作组合数。一般用$C^k_n$表示，但是这里我们引入一个新的符号$\binom n k$，读作$n$选$k$，那么根据刚才的理解：

$$\binom n k = \frac{n^{\underline k}}{k!}$$

现在我们可以解释了为什么从3个parasprite中选3个的方案只有一种了。因为在选出3个的情况下，排列数中因为顺序不同，导致每一种选出3个的方案都被计算了$3!$次。
所以：
$$\binom 3 3 = \frac{3^{\underline 3}}{3!} = 1$$

##3、数字三角形
相信大家从前一定见过这一幅图：

![图片标题](https://leanote.com/api/file/getImage?fileId=5b24b27eab64417ce700086e)
没错，这就是杨辉三角！
同时，它也是组合数。
它的第$x$行第$y$列表示了$\binom {x - 1} {y - 1}$

这是为什么呢？

首先我们来看杨辉三角是怎么得到的：

- 每一行的第1个和最后一个数都是1
 - 其他的数都等于左上和右上的数的和

我们把上面两点蕴含的意义用组合数来说明：
$$\binom n 0 = \binom n n = 1$$
$$\binom n k = \binom {n-1} {k-1} + \binom {n-1} {k} $$

第一个等式应该不难理解，从$n$个数中选$0$个和从$n$个数中选$n$个都只有一种情况——选$0$个只能都不选，选$n$个只能全选。

对于第二个等式，我们这样想：既然要从$n$个parasprite里面选出$k$个来，我们可以思考从$n-1$个的情况推导到$n$个。这是候我们只需要知道新增的这个parasprite选不选就好了。

- 选新增的这个，那么我们要先从前$n-1$个中选出$k-1$个，再选新增的这个才合法。总共有$\binom {n-1} {k} \times 1$种
 - 不选新增的这个，那么我们要在前$n-1$个中就先选完了所有的$k$个再选新增的这个才合法。总共有$\binom {n-1} {k-1} \times 1$种。
 把这两种情况加起来不就是我们想要的$\binom n k$了吗？我们相加：
$$\binom n k = \binom {n-1} {k-1} + \binom {n-1} {k} $$

结果得到了和杨辉三角完全相同的关系！

##4、奇妙的计数

排列、组合的数学意义远不止这些，通过一系列转化，排列组合可以解决许多奇妙的计数问题。

现在我们来看另外一个有趣的问题吧！

5个**一模一样**的parasprite被抓起来了QAQ，它们被放进了3个**不同**的盒子里，**每种盒子不能为空**，有几种不同的方法？

乍一看，貌似和组合数并没有什么联系？不过我们可以枚举答案，通过枚举答案，我们发现只有6种方案。
 ooo o o
 o ooo o
 o o ooo
 oo oo o
 oo o oo
 o oo oo

发现答案就是$\binom 4 2$，但是为什么呢？

我们换一个角度考虑，因为5只parasprite都是一样的，我们把5只parasprite排成一列，在它们之间放上2块**板子**，这样就把5只parasprite分成了三个部分！ 如图：
<img src="https://leanote.com/api/file/getImage?fileId=5b260741ab6441565a000908" width="50%" height="50%" />

我们规定**板子**分隔出来的每个部分按顺序分别为1、2、3号盒子，那么每一种板子的放法、把5只parasprite放入3个不同盒子的方法是一一对应的！
没有怎么懂？我们看上面这张图，第一种对应的方案就是一号盒子一个，二号盒子一个，三号盒子三个。第二种对应的方案就是一号盒子一个，二号盒子两个，三号盒子两个……

其实到了这里聪明的你可能已经发现了这类问题的本质：
对于$k$个正整数$x_1, x_2, ... , x_k > 0$组成的方程，它们的和为$n$的解有多少种。即：
$$x_1+x_2+x_3+x_4+...+x_k = n, (x_1, x_2, x_3, x_4..., x_n > 0)$$的正整数解组数。

思考刚刚隔板的过程，那么有$n-1$个位置可以插**板子**，要插$k-1$个板子，并且没有顺序要求，那么答案自然就是：$$\binom {n-1} {k-1}$$

如果是将**不同**的parasprite放入**相同**的盒子呢？后面我们将会了解到一种类似于组合数的数列：**第二类斯特林数**，它的含义正是将$n$个不同元素放入$k$个相同盒子的方案数。不仅如此，后面我们将会看到，它还与排列数有着千丝万缕的联系！提前剧透一下，**第二类斯特林数**的写法是：
$$\left\{ \begin{matrix}n\\k\end{matrix} \right\}$$
读作：$n$子集$k$。

这样解决问题的方法通常称为**隔板法**，因为其独特的思路，**隔板法**在计数问题种有着重要的地位。

下面我们再来看一个与其相似但却又稍稍有所不同的计数问题：

在parasprite的家乡，有3种parasprite，因为parasprite的种群庞大，你可以视作每一种的个数都是**无限**的！现在你要从中选出3个parasprite来带回小马谷养(~~虽然可能被拆家~~)。问你带回家的parasprite的组成有几种可能性？

新问题，老思路，既然不知道怎么算，我们可以谨慎枚举大胆猜想——

通过枚举，一共有10种情况(这里就省略过程图了)。
发现答案就是$\binom 5 3$ 为什么呢？

可不可以把上一个问题的解决思路同样的用到这里来呢？

答案是可以的！我们假定每种parasprite拿的个数为$x_1, x_2, x_3, x_4, x_5$，那么我们会发现，这个问题的本质就是：
$$x_1 + x_2 + x_3 + x_4 + x_5 = k, (x_1, x_2, x_3, x_4, x_5 \geq 0)$$

实际上这里parasprite的种类就是盒子，而拿出$2$个来可以看作把两个**被拿出的名额**分配给每一种parasprite。

这不就和上一个问题差不多了吗？但是毕竟只是差不多，更何况问题往往就出在差的这一点点地方：
$x_n > 0$和$x_n \geq 0$

这意味着什么呢？在刚刚问题的基础上，两个隔板可以插在同一个位置！这并不满足组合数的性质。

但是我们仍然可以借助刚才的思路：

我们假设现在有5个 **物体**， 虽然我们不能知道这些物体是什么，它们有可能是**板子**，也有可能是parasprite的分配名额。但是我们已经知道的是，一定有2块板子，3个分配名额。

这样的话，我们要做的其实只是在这5个物体中选出2个来当**板子**，这样处理之后，两块板子是可以紧跟在一起的，完美的处理了上个问题的解决方法中两个板子插不到一起，导致每一个盒子里至少有一个parasprite的问题。那么答案就应该是$\binom {3+3-1} {3-1}$

于是我们就可以思考了：把问题宽泛化，有$n$种parasprite，每种都有**无限**个，你要带$k$个回小马谷，有多少种方案。

不难发现这就相当于有$n+k-1$个物体(有$k$个名额，$n-1$块板子)，从中要选出$n-1$个来作为板子，也就**相当于从中选出$k$个来做分配名额**。

这样答案就是：
$$\binom {n+k-1} {n-1} = \binom {n+k-1}{k}$$

这个发现还给了我们一个意外惊喜：
$$\binom {n} {k} = \binom {n} {n - k}$$
这个等式不难理解——选$k$个符合条件，就等于选$n-k$个不符合条件，这也是杨辉三角**对称**的原因。

##5、对组合数等式的探讨
####*本章将会用到第0章和式的内容
前面我们看到了排列组合的一些性质和相互转化，下面我们将深入讨论化简含有组合数等式的推导和化简。请在这之前**务必**想明白前几章的内容，这样你会对本章有更透彻的理解。

因为本章的内容有很多纯代数的，所以可爱的parasprite的出场率要降低一点啦~

我们将会列举一些有趣的组合数等式，并从代数角度和组合意义两方面考虑它的本质。我们会看到这些看似复杂的等式的背后竟然是有着如此浅显的组合含义。

**1、**多项式系数
现在我们来研究一个问题：
$(x+y)^k$展开括号后是什么样子？
形如$(x+y)^k$的式子在数学上称作二项式。
按照惯例，我们动动手，计算出$k=0,1,2,3,4$时的结果。
$1$
$x+y$
$x^2+2xy+y^2$
$x^3+3x^2y+3xy^2+y^3$
$x^4+4x^3y+6x^2y^2+4xy^3+y^4$
我们惊奇的发现杨辉三角中的数字出现在了系数中！
也就是说，$\binom a b$的意义实际上是二项式$(x+y)^a$展开后$x$为$b$次的项前的系数！
我们大胆猜想：
$$(x+y)^k=\sum^{k}_{i=0}\binom k i x^iy^{k-i}$$
这个奇妙的定理就是著名的**二项式定理**。
顺带一提，其实，组合数符号$\binom a b$的由来正是因为括号代表了二项式。这个符号生动形象又不失准确地表示了组合数的代数意义。
那么这是为什么呢？我们对于$x$来考虑，不难发现二项式展开后的每一个项都是形如$x^ay^{k-a}$的。并且如果有$m$个多项式乘起来，那么最高项系数为1。感性粗略的理解就是：我们从$(x+y)^k=(x+y)(x+y)...(x+y),k$个$(x+y)$中选出了$a$个$(x+y)$来乘出$x^a$的方法是多少种，因为每一种这样的方法会使得$x^ay^{k-a}$前的系数增加1。那么$x^ay^{k-a}$前的系数自然就是$\binom k a$了。

上述方法太过感性，不过不久我们将会在**生成函数**的文章中重新谈到这个话题，并且用严谨的数学方法证明这个性质。所以如果认为这个理解不可理喻的话也不用担心。

现在，我们把问题稍微复杂化一点点：
求把下面式子展开后每项的系数$(x+y+z)^k$
这种式子自然也有一个名字叫三项式。
其实有了二项式定理，我们处理起这个来就简单得多了。
我们可以先把$(y+z)$看作一个整体。那么就成了一个"二项式"我们代入二项式定理：
$$(x+(y+z))^k=\sum^{k}_{i=0}\binom k i x^i(y+z)^{k-i}$$
我们惊奇的发现，$(y+z)^{k-i}$又成为了一个二项式！于是我们又可以带入二项式定理：
$$(x+(y+z))^k=\sum^{k}_{i=0}\binom k i x^i(y+z)^{k-i}=\sum^{k}_{i=0}\binom k i x^i \sum^{k - i}_{j=0}\binom {k-i} j y^{j}z^{k-i-j}$$
想象此时我们把后半部分求和"拆括号"，用乘法分配律和前面的$x^i$相乘，我们就会得到三项式的展开，那么我们就得到了三项式展开后每一项的系数：
$$(x+(y+z))^k=\sum_{0 \leq i, j \leq k}\binom k i \binom {k-i} j x^iy^{j}z^{k-i-j}$$
这个和式看上去可不是那么好看，我们把它化简一下：
$$\sum_{0 \leq i, j \leq k}\binom k i \binom {k-i} j x^iy^{j}z^{k-i-j}=\sum_{0 \leq i, j \leq k}\binom k {k-i} \binom {k-i} j x^iy^{j}z^{k-i-j}$$
为了得到一般形式，我们不妨记$x^ay^bz^c$前的系数为$K_{a,b,c}$，那么我们把上面的$(i,j,k-i-j)$用$(a,b,c)$替换，便有了惊人的发现：
$$K_{a,b,c}=\binom {a+b+c} {b+c} \binom {b+c} {c}=\frac{(a+b+c)!}{a!b!c!}$$
这就是**三项式定理**。
其实我们已经发现了规律，不难猜到**多项式定理：
$$K_{x1,x2,x3,...,xn} = \frac{(x1+x2+x3+...+xn)!}{x1!x2!x3!...xn!}$$

Rockdu's Blog

导航

最近发表

大佬们的友链