November 2007: The lineup (solution)

The sequence must terminate with a 0 or 9, and as we move from right to left, we always have a choice between the highest unused digit or the lowest--until we hit the left end where these two choices coincide. Thus, there are two choices at each of nine opportunities, i.e., 2⁹=512 ways.

November 2007: The lineup

How many ways are there to write the numbers 0 through 9 in a row, such that each number other than the left-most is within one of some number to the left of it?