组合数学中的分配问题(一):可以区分的对象和组

分配问题是一类典型的组合数学问题,根据被分配的物品和分配去的目的地是否需要区分,以及分配方式的某些限制,分配问题可以分为很多类型。把几本不同的书分给几个人属于被分配的物品和分配去的目的地都可以区分的类型,把一叠一元钞票分给几个小孩属于被分配的物品本身没有区别,但是分配去的目的地可以区分的类型,等等等等。分配问题还可以加上额外的限制条件,比如每个人最少分到一个,或者可以有人分到0个物品等等。这篇帖子我们先来看看被分配的物品和分配去的目的地都可以区分的这类问题。

假定有三本书 《皇帝新脑》,《C语言入门》,《基督山伯爵》,需要在 Alice, Bob 和 Charlie 三个人中分配,总共有多少种分配方式?

这个问题中,被分配的对象本身和分配去的目的地都是可以区分的,而且又没有额外的条件限制,这类问题最为简单。每一本书都有3个可能的人供选择,那么3本书总共可能的选择就是:

(1)   \begin{equation*} 3 \times 3 \times 3 = 27 \end{equation*}

一般的,假定我们有 N 本不同的书,M个不同的人,那么总共的分配方法是:

(2)   \begin{equation*} M \times M \times ... \times M = M^N \end{equation*}

假定有三本书 《皇帝新脑》,《C语言入门》,《基督山伯爵》,需要在 Alice, Bob 和 Charlie 三个人中分配,假定每一个人最少分到一本书的话,总共有多少种分配方式?

这个问题中,被分配的对象本身和分配去的目的地都是可以区分的,但是因为加上了额外的限制条件,所以这个问题要比前面的问题复杂很多,下面是一个递归的解法。我们已经知道总共的分配方法是3 \times 3 \times 3, 下来我们需要把某个人或者某些人没有拿到书的分配方案从其中去掉。假定我们用记号 X(N,M) 表示 N 本不同的书在M个不同的人中分配,每个人最少拿到一本的话,那么全部的分配方案M^N中,有一个人拿到0本书,然后剩下的M-1个人拿到这N本书,而且每个人至少拿到一本的方案总数是:

(3)   \begin{equation*} {M \choose 1} \times X(N, M-1) \end{equation*}

上面的公式中,第一项表示从M中选取拿到0本书的那个人的方案总数,第二项表示在剩下M-1个人中分配N本书,而且每个人至少拿到一本的方案总数。很明显这些方案是互相不重复的。类似的,在全部的分配方案中,有两个人拿到0本书,然后剩下的M-2个人拿到N本书,而且每个人至少拿到一本的方案总数是:

(4)   \begin{equation*} {M \choose 2} \times X(N, M-2) \end{equation*}

以此类推下去,我们可以得到 X(N,M) 的递归定义如下:

(5)   \begin{equation*} \begin{split} X(N, M) = M^N &- {M \choose 1} \times X(N, M-1) \\ &- {M \choose 2} \times X(N, M-2) \\ &... \\ &- {M \choose M-1} \times X(N, 1) \\ \end{split} \end{equation*}

注意到 X(N, 1) 表示把 N 本书分给一个人,所以它总是等于1。上面的函数的值可以被递归的计算出来。具体这道问题的答案是:

(6)   \begin{equation*} \begin{split} X(3, 3) &= 3^3 - {3 \choose 1} \times X(3, 2) - {3 \choose 2} \times X(3, 1) \\ &= 27 - 3 \times X(3, 2) - 3 \\ &= 24 - 3 \times (2^3 - {2 \choose 1} \times X(3, 1)) \\ &= 24 - 3 \times (8 - 2) \\ &= 6 \end{split} \end{equation*}