Recently my friend Cary asked me to stop at a donut shop that sells five varieties, and buy a dozen donuts. She didn't say how many of each type to buy so I began to wonder: in how many ways can you buy a dozen donuts from an unlimited supply of 5 types of donuts?

This seems similar to another problem I looked at that had to do with using permutations to solve problems like: in how many ways can we rearrange the letters in the word ABRACADABRA to form a new 'word'? Here a new 'word' is one that looks different. We looked at this problem in a couple of ways one of which was to first choose where the 5 A's can go in the 11 letter 'word', now place the 2 B's in the remaining 6 spots, next place the 2 R's and finally place the C and the D. Thus the number of 'words' is

[11]C[5]*[6]C[2]*[4]C[2]*[2]C[1]*[1]C[1] = 11!/5!2!2!1!1! = 83,160.

The key to the donut problem is to think of how many distinct ways you can line up 12 x's and 4 /'s to make a `word'. Why? Because there is a one to one correspondence between such lineups and possible purchases -- the `word' xx/xxx//xxxxxx/x corresponds to 2 of type 1, 3 of type 2, 0 of type 3, 6 of type 4 and 1 of type 5 etc. Thus there are

[16]C[4]*[12]C[12] = [16]C[4] = 1820

ways to buy the donuts.

I now want to relate this `word' type problem to a real-life situation that crops up in designing computer programs. In trying to write efficient programs it is important for the programmer to know how many steps the computer is executing; in this manner the programmer can estimate how fast their program will run.

A simple situation in what may be a complicated program is the situation whereby the computer is instructed to do a particular calculation a number of times in what is called a `Do Loop'. An simple example of this is as follows:

(set the counter to 0) c:=0
For i = 1 to j do
   For j = 1 to k do
     For k = 1 to 10 do
        (increment the counter by 1) c:= c+1

What we have to do is count all the possible choices for i, j and k where 1 <= i <= j <= k <= 10, i.e. all triples {i, j, k} where 1 <= i <= j <= k <= 10. These range through {1, 1, 1}, {1, 1, 2},{1, 2, 2}, ... {3, 6, 7}, ..., {10, 10, 10}. Let's look at this as a donut problem. I claim that the answer is the same as the answer to the problem of how many ways could I buy 3 donuts from 10 types! If we solved this as we did above we would make a `word' from 3 x's and 9 /'s. The number of ways to do this is [12]C[3] = 220 ways. How does this solve the do loop question? Look at a possible donut selection: //x///x/x/// -- this says buy a donut of type 3, type 6 and type 7. But this is also a triple {3, 6, 7} of the form {i, j, k} where 1 <= i <= j <= k <= 10 as we needed in the do loop question. Thus the counter will be incremented 220 times!

More generally, the do loop

(set the counter to 0) c:=0
For i = 1 to j do
   For j = 1 to k do
     For k = 1 to m do
       For m = 1 to n do
         For n = 1 to p do
            (increment the counter by 1) c:= c+1

So the next time someone asks you what you are doing in the donut shop tell them you are counting the number of steps in a multiple do loop.