half a chessboard?

[Wouter Meeussen]

Auto-peer -review:

my own  A047993 (balanced partitions)
contains a incomplete recursion formula that should read:

"The function T[n, a, b] gives the number of partitions of n with first element <=a and length <=b. "

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, Quotient[m, a]}];

Using this, the half-a-chessboard paths count as:


Table[T[2n^2,2n,2n],{n,0,16}]

{1, 2, 8, 58, 526, 5448, 61108, 723354, 8908546, 113093022, 1470597342, 
19499227828, 262754984020, 3589093760726, 49596793134484, 692260288169282, 
9747120868919060}

check:
for n=3 the 58 paths are:
{{0, 0, 0, 6, 6, 6}, {0, 0, 1, 5, 6, 6}, {0, 0, 2, 4, 6, 6}, {0, 1, 1, 4, 6, 6}, 
 {0, 0, 3, 3, 6, 6}, {0, 1, 2, 3, 6, 6}, {1, 1, 1, 3, 6, 6}, {0, 2, 2, 2, 6, 6},
 {1, 1, 2, 2, 6, 6}, {0, 0, 2, 5, 5, 6}, {0, 1, 1, 5, 5, 6}, {0, 0, 3, 4, 5, 6}, 
 {0, 1, 2, 4, 5, 6}, {1, 1, 1, 4, 5, 6}, {0, 1, 3, 3, 5, 6}, {0, 2, 2, 3, 5, 6}, 
 {1, 1, 2, 3, 5, 6}, {1, 2, 2, 2, 5, 6}, {0, 0, 4, 4, 4, 6}, {0, 1, 3, 4, 4, 6},
 {0, 2, 2, 4, 4, 6}, {1, 1, 2, 4, 4, 6}, {0, 2, 3, 3, 4, 6}, {1, 1, 3, 3, 4, 6}, 
 {1, 2, 2, 3, 4, 6}, {2, 2, 2, 2, 4, 6}, {0, 3, 3, 3, 3, 6}, {1, 2, 3, 3, 3, 6},
 {2, 2, 2, 3, 3, 6}, {0, 0, 3, 5, 5, 5}, {0, 1, 2, 5, 5, 5}, {1, 1, 1, 5, 5, 5},
 {0, 0, 4, 4, 5, 5}, {0, 1, 3, 4, 5, 5}, {0, 2, 2, 4, 5, 5}, {1, 1, 2, 4, 5, 5},
 {0, 2, 3, 3, 5, 5}, {1, 1, 3, 3, 5, 5}, {1, 2, 2, 3, 5, 5}, {2, 2, 2, 2, 5, 5},
 {0, 1, 4, 4, 4, 5}, {0, 2, 3, 4, 4, 5}, {1, 1, 3, 4, 4, 5}, {1, 2, 2, 4, 4, 5}, 
 {0, 3, 3, 3, 4, 5}, {1, 2, 3, 3, 4, 5}, {2, 2, 2, 3, 4, 5}, {1, 3, 3, 3, 3, 5},
 {2, 2, 3, 3, 3, 5}, {0, 2, 4, 4, 4, 4}, {1, 1, 4, 4, 4, 4}, {0, 3, 3, 4, 4, 4},
 {1, 2, 3, 4, 4, 4}, {2, 2, 2, 4, 4, 4}, {1, 3, 3, 3, 4, 4}, {2, 2, 3, 3, 4, 4},
 {2, 3, 3, 3, 3, 4}, {3, 3, 3, 3, 3, 3}}

sorry, with  {0, 2, 2  ,   2, 6, 6} the saw does not pass through the centre,
so my previous calculation fails.

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