CODEWITHSUNDEEP
algorithmmath
pranay
pranay

Reputation: 2369

number of ways of distribution

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

Upvotes: 0

Views: 1078

Answers (1)

PengOne
PengOne

Reputation: 48398

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.

Upvotes: 3

Related Questions