A073192 Number of general plane trees whose n-th subtree from the left is equal to the n-th subtree from the right, for all its subtrees (i.e., are palindromic in the shallow sense).

1, 1, 2, 3, 8, 18, 54, 155, 500, 1614, 5456, 18630, 64960, 228740, 814914, 2926323, 10589916, 38561814, 141219432, 519711666, 1921142832, 7129756188, 26555149404, 99228108222, 371886574632, 1397548389644, 5265131346368

Offset

0,3

Comments

The Catalan bijection A057508 fixes only these kinds of trees, so this occurs in the table A073202 as row 168.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Formula

a(n) = Sum_{i=0..n, (n-i) is even} Gat((n-i)/2)*Gat(i-1), where Gat(-1) = 1 and otherwise like A000108(n).

A073193(n) = (A000108(n) + A073192(n))/2.

Maple

A073192 := proc(n) local d; add( (`mod`((n-d+1), 2))*Cat((n-d)/2)*(`if`((0=d), 1, Cat(d-1))), d=0..n); end;
Cat := n -> binomial(2*n, n)/(n+1);

Mathematica

a[n_] := Sum[Mod[n - k + 1, 2]*CatalanNumber[(n - k)/2]*If[k == 0, 1, CatalanNumber[k - 1]], {k, 0, n}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 05 2016 *)

Prog

(PARI) Gat(n) = if (n == -1, 1, binomial(2*n, n)/(n+1));
a(n) = sum(i=0, n, if (!((n-i)%2), Gat((n-i)/2)*Gat(i-1))); \\ Michel Marcus, May 30 2018

Crossrefs

Occurs for first time in A073202 as row 168.

Cf. also A073190.

Sequence in context: A185171 A339524 A158448 * A317722 A113183 A157015

Adjacent sequences: A073189 A073190 A073191 * A073193 A073194 A073195

Keyword

nonn

Author

Antti Karttunen, Jun 25 2002

Status

approved