Topic:Counting Rules for Probabilities

From SharedExperienceProject

Contents 1 Topic Highlights 2 Introduction and Motivation 3 Learning Activities 4 Learning Objectives 5 Lecture Notes: The Basics of Counting Outcomes 5.1 What's the deal? 5.2 Filling slots 5.2.1 Example 1 5.2.2 Example 2 5.2.3 Example 3 5.2.4 General equation for filling slots 5.2.5 Example 4 5.2.6 Example 5 5.3 Permutations 5.3.1 Example 6 5.3.2 General equation for permutations 5.3.3 Example 7 5.4 Combinations 5.4.1 Example 8 5.4.2 General equation for combinations 5.4.3 Example 9 5.5 Note 6 Lecture Notes: Getting Them Straight 6.1 How do I know which to use? 7 Lecture Notes: Using the Calculator 7.1 Permutations 7.2 Combinations 7.3 Factorials 8 Practice Problems 8.1 Practice Problem 1 8.2 Practice Problem 2 8.3 Practice Problem 3 8.4 Practice Problem 4 8.5 Other Practice Problems

Topic Highlights

(What you will learn)

• In this topic, you will learn about the three basic methods for determining the number of outcomes an experiment may have:
  
  • Filling slots
    
  • Permutations
    
  • Combinations
    
• You will also learn about the types of problems of this type that you may encounter
  

Introduction and Motivation

(Why learn it)

Throughout our whole discussion of probabilities, in Introduction to Probability and More on Probability, we assumed that we could determine the number of outcomes an experiment has. (In fact, we depended on it because of defining the probability of an event to be the ratio of the number of outcomes corresponding to the event and the total number of outcomes.)

In reality, it's not always easy to determine the number of outcomes an experiment may have. That is the goal of this topic.

Learning Activities

(How the levels of understanding will be gained)

Learning activities for this topic

Type	Name	Direction
Reading	Note: This topic is not found in Bowerman et al. Sections 4.7 of Kvanli et al.	Self-directed
In-class discussion	The Basics of Counting Outcomes (below on this page) Getting Them Straight (also below)	Instructor-directed
Practice problems	Practice Problems (below)	Self-directed
Personal activities	Reflection and review of the learning objectives	Self-directed

Learning Objectives

(Levels of understanding to be gained)

Learning objectives for this topic

Level of Understanding	Objective(s)
Very best	Can I solve Practice Problem 4?
Highly satisfactory	Can I solve Practice Problem 2 and Practice Problem 3?
Satisfactory	Can I solve Practice Problem 1? Am I familiar with the equations we used in this topic? Are they on my formula sheet? Do I know when to use each of the three counting methods, i.e. as described below under Getting Them Straight?
Maybe just enough to pass	Can I work through the examples given in the lecture: Example 1, Example 2, Example 3, Example 4, Example 5, Example 6, Example 7, Example 8, and Example 9? Do I understand the differences between the three counting methods: filling slots, permutations and combinations? Do I know how to use my calculator to compute permutations, combinations and factorials (see Using the Calculator below)?

 

Lecture Notes: The Basics of Counting Outcomes

These notes are intended to facilitate a discussion of the basics of counting outcomes.

What's the deal?

Do you remember when we first looked at probabilities (in the topic Introduction to Probability)? There, we defined the basic equation for a probability as follows:

where n is the total number of possible outcomes and m is the number of times the event of interest occurs.

Well, this topic on counting is all about determining n for cases where there is a finite number of outcomes.

There are three main ways of doing this:

1. Through filling slots
2. Through permutations
3. Through combinations

You need to know what these are, how to use them, and when to use each.

Let's take a look at them, each in turn.

Filling slots

Filling slots is just a term used to refer to the simplest counting case, where we know the number of outcomes of a series of events and we want the total number of outcomes when taken together. Let's build on some familiar examples.

Example 1

Recall our example of rolling a 4-sided dice. What are the possible outcomes?

Solution
1, 2, 3 and 4

Example 2

What are the possible outcomes if we roll two 4-sided dice? How many are there?

Solution
The sample space = possible outcomes: (1,1), (1,2), (1,3), (1,4) (2,1), (2,2), (2,3), (2,4) (3,1), (3,2), (3,3), (3,4) (4,1), (4,2), (4,3), (4,4) So, there are 16 outcomes

Example 3

Now, what if roll one 4-sided dice and one 6-sided dice?

Solution
The sample space = possible outcomes: (1,1), (1,2), (1,3), (1,4), (1,5), (1,6) (2,1), (2,2), (2,3), (2,4), (2,5), (2,6) (3,1), (3,2), (3,3), (3,4), (3,5), (3,6) (4,1), (4,2), (4,3), (4,4), (4,5), (4,6) So, there are 24 outcomes

General equation for filling slots

Are you seeing a pattern in the last few examples? You should be.

The general rule is that for k groups of possible outcomes:

total number of outcomes = n1 • n2 • ... • nk

where n₁ is the number of outcomes for the first group, n₂ is the number for the second group, and n_k is the number for the last (k^th) group.

In other words, you just take the product of the number of outcomes for all the groups.

It should make sense to you that the order of the groups does not matter here.

Example 4

If you roll four 4-sided dice and two 6-sided dice, what is the total number of possible outcomes?

Solution
Using the equation, you would write: n1 = n2 = n3 = n4 = 4 n5 = n6 = 6 So, total number of outcomes = 4 x 4 x 4 x 4 x 6 x 6 = 9216 There are 9216 possible outcomes from rolling the 6 dice - imagine figuring those out by hand!

Example 5

You are the supplier of Calgary Flames hats to the Saddledome's retail stores. They have asked you to supply 4 different sizes, 3 different logos and 2 different color schemes. How many different variations of hats do you need to be able to produce?

Solution
total number of outcomes = 4 • 3 • 2 = 24

Permutations

The above examples apply when you want to fill all slots and when the order does matter.

But what if the order does matter and the number of outcomes in each group depends on the previous outcome?

Let's look at an example.

Example 6

Imagine you have to elect students from your 30 person class to 3 positions: President, Vice-President and Water Boy. How many ways could you do this?

Solution
Because the same person cannot have two positions: There are 30 people (possible outcomes) available for the first position, n1 = 30 Once you fill the first position though, there will be one fewer, so n2 = 29 And when you get to the third, n3 = 28 So, total number of outcomes = 30 • 29 • 28 = 24360

This is what we refer to as computing the number of permutations.

General equation for permutations

As in the above example, permutations are usually computed by re-sampling the same group (rather than sampling different groups together as we did above).

A general equation for the is:

total number of outcomes = nPk = n • (n-1) • (n-2) • ... • (n-k+1)

where n is the number of outcomes in the original group and k is the number of experiments (or number of time we sample the group).

Can you use the equation to repeat Example 6?

Solution
We are given: k = 3 n = 30 From which we also get: n-1 = 29 n-k+1 = n=3+1 = n-2 = 28 So: total number of outcomes = nPk = 30 x 29 x 28

Example 7

Imagine that you and three friends go go-carting. The four of you race for the top three spots: 1^st, 2^nd and 3^rd.

a) What are the different ways can you place in these positions? Refer to each driver as

b) How many ways are there?

Solution

a) Let's refer to each driver as A, B, C and D. Because order does matter in this case, the possible outcomes (ways you could place 1st, 2nd and 3rd) are: (A B C) (A B D) (A C B) (A C D) (A D B) (A D C) (B A C) (B A D) (B C A) (B C D) (B D A) (B D C) (C A B) (C A D) (C B A) (C B D) (C D A) (C D B) (D A B) (D A C) (D B A) (D B C) (D C A) (D C B) b) You can create and then count the above list, or to save yourself a ton of time, you can compute it as follows: nPk = 4 x 3 x 2 = 24

Combinations

Example 7 assumes that the order of the outcomes matters (which it does, by nature of placing in a race). But what if the order didn't matter?

Example 8

While you and your friends are go-carting, one of your mothers wants to take pictures of you (so not cool), but can only fit three in the picture. How many groups of three can you form for the photos, assuming that the order in which you stand does not matter?

Solution

You should recognize that the number of outcomes is less than it was in Example 7. For example, (A B C) is the same as (A C B), (B A C), (B C A), (C A B) and (C B A) If you count the number of different outcomes where order does not matter, you'll find there are only 4: A photo with A and B and C (in any order) A photo with A and B and D (in any order) A photo with A and C and D (in any order) A photo with B and C and D (in any order)

General equation for combinations

Can we generalize the conclusion reached in Example 8? Actually, we can actually. When order does not matter, the number of outcomes is smaller than the number of outcomes when order does matter, by a factor that depends on the number of samples we are taking, k.

This factor is:

k • (k-1) • (k-2) • ... • 1

which we refer to as k factorial, or k!.

(So, when you see the symbol k! you should just remember that it is:

k! = k • (k-1) • (k-2) • ... • 1)

And the general equation for combinations is:

total number of outcomes = nCk = nPk / k!

Example 9

Let's make this more concrete by computing the number of possible outcomes for Example 8. Remember n = 4 (you make up four friends), and k = 3 (there are three people per group).

Solution
Let's compute k!: k = 3 (k-1) = 2 (k-2) = 1 So: k! = 3 x 2 x 1 = 6 Then, using the above equations: nPk = n • (n-1) • (n-2) • ... • (n-k+1) = 4 x 3 x 2 = 24 (recall Example 7) nCk = nPk / k! = 24/6 = 4 Which is the same answer we arrived at in Example 8

Note

In Kvanli et al., other forms are given of the equations for _nP_k and _nC_k. These are standard in statistics, and they are equivalent to the ones given here. It's up to you which you use and write on your equation sheet.

Lecture Notes: Getting Them Straight

How do I know which to use?

The following table summarizes some of the salient points for answering this question:

Getting it straight

Type	Logic	Does order matter?	Examples
Permutations	Usually sampling from one same group repeatedly to come up with the total number of outcomes There is one less possible outcome each time you sample	yes	placing 1st, 2nd, 3rd in a race placing in fixed positions in an election choosing 2 specified videos from among the 400 that Blockbuster carries finishing 1st and 2nd in your class, assuming no ties flipping two coins, where order matters
Filling slots	Usually sampling from different groups to come up with the number of outcomes Like a permutation, except that the number of outcomes does not reduce each time	no	flipping 2 coins where output does not matter rolling 2 or more dice
Combinations	Like a permutation, except that the order does not matter	no	selecting groups of 3 from the class selecting a team of deleguates to go to a conference forming a 6-person committee from 100 people on your floor

Lecture Notes: Using the Calculator

This section outlines the steps for using your BA II Plus calculator to compute permutations, combinations and factorials.

Permutations

For example, to compute ₈P₃:

Press 8

Press [2nd]

Press [nPr]

Press 3

Press [=]

Combinations

For example, to compute ₅₂C₅:

Press 52

Press [2nd]

Press [nCr]

Press 5

Press [=]

Factorials

For example, to compute 5!:

Press 5

Press [2nd]

Press [x!]

Practice Problems

We've covered the basics, now build your skills with the following problems. Don't look at the solutions until you've worked the problem through.

Practice Problem 1

Calculate the following:

a) 5!

b) ₃P₂

c) ₇P₆

d) ₅C₃

e) ₁₀C₈

Solution
a) 120 b) 6 c) 5040 d) 10 e) 45

Practice Problem 2

Answer the following questions assuming there is a pool of 10 applicants for a job:

a) What is the number of ways of selecting two applicants from the pool of applicants?

b) What is the number of ways of ranking the applicants?

c) What is the number of permutations of four applicants from this pool of applicants?

Solution
a) 10C2 = 10!/(2!8!) = 45 b) 10! = 3,628,800 c) 10P4 = 10!/6! = 5040

Practice Problem 3

Identify whether it is a permutation or a combination that needs to be calculated in each of the following statements:

a) The number of ways 1st, 2nd and 3rd place can be selected by a judge in an art contest

b) The number of ways 3 cities can be selected from a group of cities used to test a new product

c) The number of ways of selecting 5 managers from the list of managers in a company to attend a conference being held in Hawaii

d) The number of ways of ordering 4 different pairs of shoes in a display window

Solution
a) permutations b) combinations c) combinations d) permutations

Practice Problem 4

A couple is getting married and registers for gifts at Linens and Things. She chooses 7 gifts that would appeal to females. He chooses 4 gifts that would appeal to males. If 3 people have bought gifts after a week, how many combinations are possible if 1 friend of the couple has purchased one of the gifts that appeals to males and 2 friends have each purchased a gift that appeals to females?

Solution

This one's a bit tricky because you need to recognize that it is two problems in one: The combinations coming from the male gift: 4C1 The combinations coming form the female gift: 7C2 After that it's easy The first one is computed as: n = 4, k = 1 (n-k+1) = 4, so 4P1 = 4 k! = 1 So, 4C1 = 4 / 1 = 4 which makes sense, since there are only four gifts for the one person to choose from The second one is computed as: n = 7, k = 2 (n-k+1) = 7-2+1 = 6, so 7P2 = 7 x 6 = 42 k! = 2 x 1 = 2 So, 7C2 = 42 / 2 = 21 Further, you need to recognize that the total number of possible outcomes is the product of both: total number of outcomes = 21 x 4 = 84

Other Practice Problems

See also: Additional problems - Counting and Discrete Random Variables