分配方式的数量

发布于 2024-12-11 17:11:17 字数 549 浏览 0 评论 0原文

如果我们有 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 ，但无法想到有效的算法。谢谢

原文

if we have n different things and we need to distribute them among m different people then how many ways can we do it such that for each of the m persons there is conditions that:
person 1 can have at least a things and at most b things
person 2 can have at least c things and at most d things
.. and so on ?

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)).

One way i believe is to iterate through all possible combinations for each range and see which ones sum upto n , but can't think of an efficient algorithm.
Thanks

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

蓬勃野心 2024-12-18 17:11:17

您可能想使用生成函数方法。用x 的指数表示i 获得的对象数量。这意味着如果一个人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 种事物的方法数量。

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

You probably want to use a generating function approach. Represent the number of objects that person i gets by the exponents of x. This means that if person i can have at least 3 and at most 7 things, this corresponds to the term

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

Remember to think of + as OR and * as AND. If we want to impose conditions and person 1 and person 2, then multiply their functions together. For example, with person 1 having between 3 and 7 things, and say person 2 has at least 5 things, and add a third person with at most 10 things. Then we get:

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

which can also be written as

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

The way to get information back from this is the following. The coefficient of x^M in the expansion of these terms gives the number of ways to distribute a total of M things among all the people subject to the given constraints.

You can work this out from the formulas, or write a program to extract the coefficient, but the idea is to use generating functions as a convenient and efficient way to encode the constraints along with the answer.

回复收藏 0 原文

~没有更多了~