Counting problems: restrictions, cases and the complement

The plan for any counting problem

A counting problem usually adds one twist to the formulas of permutations and combinations: a digit that cannot be zero, two people who refuse to sit next to each other, a team that needs at least one person of some kind. Four tools handle nearly all of these:

1. Fill the restricted places first, then the free ones.
2. Glue objects that must stay together into one block.
3. Split into separate cases and add them (the sum rule).
4. Count the complement: everything, minus what you do not want.

Then check with a second tool. Tools 3 and 4 are natural partners: a complement answer can be confirmed by adding the cases, and the other way round.

Restricted places first

If one position has a condition, deal with it before the others, while the number of choices is still easy to see. To count three-digit numbers with distinct digits, start with the hundreds digit: it cannot be 0, so 9 choices; then the tens digit has 9 (any digit except the one used, and 0 is now allowed); then the units digit has 8. That gives $9 \times 9 \times 8 = 648$. Starting from the units digit would leave you unsure whether 0 was still available for the hundreds place.

Together: the block method

When two people must sit side by side, tie them into one block. With 6 people in a row and two who must be adjacent, you arrange 5 units (the block and 4 others) in $5! = 120$ ways, and the two inside the block can stand in $2! = 2$ orders: $240$ arrangements. Forgetting the factor $2$ for the inside of the block is the commonest slip.

Apart: complement or gaps

"Must not be adjacent" is the complement of "must be adjacent": all arrangements minus the adjacent ones. With 6 people that is $720 - 240 = 480$.

The gap method gives the same answer by a second route. Arrange the other 4 people first: $4! = 24$ ways. They leave 5 gaps: one before the first person, three between neighbours and one after the last. Put the two people into 2 different gaps, in order: $5 \times 4 = 20$. Total $24 \times 20 = 480$. Two routes, one answer: you can trust it.

"At least one": go round the back

"At least one" covers many cases (exactly one, exactly two, and so on), but its complement is a single case: none. So

$$\text{at least one} = \text{all} - \text{none}.$$

For a 4-person team from 5 women and 4 men with at least one woman: all teams $\binom{9}{4} = 126$, teams with no woman $\binom{4}{4} = 1$, so $125$.

The overcounting trap in "at least one"

A tempting shortcut is "choose the one woman who must be there, then choose the rest from everybody": $5 \times \binom{8}{3} = 5 \times 56 = 280$. It is far too big, more than the 126 teams that exist at all. A team with two women is counted twice, once for each woman playing "the required one". Whenever your answer exceeds the total with no restriction, a case has been counted more than once.

Cases, and when to add

Split by a feature that separates the outcomes cleanly, such as the number of women, the last digit or the first letter. Every outcome must land in exactly one case. Then add. Inside each case, use the product rule.

Counting digits and numbers

Numbers bring their own restrictions. A leading digit cannot be 0. "Even" fixes the last digit to 0, 2, 4, 6 or 8, and when digits must be distinct, 0 in the last place changes the count for the first place, so even numbers with distinct digits often need two cases: last digit 0, and last digit 2, 4, 6 or 8.

A sense of size

Before choosing, compare your answer with the total without any restriction. A restricted count must be smaller; a complement must be smaller still when the unwanted case is rare. Rough size checks like these catch most errors on a test where there is no calculator and no going back once you move to the next screen.