Ricardo wants to arrange three $1 \mathrm{~s}$, three $2 \mathrm{~s}$, two $3 \mathrm{~s}$, and one 4 to form nine-digit positive integers with the properties that

- when reading from left to right, there is at least one 1 before the first 2 , at least one 2 before the first 3 , and at least one 3 before the 4 , and
- no digit 2 can be next to another 2 .

(For example, the integer 121321234 satisfies these properties.) In total, how many such nine-digit positive integers can Ricardo make?
(A) 278
(B) 260
(C) 254
(D) 272
(E) 266
Suppose that $N$ is an integer that satisfies the given properties.

The first digit of $N$ must be a 1 , since there must be at least one 1 before the first 2 , at least one 2 before the first 3 , and at least one 3 before the 4 , which means that we cannot have a 2 , a 3 , or a 4 before the first 1 .

Since there are three $1 \mathrm{~s}$ in $N$, then $N$ can begin with 1,11 or 111.

The first digit of $N$ that is not a 1 must be a 2 .

Thus, $N$ begins 12, 112, or 1112.

Case 1: $N$ begins 12

Since no two $2 \mathrm{~s}$ can be next to each other, we next place the remaining two $2 \mathrm{~s}$.

Reading from the left, these $2 \mathrm{~s}$ can go in positions 4 and 6,4 and 7, 4 and 8, 4 and 9,5 and 7, 5 and 8,5 and 9,6 and 8,6 and 9 , or 7 and 9 .

In other words, there are 10 possible pairs of positions in which the $2 \mathrm{~s}$ can be placed.

Once the $2 \mathrm{~s}$ are placed, there are 5 positions left open.

Next, we place the remaining two $1 \mathrm{~s}$.

If we call these 5 positions $\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}, \mathrm{E}$, we see that there are 10 pairs of positions in which the 1s can be placed: A and B, A and C, A and D, A and E, B and C, B and D, B and E, C and $\mathrm{D}, \mathrm{C}$ and $\mathrm{E}, \mathrm{D}$ and $\mathrm{E}$.

This leaves 3 positions in which the two 3 s and one 4 must be placed. Reading from the left, a 3 must be placed in the first empty position, since there must be a 3 before the 4 .

This leaves 2 positions, in which the remaining digits (3 and 4) can be placed in any order; there are 2 such orders ( 3 and 4 , or 4 and 3 ).

In this case, there are $10 \times 10 \times 2=200$ possible integers $N$.

Case 2: $N$ begins 112

Since no two $2 \mathrm{~s}$ can be next to each other, we next place the remaining $2 \mathrm{~s}$.

Reading from the left, these 2s can go in positions 5 and 7,5 and 8,5 and 9,6 and 8, 6 and 9, or 7 and 9 .

In other words, there are 6 possible pairs of positions in which the $2 \mathrm{~s}$ can be placed.

Once the $2 \mathrm{~s}$ are placed, there are 4 positions left open.

Next, we place the remaining 1 . There are 4 possible positions in which the 1 can be placed.

This leaves 3 positions in which the two 3 s and one 4 must be placed. Reading from the left, a 3 must be placed in the first empty position, since there must be a 3 before the 4 .

This leaves 2 positions, in which the remaining digits (3 and 4) can be placed in any order; there are 2 such orders.

In this case, there are $6 \times 4 \times 2=48$ possible integers $N$.

Case 3: $N$ begins 1112

Since no two $2 \mathrm{~s}$ can be next to each other, we next place the remaining $2 \mathrm{~s}$.

Reading from the left, these $2 \mathrm{~s}$ can go in positions 6 and 8,6 and 9 , or 7 and 9 .

In other words, there are 3 possible pairs of positions in which the $2 \mathrm{~s}$ can be placed.

Once the 2 s are placed, there are 3 positions left open with only the two 3 s and the 4 remaining to be placed.

Reading from the left, a 3 must be placed in the first empty position, since there must be a 3 before the 4 .

This leaves 2 positions, in which the remaining digits (3 and 4) can be placed in any order; there are 2 such orders.

In this case, there are $3 \times 2=6$ possible integers $N$.

Combining the three cases, we see that there are $200+48+6=254$ possible integers $N$.