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?

  • 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
    Wow, I never knew about the first solution2010-07-26