Before starting this lesson, you should be familiar with factorial notation and with the concept of factorials.
E.g.
4! = 4 x 3 x 2 x 1
N! = N x (N-1) x ... x 2 x 1
Suppose that there are 5 types of sandwich bread and 4 kinds of lunch meat, then how many different types of sandwiches could be made, assuming one kind of meat is used in any one of them? The answer is 20. Why? Because for each one of the 5 different kinds of bread there were 4 different varieties of meat to slap between them, and 5 x 4 = 20.
This is an example of the fundamental principle of counting, which states that if there are n ways to do one thing, and m ways to do another, then there are n x m ways to do both things. Or more generally:
If we are making n choices, and the ith choice could be made in ki ways, then there are k1 x k2 x ... x kn ways to make all n choices.
Suppose now you are allowed to choose any two lunch meats, even the same meat twice, then there would be 5 types of bread, 4 types meats for the first choice, and 4 meats for the second. So there are 5 x 4 x 4 = 80 different kinds of sandwiches that could be prepared.
When making a sandwich in the above example, we had to make two choices - one for bread and one for meat. These two choices taken together identified the sandwich we intended to make. In other words, our selection of a sandwich was just the result of our choices. When we are talking about counting problems, especially those that involve making one choice after another, we use the word selection to mean the way in which those choices were made.
When making a selection, there are a two features to identify. One, does the order of our choice matter? And two, can we pick the same thing more than once? That is, we need to identify whether or not order is significant in our selection, and whether or not repetitions are allowed.
Suppose you give a box of 8 crayons to a boy named Thomas, and you ask him to write his name using a different color for each letter. If we want to know how many ways Thomas can write his name, we need to identify what kind of selection this is.
Because any crayon he chooses can only be used to write one letter, repetition is not allowed in the selection. Also, because he cannot write his name in any order ("Thomas", but not "Otmhsa") then order is significant. We will see how to calculate this in the next section.
Now suppose that Thomas and a friend both want to draw. In order to be fair, you decide to divide the crayons up evenly between them, giving each of them 4 colors. What can we tell about this selection?
Again, because we cannot give one crayon to both children, repetition is not allowed in this selection. Also, because it doesn't matter what order we give them out, just so long as each child ends up with 4 crayons, order is not significant in this selection. We will see how to calculate the number of ways to make this selection in a later section.
Whenever order is significant in our selection, we are dealing with a permutation. So the example above, in which Thomas had to spell his name with different colors, was a permutation problem. Another way to look at permutations is to see them as reorderings.
How many ways are there to jumble the letters in the word "cat"?
We can simply list them:
cat cta
tac tca
act atc
So the answer, including the word "cat" itself, is 6. But how could we arrive at this number without listing all of the possibilities?
Notice that we had 3 letters for the first choice, which left only 2 letters for the second choice, and only 1 letter for the final choice. So using the fundamental principle of counting we have 3 x 2 x 1 = 3! = 6 possible reorderings of the word "cat". We also say that there are six permutations of the letters of the word "cat".
Now suppose that you have opened a new bank account and you need to choose a Personal Identification Number (PIN) to use at ATMs around town. The PIN must be five digits long, and each digit can be any number 0 through 9. How many different PINs could you choose?
In this selection order is important, because 01234 is not the same PIN as 43210. However, this time, repetition is allowed because 00223 and 11112 are both valid PINs. We may again use the fundamental principle of counting. This time we have 5 choices to make, and each choice can be one of 10 numbers. That is 10 for the first choice, 10 for the second, 10 for the third and so on. So we have 10x10x10x10x10 = 105 = 100,000 possible PINs.
What about the number of ways that Thomas can write his name, using a different color for each of the six letters, and with eight colors to choose from? The solution is straightforward. Thomas has 8 colors to choose from for the first letter of his name, then only 7 colors for the second letter, then 6 for the third, 5 for the forth, 4 for the fifth, and only 3 for the sixth and final letter. So he could write his name in 8 x 7 x 6 x 5 x 4 x 3 = 20,160 ways. It is interesting that this just looks like a factorial, except that we stopped multiplying before getting to 1. In fact we left off exactly 8 - 6 = 2 numbers from our factorial. So another way to write this is 8!/2! = 20,160
Notice a special case of the second result when n = k. In that case, since (n-n)! = 0! = 1 (by convention), then we are just left with n!. So the number of permutations of n things is just n!.
When we make a selection without regard for order and without repetition, then we are selecting a combination.
Suppose that you are moving and you know five people who own trucks and would be willing to help you out. You think, however, that you could get everything moved with only two trucks. Not wanting to show favoritism, you decide to write each of your five friends' names on slips of paper and draw two of them randomly from a hat. How many different pairs of names might you draw?
This situation is a little bit like that that of Thomas writing his name with different crayons, but this time we don't care about the order. So if we calculate 5!/(5-2)! = 5!/3! = 20, we have found the number of ways to select two people in order. But this isn't quite what we wanted, since the order didn't matter, we need to divide by the number of ways to reorder two things, that is, we divide 20 by 2! = 2x1 = 2. So there are 20/2 = 10 ways to draw two names out of a hat containing five names.
What did we do in the example above? We had n things and we wanted to form a group by choosing k of them. This lead us to first calculate the number of ways of choosing k things out of n paying heed to order, so n!/(n-k)!. Next, because the order of our choice didn't matter, we divided that value by the number of ways to reorder k things, which is k!. Putting this all together we get:
The number of ways to choose k things from a set of n, without repetition and without respect for order, written nCk (pronounced "n choose k") is given by:
If you have studied the binomial theorem, you will recognize this as the value of the kth binomial coefficient. Here are a few notations, all of which mean "n choose k", or the combination of "k items form a set of n".
What about the example when a friend joins Thomas and wants to color? We wanted to know how many ways we could split up the 8 crayons into two sets of 4.
Our task is greatly simplified by noticing when we choose 4 crayons out of 8, we have also not chosen the remaining 4 crayons. This means that by selecting one set of 4 crayons, we have automatically selected the other set - it's just whatever was left over. So now our problem can be restated in more familiar terms: how many different sets of 4 crayons can be chosen out of a box containing 8 crayons?
We can just use the result listed above:
So there are 70 ways to split these 8 crayons up evenly between the two boys.
