OFFSET
0,2
COMMENTS
With a(1)=k, the same recurrence enumerates expressions in at most k variables. In particular, k=1 yields A001190.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From N. J. A. Sloane, Dec 22 2012
FORMULA
G.f. A(x) = 1 - sqrt(1 - 4*x - A(x^2)) satisfies 0 = A(x)^2 - 2*A(x) + 4*x + A(x^2), A(0)=0. - Michael Somos, Sep 06 2003
G.f.: A(x) = 2x + (1/2)*(A(x)^2 + A(x^2)).
a(0)=0, a(1)=2, a(2*n-1) = a(1)*a(2*n-2) + a(2)*a(2*n-3) + ... + a(n-1)*a(n), a(2*n) = a(1)*a(2*n-1) + a(2)*a(2*n-2) + ... + a(n-1)*a(n+1) + a(n)*(a(n) + 1) / 2.
EXAMPLE
a(3)=6, enumerating the 6 expressions with 2 # operators: x#(x#x), x#(x#y), x#(y#y), y#(x#x), y#(x#y), y#(y#y).
G.f. = 2*x + 3*x^2 + 6*x^3 + 18*x^4 + 54*x^5 + 183*x^6 + 636*x^7 + ...
MAPLE
a:= proc(n) option remember; `if`(n<2, 2*n, `if`(n::odd, 0,
(t-> t*(1-t)/2)(a(n/2)))+add(a(i)*a(n-i), i=1..n/2))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Sep 23 2018
MATHEMATICA
a[n_] := a[n] = If[n < 2, 2*n, If[OddQ[n], 0, #*(1 - #)/2&[a[n/2]]]] + Sum[a[i]*a[n - i], {i, 1, n/2}];
a /@ Range[0, 30] (* Jean-François Alcover, Sep 07 2019, after Alois P. Heinz *)
PROG
(PARI) {a(n) = local(A, m); if( n<0, 0, m=1; A = O(x); while( m<=n, m*=2; A = 1 - sqrt(1 - 4*x - subst(A, x, x^2))); polcoeff(A, n))};
CROSSREFS
KEYWORD
easy,eigen,nonn
AUTHOR
Doug McIlroy (doug(AT)cs.dartmouth.edu), Jun 12 2003
STATUS
approved