0,13

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.

H. Bottomley and A. Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.

Andrew Odlyzko, Analytic methods in asymptotic enumeration.

(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 (callan(AT)stat.wisc.edu), 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 (callan(AT)stat.wisc.edu), Oct 08 2005

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.

A073345 := n -> A073345bi(A025581(n), A002262(n));

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);

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)

Variant: A073346. Column sums: A000108. Row sums: A001699.

Diagonals: A073345(n, n) = A011782(n), A073345(n+3, n+2) = A014480(n), A073345(n+2, n) = A073773(n), A073345(n+3, n) = A073774(n) - Henry Bottomley (se16(AT)btinternet.com) and AK, see the attached notes.

A073429 gives the upper triangular region of this array. Cf. also A065329, A001263.

Sequence in context: A019222 A019141 A086077 this_sequence A138088 A112765 A105966

Adjacent sequences: A073342 A073343 A073344 this_sequence A073346 A073347 A073348

nonn,tabl

Antti Karttunen Jul 31 2002