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.

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 every cake. How many ways can I do this?

share|improve this question
    
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
3  
I'd like to see more effort on the part of the asker than this. –  Larry Wang Jul 25 '10 at 17:34

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  Ben Alpert Jul 25 '10 at 16:22
    
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. –  Isaac Jul 25 '10 at 16:31
    
Wow, I never knew about the first solution –  Casebash Jul 26 '10 at 2:09

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.