# Picking cakes if we need at least one of each type

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?

-
This is a variant on Casebash's question 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. – Ben Alpert Jul 25 '10 at 16:09
I'd like to see more effort on the part of the asker than this. – Larry Wang Jul 25 '10 at 17:34

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.