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

上一篇帖子介绍了被分配的对象和分配的目的地都可以区分的分配问题,这个帖子我们来看被分配对象不能区分的情况。

假定办公室新来了18个一样的文件夹,需要在 Alice, Bob, Charlie 和 Dave 之间分配。假定每一个人最少分到一个文件夹的话,总共有多少种分配的方式?

这个问题中,被分配的对象本身是不可区分的,但是分配去的目的地是可以区分的。Applied Combinatorics 一书中对于这个问题给出了如下的思路:假定我们把这18个文件夹排成一排,那么这些文件夹之间总共有17个空隙。在这些空隙之中选择三个空隙将把这一排文件夹分为四份,正好对应 A, B, C 和 D 四个人。因为选择这些空隙的先后顺序不影响最终的结果,所以从17个空隙中选择3个的总共方式有:

(1)   \begin{equation*} {(18-1) \choose 3} = {17 \choose 3} = 680 \end{equation*}

假定办公室新来了18个一样的文件夹,需要在 Alice, Bob, Charlie 和 Dave 之间分配。假定对于每一个人最少分到的文件夹数量不做限制的话(也就是有些人可能分到0个)的话,总共有多少种分配的方式?

上面我们已经会求解每一个人最少分到一个文件夹了。对于有些人可能分不到文件夹的情况,我们可以转化为上面的问题进行求解。如果我们虚拟的把总文件夹数目增加4个,这样我们总共就有 18+4=22 个文件夹,下面我们给每个人都最少发一个文件夹,那么按照上面的办法,总共分配的方式有:

(2)   \begin{equation*} {(22-1) \choose 3} = {21 \choose 3} = 1330 \end{equation*}

下来,我们在从每个人手中拿走一个文件夹,这样分配出去的总文件夹的数量又变回到18个,而且有些人手中可能一个文件夹都没有了。实际上通过思考我们应该可以认识到,给每人增发一个虚拟文件夹的假定下所有分配方案的总数和有些人可以分到0个文件夹的分配方案总数存在一一对应的关系,因此1330就是最后的答案。

假定办公室新来了18个一样的文件夹,需要在 Alice, Bob, Charlie 和 Dave 之间分配。假定每一个人最少分到两个文件夹的话,总共有多少种分配的方式?

同样,这个问题可以转化为上面已经解决的每人最少分配一个文件夹的问题。假定我们先给每个人一个文件夹,这样我们还剩下14个文件夹,然后把这14个文件夹按照每人最少分配一个的思路考虑,那么总共就有:

(3)   \begin{equation*} {(18-4-1) \choose 3} = {13 \choose  3} = 286 \end{equation*}