login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 15:41 EST 2019. Contains 329106 sequences. (Running on oeis4.)