Combinatorics Problem
-
How do I solve this:
"Pat is to select six cookies from a tray containing only chocolate chip, oatmeal, and peanut butter cookies. There are at least six of each of these three kinds of cookies on the tray. How many different assortments of six cookies can be selected?"
The answer is shown below, but I don't know how to get the answer. Please explain. Your help is much appreciated.
answer: 28
-
Explanation:
Of the 6 cookies Pat chooses, there are three types: chocolate chip, oatmeal, and peanut butter cookies. We also note that there can be 0 of a type. We can use the stars and bars formula to divide 6 objects into three categories (n is the number of objects, which is cookies in this case, and k is the number of categories):n+k-1 choose k-1
= 6+3-1 choose 3-1
= 8 choose 2
= 28That is why the answer is 28.
Please find below the proof for the stars and bars formula.
Let's use the cookies problem from above to help us with the proof. Right now, n=6 (6 cookies) and k=3 (3 types of cookies).
Putting 6 cookies into 3 categories looks like this:
There are 8 objects total in that picture (6 cookies + 2 bars).
Let's say we remove all objects and hold them. There are 8 spots to put our 8 objects. We can choose 2 spots of these 8 spots to put our bars, and the cookies go into the remaining 6 spots. Therefore, there are 8 choose 2 = 28 different combinations of 6 cookies.So, in the formula n+k-1 choose k-1, n+k-1 represents the total number of spots to put the objects and the bars, and k-1 represents the number of bars needed to split the objects into k categories (for example, in our problem, 2 bars were needed to split the 6 cookies into 3 categories).