4
$\begingroup$

I need $n$ cakes for a party. I go to the cake shop and there are $k$ different kinds of cake. For variety, I'd like to get at least one of each cake.

How many ways can I do this?

  • 0
    This is a variant on [Casebash's question](http://math.stackexchange.com/questions/686) that can be solved by changing this problem slightly to fit into that problem's constraints and using that formula, but there's another solution that doesn't require changing the problem.2010-07-25
  • 3
    I'd like to see more effort on the part of the asker than this.2010-07-25

1 Answers 1

7

Similar to the stars and bars technique, consider the n cakes as a row of n stars *. Instead of permuting them with k-1 bars | (which allows two bars next to each other, giving 0 of a type, place the k-1 bars (needed to split the n stars into k types) into the n-1 spaces between the stars, allowing at most one bar per space. The number of ways to do this is ${n-1 \choose k-1}$.

Alternately, since you need one of each type, there are only n-k cakes for which you are choosing types. Using the stars and bars technique, there are ${(n-k)+k-1 \choose k-1} = {n-1 \choose k-1}$ ways to do it.

  • 0
    I'd always heard this as a "ribbon cutting" problem, but that doesn't seem to be a standard term online. Looks to me like everyone teaches the including-zero variation first, but I find this one much more intuitive.2010-07-25
  • 0
    I hadn't heard the term "ribbon cutting" problem for this before. I've only seen stars & bars in one main-stream high school text, and it wasn't called stars & bars (despite my attempt to insert that term into the most recent edition)--they explained it using O instead of * and _ instead of |, talking about balls into boxes. Since stars & bars is a common contest-problem technique and can do both forms of the problem, I'd guess that means teaching stars & bars first means not having to teach the other technique specific to this problem.2010-07-25
  • 0
    Wow, I never knew about the first solution2010-07-26