🌟 Level 2 - Topic 10: Introduction to Probability & Combinatorics (Part 2) 🔢🧮

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!

Think of arranging books on a shelf, or the order in which runners finish a race. The sequence is crucial.

Imagine picking a team from a group of players, or selecting lottery numbers. The group itself matters, not the order in which you pick them.

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:

1. ABC
2. ACB
3. BAC
4. BCA
5. CAB
6. CBA

There are 6 different arrangements. For a small number of items, we can list them. But for larger numbers, we need a formula.

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}.

1. {Alice, Ben} (AB)
2. {Alice, Carol} (AC)
3. {Alice, David} (AD)
4. {Ben, Carol} (BC)
5. {Ben, David} (BD)
6. {Carol, David} (CD)

There are 6 different committees. Notice that pairs like BA, CA, DA, CB, DB, DC are not included because they represent the same committees as AB, AC, AD, BC, BD, CD respectively, just in a different order.

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.

1. 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).
2. 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:**

1. 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.

2. 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 🎯

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! 🌟