组合数学中的分配问题(四):不能区分的对象和不能区分的组

这是分配问题这个系列的最后一个帖子,关注不能区分的对象和不能区分的组。把一个正整数n分解成为几个非零的其他正整数之和,叫做该正整数的一个分组(Partition)。对于任意一个正整数n,它的分组总数(Partition Number)就是一个典型的被分配对象和分组本身都不能被区分的分配问题。 Partition Number 是一个很广阔的问题,分析它远远超出了我们这个帖子的内容,有兴趣可以参见 Wikipedia Page – Partition 。这里我们关心的是被分成的组的个数 k 已经确定的情况,也就是把一个正整数 n 分为 k 个正整数之和,一共有多少种分组方法。正像绝大多数组合数学的问题一样,这个问题有一个简洁递归公式如下:

(1)   \begin{equation*} p_k(n) = p_{k-1}(n-1) + p_k(n-k) \end{equation*}

其中 p_k(n) 就代表把正整数 n 分为 k 个正整数之和的分组数目。这个递归公式是怎么来的呢?

首先我们看到,正整数 n 分为 k 个正整数的分组有两种情况,第一种是某个分组的数等于1,第二种是所有的分组都大于1。很明显这两种情况互相不重叠,而且涵盖了所有可能的分组情况。

对于第一种情况的每个分组方案,我们可以把这个数目为1的分组拿掉,那么我们就得到了把正整数 n-1 分为 k-1 组的一个方案。可以看出,对于 p_k(n) 中的这类方案,既然它们每一个都有一个相同的数目为1的分组,那么剩下的分组也必然各不相同,因此拿掉这个数目为1的分组之后这些分组也各不相同,正好涵盖了 p_{k-1}(n-1) 的所有方案,而且我们已经成功的把数字n减少到了n-1

对于第二种情况的每个分组方案,我们可以把该方案中的每个组的数目减去1,那么我们就得到了把 正整数n-k分为 k 组的一个方案。可以看出,对于 p_k(n) 中的这类方案,每一个都对应 p_k(n-k)中的一个分组方案,而且我们已经成功的把数字n减少到了n-k。综上所述,把这两种情况的方案加起来我们就得到了上面的递归公式:

(2)   \begin{equation*} p_k(n) = p_{k-1}(n-1) + p_k(n-k) \end{equation*}

下面是一个从 stackexchange 上引用过来的一个例子,具体展示了把上面的递归公式应用于 p_3(8) 的过程:

(3)   \begin{equation*} \begin{array}{rlrlrl} &p_3(8)\qquad=&& p_2(7)\qquad\qquad+&&p_3(5)\\ \hline\\ 8&=\textbf{6+1}+1\qquad& 7&=6+1\\ &=\textbf{5+2}+1\qquad&&=5+2\\ &=\textbf{4+3}+1\qquad&&=4+3\\ &=\textbf{4+2+2}\qquad&&\qquad &\qquad5&=3+1+1\\ &=\textbf{3+3+2}\qquad&&\qquad&\qquad&=2+2+1 \end{array} \end{equation*}

很明显,在 p_2(7) 的分组方案里面加上一个数目为1的组,我们就得到了 p_3(8) 里面有一个组的数目为1的那些分组方案;而把 p_3(5) 的分组方案里面的每一个组加上1,我们就得到了 p_3(8) 里面所有分组都大于1的那些分组方案。这两部分结合起来,就是p_3(8) 的全部分组。

最后,既然这是一个递归的方案,我们必须要讨论结束递归的条件,很明显我们有:

  • p=k 的时候,分组数为1。
  • p<k 的时候,分组数为0。
  • k=1 的时候,分组数为1。