High School
SAT
ACT
University
MCAT
LSAT
DAT
Wize High School Grade 12 Pre-Calculus Textbook > Permutations and Combinations [BC/AB]

Counting Elements

Rates of Change of Logarithmic FunctionsPrevious Section
PermutationsNext Section
Popular Courses
Find My Course
0:00 / 0:00

Fundamental Counting Principle (FCP)

If there are  a ‾\underline{\ a\ } possible choices/outcomes for one thing,  b ‾\underline{\ b\ } possible choices/outcomes for another thing,  c ‾\underline{\ c\ } possible choices/outcomes for another thing..., then there are  a×b×c×... ‾\underline{\ a\times b\times c\times...\ } ways to do all these things.

"Slots" method
Number of possible sequences=      ‾×     ‾×     ‾×...\text{Number of possible sequences}=\ \underline{\ \ \ \ \ }\times\underline{\ \ \ \ \ }\times\underline{\ \ \ \ \ }\times...
Each slot represents a decision, and the number on a slot represents the possible choices for that decision.

Wize Tip
Use this FCP when the question involves a sequence of choices or outcomes!

Often, questions can be solved using this method or using a tree diagram.

Basic example

A sandwich shop has three different types of meat, two types of buns, and three varieties of cheese. If a sandwich must consist of a selection of meat, cheese and a choice of bun, how many different possible sandwhiches are there?
number of meats×number of cheeses×number of buns=3×3×2=18\begin{array}{ccccccc} &\color{red}\text{number of meats}& \color{black}\times& \color{blue}\text{number of cheeses}& \color{black}\times& \color{orange}\text{number of buns}&\\ = &\color{red}3& \color{black}\times& \color{blue}3& \color{black}\times& \color{orange}2&\\ =&18 \end{array}

Strategies

Most questions you face will have some sort of restrictions on some or all of the options

1. You can break the question down into non-overlapping cases • Start with the restrictions that give us the least amount of freedom first • Count the number of possible outcomes for each case • Add up all the cases

2. You can use the complement of a restriction (indirect counting) • Find out the total number of possible outcomes with no restructions • Subtract the number of possible outcomes in the complement (opposite) case
0:00 / 0:00

Example: Fundamental Counting Principle

Assuming a license plate consists of any three letters followed by any three digits.

a. How many such license plates are there if repetition of letters and digits is allowed?
This question involves a sequence of choices for each letter and digit in the license plate, so it's the fundamental counting principle.
Number of license plates\text{Number of license plates}
=1st letter choices×2nd letter choices×3rd letter choices×1st digit choices×2nd digit choies×3rd digit choices=\text{1st letter choices}\times\text{2nd letter choices}\times\text{3rd letter choices}\times\text{1st digit choices}\times\text{2nd digit choies}\times\text{3rd digit choices}
=26×26×26 ×10×10×10=26\times26\times26\ \times10\times10\times10

b. How many such license plates are there if you are not allowed to repeat any of the letters or digits?
Since we're not allowed repetition, once the 1st letter is decided, we will only have 25 letters to choose from for the 2nd letter, so on and so forth.
Number of license plates\text{Number of license plates}
=1st letter choices×2nd letter choices×3rd letter choices×1st digit choices×2nd digit choies×3rd digit choices=\text{1st letter choices}\times\text{2nd letter choices}\times\text{3rd letter choices}\times\text{1st digit choices}\times\text{2nd digit choies}\times\text{3rd digit choices}
=26×25×24 ×10×9×8=26\times25\times24\ \times10\times9\times8


c. How many such license plates are there if the first and second letters must be different vowels (A, E, I, O, or U)?
Number of license plates\text{Number of license plates}
=1st letter×2nd letter×3rd letter×1st digit×2nd digit×3rd digit =\text{1st letter}\times\text{2nd letter}\times\text{3rd letter}\times\text{1st digit}\times\text{2nd digit}\times\text{3rd digit}\
=5×4×26 ×10×10×10=5\times4\times26\ \times10\times10\times10

d. How many such license plates are there if the first and second digits must be the same odd number, and the third digit must be different than the other digits?
Number of license plates\text{Number of license plates}
=1st letter×2nd letter×3rd letter×1st digit×2nd digit×3rd digit =\text{1st letter}\times\text{2nd letter}\times\text{3rd letter}\times\text{1st digit}\times\text{2nd digit}\times\text{3rd digit}\
=26×26×26 ×5×1×9=26\times26\times26\ \times5\times1\times9
0:00 / 0:00

Example: Fundamental Counting Principle

A recreation centre sells student passes, adult passes, family passes and senior passes. The passes come in daily, weekly, monthly and yearly versions. The senior passes are also available in large or small print, all other passes will come in small print. How many different types of passes does the recreation centre offer?

Since this question involves choices, we can use a tree diagram or the fundamental counting principle, let's try the fundamental counting principle.

Depending on the pass type, we have 2 cases -- senior or non-serior passes

Case 1: Senior Pass
number of types of possible passes\text{number of types of possible passes}
= user type × frequency type ×print size=\ \text{user type}\ \times\ \text{frequency type}\ \times \text{print size}
= 1×4×2=\ 1\times 4\times 2
=8=8

Case 2: Non-Senior Pass
number of types of possible passes\text{number of types of possible passes}
= user type × frequency type ×print size=\ \text{user type}\ \times\ \text{frequency type}\ \times \text{print size}
=3×4×1=3\times4\times1
=12=12

Therefore, there are 8+12=20 total possible pass types.
0:00 / 0:00

Example: Fundamental Counting Principle w/ Complements

In how many ways can you give out 10 different stickers to 5 sisters if you can't give all 10 stickers to one sister?

This question involves making a sequence of choices for whom the stickers should go to, let's try the fundamental counting principle.

If you approach this problem as cases it will quickly get out of hand.
For example, the 1st sister can get 1, 2, 3, 4, 5, 6, 7, 8, or 9 stickers, or the 2nd sister can get 1, 2,... Ahhh! Too many cases!

Instead, we can think of the complement: what are we not allowed to do?
Answer: We can't give all 10 stickers to sister 1, or sister 2, or sister 3, or sister 4, or sister 5 → that's 5 things we're not allowed to do, and we're allowed to do anything else!

Number of such ways\text{Number of such ways}
=1st sticker choices×2nd sticker choices×...×10th sticker choices=\text{1st sticker choices}\times\text{2nd sticker choices}\times...\times\text{10th sticker choices}
=5×5×5×...×5=5\times5\times5\times...\times5
=510=5^{10}

Therefore, the number of ways to do this is 510−55^{10}-5
0:00 / 0:00

Tree Diagrams

Tree diagrams is a simple way to represent a sequence of choices (options) or events.

Notes:
  1. Each path represents one single sequence of events/choices
  2. "And", "Both" - Go down a specific path
  3. "Or", "Either", "At least one of" - Add up or count up multiple different paths
  4. The sum (total) at each "stage" must equal the number on the branch before it

Wize Tip
Use a tree diagram when the question involves
  • a sequence of possible outcomes/choices
  • 3 or more sets

0:00 / 0:00

Example: Tree Diagrams

Given the tree diagram below, determine n(Ac∪C)n\left(A^c\cup C\right).

Remember that the sum/total of a group of branches must equal to the branch before it.
n(Ac∪C)=the entire Ac branch + all the C branches that don’t overlap with Acn\left(A^c\cup C\right)=\color{red}\text{the entire}\ A^c\ \text{branch}\ \color{black}+\ \color{blue}\text{all the}\ C\ \text{branches that don't overlap with}\ A^c
n(Ac∪C)=20 + (5+28)n\left(A^c\cup C\right)=\color{red}20\color{black}\ +\ \color{blue}(5+28)
n(Ac∪C)=53n\left(A^c\cup C\right)=53
0:00 / 0:00

Example: Counting Choices w/ Trees

How many ways can you make change for $5.50 if you only have the option of choosing from $2, $1, and $0.25 coins?

Wize Tip
For this type of question, always start with the highest denomination!

Since we have a sequence of choices to make, let's try a tree diagram.

*Note: We only have to draw out the choices for the number of $2 and $1 coins. We don't have to worry about the choices for $0.25 because by the time we decide on the number of $2 and $1 coins, we must use $0.25 coins to make up the difference (there's no choices left!)

The total number of possible ways to make change in this scenario is the total number of branches in the tree diagram.

Therefore, there are 12 ways to make change in this way.
0:00 / 0:00

Example: Counting Elements w/ Trees

In a survey of 82 children, 40 don’t eat apples, 17 eat blueberries but not apples, 10 eat cookies and blueberries but not apples, 3 eat only cookies, 12 eat apples and cookies, 25 eat blueberries, and 16 eat both blueberries and cookies.

a) How many of the children eat exactly two of the food items?
b) How many of the children eat apples or cookies?

Since there are 3 sets - A (apples), B (blueberries), C (cookies), let's try a tree diagram.
*See video solution for more details, but here's the final tree diagram:

a) How many of the children eat exactly two of the food items?
Kids who don't eat apples: 10
Kids who don't eat blueberries: 6
Kids who don't eat cookies: 2
Therefore, 10+6+2=18 kids eat exactly two of the food items.

c) How many of the children eat apples or cookies?
Kids who eat apples: 42
Kids who eat cookies: 6+6+10+3=25
Kids who eat both apples and cookies: 6+6=12
Therefore, the number of kids who eat apples or cookies (or both) is 42+25-12=55
*Or you can count all the branches that involve apples or cookies: 6+2+6+28+10+3=55

Practice: Fundamental Counting Principle

Josh is creating a poster with the word "BORDERLANDS" on it, and can paint each letter red, yellow, or blue. How many different posters are there?

Practice: Fundamental Counting Principle w/ Cases

Considering all possible 4-digit even numbers.

a) How many of these are greater than 5999?
b) How many of these are greater than 5999 if none of the 4 digits can repeat?
a) How many of these are greater than 5999?

Practice: Counting Outcomes w/ Trees

Adam and Ben are playing a few games of rock-paper-scissors. The outcome for each game can be a win for Adam, a win for Ben, or a tie if the players choose to play the same hand gesture.






Practice: Counting Elements w/ Trees

In a survey, 22 adults have siblings and 19 watch comedy shows. Exactly 5 have siblings, watch comedy shows and eat popcorn. 13 have siblings and watch comedy shows and exactly 8 have siblings but don’t eat popcorn. 9 of those watching comedy shows don’t eat popcorn and 6 have no siblings and don’t watch any comedy shows. 4 of people in the survey have no siblings, don’t watch comedy shows and also don’t eat popcorn.