A073190 Number of general plane trees which are either empty (the case a(0)), or whose root degree is either 1 (i.e., the planted trees) or the two leftmost subtrees (of the root node) are identical.

1, 1, 2, 3, 8, 20, 60, 181, 584, 1916, 6476, 22210, 77416, 272840, 971640, 3488925, 12621168, 45946156, 168206604, 618853270, 2286974856, 8485246456, 31596023208, 118037654258, 442287721872, 1661790513944, 6259494791096

Offset

0,3

Comments

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

Links

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

Formula

a(0)=1, a(n) = Cat(n-1) + Sum_{i=0..n-2, (n-i) is even} Cat((n-i-2)/2)*Cat(i), where Cat(n) is A000108(n).

Maple

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

Mathematica

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

Prog

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

Crossrefs

Occurs for first time in A073202 as row 1. A073191(n) = (A000108(n)+A073190(n))/2. Cf. also A073192.

Sequence in context: A167123 A029895 A073268 * A066051 A056971 A108125

Adjacent sequences: A073187 A073188 A073189 * A073191 A073192 A073193

Keyword

nonn

Author

Antti Karttunen, Jun 25 2002

Status

approved