Chapter Notes: Combinatorics and Probability
When you flip a coin, roll a die, or shuffle a deck of cards, you're entering the world of probability. But before we can calculate the chance of something happening, we first need to know how many different ways things can be arranged or selected. This is where combinatorics comes in-the mathematics of counting arrangements and combinations. Together, combinatorics and probability help us understand random events, make predictions, and solve problems ranging from game strategies to analyzing survey data. In this chapter, you'll learn systematic ways to count outcomes and use those counts to calculate probabilities.
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.
This principle is the foundation of combinatorics. Instead of listing every possible outcome, we multiply the number of choices at each stage.
Think of building an outfit: if you have 4 shirts and 3 pairs of pants, you can create 4 × 3 = 12 different outfits without listing them all.
Example: A restaurant offers a dinner special where you choose one appetizer, one main course, and one dessert.
There are 3 appetizers, 5 main courses, and 4 desserts.How many different dinner combinations are possible?
Solution:
Number of appetizer choices = 3
Number of main course choices = 5
Number of dessert choices = 4
Total combinations = 3 × 5 × 4 = 60
There are 60 different dinner combinations possible.
Example: A password must consist of 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 are possible?
Solution:
First letter: 26 choices
Second letter: 26 choices
First digit: 10 choices
Second digit: 10 choices
Third digit: 10 choices
Total passwords = 26 × 26 × 10 × 10 × 10 = 676 × 1,000 = 676,000
There are 676,000 different possible passwords.
Permutations
A permutation is an arrangement of objects in a specific order. When order matters, we use permutations. The number of permutations of \( n \) distinct objects taken \( r \) at a time is denoted \( P(n, r) \) or \( {}_nP_r \).
Permutations of n Distinct Objects
If you have \( n \) distinct objects and want to arrange all of them, the number of permutations is:
\[ P(n, n) = n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 \]The symbol \( n! \) is read as "n factorial." For example, \( 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \).
Example: Five students are running for class president, vice president, secretary, treasurer, and historian.
Each position will be filled by a different student.In how many ways can these five positions be filled?
Solution:
Number of students = 5
Number of positions = 5
Total arrangements = 5! = 5 × 4 × 3 × 2 × 1 = 120
The five positions can be filled in 120 different ways.
Permutations of n Objects Taken r at a Time
When you select and arrange \( r \) objects from \( n \) available objects, the formula is:
\[ P(n, r) = \frac{n!}{(n-r)!} \]Here, \( n \) is the total number of objects, and \( r \) is the number of objects being arranged.
Example: A race has 8 runners.
Gold, silver, and bronze medals will be awarded to the top three finishers.How many different ways can the medals be awarded?
Solution:
Total runners \( n = 8 \), medals to award \( r = 3 \)
Number of ways = \( P(8, 3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} \)
\( = \frac{8 \times 7 \times 6 \times 5!}{5!} = 8 \times 7 \times 6 = 336 \)
The medals can be awarded in 336 different ways.
Permutations with Repetition
When some objects are identical, the number of distinct permutations decreases. If you have \( n \) objects where one type repeats \( n_1 \) times, another repeats \( n_2 \) times, and so on, the number of distinct permutations is:
\[ \frac{n!}{n_1! \times n_2! \times \cdots \times n_k!} \]Example: How many distinct arrangements can be made from the letters in the word MISSISSIPPI?
Solution:
Total letters = 11
M appears 1 time, I appears 4 times, S appears 4 times, P appears 2 times
Number of distinct arrangements = \( \frac{11!}{1! \times 4! \times 4! \times 2!} \)
\( = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1,152} = 34,650 \)
There are 34,650 distinct arrangements of the letters in MISSISSIPPI.
Combinations
A combination is a selection of objects where order does not matter. When you're choosing a group without caring about the arrangement, you use combinations. The number of combinations of \( n \) objects taken \( r \) at a time is denoted \( C(n, r) \), \( {}_nC_r \), or \( \binom{n}{r} \).
Combinations Formula
The formula for combinations is:
\[ C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} \]This formula divides out the arrangements (permutations) within each group because order doesn't matter in combinations.
If you're choosing 3 people from a group of 5 to form a committee, it doesn't matter in what order you pick them-the same three people make the same committee.
Example: A teacher needs to select 4 students from a class of 12 to attend a workshop.
How many different groups of 4 students can be selected?
Solution:
Total students \( n = 12 \), students to select \( r = 4 \)
Number of combinations = \( C(12, 4) = \frac{12!}{4!(12-4)!} = \frac{12!}{4! \times 8!} \)
\( = \frac{12 \times 11 \times 10 \times 9 \times 8!}{4! \times 8!} = \frac{12 \times 11 \times 10 \times 9}{24} = \frac{11,880}{24} = 495 \)
There are 495 different groups of 4 students that can be selected.
When to Use Permutations vs. Combinations
The key question is: Does order matter?
- If order matters (like finishing positions in a race or arranging books on a shelf), use permutations.
- If order doesn't matter (like choosing team members or selecting toppings for a pizza), use combinations.
Example: A pizza shop offers 8 different toppings.
You want to order a pizza with exactly 3 toppings.How many different 3-topping pizzas can you create?
Solution:
Since the order of toppings doesn't matter (pepperoni-mushroom-olive is the same pizza as olive-pepperoni-mushroom), we use combinations.
Total toppings \( n = 8 \), toppings to choose \( r = 3 \)
Number of pizzas = \( C(8, 3) = \frac{8!}{3! \times 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56 \)
You can create 56 different 3-topping pizzas.
Introduction to Probability
Probability is a measure of how likely an event is to occur. Probabilities are expressed as numbers between 0 and 1, inclusive, where 0 means the event is impossible and 1 means the event is certain. Probabilities can also be expressed as percentages between 0% and 100%.
The probability of an event A is defined as:
\[ P(A) = \frac{\text{number of favorable outcomes}}{\text{total number of possible outcomes}} \]This assumes all outcomes are equally likely.
Sample Spaces and Events
The sample space is the set of all possible outcomes of an experiment. An event is a subset of the sample space-a specific outcome or group of outcomes we're interested in.
When rolling a standard six-sided die, the sample space is {1, 2, 3, 4, 5, 6}. The event "rolling an even number" corresponds to the subset {2, 4, 6}.
Example: A bag contains 5 red marbles, 3 blue marbles, and 2 green marbles.
You randomly select one marble from the bag.What is the probability that the marble is blue?
Solution:
Total marbles = 5 + 3 + 2 = 10
Number of blue marbles = 3
Probability of blue = \( \frac{3}{10} = 0.3 \) or 30%
The probability of selecting a blue marble is 0.3 or 30%.
Probability Rules and Properties
Complement Rule
The complement of an event A, denoted \( A' \) or \( A^c \), consists of all outcomes in the sample space that are not in A. The probability of the complement is:
\[ P(A') = 1 - P(A) \]This is useful when it's easier to calculate the probability that something doesn't happen.
Example: The probability that it will rain tomorrow is 0.35.
What is the probability that it will not rain tomorrow?
Solution:
Let A = event that it rains, so \( P(A) = 0.35 \)
Probability it doesn't rain = \( P(A') = 1 - P(A) = 1 - 0.35 = 0.65 \)
The probability that it will not rain tomorrow is 0.65 or 65%.
Addition Rule for Mutually Exclusive Events
Two events are mutually exclusive (or disjoint) if they cannot both occur at the same time. For mutually exclusive events A and B:
\[ P(A \text{ or } B) = P(A) + P(B) \]When rolling a die, getting a 2 and getting a 5 are mutually exclusive-you can't roll both on a single roll.
Example: A card is drawn from a standard 52-card deck.
What is the probability that the card is either a king or a queen?
Solution:
Number of kings = 4
Number of queens = 4
These events are mutually exclusive (a card cannot be both a king and a queen).
Probability = \( P(\text{king or queen}) = \frac{4}{52} + \frac{4}{52} = \frac{8}{52} = \frac{2}{13} = 0.154 \) or approximately 15.4%
The probability of drawing a king or queen is \( \frac{2}{13} \) or approximately 15.4%.
Multiplication Rule for Independent Events
Two events are independent if the occurrence of one does not affect the probability of the other. For independent events A and B:
\[ P(A \text{ and } B) = P(A) \times P(B) \]When flipping a coin twice, the result of the first flip doesn't affect the second flip-the events are independent.
Example: You flip a fair coin and roll a fair six-sided die.
What is the probability of getting heads on the coin and a 4 on the die?
Solution:
Probability of heads = \( \frac{1}{2} \)
Probability of rolling a 4 = \( \frac{1}{6} \)
These events are independent.
Probability of both = \( \frac{1}{2} \times \frac{1}{6} = \frac{1}{12} = 0.083 \) or approximately 8.3%
The probability of getting heads and a 4 is \( \frac{1}{12} \) or approximately 8.3%.
Combining Counting Techniques with Probability
Many probability problems require using permutations or combinations to count favorable outcomes and total outcomes. This is where combinatorics and probability work together most powerfully.
Example: A committee of 5 people is to be randomly selected from a group of 8 women and 7 men.
What is the probability that the committee will consist of exactly 3 women and 2 men?
Solution:
Total people = 8 + 7 = 15
Total ways to choose 5 people from 15 = \( C(15, 5) = \frac{15!}{5! \times 10!} = 3,003 \)
Ways to choose 3 women from 8 = \( C(8, 3) = \frac{8!}{3! \times 5!} = 56 \)
Ways to choose 2 men from 7 = \( C(7, 2) = \frac{7!}{2! \times 5!} = 21 \)
Ways to choose exactly 3 women and 2 men = \( 56 \times 21 = 1,176 \)
Probability = \( \frac{1,176}{3,003} = \frac{392}{1,001} \approx 0.391 \) or approximately 39.1%
The probability that the committee consists of exactly 3 women and 2 men is approximately 39.1%.
Example: Five cards are dealt from a standard 52-card deck.
What is the probability that all five cards are hearts?
Solution:
Total ways to choose 5 cards from 52 = \( C(52, 5) = \frac{52!}{5! \times 47!} = 2,598,960 \)
Number of hearts in deck = 13
Ways to choose 5 hearts from 13 hearts = \( C(13, 5) = \frac{13!}{5! \times 8!} = 1,287 \)
Probability = \( \frac{1,287}{2,598,960} \approx 0.000495 \) or approximately 0.0495%
The probability that all five cards are hearts is approximately 0.0495% or about 1 in 2,020.
Conditional Probability
Conditional probability is the probability of an event occurring given that another event has already occurred. The conditional probability of event A given event B is written as \( P(A|B) \) and calculated as:
\[ P(A|B) = \frac{P(A \text{ and } B)}{P(B)} \]This formula assumes \( P(B) > 0 \).
Think of conditional probability as updating your prediction based on new information. If you know it's cloudy, the probability of rain is higher than on a clear day.
Example: In a class of 30 students, 18 students play sports and 12 do not.
Of the students who play sports, 10 are in the honor society.
Of the students who don't play sports, 4 are in the honor society.If a student is randomly selected and is known to play sports, what is the probability the student is in the honor society?
Solution:
Let A = student is in honor society, B = student plays sports
We need \( P(A|B) \)
Number of students who play sports and are in honor society = 10
Number of students who play sports = 18
\( P(A|B) = \frac{10}{18} = \frac{5}{9} \approx 0.556 \) or approximately 55.6%
Given that a student plays sports, the probability that the student is in the honor society is \( \frac{5}{9} \) or approximately 55.6%.
Expected Value
The expected value (also called the mean or expectation) of a random variable is the long-run average value you would expect if you repeated an experiment many times. For a discrete random variable, the expected value is calculated as:
\[ E(X) = \sum [\text{value} \times \text{probability of that value}] \]Expected value helps us make decisions when outcomes are uncertain, especially in games, investments, and risk analysis.
Example: A raffle ticket costs $5.
There is one grand prize of $500, two second prizes of $100 each, and ten third prizes of $20 each.
A total of 1,000 tickets are sold.What is the expected value of buying one raffle ticket?
Solution:
Probability of winning $500 = \( \frac{1}{1,000} = 0.001 \)
Probability of winning $100 = \( \frac{2}{1,000} = 0.002 \)
Probability of winning $20 = \( \frac{10}{1,000} = 0.01 \)
Probability of winning $0 = \( \frac{987}{1,000} = 0.987 \)
Expected winnings = (500 × 0.001) + (100 × 0.002) + (20 × 0.01) + (0 × 0.987)
= 0.50 + 0.20 + 0.20 + 0 = $0.90
Expected value = Expected winnings - Cost = 0.90 - 5.00 = -$4.10
The expected value of buying one raffle ticket is -$4.10, meaning on average you lose $4.10 per ticket.
Understanding combinatorics and probability equips you with powerful tools to analyze uncertainty, make informed decisions, and solve complex counting problems. These concepts form the foundation for statistics, data science, and many real-world applications in science, economics, and everyday life.
