1

I am looking the basics of combinations with repetition. The other name is Stars and Bars problem.

On MIT OCW I found this:

An ice-cream store specializes in super-sized deserts. They offer a “quad-sundae” which has 4 scoops of ice-cream mixed together in a bowl. Once the scoops are in the bowl, you can’t distinguish their order, you can only tell how many of each flavor there are. Note however that a sundae with 3 scoops of vanilla and 1 scoop of chocolate is different from a sundae with 3 scoops of chocolate and 1 scoop of vanilla. The store has 10 different flavors of ice cream to choose from. How many different quad-sundaes can you get?

I said that it is a Bars and Stars problem. I did it like Logic behind combinations with repetition? here or http://www.csee.umbc.edu/~stephens/203/PDF/6-5.pdf.

$\binom{10+4-1}{4-1}$ = $\binom{10+4-1}{10}$ = 286

but MIT said that:

$\binom{9+4}{9}$ = $\binom{9+4}{4}$ = 715

which one is true one :)

Thank you for your answers in advance.

Community
  • 1
Zafer
  • 173

2 Answers2

1

Basically the formula for distributing $n$ identical things in $r$ distinct bins where each bin can take any number of things is $\frac{(n+r-1)!}{r!(n-1)!}$. This is a standard formula you can look up the derivation , its easy to prove. Now in your problem scoops are the identical things and flavors the distinct bins, so $n=4$ and $r=10$ so answer is $\binom{10+4-1}{4}$.

advocateofnone
  • 2,059
0

This problem is equivalent to the number nonnegative integer solutions of this Diophantine equation:

$$x_1 + x_2 + ... + x_9 + x_{10} = 4$$

Considering the bijective relation between this nonnegative integer solutions and the stars and bars problem, the amount of stars corresponds to the right hand of the above equation which doesn't change (the total scoops of flavors should not change); and to seperate the places into 10 groups you need 10-1 bars, then there should be 10-1+4 places, 10-1 places for bars and 4 places for stars.

Lerner Zhang
  • 724