Counting and Combinatorics

How Many Ways?

Combinatorics answers "how many ways?" — how many passwords, how many committees, how many outcomes. It underpins probability, algorithm analysis, and cryptography. Two basic rules build everything:

• Sum rule — if one choice can be made in $m$ ways or another in $n$ ways (mutually exclusive), there are $m + n$ ways total.
• Product rule — if one choice is made in $m$ ways and then another in $n$ ways, there are $m \times n$ ways. "And" multiplies; "or" adds.

Two headline formulas count arrangements and selections:

• Permutations count ordered arrangements. The number of ways to arrange all $n$ distinct items is $n!$ ($n$ factorial $= n \times (n-1) \times \dots \times 1$). Choosing and ordering $k$ from $n$ is $P(n,k) = \frac{n!}{(n-k)!}$.
• Combinations count unordered selections — how many $k$-element subsets of $n$, written $C(n,k) = \binom{n}{k} = \frac{n!}{k!\,(n-k)!}$.

The single most important distinction is order. If rearranging the chosen items gives a different outcome (a race podium, a password), use permutations; if order is irrelevant (a committee, a hand of cards), use combinations. Combinations are smaller — dividing by $k!$ removes the $k!$ orderings of each selection that permutations counted separately.

Common pitfall: using a permutation where order does not matter (or vice versa), and mixing up the sum vs product rule. If order is irrelevant — a committee, a subset, a poker hand — use combinations $\binom{n}{k}$, not permutations. And "and" (sequential choices) multiplies while "or" (alternative choices) adds — reaching for the wrong one inflates or deflates the count by a lot.