Combinations

A combination is an unordered selection of objects. Order does NOT matter!

The Formula

Choosing $k$ objects from $n$ without regard to order:

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

Example: Choosing 3 people from 10:

$$\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$$

Permutation vs Combination

Why Divide by k!?

Permutations count each selection $k!$ times (all orderings). To get combinations, divide by $k!$.

Example: Choosing {A, B, C}:

• Permutations: ABC, ACB, BAC, BCA, CAB, CBA (6 ways)
• Combinations: {A, B, C} (1 way)
• Relationship: $\frac{6}{3!} = 1$

Binomial Coefficients

The notation $\binom{n}{k}$ is read as “n choose k” and called a binomial coefficient.

Properties:

• $\binom{n}{0} = \binom{n}{n} = 1$
• $\binom{n}{k} = \binom{n}{n-k}$
• $\binom{n}{1} = n$

Example: Lottery

In a lottery, you choose 6 numbers from 49. How many possible tickets?

$$\binom{49}{6} = \frac{49!}{6! \cdot 43!} = 13,983,816$$