Combinations of selecting $n$ objects with $k$ different types

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}. $$

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)

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}$$