7.3 Counting with restrictions

The counting rule in Module 7.1 and the permutation formula in Module 7.2 count arrangements when choices are freely available. A restriction changes the problem: perhaps two objects must stay together, the first digit cannot be zero, or the last digit must be even. We need to count valid outcomes, without including forbidden ones or counting any valid one twice.

This is intermediate combinatorics. Start with OpenStax's restricted selection examples; MIT's counting notes provide further practice. First decide what makes two arrangements different, then describe the restriction in those terms.

A basic idea: build only what is allowed

Suppose five distinct books include $A$ and $B$, which must be adjacent on a shelf. Treat $A$ and $B$ temporarily as one block. We now arrange four objects: the block and the other three books. That gives $4!$ orders. Inside the block, $A$ and $B$ can appear as $AB$ or $BA$, so the valid total is $2\cdot4!=48$.

A quick tour of methods

Make a block when specified objects must be together. Count their internal orders separately. This works only when the block really occupies consecutive positions.

Split into disjoint cases when a restriction changes later choices. For an even last digit, the cases “last digit is $0$” and “last digit is $2$” do not overlap; multiply within each case, then add. A single product would be wrong if the first-digit choices differ between those cases.

Use the complement when forbidden arrangements are easier to count: valid $=$ all $-$ forbidden. If there are several forbidden conditions that overlap, subtracting each separately can remove some outcomes twice. Use the overlap rule from Module 8.5 or make disjoint cases instead.

There is no formula that replaces this setup step. Before doing arithmetic, state what each case counts and why every valid outcome belongs to exactly one case.

Application 1: adjacent books

Five distinct books $A,B,C,D,E$ are arranged on a shelf. How many orders have $A$ and $B$ together?

1. Replace $A,B$ by one block. The block, $C$, $D$, and $E$ can be arranged in $4!=24$ ways.
2. Within the block, choose $AB$ or $BA$: $2$ ways.
3. Multiply to get $24\cdot2=48$. Each shelf order gives one block position and one internal order, so none is duplicated.

Application 2: even four-digit numbers

Use each of the digits $0,1,2,3$ exactly once to make a four-digit even number. How many are possible?

1. If the last digit is $0$, arrange $1,2,3$ in front: $3!=6$ numbers.
2. If the last digit is $2$, the first digit is $1$ or $3$ ($2$ choices); arrange the other two digits in the middle ($2!$ choices): $2\cdot2=4$ numbers.
3. The cases are separate and complete, so the answer is $6+4=10$. Counting $3!$ in the second case would wrongly allow a leading zero.