Counting Principles
By the end of this lesson, you’ll be able to:
- Use the Fundamental Counting Principle to count possible outcomes.
- Use factorial notation in counting problems.
- Distinguish between situations where order matters and where it does not.
- Calculate permutations and combinations.
- Determine how repetition affects the number of possible outcomes.
- Apply counting methods to probability problems.
Key Ideas
Counting methods help determine the number of possible outcomes without listing every possibility.
Three important tools are:
- the Fundamental Counting Principle
- permutations
- combinations
The first question to ask is often:
Does order matter?
Fundamental Counting Principle
If one step has \(m\) possible choices and another step has \(n\) possible choices, then the total number of possible outcomes is:
\[ \boxed{m\cdot n} \]
More generally, multiply the number of choices available at each step.
For example, suppose you have:
- 3 shirts
- 2 pairs of pants
Each shirt can be paired with either pair of pants.
Therefore:
\[ 3\cdot2 = \boxed{6\text{ outfits}} \]
The same idea extends to more than two steps.
If there are \(a\) choices for the first step, \(b\) choices for the second, and \(c\) choices for the third:
\[ \boxed{a\cdot b\cdot c} \]
gives the total number of possible outcomes.
Repetition Allowed vs. Not Allowed
The number of choices available at each step may stay the same or decrease.
Suppose a 3-digit code uses the digits 1 through 5.
Repetition Allowed
Each position has 5 choices:
\[ 5\cdot5\cdot5 = 5^3 = \boxed{125} \]
No Repetition
After using one digit, there is one fewer choice for the next position:
\[ 5\cdot4\cdot3 = \boxed{60} \]
Always check whether an item can be used more than once.
Factorials
A factorial represents the product of all positive integers from a number down to 1.
For example:
\[ 5! = 5\cdot4\cdot3\cdot2\cdot1 = \boxed{120} \]
Similarly:
\[ 3! = 3\cdot2\cdot1 = 6 \]
By definition:
\[ 0!=1 \]
Factorials are especially useful when counting arrangements.
Permutations: Order Matters
A permutation is an arrangement in which order matters.
For example, suppose three runners—Ana, Ben, and Carlos—finish a race.
The outcome:
\[ \text{Ana, Ben, Carlos} \]
is different from:
\[ \text{Ben, Ana, Carlos} \]
because the finishing order changed.
If all \(n\) objects are arranged:
\[ \boxed{n!} \]
possible arrangements exist.
If you arrange only \(r\) objects chosen from \(n\) objects:
\[ \boxed{ P(n,r) = \frac{n!}{(n-r)!} } \]
This may also be written:
\[ {}_nP_r \]
Example: Arrange All Objects
How many ways can 4 students stand in a line?
There are:
- 4 choices for the first position
- 3 choices for the second
- 2 choices for the third
- 1 choice for the fourth
Therefore:
\[ 4\cdot3\cdot2\cdot1 = 4! = \boxed{24} \]
Example: Arrange Some Objects
Eight runners compete in a race.
How many different ways can first, second, and third place be awarded?
Order matters because:
\[ \text{1st, 2nd, 3rd} \]
are different positions.
Use a permutation:
\[ P(8,3) = \frac{8!}{(8-3)!} \]
\[ P(8,3) = \frac{8!}{5!} \]
Cancel \(5!\):
\[ P(8,3) = 8\cdot7\cdot6 = \boxed{336} \]
Combinations: Order Does Not Matter
A combination is a selection in which order does not matter.
Suppose you choose Alice and Bob for a committee.
Choosing:
\[ \text{Alice, Bob} \]
is the same group as choosing:
\[ \text{Bob, Alice} \]
We should count that group only once.
The number of ways to choose \(r\) objects from \(n\) objects is:
\[ \boxed{ C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} } \]
Example: Choose a Team
How many ways can 4 students be chosen from a group of 10?
The order in which the students are selected does not matter.
Use a combination:
\[ \binom{10}{4} = \frac{10!}{4!6!} \]
Expand only what is needed:
\[ \binom{10}{4} = \frac{10\cdot9\cdot8\cdot7}{4\cdot3\cdot2\cdot1} \]
Therefore:
\[ \binom{10}{4} = \boxed{210} \]
Permutation or Combination?
A useful test is:
Would changing the order create a different outcome?
If yes → permutation.
If no → combination.
Consider choosing 3 students from 10.
If the students are being assigned:
- president
- vice president
- secretary
then order matters because the positions are different.
Use:
\[ P(10,3) \]
If the same 3 students are simply forming a committee with no assigned roles, order does not matter.
Use:
\[ \binom{10}{3} \]
Think about what the final outcome represents.
Different positions or rankings → order matters → permutation.
A group with identical roles → order does not matter → combination.
Common Problem Types
1. Sequential Choices
Multiply the number of choices at each step.
Example:
A restaurant offers:
- 4 main dishes
- 3 side dishes
- 2 drinks
Choosing one of each gives:
\[ 4\cdot3\cdot2 = \boxed{24} \]
possible meals.
2. Codes With Repetition
If repetition is allowed, the same number of choices may be available at every position.
Example:
How many 4-digit PINs are possible using digits 0 through 9 if digits may repeat?
Each position has 10 choices:
\[ 10\cdot10\cdot10\cdot10 = 10^4 = \boxed{10{,}000} \]
Because this is a PIN rather than a four-digit number, a leading zero is allowed.
3. Codes Without Repetition
If repetition is not allowed, the number of available choices decreases.
Example:
How many 3-digit codes can be created using the digits 1 through 5 without repetition?
There are:
- 5 choices for the first digit
- 4 choices for the second
- 3 choices for the third
Therefore:
\[ 5\cdot4\cdot3 = \boxed{60} \]
4. Arrangements
When objects are arranged into positions, order matters.
Example:
How many ways can 5 books be arranged on a shelf?
\[ 5! = 5\cdot4\cdot3\cdot2\cdot1 = \boxed{120} \]
5. Choosing Groups
When selecting a group and the order of selection does not matter, use combinations.
Example:
Choose 2 students from a class of 12.
\[ \binom{12}{2} = \frac{12!}{2!10!} \]
Simplify:
\[ \binom{12}{2} = \frac{12\cdot11}{2} = \boxed{66} \]
6. Assigning Different Roles
If people are selected for different positions, order matters.
Example:
From 8 students, choose a president and vice president.
There are:
\[ 8 \]
choices for president and then:
\[ 7 \]
choices for vice president.
Therefore:
\[ 8\cdot7 = \boxed{56} \]
This is also:
\[ P(8,2)=56 \]
7. Counting in Probability Problems
Counting methods can help determine the number of favorable and total outcomes.
Recall:
\[ P(\text{event}) = \frac{\text{favorable outcomes}} {\text{total outcomes}} \]
Suppose 2 cards are chosen from a standard 52-card deck.
How many different pairs of cards are possible?
Because the order of the two cards does not matter:
\[ \binom{52}{2} \]
Suppose we want both cards to be aces.
There are 4 aces, so the number of favorable pairs is:
\[ \binom{4}{2} \]
Therefore:
\[ P(\text{two aces}) = \frac{\binom{4}{2}} {\binom{52}{2}} \]
Calculate:
\[ P(\text{two aces}) = \frac{6}{1326} = \boxed{\frac{1}{221}} \]
This agrees with the sequential probability approach:
\[ \frac{4}{52}\cdot\frac{3}{51} = \frac{1}{221} \]
Strategies
Step 1: Identify the Decisions
Break the problem into individual choices or positions.
Ask:
- How many choices are available at the first step?
- How many choices remain at the second?
- Does the number continue changing?
Step 2: Check Whether Repetition Is Allowed
If repetition is allowed, the number of choices may stay the same.
For example:
\[ 5\cdot5\cdot5 \]
If repetition is not allowed, the choices may decrease:
\[ 5\cdot4\cdot3 \]
Step 3: Ask Whether Order Matters
Ask:
Would rearranging the selected items produce a different outcome?
If yes:
\[ \boxed{\text{permutation}} \]
If no:
\[ \boxed{\text{combination}} \]
Step 4: Choose the Simplest Method
Use:
- Fundamental Counting Principle for sequential choices
- factorials for arranging all objects
- permutations when selecting and arranging
- combinations when selecting a group
Sometimes more than one method works.
Step 5: Simplify Factorials Before Calculating
Instead of calculating huge factorials directly, cancel first.
For example:
\[ \frac{10!}{7!} \]
can be simplified immediately:
\[ \frac{10\cdot9\cdot8\cdot7!}{7!} = 10\cdot9\cdot8 \]
This is much easier than calculating \(10!\) and \(7!\) separately.
Worked Examples
Example 1 — License Plates
A license plate contains:
- 3 letters
- followed by 3 digits
Suppose repetition is allowed.
Each letter has:
\[ 26 \]
choices.
Each digit has:
\[ 10 \]
choices.
Using the Fundamental Counting Principle:
\[ 26\cdot26\cdot26\cdot10\cdot10\cdot10 \]
Using exponents:
\[ 26^3\cdot10^3 \]
Therefore:
\[ \boxed{17{,}576{,}000} \]
different license plates are possible.
Example 2 — Race Finishers
Eight runners compete in a race.
How many ways can the top 3 finishers be ordered?
Because first, second, and third place are different positions, order matters.
Use a permutation:
\[ P(8,3) = \frac{8!}{5!} \]
Simplify:
\[ P(8,3) = 8\cdot7\cdot6 = \boxed{336} \]
Example 3 — Project Team
Ten students are available for a project.
How many different teams of 4 students can be formed?
The order in which the students are chosen does not matter.
Use a combination:
\[ \binom{10}{4} = \frac{10!}{4!6!} \]
Simplify:
\[ \binom{10}{4} = \frac{10\cdot9\cdot8\cdot7} {4\cdot3\cdot2\cdot1} \]
Therefore:
\[ \boxed{210} \]
different teams are possible.
Example 4 — Same People, Different Question
Eight students are available.
Situation A
Choose 3 students to form a committee.
Order does not matter:
\[ \binom{8}{3} = \boxed{56} \]
Situation B
Choose a president, vice president, and secretary.
Order matters because the roles are different:
\[ P(8,3) = 8\cdot7\cdot6 = \boxed{336} \]
The same number of people are selected, but the number of outcomes changes because the second situation assigns different roles.
Example 5 — No Repeated Digits
How many 4-digit codes can be created using the digits:
\[ 1,2,3,4,5,6 \]
if no digit can repeat?
There are:
- 6 choices for the first position
- 5 choices for the second
- 4 choices for the third
- 3 choices for the fourth
Therefore:
\[ 6\cdot5\cdot4\cdot3 = \boxed{360} \]
This could also be written:
\[ P(6,4)=360 \]
Choosing the Right Counting Method
- Adding the number of choices when the Fundamental Counting Principle requires multiplication.
- Using a permutation when order does not matter.
- Using a combination when different positions or rankings make order important.
- Forgetting to check whether repetition is allowed.
- Keeping the same number of choices after an item has already been used when repetition is not allowed.
- Counting the same group multiple times because its members were selected in a different order.
- Calculating large factorials before simplifying.
- Assuming every counting problem requires a permutation or combination formula when simple multiplication may be easier.
Practice Problems
You have 4 shirts and 3 pairs of pants. How many different outfits can you make by choosing one shirt and one pair of pants?
How many ways can 5 different books be arranged on a shelf?
How many different groups of 2 students can be selected from 12 students?
Using the digits 1 through 5, how many 3-digit codes can be formed if no digit can repeat?
A restaurant offers 3 appetizers, 5 main dishes, and 4 desserts. How many meals can be created by choosing one of each?
From 10 students, how many ways can a president, vice president, and secretary be chosen?
From the same 10 students, how many different 3-person committees can be formed?
A 4-digit PIN uses digits 0 through 9. If repetition is allowed, how many PINs are possible?
1. There are 4 choices for the shirt and 3 choices for the pants.
Use the Fundamental Counting Principle:
\[ 4\cdot3 = \boxed{12} \]
2. All 5 books are being arranged, so order matters.
Use:
\[ 5! \]
Calculate:
\[ 5! = 5\cdot4\cdot3\cdot2\cdot1 = \boxed{120} \]
3. We are choosing a group of 2 students.
The order of selection does not matter.
Use a combination:
\[ \binom{12}{2} = \frac{12!}{2!10!} \]
Simplify:
\[ \binom{12}{2} = \frac{12\cdot11}{2} = \boxed{66} \]
4. There are 5 choices for the first digit.
Because digits cannot repeat, there are then 4 choices followed by 3 choices.
Therefore:
\[ 5\cdot4\cdot3 = \boxed{60} \]
5. There are:
- 3 appetizer choices
- 5 main-dish choices
- 4 dessert choices
Multiply:
\[ 3\cdot5\cdot4 = \boxed{60} \]
different meals.
6. The three positions are different:
- president
- vice president
- secretary
Therefore, order matters.
Use a permutation:
\[ P(10,3) = 10\cdot9\cdot8 = \boxed{720} \]
7. The students are simply forming a 3-person committee.
There are no different roles, so order does not matter.
Use a combination:
\[ \binom{10}{3} = \frac{10\cdot9\cdot8}{3\cdot2\cdot1} = \boxed{120} \]
8. Each of the 4 positions can contain any of 10 digits.
Because repetition is allowed:
\[ 10\cdot10\cdot10\cdot10 = 10^4 = \boxed{10{,}000} \]
Summary
The Fundamental Counting Principle says to multiply the number of choices available at each step:
\[ \boxed{ (\text{choices at step 1}) (\text{choices at step 2}) \cdots } \]
A permutation is used when order matters:
\[ \boxed{ P(n,r)=\frac{n!}{(n-r)!} } \]
A combination is used when order does not matter:
\[ \boxed{ \binom{n}{r} = \frac{n!}{r!(n-r)!} } \]
Before calculating, ask:
- How many choices are available at each step?
- Is repetition allowed?
- Does order matter?
- Multiple sequential choices → multiply.
- Arrange all \(n\) objects → \(n!\).
- Different positions or rankings → permutation.
- Selecting a group → combination.
- Repetition allowed → choices may stay the same.
- No repetition → choices usually decrease.
- Ask “Does order matter?” before choosing between permutations and combinations.
- Simplify factorials before calculating large numbers.