half a chessboard : solved

[Wouter Meeussen]

to Neil : I'll format 'm shortly.

the problem restated:
consider a 2n*2n chessboard.

In how many ways can it be cut in two pieces by a (saw) line so that:
both pieces have area 2n^2
the line starts in the lower left corner and moves right or up (= non-descending)

answer:
we need the Ferrers-plot of the partitions of 2n^2 that fit within a 2n * 2n box:

res=Table[Length at Select[Partitions[2n^2 ],Length[#]<=2n && First[#]<=2n&],{n,1,5}]
Out[]=  {2, 8, 58, 526, 5448}

this can be done with a smarter recursion using T[n,a,b] as defined at the bottom

seq=Table[T[2n^2,2n,2n],{n,0,24}]
Out[]=
{1, 2, 8, 58, 526, 5448, 61108, 723354, 8908546, 113093022, 1470597342, 
19499227828, 262754984020, 3589093760726, 49596793134484, 692260288169282, 
9747120868919060, 138298900243896166, 1975688102624819336, 
28396056820503468894, 410363630540693436398, 5959655019225784501068, 
86939455386909569830784, 1273457852883917610870526, 
18722947389749571043063270}

If we also force the (saw) line to pass through the centre of the chessboard, then we can use
the brute-force construction from my initial mail:

Table[(#.Reverse[#])&@(Length/@Split[Sort[Apply[Plus,Drop[#,-1]]&/@(FoldList[Plus,First[#],Rest[#]]&/@Compositions[n,n+1])]]),{n,1,8}]
Out[]=
{2, 8, 48, 390, 3656, 37834, 417540, 4836452}

which can again be done smarter with the same T[n,a,b] :

Table[(#.#)&@Table[T[k,n,n],{k,0,n^2}],{n,0,24}]
Out[]=
{1, 2, 8, 48, 390, 3656, 37834, 417540, 4836452, 58130756, 719541996, 
9121965276, 117959864244, 1551101290792, 20689450250926, 279395018584860, 
3813887739881184, 52557835511244660, 730403326965323706, 
10227123663407957856, 144171319037014478826, 2044823450612944407184, 
29163549891477988409308, 418042863718291394846576, 6020216328504677143959536}

This T[n,a,b] counts the partitions of n who's Ferrers plot fit within an (a * b) box,
and this function (I lost the name & mails from the original author on mathfun, around 18/10/1999)
is also defined elsewhere in EIS :  A047993 (balanced partitions):
T[m_, a_, b_] /; b < a := T[m, b, a]; T[m_, a_, b_] /; m > a b := 0;
T[m_, a_, b_] /; (2m > a b) := T[a*b - m, a, b];
T[m_, 1, b_] := If[b < m, 0, 1];  T[0, _, _] := 1;
T[m_, a_, b_] := T[m, a, b] = Sum[T[m - a i, a - 1, b - i], {i, 0, Floor[m/a]}];


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