FW: half a chessboard?

[Wouter Meeussen]

-----Original Message-----
From:	BKA eunet (bkarnd) 
Sent:	Thursday, August 02, 2001 1:59 PM
To:	'seqfan at ext.jussieu.fr'
Subject:	half a chessboard?

hi,

number of non-descending paths cutting a (2n)x(2n) chessboard in two equal halves. (maybe 'committed path': path that is non-redescending)

total number of committed paths on such board = 4n choose 2n (well known)
number of halving paths using brute force :
{2, 8, 48, 390, 3656, 37834, 417540,4836452...} not in EIS, 

I'm looking for a more intelligent (combinatorial) way of counting 'm,
better than the following:
-----------------------------------------
let the dots represent the centres of the squares.
The saw starts at "s" and must pass thru "o".
In the first half, left from "o", any path s-o is feasible,
and the number of squares cut of can be represented by
the running sum (or total) of the Compositions[n,n+1]
because this generates all distributions of n items (rises) partitioned over n+1 slots.
 . . . .

 . . . .
    o
 . . . .

 . . . .
s


the rises from s to o can be
0,0,2
0,1,1
0,2,0
1,0,1
1,1,0
2,0,0
and there are of course 2n choose n of them.
The number of squares cut is the total of the
running sum of the all-but last:
0,0,2 +=0
0,1,2 +=1
0,2,2 +=2
1,1,2 +=2
1,2,2 +=3
2,2,2 +=4

now we need to count in how many ways we
can get totals of 0,..,n^2 
(and then simply convolute to account for the other half of the board)

        0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
       {1, 1} ,
       {1, 1, 2, 1, 1} ,
       {1, 1, 2, 3, 3, 3, 3, 2, 1, 1} ,
       {1, 1, 2, 3, 5, 5, 7, 7, 8, 7, 7, 5, 5, 3, 2, 1, 1} 
        ...
**** I can't smartly generate this last table, 
**** and so that's where I can only resort to brutalities:

Table[(#.Reverse[#])&@(Length/@Split[Sort[Apply[Plus,Drop[#,-1]]&/@(FoldList[Plus,First[#],Rest[#]]&/@Compositions[n,n+1])]]),{n,1,8}]

{2, 8, 48, 390, 3656, 37834, 417540, 4836452}

can you show me how it should be done?

Wouter Meeussen
tel +32 (0)51 33 21 24
fax +32 (0)51 33 21 75
wouter.meeussen at vandemoortele.com