Section 1.1 – Making Lists

Listing the Possibilities

My youngest son Randy's favorite sandwich is a BLT. He would have one every day for lunch. To try to bring a little variety to his meals, I suggested adding some options to each part of the sandwich.

With those options to choose from, could he go a whole week without having the same sandwich twice? Could you go a whole month without having the same sandwich twice?

The most straightforward way to approach this kind of question is to list out all of the possible options. For example

Try to finish the list on your own and see how many combinations you end up with.

Your final list should have 12 combinations. If it doesn't then you stumbled on the biggest challenge with making out a list: It's easy to either miss an option and under count the total or include an option twice and over count it.

One way to improve the accuracy of a list is to organize the options into what's called a tree diagram. To create this kind of diagram, you should start with what it is you're trying to count, sandwich options in our case, and then draw lines or branches going out from there listing every option. Using our sandwich example, my tree would start with "sandwich options" and then have a branch for each type of lettuce:

The second choice my son has to make is the type of tomato. To add this to the tree, I'll put another set of branches coming off of each lettuce option showing the tomato choices.

And, finally, he gets to choose a type of bacon. I'll add those to the diagram by putting a final set of branches, one for each of the three bacon types, coming from each of the tomato branches.

To get the sandwich combinations that I listed on the right hand side, you just follow each branch all the way to the end. For example, following the top branches gave me iceberg lettuce then green tomatoes and then regular bacon. Following the bottom branches gave me Romaine lettuce, beefsteak tomatoes and maple bacon. If you count up the combinations, you'll see that I ended up with the 12 that I said you should find on the previous page.

Before we move on, we need a quick definition that will let us refer to all of the possible outcomes as a single group.

In our BLT example, the sample space would be all of the combinations in the list on the right side of the tree, i.e. {iceberg lettuce, green tomato, regular bacon}, {iceberg lettuce, green tomato, extra thick bacon}, {iceberg lettuce, green tomato, maple bacon}, etc.

Decomposition

In mathematics, decomposition refers to breaking down a big problem into smaller pieces. When we're doing combinatorics problems, it refers to taking a problem like making a sandwich and breaking it down into a series of individual choices. In our sandwich example, there were three choices that had to be made:

Throughout this chapter, many of the solutions are going to start off with the question, "What choices do I have to make?" or "How can an event occur?" For example, if I told you that a couple had two children and asked you to make a tree diagram to represent the possible boy/girl combinations you would be looking at events rather than choices. For example, the first branch would be the two possible results of the first birth: either the baby is a boy or the baby is a girl.

The second set branches would represent the outcomes of the second event, i.e. second birth. This will be another set of boy/girl branches coming from each of the two original branches.

So how many different families are there? At first glance, you might say four because there are four branch endings but take a look at the middle two: {boy, girl} and {girl, boy}. Are those two really different? They both represent a family with one boy and one girl. The answer is, it depends. The big question you have to ask here is, "Does the order in which the kids are born make a difference?" If it does then the answer is four because {boy, girl} really means {boy first, girl second}. If the order doesn't matter then the answer is three because {boy, girl} and {girl, boy} both mean a family with one child of each gender.

For purposes of making a tree diagram, this isn't a big concern. Your tree should always have all the possible branches like my boy/girl family tree does. We'll talk about this more when we get to Section 1.3.