Postcards: A math problem

Help! Apparently I have forgotten more math than I thought I had. Here’s the problem:

The provided answer is


I don’t get it. Can somebody please help me? This is driving me nuts! As always, be sure to show your work :slight_smile:

It’s a multi-choose problem, more commonly thought of this way. There are f flavors of ice cream available, and you order a sundae with n scoops. how many different sundaes are possible. The answer is (f+n)!/((f-1)!n!).

Here we have 4 flavors and 5 scoops, so the answer is 8!/(3!5!) = 56.

Here’s one way to think of it. Call the flavors A, B, C etc… Now imagine that you’re going to put all the scoops of flavor A in a line, then put a spoon at the end of that line, then add all the scoops of flavor B to the line, then add another spoon, then add all the scoops of flavor C, etc… You place a total of f+n objects in the line, f+1 of them are spoons. So the total number of possible arrangements is just the number of possible ways to arrange the spoons, which is f+n choose f-1.

Count the number of partitions of five into integers. For an n-part partition, multiply by the number of ways of choosing those n kinds of cards from four kinds total. Be careful not to count a combination twice.

This is essentially correct, except for a few typos:
[li]The overall answer is (f + n - 1)!/((f - 1)! n!).[/li][li]You think of placing f + n - 1 objects in a line, f - 1 of which are spoons.[/li][li]The number of ways to arrange the spoons is (f + n - 1) choose (f - 1).[/li][/ul]
I’m pretty sure this is the usual answer you’ll find in a combinatorics textbook. Still, the general gist was right. :slight_smile:

Another way to do it, which I think is kind of nice, uses generating functions:

Represent each of the four different types of postcards with the letters a-d. We can represent each selection of five postcards with a monomial such as:


(i.e., we chose two “a” postcards, 1 b, zero c’s, and 2 d’s).

Since we’re choosing five postcards, we want the exponents in the monomial to add up to five.

How do we get a collection of all these monomials? Simply multiply:

(1 + a + a^2 + … + a^5)(1 + b + … + b^5)…(1 + d + … + d^5)

That product will give us all of the possible monomials.

But since we just want to count the ones whose exponents add to five, that’s equivalent to finding the coefficient of x^5 in:

(1 + x + x^2 + … + x^5)^4

This product is:

1+ 4x + 10x^2 + 20x^3 + 35x^4 + 56x^5 + 80x^6 + 20x^17 + 104x^7 + 125x^8 + 140x^9 + 146x^10 + 140x^11 + 125x^12 + 104x^13 + 80x^14 + 56x^15 + 35x^16 + 10x^18 + 4*x^19 + x^20

This also shows, for example, that there are 146 different combinations of 10 postcards (if we choose at most five of each type).

Nice! Good methodology.

I now see the error in the method I was using. Thanks, gang!