Permutations and Combinations

When calculating probabilities, you often need to figure out exactly how many ways a certain event can happen. This is where permutations and combinations come in. They are powerful mathematical tools used to count the number of ways to arrange or select items from a larger group.

The Fundamental Counting Principles

Before diving into formulas, it helps to understand two basic rules of counting:

• The Multiplication Principle (AND): If you must make one choice and then another choice, you multiply the number of options. If event A can happen in $m$ ways and event B can happen in $n$ ways, both events happen in $m \times n$ ways.
• The Addition Principle (OR): If you can make one choice or another choice (but not both), you add the number of options. If event A can happen in $m$ ways and event B in $n$ ways, either A or B happens in $m + n$ ways.

Permutations (Order Matters)

A permutation is an arrangement of items where the order is important. For example, a password of "123" is fundamentally different from "321".

The number of ways to arrange $r$ items chosen from a total of $n$ distinct items is given by the formula:

$^n P_r = \frac{n!}{(n-r)!}$

(Note: $n!$ is read as "n factorial" and means multiplying all positive integers from $n$ down to 1. For example, $4! = 4 \times 3 \times 2 \times 1 = 24$.)

Example: How many ways can 5 books be arranged on a shelf from 8 books? Since arranging books on a shelf implies a specific order (left to right), we use permutations. Here, $n = 8$ and $r = 5$.

$^8 P_5 = \frac{8!}{(8-5)!} = \frac{8!}{3!} = 8 \times 7 \times 6 \times 5 \times 4 = 6,720$

There are 6,720 ways to arrange the books.

Combinations (Order Doesn't Matter)

A combination is a selection of items where the order does not matter. For example, a team consisting of Alice and Bob is the exact same team as Bob and Alice.

The number of ways to choose $r$ items from $n$ distinct items is given by the formula:

$^n C_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Notice that this formula is just the permutation formula divided by $r!$. We divide by $r!$ to remove the duplicate arrangements of the same chosen items.

Example: How many committees of 4 can be formed from 10 people? A committee is just a group of people; there are no specific roles mentioned, so the order in which they are selected doesn't matter. We use combinations. Here, $n = 10$ and $r = 4$.

$^{10} C_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} = 210$

There are 210 different committees possible.

Summary: How to Choose?

When faced with a counting problem, ask yourself one simple question: "Does changing the order change the outcome?"

• If Yes, use Permutations (e.g., passwords, rankings, arranging items in a row).
• If No, use Combinations (e.g., forming a team, drawing a hand of cards, picking toppings for a pizza).