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.

We count the number of ways that some lane can be left empty, and subtract from the total:

Each driver has three choices, so it's .

Now, we count the ways where at least 1 lane is left empty:

But we have double-counted the situations where two lanes are left empty. Since each driver only has one choice, there are situations we overcount. This leaves ways to fill all three lanes.

Also, you took this question directly from Alcumus. The source is AoPS Staff they wrote this problem, and might request this post be taken down since you technically are not allowed to post Alcumus problems on the internet or their own forums.