Counting question regarding ways to attain at least two adjacent spaces in a row of 16 spaces.

combinatoricsinclusion-exclusionprobability

A parking lot has 16 spaces in a row. Twelve cars arrive, each of which requires one parking space, and their drivers chose spaces at random from among the available spaces. Auntie Em then arrives in her SUV, which requires 2 adjacent spaces. What is the probability that she is able to park?

This question is from the 2008 AMC 12b, and I'm trying to solve it using PIE. I keep getting the wrong answer, but I can't figure out why it's wrong.

What I did:

The total number of ways the cars can park is $\binom{16}{4}$.

In order to count the ways Auntie Em can park, I first counted the ways in which there are at least two adjacent empty parking spaces using PIE. For this, I got $15\binom{14}{2}$ because there are 15 ways to choose the two adjacent parking spots and $\binom{14}{2}$ ways to choose the ways the 12 cars can park in the remaining 14 parking spots.

I then subtracted $14\binom{13}{1}$ because there's 14 ways to choose three adjacent parking spots, and $\binom{13}{1}$ ways to let the 12 vehicles park in the remaining 13 spots.

Since we counted the four adjacent parking spots $3-2=1$ time, I don't have to add or subtract the case where there are at least four adjacent parking spots.

I then got: $\frac{15\binom{14}{2}-14\binom{13}{1}}{\binom{16}{4}}$, which doesn't simplify to $\frac{17}{28}$ (which is the answer). What did I do wrong?

Best Answer

You have to account for pairs of adjacent empty spaces rather than consecutive empty spaces.

Let's focus on the four empty spaces that remain once the twelve cars have parked. We wish to find the probability that there are at least two adjacent empty spaces among those four.

A pair of adjacent empty spaces: There are $15$ places for a block of two empty spaces to begin. Once they have been selected, there are $\binom{14}{2}$ ways to select the positions of the other two empty spaces, giving an initial count of $$\binom{15}{1}\binom{14}{2}$$ arrangements with four empty spaces that include two adjacent empty spaces.

However, we have counted those arrangements in which there are two pairs of adjacent empty spaces twice, once for each way of designating one of those pairs of adjacent empty spaces as the pair of adjacent empty spaces. We only want to count those arrangements once, so we must subtract those arrangements in which there are two pairs of adjacent empty spaces.

Two pairs of adjacent empty spaces: This can occur in two ways. The pairs can overlap, in which case there are three consecutive empty spaces, or be disjoint.

Two overlapping pairs of adjacent empty spaces: This includes a block of three consecutive adjacent empty spaces. The block must begin in one of the first $14$ positions. That leaves $13$ positions in which to place the remaining empty space. Thus, there are $$\binom{14}{1}\binom{13}{1}$$ such arrangements.

Two disjoint pairs of adjacent empty spaces: We have $14$ objects to arrange, two blocks of two empty spaces and $12$ occupied spaces. Choose which two of those $14$ positions will be filled with the blocks, which can be done in $$\binom{14}{2}$$ ways.

If we subtract those arrangements in which there are two pairs of adjacent empty spaces from the total, we will not have counted those arrangements in which there are three pairs of adjacent empty spaces at all. This is because we first added them three times, once for each way we could designate one of those three pairs as the pair of adjacent empty spaces, and subtracted them three times, once for each way of the $\binom{3}{2}$ ways we could designate two of those three pairs as the pairs of adjacent empty spaces. Thus, we must add those arrangements with three pairs of adjacent empty spaces to the total.

Three pairs of adjacent empty spaces: This can only occur if there are four consecutive empty spaces. A block of four consecutive empty spaces must begin in one of the first $13$ positions.

Since there are $\binom{16}{4}$ ways to select four empty parking places, the probability that Auntie Em can park is $$\frac{\dbinom{15}{1}\dbinom{14}{2} - \dbinom{14}{1}\dbinom{13}{1} - \dbinom{14}{2} + \dbinom{13}{1}}{\dbinom{16}{4}}$$