Discrete Mathematics An Open Introduction, 4th Edition

List all possible two-chip stacks. For example, the stack with a red chip on bottom and a green chip on top can be listed as “RG”.

Using the additive principle, we notice that there are stacks that have blue on the bottom, another stacks that have red on the bottom, so there are a total of possible stacks.

If we use the multiplicative principle, then there are choices for the bottom chip and choices for the top chip, so there are possible stacks.

First, how many three-chip stacks with no repeated color have blue on the bottom and green in the middle?

And how many three-chip stacks with no repeated color have blue on the bottom and yellow in the middle?

In fact, for any stack with blue on the bottom and some other color in the middle, there are possible stacks.

If we insist that blue is on the bottom, how many choices do we have for the color of the middle chip?

Combining this with the answer from the previous question, how many three-chip stacks with no repeated color have blue on the bottom?

Of course, we didn’t need to start with blue on the bottom. How many choices do we have for the color of the bottom chip?

So how many three-chip stacks with no repeated color are there?

How many four-chip sticks are there with no repeated color?

One outcome is taking the blue, green, and purple chips. How many of the three-chip stacks of different color chips correspond to this single pocketful?

How many different stacks of chips would result in picking up the red, yellow, and green chips?

So of the possible three-chip stacks, we can group the chips into groups of size , where each group corresponds to the same pocketful of chips. How many different pocketfuls of chips are there?

How many different pocketfuls of chips are there if you take four chips?