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

Author

Antti Karttunen, Jun 25 2002

Keywords

• nonn

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

Crossrefs

Occurs for first time in A073202 as row 168.

Cf. also A073190.

Programs

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

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

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.