algorithm - 分配方式数

Question

如果我们有 n 个不同的东西，我们需要将它们分配给 m 个不同的人，那么我们有多少种方法可以做到这一点，使得 m 个人中的每个人都满足以下条件:人 1 至少可以拥有 a 东西，最多可以拥有 b 东西人 2 至少可以拥有 c 东西，最多可以拥有 d 东西..等等？

e.g if n = 5 and m =3 and the conditions are:
person 1 can receive at least 0 and at most 1 gift
person 2 can receive at least 1 and at most 3 gift
person 3 can receive at least 1 and at most 4 gift
then the number of ways of distributing  these 5 gifts is 6((0 1 4), (0 2 3), (0 3 2), (1 1 3), (1 2 2), (1 3 1)).

我认为一种方法是遍历每个范围的所有可能组合，看看哪些组合总和为 n ，但想不出一个有效的算法。谢谢

Answer 1

您可能想使用生成函数方法。表示 i 人获得的对象数量，由 x 的指数表示。这意味着如果人 i 可以拥有至少 3 和至多 7 的东西，这对应于术语

x^3 + x^4 + x^5 + x^6 + x^7

请记住将+ 视为OR 并将* 视为AND。如果我们想强加条件和人 1 和人 2，然后将它们的函数相乘。例如，1 人拥有 3 和 7 之间的东西，并且说 2 人至少有 5 事物，并添加最多 10 事物的第三人称。然后我们得到:

(x^3 + x^4 + x^5 + x^6 + x^7) * (x^5 + x^6 + ... ) * (1 + x + x^2 + ... + x^10)

也可以写成

(x^3 + x^4 + x^5 + x^6 + x^7) * ( x^5/(1+x) ) * (1 + x + x^2 + ... + x^10)

从这里获取信息的方法如下。 x^M 在这些项的扩展中的系数给出了在所有受给定约束的人中分配总共 M 事物的方法数。

您可以从公式中计算出来，或者编写一个程序来提取系数，但我们的想法是使用生成函数作为一种方便有效的方法来对约束和答案进行编码。