Combination problem?

Question

If 20 souvenirs are to be divided among 4 candidates with each getting at least three, I think the answer is the coeff. of x^20 in the expansion of (x^3+x^4+......+x^20)^4. What will be the answer if the constraint of minimum souvenirs is removed? Please explain how this bracket is arrived? Please also give some more such examples. I think one of these is: in how many ways one can get m marks in aggregate if there are x papers of n marks each.

Answer 1

In the expansion, x^20 is the product of 4 terms of x of various powers, but sum of their powers is 20. E.g. x^3x^4x^5x^8. (...)^4 = (...)(...)(...)(...) and imagine that from each bracket, which corresponds to each of the 4 candidates, we choose a term of a certain power, which corresponds to the number of souvenirs the particular candidate is getting. Thus, the number of x^20 terms in the expansion is the number of ways this can be done. Since all coefficients in the bracket are 1, the number of x^20 terms = coefficient of the x^20 term.

Starting from x^3 corresponds to the constraint of each getting at least three. In fact, since each getting at least 3, the maximum one can get is 20-3-3-3=11. Thus, you only need to expand (x^3+x^4+...+x^11)^4.

Removing the constraint mean you need to consider the coefficient of x^20 in the expansion of (1+x+x^2+x^3+..+x^20)^4.

Yes, your example leads to finding the coefficient of x^m in the expansion of (1+x+x^2+x^3+..+x^n)^n.

Answer 2

I like to split up the process into independent parts and use the counting principle.

Step 1: There are 4 people, each getting 3 things, so that's 12. How many ways can you select 12 of 20? That's 20C12 ways to grab the stuff that everyone must have.
Step 2: How many ways to select 3 of 12 (12C3) then 3 of the remaining 9 (9C3) then 3 of 6 (6C3) and then 3 of the last 3 (3C3). So that is 12C3*9C3*6C3.
Step 3 is to determine how many ways to distribute 4 things among 4 people. That's (4P4).
Then everyone has three objects.

Step 4 is to count the ways to distrubute the leftovers. There are 8 objects left, and you need to distrubute them among 4 people. Imagine you have three boxes like this

[ | | | ]

and you can put each of the 8 things in any of the compartments. There are 4 choices for each thing, so there are 4^8 ways for this to happen.

The answer is the product of all of these independent factors:

(20C12)*(12C3*9C3*6C3)
*(4P4)*(4^8).