Combinatorics: Combinations and Selections

TL;DR

Combinations are about choosing items from a group where the order doesn't matter. You use the "n choose k" formula to calculate the number of ways to make these selections. Understanding when order matters (permutations) versus when it doesn't (combinations) is key to solving problems.

1. The Mental Model

Think of combinations as picking a handful of candies from a jar. It doesn't matter which candy you pick first, second, or third; you just care about which candies end up in your hand. It's all about the group you select, not the sequence.

2. The Core Material

When we talk about combinations, we're dealing with situations where you're selecting a certain number of items from a larger set, and the order in which you pick them doesn't change the selection itself. For example, if you're choosing 3 students for a committee, "Alice, Bob, Carol" is the same committee as "Bob, Carol, Alice."

This is different from permutations, where order does matter. If you're arranging 3 students in a line, "Alice, Bob, Carol" is a different arrangement from "Bob, Carol, Alice."

The Combination Formula

Photo by Jeswin Thomas on Pexels

The number of combinations of selecting k items from a set of n distinct items is given by the formula:

$C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$

Where:
* $n$ is the total number of items available.
* $k$ is the number of items you are choosing.
* $!$ denotes the factorial (e.g., $5! = 5 \times 4 \times 3 \times 2 \times 1$).

Let's break down why this formula works:

1. Permutations first: If order did matter, there would be $P(n, k) = \frac{n!}{(n-k)!}$ ways to choose k items from n.
2. Removing duplicates: Since order doesn't matter for combinations, any group of k items can be arranged in $k!$ different ways. We've counted each unique combination $k!$ times in our permutation calculation.
3. Divide to correct: To get the number of combinations, we divide the number of permutations by $k!$ to remove these duplicate orderings.

When to Use Combinations vs. Permutations

Photo by Ann H on Pexels

The most common point of confusion is deciding whether to use combinations or permutations. Here's a simple thought process:

graph TD
    A["Does the order of selection matter?"] -->|Yes| B["Use Permutations"]
    A -->|No| C["Use Combinations"]

Examples of Combinations

Photo by Laura Gigch on Pexels

• Choosing 3 toppings for a pizza from a list of 10. (The order you tell the server the toppings doesn't change the pizza.)
• Selecting 5 cards from a deck of 52 for a poker hand. (The order you receive the cards doesn't change your hand.)
• Forming a committee of 4 people from a group of 15. (All members are equal; their selection order is irrelevant.)

3. Worked Example

You have a group of 8 students, and you need to select a committee of 3 to organize a school event. How many different committees can be formed?

Here, the order in which you pick the students for the committee doesn't matter. A committee of "Student A, Student B, Student C" is the same as "Student C, Student A, Student B." So, we use combinations.

• $n = 8$ (total number of students)
• $k = 3$ (number of students to choose for the committee)

Using the combination formula:

$C(8, 3) = \frac{8!}{3!(8-3)!}$
$C(8, 3) = \frac{8!}{3!5!}$
$C(8, 3) = \frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1)(5 \times 4 \times 3 \times 2 \times 1)}$

We can cancel out $5!$ from the numerator and denominator:

$C(8, 3) = \frac{8 \times 7 \times 6}{3 \times 2 \times 1}$
$C(8, 3) = \frac{336}{6}$
$C(8, 3) = 56$

There are 56 different ways to form a committee of 3 students from a group of 8.

4. Key Takeaways

• Combinations are used when the order of selection doesn't affect the outcome or group.
• The formula for combinations is $C(n, k) = \frac{n!}{k!(n-k)!}$.
• Factorials ($n!$) represent the product of all positive integers up to $n$.
• Look for keywords like "choose," "select," "group," or "committee" to suggest combinations.
• If the problem implies distinct roles or positions, it's likely a permutation, not a combination.

Common Mistakes to Avoid

Photo by KATRIN BOLOVTSOVA on Pexels

• Confusing combinations with permutations: Always ask yourself if order matters.
• Incorrectly calculating factorials: $0!$ is defined as 1.
• Using the wrong values for n and k: Ensure $n$ is the total available and $k$ is the number being chosen.
• Forgetting to simplify the formula: You can often cancel out parts of the factorials to make calculations easier.

5. Now Try It

You're playing a card game and need to draw 4 cards from a standard deck of 52 cards. How many different 4-card hands are possible? Write down your steps and the final calculation. Success looks like correctly applying the combination formula and arriving at the numerical answer for the number of possible hands.