Problem: How many of the rearrangements of the digits 123456 have the property that for each digit, no more than two digits smaller than that digit appear to the right of that digit? For example, the rearrangement 315426 has this property because digits 1 and 2 are the only digits smaller than 3 which follow 3 , digits 2 and 4 are the only digits smaller than 5 which follow 5 , and digit 2 is the only digit smaller than 4 which follows 4 . Solution: Notice that there is a great control we get by placing the digits from greatest to least in our empty string _ _ _ _ _ _. Say we want to place the $6$. Then, we know that $6$ must go in spot $5$ or $6$, otherwise, two smaller numbers must proceed it. So, we have two choices for the $6$. Once we place $6$, we need not worry about it, and we ask, how many spots can we place the $5$? Again, there are two ways to place $5$ (the two leftmost open slots). Likewise, there are two ways to place the $4$ and then two ways to place the $2$. Then, there are two ways to place the $2$. Hence, the answer is $3^4 \cdot 2 = 162$.