1) Expanding Our Combinatorics Toolkit 🧮
Welcome back to Probability and Combinatorics! In Part 1, we took our first steps by understanding basic probability concepts and the Basic Counting Principle (Multiplication Principle). Now, in Part 2, we're going to significantly expand our combinatorics toolkit.
In Part 1, the Basic Counting Principle was great for situations where we had a sequence of independent choices. But what if the order of items matters, or if we are selecting groups where order *doesn't* matter? That's where Permutations and Combinations come in!
Permutations are about counting arrangements where order matters. We're interested in how many different ways we can arrange items in a specific sequence.
Combinations are about counting selections where order does not matter. We are interested in how many ways we can choose a group of items, regardless of their arrangement within the group.
In this Part 2, we will explore:
- Understanding Permutations: when order matters, and how to calculate the number of permutations.
- Understanding Combinations: when order does not matter, and how to calculate the number of combinations.
- Learning to differentiate between permutation and combination scenarios.
- Applying permutations and combinations to calculate probabilities in more complex situations.
Let's dive into permutations and combinations, and further enhance our ability to count and understand probability! 🚀
2) Permutations: When Order Matters 🧮
2.1 Introduction to Permutations
Permutations deal with ordered arrangements. When we are concerned about the sequence or order in which items are arranged, we use permutations.
Example 1: Arranging Letters
How many different ways can you arrange the letters A, B, and C?
Let's list them out:
- ABC
- ACB
- BAC
- BCA
- CAB
- CBA
2.2 The Permutation Formula
The number of permutations of choosing \(r\) items from a set of \(n\) distinct items (where order matters and without repetition) is given by the formula:
\( P(n, r) = \frac{n!}{(n - r)!} \)
Where \(n!\) (n-factorial) is the product of all positive integers up to \(n\). For example, \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\). And by definition, \(0! = 1\).
\(P(n, r)\) is often read as "the number of permutations of \(n\) items taken \(r\) at a time".
Example 2: Permutations of Letters (Formula)
Let's revisit arranging the letters A, B, and C using the formula. Here, we are arranging all 3 letters, so \(n = 3\) and \(r = 3\).
Using the permutation formula: \( P(n, r) = \frac{n!}{(n - r)!} \)
\( P(3, 3) = \frac{3!}{(3 - 3)!} = \frac{3!}{0!} = \frac{3 \times 2 \times 1}{1} = 6 \)
This matches our earlier listing – there are 6 permutations.
Example 3: Choosing and Ordering Contest Winners
In a contest with 10 participants, how many ways can we award 1st, 2nd, and 3rd place prizes?
Here, order is crucial (1st place is different from 2nd). We are choosing 3 winners from 10 participants, and the order matters. So, this is a permutation problem with \(n = 10\) and \(r = 3\).
Using the permutation formula: \( P(n, r) = \frac{n!}{(n - r)!} \)
\( P(10, 3) = \frac{10!}{(10 - 3)!} = \frac{10!}{7!} = \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1} = 10 \times 9 \times 8 = 720 \)
There are 720 different ways to award the 1st, 2nd, and 3rd place prizes.
3) Combinations: When Order Does Not Matter 🔢
3.1 Introduction to Combinations
Combinations are about selections where order is irrelevant. If we are only interested in choosing a group of items, and not the order in which they are chosen, we use combinations.
Example 4: Choosing a Committee
Suppose you need to choose a committee of 2 students from a group of 4 students: Alice (A), Ben (B), Carol (C), and David (D). How many different committees can you form?
Let's list the possible committees. Remember, order doesn't matter, so committee {Alice, Ben} is the same as {Ben, Alice}.
- {Alice, Ben} (AB)
- {Alice, Carol} (AC)
- {Alice, David} (AD)
- {Ben, Carol} (BC)
- {Ben, David} (BD)
- {Carol, David} (CD)
3.2 The Combination Formula
The number of combinations of choosing \(r\) items from a set of \(n\) distinct items (where order does not matter and without repetition) is given by the formula:
\( C(n, r) = \frac{n!}{r!(n - r)!} \)
This formula is very similar to the permutation formula, but with an additional \(r!\) in the denominator. This \(r!\) accounts for the fact that for each combination of \(r\) items, there are \(r!\) possible permutations (orderings), and we want to count each *combination* only once.
\(C(n, r)\) is often read as "the number of combinations of \(n\) items taken \(r\) at a time", or "n choose r". It's also sometimes written as \( \binom{n}{r} \).
Example 5: Combinations of Students (Formula)
Let's calculate the number of 2-student committees from 4 students using the formula. Here, \(n = 4\) and \(r = 2\).
Using the combination formula: \( C(n, r) = \frac{n!}{r!(n - r)!} \)
\( C(4, 2) = \frac{4!}{2!(4 - 2)!} = \frac{4!}{2!2!} = \frac{4 \times 3 \times 2 \times 1}{(2 \times 1)(2 \times 1)} = \frac{24}{4} = 6 \)
Again, this matches our earlier listing – there are 6 combinations for the committees.
Example 6: Choosing Lottery Numbers
In a lottery, you need to choose 6 numbers from 49 (numbers are from 1 to 49). How many different lottery number combinations are possible?
In lottery number selection, the order in which you choose the numbers doesn't matter – just the set of 6 numbers. So, this is a combination problem with \(n = 49\) and \(r = 6\).
Using the combination formula: \( C(n, r) = \frac{n!}{r!(n - r)!} \)
\( C(49, 6) = \frac{49!}{6!(49 - 6)!} = \frac{49!}{6!43!} = \frac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = 13,983,816 \)
There are almost 14 million different combinations of lottery numbers! This is why winning the lottery is statistically very unlikely.
4) Permutations and Combinations in Probability 🍀
4.1 Applying Combinatorics to Probability
Permutations and combinations become powerful tools when we need to calculate probabilities in situations with many possible outcomes where direct counting becomes tedious or impractical. By using these techniques, we can efficiently determine the "total number of possible outcomes" and the "number of favorable outcomes" for our probability formula:
\( P(\text{Event}) = \frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}} \)
Example 7: Probability of Winning the Lottery (Simplified)
Let's simplify the lottery example. Suppose you need to choose 2 numbers from 5 (numbers 1, 2, 3, 4, 5) to win. What is the probability of winning if you buy one ticket (one combination of 2 numbers)?
**Solution:**
- Total possible outcomes: The total number of ways to choose 2 numbers from 5 is given by combinations \(C(5, 2)\).
\( C(5, 2) = \frac{5!}{2!(5 - 2)!} = \frac{5!}{2!3!} = \frac{5 \times 4}{2 \times 1} = 10 \)
There are 10 possible combinations of 2 numbers chosen from 5. - Favorable outcomes: There is only 1 winning combination of numbers. So, number of favorable outcomes = 1.
Using the probability formula: \( P(\text{Event}) = \frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}} \)
\( P(\text{Winning lottery}) = \frac{1}{10} \)
The probability of winning this simplified lottery is \( \frac{1}{10} \) or 10%.
Example 8: Probability in Card Hands (Poker Hand)
What is the probability of being dealt a 2-card hand from a standard 52-card deck that consists of two Aces?
**Solution:**
- Total possible outcomes: The total number of 2-card hands you can be dealt from a 52-card deck is the number of combinations of choosing 2 cards from 52, which is \(C(52, 2)\).
\( C(52, 2) = \frac{52!}{2!(52 - 2)!} = \frac{52!}{2!50!} = \frac{52 \times 51}{2 \times 1} = 1326 \)
There are 1326 possible 2-card hands. - Favorable outcomes: We want a hand with two Aces. There are 4 Aces in a deck. The number of ways to choose 2 Aces from the 4 available Aces is \(C(4, 2)\).
\( C(4, 2) = \frac{4!}{2!(4 - 2)!} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6 \)
There are 6 ways to get a 2-card hand with two Aces.
Using the probability formula: \( P(\text{Event}) = \frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}} \)
\( P(\text{Two Aces}) = \frac{6}{1326} = \frac{1}{221} \)
The probability of being dealt a 2-card hand of two Aces is \( \frac{1}{221} \), which is quite low.
5) Examples (Detailed) 🍀
Example 9: Permutations vs. Combinations – Choosing a Team and Roles
Let's clarify the difference between permutations and combinations with a comparative example.
- Challenge 1 (Permutation): From a group of 5 students (A, B, C, D, E), how many ways can you choose a president, a vice-president, and a treasurer? (Different roles matter, order matters).
- Challenge 2 (Combination): From the same group of 5 students (A, B, C, D, E), how many ways can you form a committee of 3 students? (Roles don't matter, order doesn't matter).
**Let's solve each challenge:**
- Solution to Challenge 1 (Permutation): Choosing Roles
Here, the order matters because the roles are distinct (President, VP, Treasurer). Choosing student A as President, B as VP, and C as Treasurer is different from choosing B as President, A as VP, and C as Treasurer. We are choosing 3 positions from 5 students, order matters – permutation \(P(5, 3)\).
\( P(5, 3) = \frac{5!}{(5 - 3)!} = \frac{5!}{2!} = 5 \times 4 \times 3 = 60 \)
There are 60 ways to assign the roles of president, vice-president, and treasurer.
- Solution to Challenge 2 (Combination): Forming a Committee
In this case, the order does not matter. A committee of {A, B, C} is the same as a committee of {C, B, A} or any other order. We are simply choosing a group of 3 students from 5, order doesn't matter – combination \(C(5, 3)\).
\( C(5, 3) = \frac{5!}{3!(5 - 3)!} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10 \)
There are 10 possible committees of 3 students that can be formed.
Notice how the number of permutations (60) is significantly larger than the number of combinations (10) for the same numbers of items (5 and 3). This highlights the impact of order being important in permutations but not in combinations.
6) Practice Questions 🎯
6.1 Fundamental – Build Skills
1. Calculate \(P(6, 2)\) and \(C(6, 2)\). What is the difference and why?
2. In how many ways can you arrange 4 books on a shelf?
3. How many different 3-digit numbers can be formed using digits 1, 2, 3, 4, 5, 6, 7, 8, 9 without repetition of digits?
4. From a group of 7 friends, how many ways can you choose a group of 4 friends to go to the cinema?
5. A lock combination consists of 3 numbers chosen from 1 to 30. If numbers cannot be repeated, how many different lock combinations are possible? (Hint: does order matter for a lock combination?)
6. If you have 5 different flavors of ice cream, how many ways can you choose 2 scoops for a cone if the order of scoops doesn't matter?
7. What is the probability of winning a raffle if 500 tickets are sold and you buy 5 tickets? (Assume only one winning ticket).
8. From a standard deck of 52 cards, what is the probability of being dealt a 2-card hand of two Kings?
9. How many ways can a president and vice-president be chosen from a club of 20 members?
10. In a race with 8 runners, in how many ways can the top 3 finishers be ordered (1st, 2nd, 3rd place)?
11. You have 10 songs and want to create a playlist of 4 songs. How many different playlists can you create if the order of songs matters?
12. From a committee of 8 people, a subcommittee of 3 people is to be formed. How many different subcommittees are possible?
6.2 Challenging – Push Limits 💪🚀
1. What is the probability of drawing 3 hearts from a standard deck of 52 cards if you draw 3 cards without replacement?
2. In a group of 10 people, 4 are left-handed. If you randomly select 3 people from this group, what is the probability that exactly 2 of them are left-handed?
3. Word Problem: A pizza shop offers 12 different toppings. How many different pizzas can be made with exactly 4 toppings?
4. (Conceptual) Explain in your own words the key difference between permutations and combinations. Give a real-life example of when you would use permutations and when you would use combinations.
5. (Probability & Combinations Combined) You have a bag with 6 red marbles and 4 blue marbles. If you randomly draw 2 marbles without replacement, what is the probability that you get one red marble and one blue marble?
7) Summary 🎉
- Permutations count arrangements where order matters. Formula: \( P(n, r) = \frac{n!}{(n - r)!} \).
- Combinations count selections where order does not matter. Formula: \( C(n, r) = \frac{n!}{r!(n - r)!} \).
- Key difference: Permutations are for ordered arrangements, Combinations are for unordered selections (groups).
- Permutations and combinations are essential for calculating probabilities in situations with many possible outcomes, especially when outcomes are equally likely.
- Remember to identify whether order matters or not in a problem to decide whether to use permutations or combinations.
Congratulations! You've now significantly expanded your combinatorics toolkit with permutations and combinations! You can now tackle a wider range of counting problems and more complex probability scenarios. In Level 3, we will delve deeper into probability, including conditional probability and expected value. Keep practicing, and you'll become even more skilled in the art of chance and counting! 🌟
← Back to Previous Topic (Part 1 - Intro) Continue to Level 3 Topics → View Level 2 Topics Overview →