Problem Solving with Permutations and Combinations

TL;DR

Permutations are about arrangements where order matters, while combinations are selections where order doesn't. You need to identify whether order matters to choose the correct method for counting possibilities. Mastering these concepts helps you count arrangements and selections accurately in various scenarios.

1. The Mental Model

Imagine you're picking items. Sometimes, putting them in a different order changes the outcome (like a password). Other times, the order doesn't matter (like picking fruit for a salad). This "order matters or not" distinction is key.

2. The Core Material

When solving problems involving permutations and combinations, the first step is always to determine if the order of the items being arranged or selected makes a difference. If it does, you're looking at a permutation. If it doesn't, you're dealing with a combination.

Identifying Permutations (Order Matters)

Photo by Brett Jordan on Pexels

Use permutations when the arrangement or sequence of items is important. Think about:
* Arranging people in a line.
* Forming passwords or security codes.
* Awarding 1st, 2nd, and 3rd place in a race.

The formula for permutations of $n$ items taken $r$ at a time is:
$P(n, r) = \frac{n!}{(n-r)!}$

Identifying Combinations (Order Doesn't Matter)

Photo by Brett Jordan on Pexels

Use combinations when you're selecting a group of items and the order in which they are chosen doesn't change the group itself. Think about:
* Choosing members for a committee.
* Selecting cards for a hand.
* Picking toppings for a pizza.

The formula for combinations of $n$ items taken $r$ at a time is:
$C(n, r) = \frac{n!}{r!(n-r)!}$

Notice that the combination formula is the permutation formula divided by $r!$, which accounts for the different ways the $r$ selected items can be arranged among themselves (since order doesn't matter for combinations).

graph TD
    A["Start: Counting Problem"] --> B{Does "order" matter?};
    B -- "Yes, order matters" --> C["Use Permutations"];
    B -- "No, order doesn't matter" --> D["Use Combinations"];
    C --> E["P(n, r) = n! / (n-r)!"];
    D --> F["C(n, r) = n! / (r!(n-r)!)"];
    E --> G["Calculate the number of arrangements."];
    F --> G;
    G --> H["End"];

Dealing with Repetition

Photo by Ann H on Pexels

Sometimes, you might have identical items.
* Permutations with Repetition: If you have $n$ items where $n_1$ are identical, $n_2$ are identical, and so on, the number of distinct permutations is $\frac{n!}{n_1!n_2!...n_k!}$. Example: arranging letters in "MISSISSIPPI".
* Combinations with Repetition: This is a bit more complex and less common in basic problems. It's like picking items from a set where you can pick the same item multiple times. The formula is $C(n+r-1, r)$.

3. Worked Example

Let's say you have 10 unique books.

Problem:
a) How many ways can you arrange 4 of these books on a shelf?
b) How many ways can you choose 4 of these books to donate to a library?

Solution:

a) Arranging books on a shelf: The order matters here (arranging books A, B, C, D is different from A, C, B, D). So, we use a permutation.
$n = 10$ (total books)
$r = 4$ (books to arrange)

$P(10, 4) = \frac{10!}{(10-4)!} = \frac{10!}{6!} = 10 \times 9 \times 8 \times 7 = 5040$ ways.

b) Choosing books to donate: The order doesn't matter here (picking books A, B, C, D is the same as picking D, C, B, A; it's still the same set of books). So, we use a combination.
$n = 10$ (total books)
$r = 4$ (books to choose)

$C(10, 4) = \frac{10!}{4!(10-4)!} = \frac{10!}{4!6!} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = \frac{5040}{24} = 210$ ways.

4. Key Takeaways

• Always ask yourself: "Does the order of selection/arrangement matter?"
• Use permutations when order is significant (e.g., arrangements, rankings, codes).
• Use combinations when order is not significant (e.g., selections, groups, committees).
• Factorials ($n!$) represent the number of ways to arrange $n$ distinct items.
• Be careful when problems involve "at least" or "at most" conditions, often requiring summing multiple cases or using the complement.

Common Mistakes:
- Forgetting to identify if order matters, leading to using the wrong formula.
- Mixing up $n$ and $r$ in the formulas. $n$ is always the total number of items available, and $r$ is the number you're selecting or arranging.
- Not accounting for identical items when they are present in a permutation problem.
- Incorrectly simplifying factorial expressions, especially in the denominator.

5. Now Try It

A club has 12 members.

a) In how many ways can they choose a president, a vice-president, and a treasurer?
b) In how many ways can they choose a committee of 3 members?

Think about whether the roles (president, vice-president, treasurer) imply order, versus a committee where everyone is just a "member." Calculate both answers. Success looks like you correctly identifying the method for each part and arriving at the correct numerical answer.