3.6: Basic Counting Rules
Learning Objectives
 Understand the definition of random sampling.
 Calculate ordered arrangements using factorials.
 Calculate combinations and permutations.
 Calculate probabilities with factorials.
Inferential Statistics is a method of statistics that consists of drawing conclusions about a population based on information obtained from a subset or sample of the population. The main reason a sample of the population is only taken rather than the entire population (a census) is because it is less costly and it can be done more quickly than a census. In addition, because of the inability to actually reach everyone in a census, a sample can actually be more accurate than a census.
Once a statistician decides that a sampling is appropriate, the next step is to decide how to select the sample. That is, what procedure should we use to select the sample from the population? The most important characteristic of any sample is that it must be a very good representation of the population. It would not make sense to use the average height of basketball players to make an inference about the average height of the entire US population. It would not be also reasonable to estimate the average income of the entire state of California by sampling the average income of the wealthy residents of Beverly Hills. Therefore, the goal of sampling is to obtain a representative sample. For now, we will only study one powerful way of taking a sample from a population. It is called random sampling.
Random Sampling
A random sampling is a procedure in which each sample of a given size is equally likely to be the one selected. Any sample that is obtained by random sampling is called a random sample.
In other words, if \begin{align*}n\end{align*} elements are selected from a population in such a way that every set of \begin{align*}n\end{align*} elements in the population has an equal probability of being selected, then the \begin{align*}n\end{align*} elements form a random sample.
Example:
Suppose you randomly select \begin{align*}4\;\mathrm{cards}\end{align*} from an ordinary deck of \begin{align*}52\;\mathrm{cards}\end{align*} and all the cards selected are kings. Would you conclude that the deck is still an ordinary deck or do you conclude that the deck is not an ordinary one and probably contains more than \begin{align*}4\end{align*} kings?
Solution:
The answer depends on how the cards were drawn. It is possible that the \begin{align*}4\end{align*} kings were intentionally put on top of the deck and hence drawing \begin{align*}4\end{align*} kings is not unusual, it is actually certain. However, if the deck was shuffled well, getting \begin{align*}4\end{align*} kings is highly improbable. The point of this example is that if you want to select a random sample of \begin{align*}4\;\mathrm{cards}\end{align*} to draw an inference about a population, the \begin{align*}52\;\mathrm{cards}\end{align*} deck, it is important that you know how the sample was selected from the deck.
Example:
Suppose a lottery consists of \begin{align*}100\end{align*} tickets and one winning ticket is to be chosen. What would be a fair method of selecting a winning ticket?
Solution:
First we must require that each ticket has an equal chance of winning. That is, each ticket must have a probability of \begin{align*}1/100\end{align*} of being selected. One fair way of doing that is mixing all the tickets in a container and blindly picking one ticket. This is an example of random sampling.
However, this method would not be too practical if we were dealing with a very large population, say a million tickets, and we were asked to select \begin{align*}5\end{align*} winning tickets. There are several standard procedures for obtaining random samples using a computer or a calculator.
Sometimes experiments have so many simple events that it is impractical to list them. However, in some experiments we can develop a counting rule, with the use of tree diagrams that can aid us to do that. The following examples show how that is done.
Example:
Suppose there are six balls in a box. They are identical except in color. Two balls are red, three are blue, and one is yellow. We will draw one ball, record its color, and set it aside. Then we will draw another one, record its color. With the aid of a tree diagram, calculate the probability of each outcome of the experiment.
Solution:
We first draw a tree diagram to aid us see all the possible outcomes of this experiment.
The tree diagram shows us the two stages of drawing two balls without replacing them back into the box. In the first stage, we pick a ball blindly. Since there are \begin{align*}2\end{align*} red, \begin{align*}3\end{align*} blue, and \begin{align*}1\end{align*} yellow, then the probability of getting a red is \begin{align*}2/6.\end{align*} The probability of getting a blue is \begin{align*}3/6\end{align*} and the probability of getting a yellow is \begin{align*}1/6.\end{align*}
Remember that the probability associated with the second ball depends on the color of the first ball. Therefore, the two stages are not independent. To calculate the probabilities of getting the second ball, we look back at the tree diagram and observe the followings.
There are eight possible outcomes for the experiment:
 RR: red on the \begin{align*}1^{st}\end{align*} and red on the \begin{align*}2^{nd}\end{align*}
 RB: red on the \begin{align*}1^{st}\end{align*} and blue on the \begin{align*}2^{st}\end{align*}
And so on. Here are the rest,
\begin{align*}RY, BR, BB, BY, YR, YB.\end{align*}
Next, we want to calculate the probabilities of each outcome.
\begin{align*}P(R\ 1^{st}\ \text{and}\ R\ 2^{st} ) & = P(RR) = 2/6 \cdot 1/5 = 2/30\\ P(R\ 1^{st}\ \text{and}\ B\ 2^{st} ) & = P(RB) = 2/6 \cdot 3/5 = 6/30\\ P(RY) & = 2/6 \cdot 1/5 = 2/30\\ P(BR) & = 3/6 \cdot 2/5 = 6/30\\ P(YB) & = 3/6 \cdot 2/5 = 6/30\\ P(YB) & = 3/6 \cdot 1/5 = 3/30\\ P(YB) & = 1/6 \cdot 2/5 = 2/30\\ P(YB) & = 1/6 \cdot 3/5 = 3/30\end{align*}
Notice that all the probabilities must add up to \begin{align*}1\end{align*}, as they should.
The method used to solve the example above can be generalized to any number of stages. This method is called the Multiplicative Rule of Counting.
The Multiplicative Rule of Counting
(I) If there are \begin{align*}n\end{align*} possible outcomes for event \begin{align*}A\end{align*} and \begin{align*}m\end{align*} possible outcomes for event \begin{align*}B\end{align*}, then there are a total of \begin{align*}nm\end{align*} possible outcomes for the series of events \begin{align*}A\end{align*} followed by \begin{align*}B\end{align*}.
Another way of stating it:
(II) You have \begin{align*}k\end{align*} sets of elements, \begin{align*}n_1\end{align*} in the first set, \begin{align*}n_2\end{align*} in the second set,..., and \begin{align*}n_k\end{align*} in the \begin{align*}k\end{align*}th set. Suppose you want to take one sample from each of the \begin{align*}k\end{align*} sets. The number of different samples that can be formed is the product
\begin{align*}n_1 n_2 n_3 \ldots n_k\end{align*}
Example:
A restaurant offers a special dinner menu every day. There are three entrées to choose from, five appetizers, and four desserts. A costumer can only select one item from each category. How many different meals can be ordered from the special dinner menu?
Solution:
Let’s summarize what we have.
 Entrees:3
 Appetizer: 5
 Dessert: 4
We use the multiplicative rule above to calculate the number of different dinner meals that can be selected. We simply multiply all the number of choices per item together:
\begin{align*}(3)(5)(4) = 60\end{align*}
There are \begin{align*}60\end{align*} different dinners that can be ordered by the customers.
Example:
Here is a classic example. In how many different ways can you seat \begin{align*}8\end{align*} people at a dinner table?
Solution:
For the first seat, there are eight choices. For the second, there are seven remaining choices, since one person has already been seated. For the third seat, there are \begin{align*}6\end{align*} choices, since two people are already seated. By the time we get to the last seat, there is only one seat left. Therefore, using the multiplicative rule above, we get
\begin{align*}(8)(7)(6)(5)(4)(3)(2)(1) = 40,320\end{align*}
The multiplication pattern above appears so often in statistics that it has its own name and its own symbol. So we say “eight factorial,” and we write \begin{align*}8!\end{align*}.
Factorial Notation
\begin{align*}n! = n(n  1)(n  2) \ldots 1\end{align*}
Example:
Suppose there are \begin{align*}30\end{align*} candidates that are competing for three executive positions. How many different ways can you fill the three positions?
Solution:
This is a more difficult problem than the examples above and we will use the second version of the Multiplicative Rule of Counting. We need to analyze it in the following way:
The executive positions can be denoted by \begin{align*}k = 3\end{align*} sets of elements that correspond to
 \begin{align*}n_1 =\end{align*} The number of candidates that are available to fill the first position
 \begin{align*}n_2 =\end{align*} The number of candidates remaining to fill the second position
 \begin{align*}n_3 =\end{align*} The number of candidates remaining to fill the third position
Hence,
\begin{align*} n_1 = 30\\ n_2 = 29\\ n_3 = 28\end{align*}
The number of different ways to fill the three positions is
\begin{align*}n_1 n_2 n_3 = (30)(29)(28) = 24,360\ \text{possible positions.}\end{align*}
The arrangement of elements in distinct order, as the example above shows, is called the permutation. Thus, from the example above there are \begin{align*}24,360\end{align*} possible permutations of three positions drawn from a set of \begin{align*}30\end{align*} elements.
Counting Rule for Permutations
The number of ways to arrange in order \begin{align*}n\end{align*} different objects within \begin{align*}r\end{align*} positions is
\begin{align*}P^n_r = \frac{n!} {(n r)!}\end{align*}
Example:
Let’s go back to the previous example but this time we want to compute the number of ordered seating arrangements we have for \begin{align*}8\end{align*} people for only \begin{align*}5\end{align*} seats.
Solution:
In this case, we are considering a total of \begin{align*}n = 8\end{align*} people and we wish to arrange \begin{align*}r = 5\end{align*} of these people to be seated. Substituting into the permutation equation,
\begin{align*}P^n_r & = \frac{n!} {(n  r)!} = \frac{8!} {(8 5)!} \\ & = \frac{8!} {3!} \\ & = \frac{40,320} {6} \\ & =6720\end{align*}
Another way of solving this problem is to use the Multiplicative Rule of Counting,
Since there are only \begin{align*}5\end{align*} seats available for \begin{align*}8\end{align*} people, then for the first seat, there are eight people. For the second seat, there are seven remaining people, since one person has already been seated. For the third seat, there are \begin{align*}6\end{align*} people, since two people are already seated. For the fifth seat, there are \begin{align*}4\end{align*} people. After that we run out of seats. Thus
\begin{align*}(8)(7)(6)(5)(4) = 6720.\end{align*}
Of course, the permutation rule is more powerful since it has the advantage of using the factorial. Most scientific calculators can do factorials permutations, so make sure to know how to do them on your calculator.
Example:
The board of directors at The Orion Foundation has \begin{align*}13\end{align*} members. Three officers will be elected from the \begin{align*}13\end{align*} members to hold the positions of a provost, a general director and a treasure. How many different slates of three candidates are there, if each candidate must specify which office he or she wishes to run for?
Solution:
Each slate is a list of one person for each of three positions, the provost, the general director and the treasure. If, for example, Mr. Smith, Mr. Hale, and Ms. Osborn wish to be on a slate together, there are several different slates possible, depending on which one will run for provost, general director and treasurer. So we are not just asking for the number of different groups of three names on a slate but we are also asking for a specific order, since it makes a difference which name is listed in which position.
So,
\begin{align*}n = 13\\ r = 3 \end{align*}
Using the permutation formula,
\begin{align*}P^n_r = \frac{n!} {(n  r)!} = \frac{13!} {(13  3)!} = 1716\end{align*}
There are \begin{align*}1716\end{align*} different slates of officers.
Notice that in our previous examples, the order of people or objects was taken into account. What if the order is not important? For example, in the previous example for electing three officers, what if we wish to choose \begin{align*}3\end{align*} members of the \begin{align*}13\end{align*}member board to attend a convention. Here, we are more interested in the group of three but we are not interested in their order. In other words, we are only concerned with different combinations of \begin{align*}13\end{align*} people taken \begin{align*}3\end{align*} at a time. The permutation rule will not work here since order is not important. We have a new formula that will compute different combinations.
Counting Rule for Combinations
The number of combinations of \begin{align*}n\end{align*} objects taken \begin{align*}r\end{align*} at a time is
\begin{align*}C^n_r = \frac{n!} {r!(n  r)!}\end{align*}
It is important to notice the difference between permutations and combinations. When we consider grouping and order, we use permutations. But when we consider grouping with no particular order, we use combinations.
Example:
Back to our example above. How many different groups of three are there, taken out of \begin{align*}13\end{align*} people?
Solution:
As explained in the previous paragraph, we are interested in combinations rather than permutations of \begin{align*}13\end{align*} people taken \begin{align*}3\end{align*} at a time. We use the combination formula
\begin{align*}C^n_r & = \frac{n!} {r!(n  r)!} \\ C^{13}_3 & = \frac{13!} {3!(13  3)!} = \frac{13!} {3!10!} = 286\end{align*}
There are \begin{align*}286\end{align*} different groups of \begin{align*}3\end{align*} to go to the convention.
In the above computation you can see that the difference between the formulas for \begin{align*}nCr\end{align*} and \begin{align*}nPr\end{align*} is in the factor \begin{align*}r!\end{align*} in the denominator of the fraction. Since \begin{align*}r!\end{align*} is the number of different orders of \begin{align*}r\end{align*} things, and combinations ignore order, then we divide by the number of different orders.
Example:
You are taking a philosophy course that requires you to read \begin{align*}5\end{align*} books out of a list of \begin{align*}10\end{align*} books. You are free to select any five books and read them in whichever order that pleases you. How many different combinations of \begin{align*}5\end{align*} books are available from a list of \begin{align*}10\end{align*}?
Solution:
Since considerations of order in which the books are selected are not important, we compute the number of combinations of \begin{align*}10\end{align*} books taken \begin{align*}5\end{align*} at a time. We use the combination formula
\begin{align*}C^n_r & = \frac{n!} {r!(n  r)!}\\ C^{10}_5 & = \frac{10!} {5!(10  5)!} = 256\end{align*}
There are \begin{align*}252\end{align*} different groups of \begin{align*}5\end{align*} books that can be selected from a list of \begin{align*}10\end{align*} books.
Technology Note
The TI83/84 calculators and the EXCEL spreadsheet have commands for factorials, permutations, and combinations.
Using the TI83/84 Calculators
Press [MATH] and then choose PRB (Probability). You will see the following choices, among others: \begin{align*}nPr, nCr,\end{align*} and ! The screens show the menu and the proper uses of these commands.
Using EXCEL
In Excel the above commands are entered as follows:
 \begin{align*}=\end{align*} PERMUT (10,2)
 \begin{align*}=\end{align*} COMBIN (10,2)
 \begin{align*}=\end{align*} FACT (10)
Lesson Summary
 Inferential Statistics is a method of statistics that consists of drawing conclusions about a population based on information obtained from a subset or sample of the population.
 A random sampling is a procedure in which each sample of a given size is equally likely to be the one selected.
 The Multiplicative Rule of Counting states: if there are \begin{align*}n\end{align*} possible outcomes for event \begin{align*}A\end{align*} and \begin{align*}m\end{align*} possible outcomes for event \begin{align*}B\end{align*}, then there are a total of \begin{align*}nm\end{align*} possible outcomes for the series of events \begin{align*}A\end{align*} followed by \begin{align*}B\end{align*}.
 The factorial, ' ! ', means \begin{align*}n! = n(n  1)(n  2) \ldots 1.\end{align*}
 The number of permutations (ordered arrangements) of \begin{align*}n\end{align*} different objects within \begin{align*}r\end{align*} positions is \begin{align*}P^n_r = \frac{n!} {(n r)!} \end{align*}
 The number of combinations (unordered arrangements) of \begin{align*}n\end{align*} objects taken \begin{align*}r\end{align*} at a time is \begin{align*}C^n_r = \frac{n!} {r!(n  r)!}\end{align*}
Review Questions
 Determine the number of simple events when you toss a coin the following number of times: (Hint: as the numbers get higher, you will need to develop a systematic method of counting all the outcomes)
 Twice
 Three times
 Five times
 Look for a pattern in the results of a) through c) and try to figure out the number of outcomes for tossing a coin \begin{align*}n\end{align*} times.
 Flying into Los Angeles from Washington DC, you can choose one of three airlines and can choose either first class or economy. How many travel options do you have?
 How many different \begin{align*}5\end{align*}card hands can be chosen from a \begin{align*}52\end{align*}card deck?
 Suppose an automobile license plate is designed to show a letter of the English alphabet, followed by a fivedigit number. How many different license plates can be issued?
Review Answers

 \begin{align*}4\end{align*}
 \begin{align*}8\end{align*}
 \begin{align*}32\end{align*}
 \begin{align*}2^n\end{align*}
 \begin{align*}6\end{align*}
 \begin{align*}2,598,960\end{align*}
 \begin{align*}2,600,000\end{align*}