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(a)math.ucdavis.edu
