# Counting Basics

Fundamental Principle of Multiplication:

Suppose that you are making a sandwich. If there are 3 types of bread to choose from, and there are 7 different condiments that you can put in the sandwich, the total number of sandwiches you can make is 3*7 = 21.

This can be generalized to any number of choices. If a task can be done in m ways, and the next task can be done in n ways, then the two jobs together can be done in m*n ways.

Example 1:

Q: Amy has three skirts and five blouses.  How many skirt-blouse outfits can Amy wear?

Solution: Amy has three choices for skirts and five choices for blouses. For each of the choice of her skirt, Amy has five choices for a blouse to make an outfit. So she can make

3 X 5 = 15

Skirt-blouse outfits.

Concept of Permutation:

The word permutation means arrangement. Think about this as how many ways we can arrange something. So if we have three people A, B and C trying to sit in a movie theater, how many ways can they be seated?

Permutations: ABC, ACB, BAC, BCA, CAB, CBA

There are 6 ways to do this. Now let’s see how we can do this without having to write them all out.

Example 2:

Q: In how many ways can 10 people be seated in a row of 10 chairs?

Solution:

We can use this example to calculate permutations in a fast and easy way. We can choose any of the 10 people to sit in the first seat, so we have 10 choices. Now there are 9 people left to choose from, so for the second seat, there are 9 choices. Similarly, there are 8 choices for the third seat, 7 for the fourth seat and so on until there is only one choice for the last seat. Thus, the total number of choices, using our rule of multiplication from above is 10*9*8*7….*3*2*1.

This number can also be written as 10!, and it is called a factorial. In general, n! is the same as n*(n-1)*(n-2)*…*3*2*1. Essentially, it is the same as multiplying all the numbers equal to or less than n. A special case for factorial occurs when you consider 0!, and this value happens to be 1 (since there is only one way to count nothing!)

Let’s look at another example:

Example 3:

Q: In how many ways can a row of 5 seats be filled from a set of 12 people?

Solution: Similar to the previous problem, we have 12 choices for the first seat, 11 for the second, 10 for the third, 9 for the fourth and 8 for the fifth seat. So the total number of ways is

12 x 11 x 10 x 9 x 8

It is important to note that the order of the people sitting is important in a permutation. Also, we can’t have any repetitions. This particular permutations is one of 12 objects(number of people) taken 5 at a time (seats to be filled).

Now, let’s look at a case where we might be over-counting our choices.

Over counting:

Example 4:

Q: How many different ways can the five letters of the word STATE be scrambled?

Solution:  As we have seen earlier, five letters of the word STATE can be scrambled in 5*4*3*2*1 = 5! ways.

However, note that the letter “T” is repeated twice and these two T’s are indistinguishable and provide the same arrangement during scrambling. So we over counted the number of ways of scrambling this word.  These two T‘s  can be arranged in 2! ways. To make the counting correct, we want to divide our total by 2!.

So the total arrangements is 5!/2! = 120/2 = 60 ways.

Practice makes perfect, so let’s try another example:

Example 5:

Q: How many different ways can the five letters of the word BREEZE be scrambled?

Solution: There are 6 letters, so total number of permutations is 6*5*4*3*2*1 = 6!. However, we see that “E” is repeated three times, and they are over counted by 3*2*1 = 3! times. So, the different ways of scrambling BREEZE is

6!/3! = 120 ways

So we’ve seen permutations, and permutations with repetitions thus far. Now, let’s move on to cases where the order doesn’t matter. These are called combinations. For example, when we pick 5 people for a team, we don’t care what order they are picked, we only care about which five people we have on the team. Let’s look at the mathematics behind this idea of combinations:

Combination:

Example 6:

Q: In how many ways can a team of 5 people be selected from a group of 12 people?

Note that the order is not important here. It is immaterial the way 5 people are selected.   Arrangements in which order is not important are called combinations.  We say that this is a combination of 12 objects (number of people) taken 5 at a time (seats to be filled).

Solution: If we first think of how many ways we can pick the 5 people, there are 12 choices for the first person, 11 for the second, and so on. Thus like before, we get a total of 12*11*10*9*8. However, since order does not matter, any of the five permutations of selected people would produce the same combination. What do we mean by this? Suppose we select Amy, Bush, Clara, Danny and Eve. The order in which they are selected doesn’t matter. There are 5*4*3*2*1 = 5! ways to arrange them. All these arrangements still result in the same 5 people being chosen. Thus, we are over-counting.  Therefore, we need to divide the total arrangements by 5!.The final answer becomes (12*11*10*9*8)/5!.

Let’s look at another example of combinations:

Example 7:  A merchant decides to put two of his eight VCR models on sale, but has not decided which two.  How many different selections can she make?

Solution: The first one can be picked in 8 ways, and the second in 7 ways. However, we don’t care about the order, so we divide by 2!. Thus the total is 8*7/2! = 28 ways.

Quick Recap:

So far, started with the simple idea of multiplication, and counted permutations or arrangements of objects. Then we looked at permutations with repetitions. Finally, we looked at combinations, where the order doesn’t matter when counting objects. Now let’s look at one last way to count the something. By counting what we don’t want, and subtracting that amount from the total number of options. This is called complimentary counting.

Complementary Counting

Example 8:

Q: How many three-digit numbers are not multiple of 7?

Since the title above says complimentary counting, I guess we can give it a shot! Let’s count how many three digit numbers are a multiple of 7, and subtract that from the total number of three digit numbers.

The first multiple of 7 that is a three digit number is 7*15 = 105. The last one is 7*142 = 994. This means all the multiples of 7 from 15 to 142 are the ones we are looking for. There are 128 of these. Now, there are 900 total three digit numbers (since 100 is the lowest, and 999 is the highest). Thus, the total number of three digit number that are not a multiple of 7 is 900-128 = 772.

Let’s look at a slightly more complicated problem which can be solved by complimentary counting:

Example 9:

Q: The Smith family has 4 sons and 3 daughters. In how many ways can they be seated in a row of 7 chairs such that at least 2 boys are next to each other?

Solution: So, we want to first count the number of ways that the 7 children can be seated such that no two boys are seated together. We can then subtract this from the total number of ways that the 7 people can be seated.

If we think about how we can seat the kids so that the boys won’t sit next to each other, we realize that each pair of boys must be separated by a girl. Thus, the only arrangement in terms of gender is BGBGBGB. Since we have the arrangement in place, the number of ways to do this depends only on what order the boys sit in, and the order in which the girls sit. This is 4! for the boys and 3! for the girls, so the total of 4!*3!.

Now the total number of ways to sit 7 children is simply 7!.

Thus our final answer becomes 7!-4!*3! = 4896.

Example 10:

Q: Find the total number of ways in which 10 distinct objects can be put into 2 different boxes so that no box remains empty?

Solution:

Again, using our complimentary counting skills, we first want to see how many ways we can put these 10 objects in these 2 boxes such that at least one of them remains empty. We can then subtract this from the total number of ways. Both boxes can’t be empty, so either the first is empty or the second is empty. Thus there are only two ways of this happening.

Now we find the total number of ways. Each object has 2 choices: it can be in the first or the second box. Thus the total number is 2*2*2*..*2 = $2^{10}$ ways

Therefor, our final answer becomes $2^{10}-2$ .

Exercises:

1. How many four letter code words are possible using first 10 letters of the English alphabet, if no letter can be repeated?

2.  How many numbers are there between 100 and 1000 such that every digit is either 2 or 9?

3.  How many committees of seven with a given chairman can be selected from twenty people?

4. How many hand shakes if 10 friends meet and shake hands with one another?

5. In how may ways a deck of cards be arranged if no two hearts are adjacent?

6.  Three distinguishable dice are thrown. In how many ways they can land and give a sum of 9?

7. In how many ways one permute the word MEPHISTOPHELES?