How Many Different Boxes of Donuts Can Be Made?
Date: 03/01/98 at 00:27:50 From: Denise Ferreira Subject: probability, combos, and permutations A donut shop has exactly 5 different types of donuts. How many different boxes of a dozen donuts can be made? Now, I can sit here for ages and write out all of the combos, but I want a formula to help me with this problem. In beginning to solve this problem, I began to think of some easier ways to put the donuts together. I came up with the first five boxes being each of the same kind of donut, and then putting one of each with eleven of the others donuts for ten more boxes. Then two of one type of donut, with only ten of another, making that ten more boxes -- and I know I can keep going with combos of 3 and 9, 4 and 8. However, I would like to find an easier and more efficient way. Thank You! QA
Date: 03/01/98 at 13:28:27 From: Doctor Sam Subject: Re: probability, combos, and permutations Denise, Think about taking an order for a dozen donuts from your friends. You might make marks on a sheet of paper like this: Donut A * B * C * D * E -------------------------------------- || * | * |||| * ||| * || meaning 2 type As, 1 type B, 4 type C's, 3 type D's and 2 type E's. Some other possibilities are: Donut A * B * C * D * E ------------------------------------- |||| * || * ||| * * ||| (4, 2, 3, 0, 3) ||||||* |||| * * * || (6, 4, 0, 0, 2) Every possible order can be listed simply by placing 12 marks inside these five columns. You have been working out the distributions one-at-a-time. There is an easier way. It depends upon you suddenly seeing the above picture as a list of 16 symbols: twelve | and four *. ANY list of these 16 symbols can be interpreted as a donut order. For example, ||**|||||||*|||* means 2 A's, 0 B's, 7 C's, 3 D's, 0 E's Once you have this idea, the problem is easy, because we have changed it from "number of kinds of donut boxes" to "number of ways of placing 12 |'s and 4 *'s in a row. If you have sixteen places then you can choose a place for the four *'s in C(16,4) ways. Once the *'s are in place, fill in the remaining spaces with |'s. So the answer is 16C4 = 1820. This method is called "stars and bars." -Doctor Sam, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.