Counting Rules

The Counting Principle

Before we can delve into the properties of probability and odds, we need to understand the Counting Principle. We use the Counting Principle to determine how many different ways one can choose/do certain events. It is easier to define the Principle through examples:

Independent Events

Let's say that John is at a deli sub restaurant. There are 3 different breads, 3 different cheeses, 3 different condiments, and 3 different vegetables he can place on his sandwich, assuming that he can only place one from each category on to his sandwich. How many different ways can he set up his sandwich?

Since choosing a cheese doesn't affect the number of choices of vegetables, condiments, or bread, these events are called independent events. For this problem, we will multiply $3\times 3\times 3\times 3$ , so $3^{4}$ , which is 81. So there are 81 different possible combinations to form this sandwich.

Practice Problems

1) Thomas goes to a McDonalds' restaurant and chooses to create his own burger. He has 2 different kinds of cheese, 3 different breads, and 3 different sauces he can choose from, but he can only choose one of each category. How many different ways can he create this burger?

2) Diane is ordering pizza for her family. There are 4 different possible sizes of the pizza. Also, she has to choose one of 5 toppings to place on the pizza and one of 3 different types of cheese for the pizza. In addition, she must choose one of 3 different kinds of crust. How many different ways can she have her pizza?

3)

a) How many 3-digit numbers can be formed from the digits 2, 3, 4, 5, 7 and 9?

b) How many of these numbers are less than 400?

Answers

1) $(2)(3)(3)=18$

2) $(4)(5)(3)(3)=180$

3)

a) Since there are six available digits, the answer is $(6)(6)(6)=216$

b) For the value of the 3-digit number to be less than 400, we only have two choices for the first digit, namely 2 or 3. After that we can choose the other two digits freely. The answer is thus $(2)(6)(6)=72$.

Dependent Events

Assume that John is now working at a library. He must put 5 books on a shelf in any order. How many different ways can he order the books on the shelf? Unlike the independent events, when John puts a book on the shelf, that eliminates one book from the remaining choices of books to put next on the shelf; thus these are referred to as dependent events. At first, he has 5 different choices, so our first number in the multiplication problem will be 5. Now that one is missing, the number is reduced to 4. Next, it's down to 3, and so on. So, the problem will be

$(5)(4)(3)(2)(1)$

However, there is a symbol for this very idea. A $!$ represents the term factorial. So, for example, $3!=(3)(2)(1)$ . Factorials are very useful in statistics and probability.

Therefore, the problem can be rewritten as $5!$ , which ends up being equal to 120.

However, not all dependent event problems are that simple. Let's say that there are 10 dogs at a dog competition. How many different ways can one select the Champion AND the Runner-Up? This problem could actually be considered simpler than the last one, but it doesn't involve a factorial. So, how many different ways can the judge determine the Champion? Of course, there are 10 different dogs, so 10 different ways. Next, how many dogs are left to select the Runner-Up from? Well, you removed one, so it's down to 9. Instead of placing a factorial, though, you will only multiply 10 and 9, resulting in 90.

Independent Or Dependent?

To help you differentiate between the two, we will do a few more examples, but we will have to decide if it is dependent or independent before solving the problem.

Let's say that you are creating a 5-digit garage door opener code (the digits would include 0-9). If there were absolutely no restrictions, would the events be independent of each other or dependent on each other? Of course, there are no restrictions, since you could have five 4's for the code, so to solve the problem, you multiply 10 by itself 5 times, resulting in 100000.

Alternatively, suppose that the first number of the code cannot be 0, and that there can be no repeated numbers whatsoever. Obviously these events are dependent on each other, because there cannot be any repetitions. Let's look at this problem one number at a time.

The first number can be all the numbers except 0, reducing the possible numbers to 9. The second number can be 0 this time, so the possible numbers returns to 10. However, it cannot be a repeat of the previous number, so there are 9 possible choices again. After that, the numbers will reduce by one each time, due to the fact that there cannot be repeats, so the problem would look like this

$(9)(9)(8)(7)(6)={\frac {(9)(9!)}{(5!)}}=27216$

Now, just one more example. Let's say that you were choosing your schedule for school. There are 8 periods each day, and there are 7 classes to choose from. Nonetheless, you must have a lunch period during the 4th period. We can think of 4th period as non existent because it is in a constant position and therefore does not affect the possible choices. With 7 slots and 7 options, the answer is simply $7!$ .

$(7!)=5040$

Review Of The Counting Principle

So, we use the Counting Principle to determine the different unique ways we can do something, such as a sandwich or a selection of classes. Sometimes, these events will affect each other, such as when you can't choose the same number twice for your garage door code, so they are dependent events. However, other times, one event has no effect on the next event, such as when you have different cheeses and breads to choose for your sandwich, so they are independent events. The Counting Principle is a fundamental mathematical idea and an essential part of probability.

Counting Rules

Rule 1: If any one of $k$ mutually exclusive and exhaustive events can occur on each of $n$ trials, there are $k^{n}$ different sequences that may result from a set of such trials.

• Example: Flip a coin three times, finding the number of possible sequences. $n=3\ ,\ k=2$ , therefore, $k^{n}=2^{3}=8$

Rule 2: If $k_{1},\dots ,k_{n}$ are the numbers of distinct events that can occur on trials $1,\dots ,n$ in a series, the number of different sequences of $n$ events that can occur is $k_{1}\times \cdots \times k_{n}$ .

• Example: Flip a coin and roll a die, finding the number of possible sequences. Therefore, $(k_{1})(k_{2})=(2)(6)=12$

Rule 3: The number of different ways that $n$ distinct things may be arranged in order is $n!=(1)(2)(3)\times \cdots \times (n-1)(n)$ , where $0!=1$ . An arrangement in order is called a permutation, so that the total number of permutations of $n$ objects is $n!$ (the symbol $n!$ Is called n-factorial).

• Example: Arrange 10 items in order, finding the number of possible ways. Therefore, $10!=10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=3,628,800$

Rule 4: The number of ways of selecting and arranging $k$ objects from among $n$ distinct objects is: ${\frac {n!}{(n-k)!}}$ , or as seen on calculators, [nPr].

• Example: pick 3 things from 10 items, and arrange them in order. Therefore $n=10\ ,\ k=3$ , therefore ${\frac {10!}{(10-3)!}}={\frac {10!}{7!}}=720$

Rule 5: The total number of ways of selecting $k$ distinct combinations of $n$ objects, irrespective of order (ie order NOT important), is: ${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}$ or as seen on calculators, [nCr].

• Example: Pick 3 items from 10 in any order, where $n=10\ ,\ k=3$ , Therefore, ${\binom {10}{3}}={\frac {10!}{3!(7!)}}={\frac {720}{6}}=120$ .

Resources

• Some Simple Counting Rules, Hamilton Institute
• Basic Counting Rules, Permutations, Combinations, Purdue University