Suppose an ice cream parlor has 12 flavors available and the "pig out" special is an order of four scoops of ice cream. How many ways are there to order a "pig out" special that contains four different flavors of ice cream (the order of scoops doesn't matter).

Though there are obviously going to be easier methods in solving this this problem, I was wondering how this question relates to the stars and bars method, I didn't think that it did until a question specifically said to solve it in the stars and bars method

Though what I was attempting to do is flawed,

I was thinking that we can use 4 bars and 12 flavors which is 16C4 but that didn't get me the right answer

I was also wondering how one may approach this problem if flavors could be repeated? i.e. four scoops of onion flavored ice cream

  • $\begingroup$ Note that the bars divide the categories, and the stars represent the actual things you choose. That way, there are $11$ bars (because eleven dividers makes twelve regions) and $4$ stars (because you get for scoops). Also, stars and bars allow repeating inherently, because there can be more than one star between two bars. $\endgroup$ – Arthur May 23 '17 at 7:05
  • $\begingroup$ There is no repetition in this problem since each flavor is different. Since order does not matter, you just want to select a subset of four of the twelve flavors, which can be done in $\binom{12}{4}$ ways. $\endgroup$ – N. F. Taussig May 23 '17 at 10:27
  • $\begingroup$ @N.F.Taussig: OP has mentioned that obviously there are easier methods, but that the question specifically asks for a solution using stars and bars. $\endgroup$ – true blue anil May 23 '17 at 14:43

You can use stars and bars here,
but it will be like catching your nose by bringing your arm from behind !

Imagine that you have unflavored scoops of ice cream, and $12$ "flavored buckets" which give the ice cream a distinctive flavor.

Now since we aren't to allow two scoops of a flavor, to exclude such cases,we deliberately put $2$ scoops in one or more buckets (here, obviously a max of $2$), and apply inclusion-exclusion.

Thus $\binom{15}{11} - \binom{12}{1}\binom{13}{11} + \binom{12}{2}\binom{11}{11} = 495$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.