Counting: permutations, combinations and Venn diagrams

The multiplication principle

Almost every counting question reduces to one idea. If a task is done in stages, with $a$ ways to do the first stage and, for each of those, $b$ ways to do the second, then the whole task can be done in $a \times b$ ways. The rule extends to any number of stages.

A café offers 4 sandwiches, 3 drinks and 2 desserts. A meal of one of each can be chosen in $4 \times 3 \times 2 = 24$ ways. Draw one slot per stage, write the number of choices in each slot, and multiply.

Use addition instead when the cases are alternatives that cannot happen together: if a meal is either a sandwich (4 options) or a salad (3 options), there are $4 + 3 = 7$ choices. "And" between stages multiplies; "or" between separate cases adds.

Factorials and arranging everything

The number of ways to arrange $n$ different objects in a row is

$$n! = n \times (n-1) \times \cdots \times 2 \times 1,$$

because there are $n$ choices for the first place, $n - 1$ for the second, and so on. By definition $0! = 1$. Factorials grow fast: $5! = 120$, $6! = 720$, $8! = 40\,320$.

Permutations: order matters

When you choose $r$ objects from $n$ and the order matters (first, second and third prize; a president and a treasurer; a code), the count is

$$P(n, r) = n \times (n-1) \times \cdots \times (n - r + 1) = \frac{n!}{(n-r)!}.$$

Choosing a gold, silver and bronze winner from 10 runners: $10 \times 9 \times 8 = 720$ ways. In practice you rarely need the formula: fill the slots and multiply.

Combinations: order does not matter

When you choose a group, where swapping members gives the same group (a committee, a hand of cards, a set of toppings), each group of $r$ has been counted $r!$ times by the slot method. Divide that out:

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

Choosing 3 runners to advance from 10: $\frac{720}{3!} = \frac{720}{6} = 120$ groups. Two facts save time: $\binom{n}{r} = \binom{n}{n-r}$, because choosing who is in is the same as choosing who is out, and $\binom{n}{1} = n$, $\binom{n}{n} = 1$.

The test for order: swap two of the chosen items. If the outcome is different (different roles, positions or sequence), order matters. If it is the same, it does not.

Restrictions

• Fill restricted places first. If a code must start with a vowel, count the first slot's choices before the others.
• Items that must stay together: glue them into one block, arrange the block with the other items, then multiply by the number of orders inside the block.
• Items that must stay apart: count all arrangements and subtract those where they are together.
• "At least one": count everything and subtract the outcomes with none.
• Identical items: arranging $n$ objects where $a$ are identical to each other and $b$ are identical to each other gives $\frac{n!}{a!\,b!}$ arrangements, since swapping identical items changes nothing.

Groups that overlap: Venn diagrams

When people or objects can belong to two groups at once, adding the two group sizes counts the overlap twice. Correct for it once:

$$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$

Here $n(\cdot)$ means "the number in". Everyone not in either group is $\text{total} - n(A \cup B)$. Drawing two overlapping circles and filling in the overlap first, then "A only" and "B only", then "neither", turns most of these questions into subtraction.

Region	How to get it
both	given, or $n(A) + n(B) - n(A \cup B)$
A only	$n(A) - \text{both}$
B only	$n(B) - \text{both}$
neither	$\text{total} - n(A \cup B)$

Checking an answer

Counting answers are hard to check by recomputing the same way, so look for a second route: count the complement, or try a smaller version you can list by hand. With 4 people choosing 2, there are $\binom{4}{2} = 6$ pairs, and you can write all six down.