Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Seeded question –  Casebash Jul 25 '10 at 10:54
1  
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
2  
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
1  
@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

3 Answers 3

up vote 13 down vote accepted

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

share|improve this answer
    
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
1  
Here is a derivation of your formula using the Polya Enumeration Theorem. –  Marko Riedel Oct 28 '13 at 0:42

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

share|improve this answer

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)

share|improve this answer
    
nice solution Jason S............... –  juantheron Dec 13 '13 at 3:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.