Counting: arrangements, selections and restrictions

The multiplication principle

If a task is a sequence of choices, with $m$ options for the first and $n$ for the second whatever the first was, the task can be done in $m \times n$ ways. Almost every counting question is this principle in some form. Draw one slot per choice, write the number of options in each slot, and multiply. A code of one letter from A to E followed by two different digits has $5 \times 10 \times 9 = 450$ possibilities: the second digit has only 9 options because it must differ from the first.

Fill restricted slots first

When some positions carry conditions, fill those slots first, because a condition can only shrink the options. For a four-digit number the first digit cannot be 0; for an even number the last digit must be even. When two conditions interact (the last digit might be 0, which affects the first digit), split into cases.

Order matters: permutations

Arranging $r$ of $n$ different items in order is a slot problem with shrinking options:

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

Arranging all $n$ items gives $n!$. Know the small factorials: $3! = 6$, $4! = 24$, $5! = 120$, $6! = 720$, $7! = 5040$.

Order does not matter: combinations

Choosing $r$ of $n$ items when order is irrelevant (a committee, a hand of cards, toppings) counts each group once instead of $r!$ times:

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

Compute by cancelling, never by multiplying out factorials: $\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$. Choosing $r$ to take is the same as choosing $n - r$ to leave, so $\binom{10}{7} = \binom{10}{3}$.

To decide which applies, swap two of the chosen items. If the swap gives a different outcome (president and treasurer exchanged), order matters. If it gives the same outcome (two committee members exchanged), it does not.

Identical items

Arranging $n$ items of which $a$ are identical, $b$ are identical among themselves, and so on, gives

$$\frac{n!}{a!\,b!\,\cdots}$$

because swapping identical items does not create a new arrangement, so each distinct arrangement was counted $a! \times b! \times \cdots$ times among the $n!$.

Restrictions

• Must be together. Glue the items into one block, arrange the block with the others, then multiply by the ways to arrange the items inside the block.
• Must be apart. Count all arrangements and subtract those in which they are together.
• At least one. Count all selections and subtract those with none. Counting directly ("pick one woman, then anyone") counts some groups more than once.

Keep the numbers small

Answer choices for counting questions are often far apart, so a sensible estimate of the size of the answer rules out several. Before multiplying, check whether a product such as $\frac{8 \times 7 \times 6}{3 \times 2}$ cancels first: it is $8 \times 7 = 56$.