# Combinations of selecting n objects with k different types

Suppose that I am buying cakes for a party. There are k different types and I intend to buy a total of n cakes. How many different combinations of cakes could I possibly bring to the party?

-
Seeded question –  Casebash Jul 25 '10 at 10:54
PS. This problem has a really nice proof. I'm pretty hopeful that someone else has seen it posts it –  Casebash Jul 25 '10 at 11:23
Whenever I do this sort of thing, the shop runs out of the cakes I want. –  walkytalky Jul 25 '10 at 15:20
voting to close--because I'd do so if I saw it as a real question--no indication the asker has thought about the problem first. –  Jamie Banks Jul 25 '10 at 19:24
@Katie: Its a perfectly valid question and I haven't seen a hasn't thought about it close reason on any of the other SO websites (maybe mathoverflow is different though). If you want someone to think about a problem, the best solution is to just not give them the whole solution. For example, show them how you go about proving it and leave out the actual formula –  Casebash Jul 25 '10 at 20:54

Using a method that's often called "stars and bars":

We draw $n$ stars in a row to represent the cakes, and $k-1$ bars to divide them up. All of the stars to the left of the first bar are cakes of the first type; stars between the first two bars are of the second type; . . . .

**|***||*|


Here's an example with $n=6$ and $k=5$. We're getting 2 of the first type, 3 of the second type, 0 of the third type, 1 of the fourth type, and 0 of the fifth type.

In order to solve the problem, we just need to reorder the stars and bars by choosing the $k-1$ spots for the bars out of the $n+k-1$ total spots, so our answer is:

$$\binom{n+k-1}{k-1}.$$

-
Exactly what I was looking for –  Casebash Jul 25 '10 at 20:51
Note that $\binom {n+k-1}{k-1} = \binom {n+k-1}{n}$ - here the description picks the $k-1$ spots for the bars - equivalently we could pick the $n$ spots for the cakes. –  Mark Bennet May 28 '13 at 17:20
Here is a derivation of your formula using the Polya Enumeration Theorem. –  Marko Riedel Oct 28 '13 at 0:42

Let g(n,k) = # combinations of cakes.

Notice that:

• g(n,1) = 1. (all the cakes are the same)
• g(n,2) = n+1. (e.g. for 5 cakes, the # of cakes of type 1 can be 0, 1, 2, 3, 4, 5)
• g(1,k) = k.
• g(2,k) = k*(k-1)/2 + k (the first term is two different cakes; the second term is when both cakes are the same), as long as k > 1. (otherwise g(2,1) = 1)
• g(3,k) = k * (k-1) * (k-2)/6 + k*(k-1)/2 * 2 + k (the first term is 3 different cakes; the second term is 2 different cakes, with a *2 since there are two choices for which one to duplicate, the third term is when all 3 cakes are the same), as long as k > 2.

If we think of k as a radix rather than the # of cakes, then this problem is equivalent to expressing the # of distinct n-digit numbers in base k whose digits are in sorted order. (e.g. 1122399 is equivalent to 9921231)

I think I can express it as a nonrecursive sum:

g(n,k) = sum from j=1 to max(n,k) of { (k choose j) * h(n,j) }

where h(n,j) is the # of ways to partition N cakes using j different types. (the term in the sum is when there are j distinct cakes actually chosen.)

But that's about as far as I can get... :/

edit: looks like it's combinations with repetitions = ((k+n-1) choose n). (same as the wikipedia article with n and k swapped)

-
nice solution Jason S............... –  juantheron Dec 13 '13 at 3:34

Let's assume you have $n$ items and $k$ bins. You need $k-1$ separators to get the $n$ items into the $k$ bins. There are $(n + k - 1)!$ permutations of ordering $n$ items and $(k-1)$ separators. The permutations of the $n$ items don't matter, and the permutations of the $(k-1)$ separators don't matter, so you'll need to divide by $n!$ and $(k-1)!$

Thus you have $$\frac{(n + k - 1)!}{n!(k-1)!} = \binom{n+k-1}{k-1}$$

-