<meta http-equiv="refresh" content="1; url=/nojavascript/"> Basic Counting Rules | CK-12 Foundation
You are reading an older version of this FlexBook® textbook: CK-12 Probability and Statistics - Advanced (Second Edition) Go to the latest version.

3.6: Basic Counting Rules

Created by: CK-12
0  0  0

Learning Objectives

• Understand the definition of simple random sample.
• Calculate ordered arrangements using factorials.
• Calculate combinations and permutations.
• Calculate probabilities with factorials.

Introduction

Inferential Statistics is a method of statistics that consists of drawing conclusions about a population based on information obtained from samples. Samples are used because it can be quite costly in time and money to study an entire population. In addition, because of the inability to actually reach everyone in a census, a sample can be more accurate than a census.

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. Likewise, it would not be reasonable to estimate the average income of the entire state of California by sampling the average income of the wealthy residents of Beverly Hills. The goal of sampling is to obtain a representative sample. There are a number of different methods for taking representative samples, and in this lesson, you will learn about simple random samples. You will also be presented with the various counting rules used to calculate probabilities.

Simple Random Sample

A simple random sample of size $n$ is one in which all samples of size $n$ are equally likely to be selected. In other words, if $n$ elements are selected from a population in such a way that every set of $n$ elements in the population has an equal probability of being selected, then the $n$ elements form a simple random sample.

Example: Suppose you randomly select 4 cards from an ordinary deck of 52 playing cards, and all the cards selected are kings. Would you conclude that the deck is still an ordinary deck, or would you conclude that the deck is not an ordinary one and probably contains more than 4 kings?

The answer depends on how the cards were drawn. It is possible that the 4 kings were intentionally put on top of the deck, and hence, the drawing of the 4 kings was not unusual, and in fact, it was actually certain. However, if the deck was shuffled well, getting 4 kings is highly improbable.

Example: Suppose a lottery consists of 100 tickets, and one winning ticket is to be chosen. What would be a fair method of selecting a winning ticket?

First, we must require that each ticket has an equal chance of winning. That is, each ticket must have a probability of $\frac{1}{100}$ of being selected. One fair way of doing this is to mix up all the tickets in a container and blindly pick 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, such as, say, a million tickets, and we were asked to select 5 winning tickets. One method of picking a simple random sample is to give each element in the population a number. Then use a random number generator to pick 5 numbers. The people who were assigned one of the five numbers would then be the winners.

Some experiments have so many simple events that it is impractical to list them all. Tree diagrams are helpful in determining probabilities in these situations.

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 then set it aside. Next, we will draw another ball and record its color. With the aid of a tree diagram, calculate the probability of each of the possible outcomes of the experiment.

We first draw a tree diagram to aid us in seeing all the possible outcomes of this experiment.

The tree diagram shows us the two stages of drawing two balls without putting the first one back into the box. In the first stage, we pick a ball blindly. Since there are 2 red balls, 3 blue balls, and 1 yellow ball, the probability of getting a red ball is $\frac{2}{6}$, the probability of getting a blue ball is $\frac{3}{6}$, and the probability of getting a yellow ball is $\frac{1}{6}$.

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 when selecting the second ball, we can look back at the tree diagram.

When taking the first ball and the second ball into account, there are eight possible outcomes for the experiment:

$RR$: red on the $1^{\text{st}}$ and red on the $2^{\text{nd}}$

$RB$: red on the $1^{\text{st}}$ and blue on the $2^{\text{nd}}$

$RY$: red on the $1^{\text{st}}$ and yellow on the $2^{\text{nd}}$

$BR$: blue on the $1^{\text{st}}$ and red on the $2^{\text{nd}}$

$BB$: blue on the $1^{\text{st}}$ and blue on the $2^{\text{nd}}$

$BY$: blue on the $1^{\text{st}}$ and yellow on the $2^{\text{nd}}$

$YR$: yellow on the $1^{\text{st}}$ and red on the $2^{\text{nd}}$

$YB$: yellow on the $1^{\text{st}}$ and blue on the $2^{\text{nd}}$

We want to calculate the probability of each of these outcomes. This is done as is shown below.

$P(RR) & = \frac{2}{6} \bullet \frac{1}{5}=\frac{2}{30}\\P(RB) & = \frac{2}{6} \bullet \frac{3}{5}=\frac{6}{30}\\P(RY) & = \frac{2}{6} \bullet \frac{1}{5}=\frac{2}{30}\\P(BR) & = \frac{3}{6} \bullet \frac{2}{5}=\frac{6}{30}\\P(YB) & = \frac{3}{6} \bullet \frac{2}{5}=\frac{6}{30}\\ P(YB) & = \frac{3}{6} \bullet \frac{1}{5}=\frac{3}{30}\\P(YB) & = \frac{1}{6} \bullet \frac{2}{5}=\frac{2}{30}\\P(YB) & = \frac{1}{6} \bullet \frac{3}{5}=\frac{3}{30}$

Notice that all of the probabilities add up to 1, as they should.

When using a tree diagram to compute probabilities, you multiply the probabilities as you move along a branch. In the above example, if we are interested in the outcome $RR$, we note that the probability of picking a red ball on the first draw is $\frac{2}{6}$. We then go to the second branch, choosing a red ball on the second draw, the probability of which is $\frac{1}{5}$. Therefore, the probability of choosing $RR$ is $\left (\frac{2}{6}\right )\left (\frac{1}{5}\right )$. The method used to solve the example above can be generalized to any number of stages.

Example: A restaurant offers a special dinner menu every day. There are three entrées, five appetizers, and four desserts to choose from. A customer can only select one item from each category. How many different meals can be ordered from the special dinner menu?

Let’s summarize what we have.

Entrees: 3

Appetizer: 5

Dessert: 4

We use the Multiplicative Rule above to calculate the number of different dinners that can be selected. We simply multiply each of the numbers of choices per item together: $(3)(5)(4) = 60$. Thus, there are 60 different dinners that can be ordered by the customers.

The Multiplicative Rule of Counting

The Multiplicative Rule of Counting states the following:

(I) If there are $n$ possible outcomes for event $A$ and $m$ possible outcomes for event $B$, then there are a total of $nm$ possible outcomes for event $A$ followed by event $B$.

Another way of stating this is as follows:

(II) Suppose you have $k$ sets of elements, with $n_1$ elements in the first set, $n_2$ elements in the second set, and $n_k$ elements in the $k^{\text{th}}$ set, and you want to take one sample from each of the $k$ sets. The number of different samples that can be formed is the product $n_1n_2n_3\ldots. n_k$.

Example: In how many different ways can you seat 8 people at a dinner table?

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 6 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 $(8)(7)(6)(5)(4)(3)(2)(1) = 40, 320$.

The multiplication pattern above appears so often in statistics that it has its own name, which is factorial, and its own symbol, which is '!'. When describing it, we say, “Eight factorial,” and we write, "8!."

Factorial Notation

$n!=n(n-1)(n-2)(n-3).....(3)(2)(1)$

Example: Suppose there are 30 candidates that are competing for three executive positions. How many different ways can you fill the three positions?

Since there are three executive positions and 30 candidates, let $n_1 =$ the number of candidates that are available to fill the first position, $n_2 =$ the number of candidates remaining to fill the second position, and $n_3 =$ the number of candidates remaining to fill the third position.

Hence, we have the following:

$n_1& =30\\n_2& =29\\n_3& =28$

The number of different ways to fill the three executive positions with the given candidates is $(n_1)(n_2)(n_3)=(30)(29)(28)=34,360$.

The arrangement of elements in a distinct order, as the example above shows, is called a permutation. Thus, from the example above, there are 24,360 possible permutations of three elements drawn from a set of 30 elements.

Counting Rule for Permutations

The Counting Rule for Permutations states the following:

The number of ways to arrange $n$ different objects in order within $r$ positions is $P^n_r=\frac{n!}{(n-r)!}$.

Example: Let’s compute the number of ordered seating arrangements we have with 8 people and only 5 seats.

In this case, we are considering a total of $n=8$ people, and we wish to arrange $r=5$ of these people to be seated. Substituting into the permutation equation, we get the following:

$P^n_r& =\frac{n!}{(n-r)!}\\& =\frac{8!}{(8-5)!}\\& =\frac{8!}{3!}\\& =\frac{40,320}{6}\\& =6,720$

Another way of solving this problem is to use the Multiplicative Rule of Counting. Since there are only 5 seats available for 8 people, for the first seat, there are 8 people available. For the second seat, there are 7 remaining people available, since one person has already been seated. For the third seat, there are 6 people available, since two people have already been seated. For the fourth seat, there are 5 people available, and for the fifth seat, there are 4 people available. After that, we run out of seats. Thus, $(8)(7)(6)(5)(4) = 6,720$.

Example: The board of directors at The Orion Foundation has 13 members. Three officers will be elected from the 13 members to hold the positions of a provost, a general director, and a treasurer. How many different slates of three candidates are there if each candidate must specify which office he or she wishes to run for?

Each slate is a list of one person for each of three positions: the provost, the general director, and the treasurer. If, for example, Mr. Smith, Mr. Hale, and Ms. Osborn wish to be on the slate together, there are several different slates possible, depending on which one will run for provost, which one will run for general director, and which one will run for treasurer. This means that we are not just asking for the number of different groups of three names on the slate, but we are also asking for a specific order, since it makes a difference which name is listed in which position.

When computing the answer, $n = 13$ and $r = 3$.

Using the permutation formula, we get the following:

$P^n_r& =\frac{n!}{(n-r)!}\\& =\frac{13!}{(13-3)!}\\& =\frac{(13)(12)(11)(10!)}{10!}\\& =(13)(12)(11)\\& =1,716$

Thus, there are 1,716 different slates of officers possible.

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 3 members of the 13 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 13 people taken 3 at a time. The permutation formula will not work here, since, in this situation, order is not important. However, we have a new formula that will compute different combinations.

Counting Rule for Combinations

The Counting Rule for Combinations states the following:

The number of combinations of $n$ objects taken $r$ at a time is $C^n_r=\frac{n!}{r!(n-r)!}$.

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: How many different groups of 3 are possible when taken out of 13 people?

Here, we are interested in combinations of 13 people taken 3 at a time. To find the answer, we can use the combination formula: $C^n_r=\frac{n!}{r!(n-r)!}.$

$C^{13}_3=\frac{13!}{3!(13-3)!} = 286$

This means that there are 286 different groups of 3 people to go to the convention.

In the above computation, you can see that the difference between the formulas for $_nC_r$ and $_nP_r$ is the factor $r!$ in the denominator of the fraction. Since $r!$ is the number of different orders of $r$ objects, and combinations ignore order, we divide by the number of different orders.

Example: You are taking a philosophy course that requires you to read 5 books out of a list of 10 books. You are free to select any 5 books and read them in whichever order that pleases you. How many different combinations of 5 books are available from a list of 10?

Since consideration of the order in which the books are selected is not important, we compute the number of combinations of 10 books taken 5 at a time. We use the combination formula as is shown below:

$C^n_r & = \frac{n!}{r!(n-r)!}\\C^{10}_5 & =\frac{10!}{5!(10-5)!} = 252$

This means that there are 252 different groups of 5 books that can be selected from a list of 10 books.

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 selected.

The Multiplicative Rule of Counting states that if there are $n$ possible outcomes for event $A$ and $m$ possible outcomes for event $B$, then there are a total of $nm$ possible outcomes for the series of events $A$ followed by $B$.

The factorial sign, or ‘!’, is defined as $n!=n(n-1)(n-2)(n-3).....(3)(2)(1)$.

The number of permutations (ordered arrangements) of $n$ different objects within $r$ positions is $P^n_r=\frac{n!}{(n-r)!}$.

The number of combinations (unordered arrangements) of $n$ objects taken $r$ at a time is $C^n_r=\frac{n!}{r!(n-r)!}$.

Review Questions

1. 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.)
1. Twice
2. Three times
3. Five times
4. $n$ times (Look for a pattern in the results of a) through c).)
2. Flying into Los Angeles from Washington DC, you can choose one of three airlines and can also choose either first class or economy. How many travel options do you have?
3. How many different 5-card hands can be chosen from a 52-card deck?
4. Suppose an automobile license plate is designed to show a letter of the English alphabet, followed by a five-digit number. How many different license plates can be issued?

Technology Note: Generating Random Numbers on the TI-83/84 Calculator

Press [MATH], and then scroll to the right and choose PRB. Next, choose '1:rand' and press [ENTER] twice. The calculator returns a random number between 0 and 1. If you are taking a sample of 100, you need to use the first three digits of the random number that has been returned. If the number is out of range (that is, if the first three digits of the number form a number that is greater than 100), press [ENTER] again, and the calculator will return another random number. Similarly, if a the calculator returns the same first three digits more than once, you can ignore them and press [ENTER] again.

Technology Note: Computing Factorials, Permutations and Combination on the TI-83/84 Calculator

Press [MATH], and then scroll to the right and choose PRB. You will see the following choices, among others: '2:nPr', '3:nCr'. and '4:!'. The screenshots below show the menu and the proper uses of these commands.

Technology Note: Using EXCEL to Computer Factorials, Permutations and Combinations

In Excel, the commands shown above are entered as follows:

$=$PERMUT(10,2)

$=$COMBIN(10,2)

$=$FACT(10)

Keywords

The Additive Rule of Probability states that the union of two events can be found by adding the probabilities of each event and subtracting the intersection of the two events, $P(A \cup B)=P(A) + P(B) - P(A \cap B)$
Classical probability
Classical probability is defined to be the ratio of the number of cases favorable to an event to the number of all outcomes possible, where each of the outcomes is equally likely.

$P(A)=\frac{\text{The number of outcomes for} \ A \ \text{to occur}}{\text{The size of the sample space}}$

Combinations
A combination is selection of objects without regard to order.
Complement
The complement $A'$ of the event $A$ consists of all elements of the sample space that are not in $A$.
Complement Rule
The Complement Rule states that the sum of the probabilities of an event and its complement must equal 1. $P(A)+P(A')=1$
Compound event
we need to combine two or more events into one compound event. This compound event can be formed in two ways.
Conditional probability
If A and B are two events, then the probability of event A occurring, given that event B has occurred, is called conditional probability.
Counting Rule for Combinations
The number of combinations of $n$ objects taken $r$ at a time is $C^n_r=\frac{n!}{r!(n-r)!}$.
Counting Rule for Permutations
The number of ways to arrange $n$ different objects in order within $r$ positions is $P^n_r=\frac{n!}{(n-r)!}$.
Event
An event is something that occurs, or happens, with one or more possible outcomes.
Experiment
An experiment is the any physical action or procedure that is observed and the outcome noted
Factorial
The factorial sign, or ‘!’, is defined as $n!=n(n-1)(n-2)(n-3).....(3)(2)(1)$.
Independent events
Two events are considered independent if the occurrence or nonoccurrence of one event has no influence on the occurrence or nonoccurrence of the other event.
Intersection of events
The intersection of events $A$ and $B$ occurs if both event $A$ and event $B$ occur in a single performance of an experiment.
Multiplicative Rule of Counting
If there are $n$ possible outcomes for event $A$ and $m$ possible outcomes for event $B$, then there are a total of $nm$ possible outcomes for event $A$ followed by event $B$.
Multiplicative Rule of Probability
$P(A \cap B) = P(A|B) \bullet P(B)$
Mutually exclusive
if there is not overlap between the two sets, we say that $A$ and $B$ are mutually exclusive.
Natural frequencies approach
Another way to determine a conditional probability is to use the natural frequencies approach.
Permutation
A Permutation is an arrangement of objects in a definite order
Sample space
The sample space is the set of all possible outcomes of an experiment, or the collection of all the possible simple events of an experiment.
Simple events
An event that has exactly one outcome.
Simple random sample
A simple random sample of size $n$ is one in which all samples of size $n$ are equally likely to be selected.
Tree diagram
Tree diagrams are useful for showing all the possible outcomes when there is a series of events.
Union of events
The union of events $A$ and $B$ occurs if either event $A$, event $B$, or both occur in a single performance of an experiment.
Venn diagram
are diagrams that show all possible logical relations between a finite collection of sets.

Feb 23, 2012

Aug 21, 2014