Chapter Notes: Counting, Permutations, and Combinations
When planning an event, designing a password, or creating a team lineup, one question comes up repeatedly: how many different ways can we arrange or select items? The mathematics of counting is far more powerful than simply adding up objects. In this chapter, you will learn systematic methods to count arrangements and selections without having to list every single possibility. These techniques-counting principles, permutations, and combinations-form the foundation of probability theory and appear in fields ranging from computer science to genetics to game theory.
Fundamental Counting Principle
The Fundamental Counting Principle (also called the Multiplication Principle) states that if one event can occur in \( m \) ways and a second independent event can occur in \( n \) ways, then the two events together can occur in \( m \times n \) ways. This principle extends to any number of events.
Think of it like choosing an outfit: if you have 4 shirts and 3 pairs of pants, you can create 4 × 3 = 12 different outfits.
Example: A restaurant offers a dinner special where you choose one appetizer, one entrée, and one dessert.
There are 3 appetizers, 5 entrées, and 4 desserts available.How many different dinner combinations are possible?
Solution:
Using the Fundamental Counting Principle, multiply the number of choices at each stage:
Number of combinations = 3 × 5 × 4
Number of combinations = 60
There are 60 different dinner combinations possible.
Example: A password requires 2 letters followed by 3 digits.
Letters can be any of the 26 letters in the alphabet, and digits can be any number from 0 to 9.
Repetition is allowed.How many different passwords can be created?
Solution:
For the first letter: 26 choices
For the second letter: 26 choices
For the first digit: 10 choices
For the second digit: 10 choices
For the third digit: 10 choices
Total passwords = 26 × 26 × 10 × 10 × 10 = 676 × 1,000 = 676,000
There are 676,000 different possible passwords.
Counting Without Replacement
When items cannot be repeated (sampling without replacement), the number of choices decreases at each stage. This situation occurs frequently in real-world problems involving selection from a finite pool.
Example: A club with 8 members needs to select a president, vice president, and treasurer.
One person cannot hold multiple positions.How many different ways can these three positions be filled?
Solution:
For president: 8 choices
For vice president: 7 remaining choices (one person is already president)
For treasurer: 6 remaining choices (two people are already selected)
Total arrangements = 8 × 7 × 6 = 336
There are 336 different ways to fill the three positions.
Factorial Notation
Before diving into permutations and combinations, we need a mathematical shorthand for repeated multiplication of consecutive integers. The factorial of a positive integer \( n \), written \( n! \), is the product of all positive integers from 1 to \( n \).
\[ n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1 \]For example:
- \( 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \)
- \( 4! = 4 \times 3 \times 2 \times 1 = 24 \)
- \( 3! = 3 \times 2 \times 1 = 6 \)
- \( 2! = 2 \times 1 = 2 \)
- \( 1! = 1 \)
By definition, \( 0! = 1 \). This may seem strange at first, but this definition makes many formulas work correctly, particularly in permutations and combinations.
Important property: Notice that \( n! = n \times (n-1)! \). This recursive relationship is useful for simplifying expressions. For instance, \( 7! = 7 \times 6! \), so if you're computing a fraction like \( \frac{7!}{6!} \), it simplifies to just 7.
Permutations
A permutation is an arrangement of objects in a specific order. When order matters-such as assigning rankings, arranging books on a shelf, or determining the order of contestants-you are working with permutations.
Permutations of n Distinct Objects
The number of ways to arrange \( n \) distinct objects in order is \( n! \).
Example: Five students-Alice, Ben, Carmen, David, and Emma-are standing in line for lunch.
In how many different orders can they stand?
Solution:
For the first position: 5 choices
For the second position: 4 remaining choices
For the third position: 3 remaining choices
For the fourth position: 2 remaining choices
For the fifth position: 1 remaining choice
Total arrangements = 5! = 5 × 4 × 3 × 2 × 1 = 120
The five students can stand in 120 different orders.
Permutations of r Objects from n Objects
Often we want to arrange only some of the available objects. The number of permutations of \( r \) objects selected from \( n \) distinct objects is denoted \( P(n, r) \) or \( {}_n P_r \) and calculated as:
\[ P(n, r) = \frac{n!}{(n-r)!} \]This formula counts the number of ways to fill \( r \) positions using \( n \) distinct items, where order matters.
The logic: you have \( n \) choices for the first position, \( n-1 \) for the second, continuing down to \( n-r+1 \) choices for the \( r \)-th position. This product equals \( \frac{n!}{(n-r)!} \).
Example: A race has 10 runners competing.
Medals are awarded for first, second, and third place.How many different ways can the medals be awarded?
Solution:
We need to arrange 3 runners out of 10, and order matters (first place is different from second place).
Using the permutation formula: \( P(10, 3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} \)
\( P(10, 3) = 10 \times 9 \times 8 = 720 \)
The medals can be awarded in 720 different ways.
Example: A playlist will play 4 songs selected from a library of 12 songs.
Each song will be played exactly once, and the order of the songs matters.How many different playlists are possible?
Solution:
We need permutations of 4 songs from 12 songs.
\( P(12, 4) = \frac{12!}{(12-4)!} = \frac{12!}{8!} \)
\( P(12, 4) = 12 \times 11 \times 10 \times 9 = 11,880 \)
There are 11,880 different possible playlists.
Permutations with Repetition
When some objects are identical, the number of distinguishable permutations decreases. If you have \( n \) total objects where \( n_1 \) are identical of one type, \( n_2 \) are identical of another type, and so on, the number of distinguishable permutations is:
\[ \frac{n!}{n_1! \cdot n_2! \cdot n_3! \cdots n_k!} \]where \( n_1 + n_2 + n_3 + \cdots + n_k = n \).
Example: How many distinguishable arrangements can be made using all the letters in the word MISSISSIPPI?
How many distinct arrangements exist?
Solution:
Count the letters: M appears 1 time, I appears 4 times, S appears 4 times, P appears 2 times.
Total letters: \( n = 11 \)
Number of distinguishable arrangements = \( \frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} \)
\( = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1,152} = 34,650 \)
There are 34,650 distinguishable arrangements of the letters in MISSISSIPPI.
Combinations
A combination is a selection of objects where order does not matter. When choosing a committee, selecting toppings for a pizza, or picking lottery numbers, you are working with combinations. The key distinction: permutations care about order, combinations do not.
Combinations of r Objects from n Objects
The number of combinations of \( r \) objects selected from \( n \) distinct objects is denoted \( C(n, r) \), \( {}_n C_r \), or \( \binom{n}{r} \) (read as "\( n \) choose \( r \)") and calculated as:
\[ C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} \]This formula counts the number of ways to choose \( r \) items from \( n \) items when the order of selection doesn't matter.
Why divide by \( r! \)? Because each combination corresponds to \( r! \) different permutations. By dividing the permutation count by \( r! \), we eliminate the overcounting caused by different orderings of the same group.
Example: A teacher needs to select 3 students from a class of 15 to form a committee.
How many different committees can be formed?
Solution:
We need combinations because the order in which students are selected doesn't matter-choosing Alice, Ben, Carmen is the same committee as choosing Carmen, Alice, Ben.
\( C(15, 3) = \frac{15!}{3!(15-3)!} = \frac{15!}{3! \cdot 12!} \)
\( = \frac{15 \times 14 \times 13 \times 12!}{6 \times 12!} = \frac{15 \times 14 \times 13}{6} = \frac{2,730}{6} = 455 \)
There are 455 different committees that can be formed.
Example: A pizza shop offers 10 different toppings.
You want to order a pizza with exactly 4 toppings.How many different 4-topping pizzas can you create?
Solution:
Order doesn't matter (pepperoni-mushroom-onion-pepper is the same pizza as mushroom-pepper-pepperoni-onion).
\( C(10, 4) = \frac{10!}{4!(10-4)!} = \frac{10!}{4! \cdot 6!} \)
\( = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = \frac{5,040}{24} = 210 \)
You can create 210 different 4-topping pizzas.
Important Properties of Combinations
Several useful identities help simplify combination calculations:
- Symmetry Property: \( \binom{n}{r} = \binom{n}{n-r} \). Choosing \( r \) items to include is equivalent to choosing \( n-r \) items to exclude.
- Boundary Cases: \( \binom{n}{0} = 1 \) (one way to choose nothing) and \( \binom{n}{n} = 1 \) (one way to choose everything).
- Single Selection: \( \binom{n}{1} = n \) (choosing one item from \( n \) items gives \( n \) options).
Distinguishing Permutations from Combinations
The critical question to ask: Does order matter?
Example: A standard deck of 52 cards is used for a card game.
You are dealt a 5-card hand.How many different 5-card hands are possible?
Solution:
Order doesn't matter-receiving the Ace of Spades first or last doesn't create a different hand.
\( C(52, 5) = \frac{52!}{5!(52-5)!} = \frac{52!}{5! \cdot 47!} \)
\( = \frac{52 \times 51 \times 50 \times 49 \times 48}{5 \times 4 \times 3 \times 2 \times 1} = \frac{311,875,200}{120} = 2,598,960 \)
There are 2,598,960 different possible 5-card hands.
Applications and Problem-Solving Strategies
Multi-Stage Problems
Many real-world problems involve both counting principles, permutations, and combinations in sequence. Break complex problems into stages and apply the appropriate technique at each stage.
Example: A debate team has 6 members.
They need to select 4 members to attend a tournament, then assign those 4 members specific speaking roles: opener, rebuttal, summary, and closing.How many ways can this be done?
Solution:
Stage 1: Select 4 members from 6 (order doesn't matter at this stage).
\( C(6, 4) = \frac{6!}{4! \cdot 2!} = \frac{6 \times 5}{2 \times 1} = 15 \)
Stage 2: Assign the 4 selected members to 4 specific roles (order matters).
\( P(4, 4) = 4! = 24 \)
Total ways = 15 × 24 = 360
There are 360 different ways to select and assign the team.
Complementary Counting
Sometimes it's easier to count what you don't want and subtract from the total. This technique is called complementary counting.
Example: A committee of 5 people is selected from a group of 8 women and 7 men.
At least one woman must be on the committee.How many different committees satisfy this requirement?
Solution:
Total people = 8 + 7 = 15
Total possible committees (no restrictions) = \( C(15, 5) = \frac{15!}{5! \cdot 10!} = 3,003 \)
Committees with no women (all 5 men) = \( C(7, 5) = \frac{7!}{5! \cdot 2!} = 21 \)
Committees with at least one woman = Total committees - All-male committees
Committees with at least one woman = 3,003 - 21 = 2,982
There are 2,982 committees with at least one woman.
Dividing into Groups
When dividing objects into distinct groups, use combinations for each group and multiply. When groups are indistinguishable from each other, you must divide by the number of ways to arrange the groups.
Example: Twelve people need to be divided into three distinct teams: Team A with 5 people, Team B with 4 people, and Team C with 3 people.
How many ways can this be done?
Solution:
Choose 5 people for Team A: \( C(12, 5) = 792 \)
Choose 4 people for Team B from the remaining 7: \( C(7, 4) = 35 \)
The remaining 3 people go to Team C: \( C(3, 3) = 1 \)
Total ways = 792 × 35 × 1 = 27,720
There are 27,720 ways to divide the twelve people into the three distinct teams.
Summary of Formulas
Mastering these counting techniques enables you to solve complex probability problems, analyze outcomes in games and competitions, and understand the mathematical structures underlying decision-making and randomness. The key to success is careful analysis of whether order matters and whether you're arranging all items or selecting a subset.
