16
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Seeded question $\endgroup$ – Casebash Jul 25 '10 at 10:54
  • 1
    $\begingroup$ PS. This problem has a really nice proof. I'm pretty hopeful that someone else has seen it posts it $\endgroup$ – Casebash Jul 25 '10 at 11:23
  • 1
    $\begingroup$ Classic stars and bars problem. It's also equivalent to the number of ways to distribute n identical pieces of candy to k children or putting n identical balls into k urns or the number of terms in the expansion of (x_1+...+x_k)^n. $\endgroup$ – Isaac Jul 25 '10 at 16:01
  • 2
    $\begingroup$ 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. $\endgroup$ – Jamie Banks Jul 25 '10 at 19:24
  • 2
    $\begingroup$ @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 $\endgroup$ – Casebash Jul 25 '10 at 20:54
27
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Exactly what I was looking for $\endgroup$ – Casebash Jul 25 '10 at 20:51
  • $\begingroup$ 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. $\endgroup$ – Mark Bennet May 28 '13 at 17:20
  • 1
    $\begingroup$ Here is a derivation of your formula using the Polya Enumeration Theorem. $\endgroup$ – Marko Riedel Oct 28 '13 at 0:42
3
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ nice solution Jason S............... $\endgroup$ – juantheron Dec 13 '13 at 3:34
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Since cakes are involved, I shall solve it using what's called the "ice-cream parlour" approach.

For each of the $k$ types, go on saying yes, yes, yes... until you don't want any more, and then say no and move on to the next type.

Of course, you may say no straight away to any type if you don't want it, and you don't need to say no after the $k^{th}$ type because there is no next type.

So there will be $n$ of yes and $(k-1)$ of no whichever way you choose, and the only decision you need to take is where to place the no's in the string of $(n+k-1)$ responses,

thus $\dbinom{n+k-1}{k-1}$ different combinations of cakes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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