OFFSET
0,13
REFERENCES
Luo Jian-Jin, Catalan numbers in the history of mathematics in China, in Combinatorics and Graph Theory, (Yap, Ku, Lloyd, Wang, Editors), World Scientific, River Edge, NJ, 1995.
LINKS
Alois P. Heinz, Antidiagonals n = 0..200, flattened
Henry Bottomley and Antti Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.
Andrew Odlyzko, Analytic methods in asymptotic enumeration.
FORMULA
(See the Maple code below. Is there a nicer formula?)
This table was known to the Chinese mathematician Ming An-Tu, who gave the following recurrence in the 1730s. a(0, 0) = 1, a(n, k) = Sum[a(n-1, k-1-i)( 2*Sum[ a(j, i), {j, 0, n-2}]+a(n-1, i) ), {i, 0, k-1}]. - David Callan, Aug 17 2004
The generating function for row n, T_n(x):=Sum[T(n, k)x^k, k>=0], is given by T_n = a(n)-a(n-1) where a(n) is defined by the recurrence a(0)=0, a(1)=1, a(n) = 1 + x a(n-1)^2 for n>=2. - David Callan, Oct 08 2005
EXAMPLE
The top-left corner of this square array is
1 0 0 0 0 0 0 0 0 ...
0 1 0 0 0 0 0 0 0 ...
0 0 2 1 0 0 0 0 0 ...
0 0 0 4 6 6 4 1 0 ...
0 0 0 0 8 20 40 68 94 ...
E.g. we have A000108(3) = 5 binary trees built from 3 non-leaf (i.e. branching) nodes:
_______________________________3
___\/__\/____\/__\/____________2
__\/____\/__\/____\/____\/_\/__1
_\/____\/____\/____\/____\./___0
The first four have height 3 and the last one has height 2, thus T(3,3) = 4, T(3,2) = 1 and T(3,any other value of k) = 0.
MAPLE
A073345bi := proc(n, k) option remember; local i, j; if(0 = n) then if(0 = k) then RETURN(1); else RETURN(0); fi; fi; if(0 = k) then RETURN(0); fi; 2 * add(A073345bi(n-i-1, k-1) * add(A073345bi(i, j), j=0..(k-1)), i=0..floor((n-1)/2)) + 2 * add(A073345bi(n-i-1, k-1) * add(A073345bi(i, j), j=0..(k-2)), i=(floor((n-1)/2)+1)..(n-1)) - (`mod`(n, 2))*(A073345bi(floor((n-1)/2), k-1)^2); end;
A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))), 2) - (n+1);
A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))), 2);
MATHEMATICA
a[0, 0] = 1; a[n_, k_]/; k<n||k>2^n-1 := 0; a[n_, k_]/; 1 <= n <= k <= 2^n-1 := a[n, k] = Sum[a[n-1, k-1-i](2Sum[ a[j, i], {j, 0, n-2}]+a[n-1, i]), {i, 0, k-1}]; Table[a[n, k], {n, 0, 9}, {k, 0, 9}]
(* or *) a[0] = 0; a[1] = 1; a[n_]/; n>=2 := a[n] = Expand[1 + x a[n-1]^2]; gfT[n_] := a[n]-a[n-1]; Map[CoefficientList[ #, x, 8]&, Table[gfT[n], {n, 9}]/.{x^i_/; i>=9 ->0}] (Callan)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Antti Karttunen, Jul 31 2002
STATUS
approved