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.

(a) For breakfast, you have a choice of 4 kinds of doughnuts: glazed, chocolate, sugar and plain. In how many different ways can you choose 5 of these doughnuts?

(b) What is the answer in the general case that there are k kinds of dough- nuts and you want to select n doughnuts?

i think you have to use the Convolution Rule for this problem, but not really sure how to apply it

share|improve this question

1 Answer 1

Let $x_1,x_2,x_3$, and $x_4$ be the numbers glazed, chocolate, sugar, and plain doughnuts that you choose. Then each of these numbers must be a non-negative integer, and

$$x_1+x_2+x_3+x_4=5\;.\tag{1}$$

Each solution of $(1)$ in non-negative integers gives you a possible choice of doughnuts, and each possible choice of doughnuts gives you a solution to $(1)$ in non-negative integers. Thus, your problem reduces to counting the solutions to $(1)$ in non-negative integers. This kind of problem is often called a stars-and-bars problem; the linked article gives you the answer,

$$\binom{5+4-1}{4-1}=\binom83\;,$$

and a pretty decent explanation of the reasoning behind it. Between what I’ve done here with (a) and what you find in the article, you should be able to make a good stab at (b), but feel free to ping me if you get stuck.

share|improve this answer
    
what do you mean by "(1) in non-negative integers"? –  dotdotdot Jan 30 '13 at 9:15
    
@dotdotdot: $(1)$ is a reference to equation $(1)$, the first displayed equation: you’ll find its label, $(1)$, at the far righthand side. The phrase in non-negative integers modifies solutions: you’re looking for solutions in non-negative integers to the equation labelled $(1)$. –  Brian M. Scott Jan 30 '13 at 9:17
    
right... didn't see the (1) –  dotdotdot Jan 30 '13 at 9:19
    
quick question... when do you know its appropriate to use the stars and bars method... is there a clue i need to look for in a problem to determine if the stars and bars method applies? –  dotdotdot Jan 30 '13 at 10:03
    
@dotdotdot: Whenever you can recast it as a problem involving solving an equation of the form $x_1+\ldots+x_m=n$, the stars-and-bars idea is likely to be at least part of the solution. Alternatively, if you can think of it as counting the number of ways of distributing $n$ identical objects amongst $m$ distinct containers (so that $x_k$ is the number in container $k$), it’s a stars-and-bars problem. But I won’t conceal from you that sometimes it’s not obvious that a problem can be thought of in this way. This problem is perhaps an example. –  Brian M. Scott Jan 30 '13 at 10:07

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.