Mostly to Jon Perry:
Consider a tower of height n on the left hand side of a square, and we wish to create a horizontal line along the bottom of the square.
We can push any block at the top of a column 1 space to the right, and then gravity takes over.
How many ways can we do this?
So far I have for n=1, 0,1,2,5, and I guess n=5 is 15 (Catalan numbers? A000108)
If we label the blocks for convience, then the 5 options for n=4 are:
444332 444322 443222 433222 433322
You missed some for n=4. How many depends on exactly what you want to count. If you're just interested in the number of possible arrangements at the end, then there are 6; the missing one is given by 433342. But there are other sequences of moves that lead to the same final arrangements as some of the above. If I haven't made any mistakes, there are 10 ways to move the blocks; each is shown here along with the final arrangement on the bottom row: 433222 1432 433232 1423 433322 1423 433342 1243 443222 1342 443242 1324 443422 1324 443432 1234 444322 1324 444332 1234 In general, with n blocks, we can get any permutation along the bottom row that has 1 in the leftmost position, so the number of final arrangements is (n-1)!. (Use induction on n: First move the top n-2 blocks to the bottom row, in the desired order. Then push some of them 1 space to the right, leaving a gap that block 2 can be pushed into.) I don't know how many possible sequences of moves there are. Dean Hickerson dean@math.ucdavis.edu