FW: half a chessboard?
Wouter Meeussen
w.meeussen.vdmcc at vandemoortele.be
Thu Aug 2 15:05:48 CEST 2001
-----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
More information about the SeqFan
mailing list