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/