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

Author

Antti Karttunen, Jun 25 2002

Keywords

• nonn

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

Crossrefs

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

Programs

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

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

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