Combinatorics

Counting without listing — permutations, combinations, the pigeonhole principle, and the binomial coefficients behind probability and algebra alike.

Pascal's triangle: each entry C(n,k) counts ways to choose k items from n

121

1331

14641

15101051

Highlighted: C(5,2) = 10. Order does not matter when choosing.

Definition

Combinatorics is the art of counting without listing everything out. The two core tools:

Permutations: arrangements where order matters. The number of ways to arrange $n$ distinct items is $n! = n \times (n-1) \times \cdots \times 1$ .
Combinations: selections where order doesn't matter. The number of ways to choose $k$ items from $n$ is $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ , read "n choose k."

Permutation vs. combination

Choosing a president and vice-president from 5 candidates (order matters — these are different roles): $5 \times 4 = 20$ ways.

Choosing a 2-person committee from the same 5 candidates (order doesn't matter): $\binom{5}{2} = \frac{5!}{2!3!} = 10$ ways — half as many, because each pair was counted twice in the first count.

Try it

How many ways can you arrange the letters A, B, C in a row?

Solution

$3! = 3 \times 2 \times 1 = 6$ ways: ABC, ACB, BAC, BCA, CAB, CBA.

Related concepts

Needs first

Order of Operations

Graph Theory Basics Probability

View in full concept graph →