+586 Six cars pull up to a red light, one at a time. At the light, there are three lanes, one left-turn lane, one straight-going lane, and one right-turn lane. How many ways can the cars stack up so that all three lanes are occupied?
Note that if the first car turns left and the second goes straight, this is considered different from the first car going straight and the second car turning left. In other words, the cars are distinguishable, but pull up to the intersection in a fixed order.
+6250 \(\text{Each driver has 3 choices as the arrive}\\ \text{The total number of arrangements is $\dbinom{3}{3}3^6=729$}\\~\\ \text{There are $\dbinom{3}{2}2^6 = 192$ arrangements with 1 lane empty}\\ \text{There are $\dbinom{3}{1}1^6 = 3$ arrangements with 2 lanes empty}\\~\\ \text{Thus there are $729-192-3 = 534$ arrangements with all lanes occupied}\)
.
