A083563 Number of binary rooted trees (every node has out-degree 0 or 2) with n labeled leaves (2n-1 nodes in all) and at most 2 distinct labels. Also the number of expressions in at most two variables constructible with n-1 instances of a single commutative and nonassociative binary operator.

0, 2, 3, 6, 18, 54, 183, 636, 2316, 8610, 32763, 126582, 495981, 1964718, 7857939, 31682202, 128644290, 525573252, 2158930398, 8911295286, 36942107373, 153742174722, 642088530453, 2690224616904, 11304554951127, 47630390054802, 201181338802308, 851690762495448

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

Column k=2 of A319539.

Cf. A000108, A001190, A001699.

Sequence in context: A080338 A057581 A089424 * A038056 A072241 A093468

Adjacent sequences: A083560 A083561 A083562 * A083564 A083565 A083566

Keyword

easy,eigen,nonn

Author

Doug McIlroy (doug(AT)cs.dartmouth.edu), Jun 12 2003

Status

approved