In this tutorial, some counting methods will be discussed. In particular, counting the number of ways to form subsets of a larger set under various conditions.
Introduction
Suppose you own a landscaping company with six employees: Alice, Bob, Charlie, Dorothy, Evan, and Fred. To make managing easier, you decide to divide the six workers into two evenly sized teams. How many ways are there to do this?
As it turns out, there are ten ways to accomplish the division. You can verify by enumerating the ten possibilities. However, for problems on a larger scale, enumeration will not suffice and it becomes necessary to formulate and generalize counting methods.
Preliminaries
Let us begin with a couple basic concepts. Suppose you have the integers from 1 to 10 lined up in order. Next, you scramble and shuffle them into any order you wish. How many ways can you do this?
Well, any of the ten numbers can become the first number. So there are ten options for the first number in the new order. Now, whatever number you choose to be the first number, there will be nine remaining numbers to set as the second number in the new order. And whatever number you choose, there will be eight remaining numbers for the third number and so on. In this way, you will have 10 options for the first choice, 9 options for the second choice, 8 options for the third choice, all the way down to 1 option for the tenth choice. So the number of ways to scramble the ten numbers is
$ 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 10! $
This is known as counting permutations. In general, there are $ n! $ ways to permute $ n $ distinguishable objects.
However, we can generalize this concept. Suppose instead of taking the numbers and forming a new order, suppose we take only six numbers and make a new order from those three. Similar to the other case, there will be 10 options for the first choice, 9 options for the second choice, all the way down to 5 options for the sixth choice. So the number of ways to choose a new order with five numbers is
$ 10 \times 9 \times 8 \times 7 \times 6 \times 5 = \frac{10!}{4!} $
In general, there are
$ \frac{n!}{(n-k)!} $
ways to choose k objects with order from a set of n distinguishable objects. Let us denote this as $ P^n_k $.
Finally, let us introduce the concept of a combination. A combination is a way to choose k objects without order from a set of n distinguishable objects and will be denoted as $ C^n_k $. You may notice that for these k objects, there are k! ways to order them. So since we can choose a combination of k objects and an ordering for those k objects and get a unique way to choose k objects with order. So,
$ C^n_k \times k! = P^n_k $
$ {n \choose k} := C^n_k = \frac{P^n_k}{k!} = \frac{n!}{(n-k)!k!} $
Examples
Q: How many ways are there to arrange the letters in the alphabet?
- A: This is a permutation of a set with 26 distinguishable objects. So there are 26! ways. (You can compute this with a calculator if you wish but we will leave it in this simplified form.)
Q: An Olympic race has 100 contestants. How many ways to give gold, silver, and bronze medals?
- A: This is choosing 3 objects with order from a set of 100 objects. So the number of ways is,
$ P^{100}_3 = \frac{100!}{97!} = 970200 $
Q: A wealthy car manufacturer is writing her will. She has 3 different cars and 100 grandchildren. She won't give multiple cars to one grandchild. How many ways are there to give the cars away in her will?
- A: We can think of this problem as selecting 3 grandchildren with order from the set of 100 grandchildren, then giving the first selected grandchild the first car, and so on. Thus, the number of ways is,
$ P^{100}_3 = \frac{100!}{97!} = 970200 $
Q: A town security system has 10 security shifts available and 22 applicants. How many ways to hire for the 10 different positions?
- A: Once again, we think of selecting 10 people with order from the 22 applicants and giving the first person the first shift and so on. So the number of ways is,
$ P^{20}_{10} = \frac{22!}{12!} $
Q: The Omaha Zoo is hiring 12 zookeepers. They have 300 applicants. How many ways to hire 12 zookeepers from the applicants?
- A: We would use combinations in this case since hired people are indistinguishable. In other words, the order of the hiring doesn't matter. So, the number of ways is,
$ {300 \choose 12} = \frac{300!}{12! \times 288!} $
