Permutation and combination

The formula for combinations is used when we want to select items from a larger group, and the order of selection does not matter.

The formula is written as $C(n, r)$ or $\binom{n}{r}$ (read as "n choose r").

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

1. What the Symbols Mean

• $n$ (Total Number): The total number of items available to choose from.

• $r$ (Selection Size): The number of items you are choosing.

• $!$ (Factorial): This means multiplying a series of descending natural numbers.

  • Example: $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.

---

2. The Logic Behind the Formula

To understand why the formula works, it helps to break it down into two steps: Permutation (where order matters) and Correction (removing the order).

Step 1: The Numerator (Permutations)

$\frac{n!}{(n-r)!}$

Imagine you are picking 3 winners from 10 people for Gold, Silver, and Bronze medals. Here, the order matters (Alice-Bob-Charlie is different from Charlie-Bob-Alice).

• First pick: 10 options.

• Second pick: 9 options.

• Third pick: 8 options.

• Mathematically, this is $10 \times 9 \times 8$.

• This is equivalent to $\frac{10!}{(10-3)!}$ or $\frac{n!}{(n-r)!}$.

Step 2: The Denominator (The Correction)

$\frac{1}{r!}$

In a lottery or a card hand, the order doesn't matter. "1, 2, 3" is the same winning ticket as "3, 2, 1".

The permutation formula in Step 1 counts "1, 2, 3" and "3, 2, 1" as different outcomes. We have overcounted! To fix this, we must divide by the number of ways you can arrange the chosen items among themselves.

• If you picked $r$ items, there are $r!$ ways to arrange them.

• Dividing by $r!$ removes these "duplicate" arrangements, leaving you with just the unique groups.

---

3. A Simple Example

Let's say you have 3 letters: A, B, C, and you want to choose 2 of them.

Using the Logic (Step-by-Step):

1. Permutations (Order matters): AB, BA, AC, CA, BC, CB. (6 ways)

2. Redundancy: Notice that AB and BA are the same pair. AC and CA are the same pair.

3. Correction: Divide by $2!$ (which is 2) to remove the duplicates.

4. Result: {A,B}, {A,C}, {B,C}. (3 ways)

Using the Formula:

$n=3, r=2$

$C(3, 2) = \frac{3!}{2!(3-2)!}$

$= \frac{3 \times 2 \times 1}{(2 \times 1) \times (1)}$

$= \frac{6}{2} = 3$

Summary

• $n!$ represents the total arrangements of all items.

• $(n-r)!$ removes the items we didn't pick.

• $r!$ removes the specific order of the items we did pick, leaving us with just the groups.