# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a083563
Showing 1-1 of 1

%I A083563 #19 Sep 07 2019 15:11:01
%S A083563 0,2,3,6,18,54,183,636,2316,8610,32763,126582,495981,1964718,7857939,
%T A083563 31682202,128644290,525573252,2158930398,8911295286,36942107373,
%U A083563 153742174722,642088530453,2690224616904,11304554951127,47630390054802,201181338802308,851690762495448
%N 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.
%C A083563 With a(1)=k, the same recurrence enumerates expressions in at most k variables. In particular, k=1 yields A001190.
%H A083563 Andrew Howroyd, <a href="/A083563/b083563.txt">Table of n, a(n) for n = 0..500</a>
%H A083563 V. P. Johnson, <a href="http://people.math.sc.edu/czabarka/Theses/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From _N. J. A. Sloane_, Dec 22 2012
%F A083563 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
%F A083563 G.f.: A(x) = 2x + (1/2)*(A(x)^2 + A(x^2)).
%F A083563 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.
%e A083563 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).
%e A083563 G.f. = 2*x + 3*x^2 + 6*x^3 + 18*x^4 + 54*x^5 + 183*x^6 + 636*x^7 + ...
%p A083563 a:= proc(n) option remember; `if`(n<2, 2*n, `if`(n::odd, 0,
%p A083563       (t-> t*(1-t)/2)(a(n/2)))+add(a(i)*a(n-i), i=1..n/2))
%p A083563     end:
%p A083563 seq(a(n), n=0..30);  # _Alois P. Heinz_, Sep 23 2018
%t A083563 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}];
%t A083563 a /@ Range[0, 30] (* _Jean-François Alcover_, Sep 07 2019, after _Alois P. Heinz_ *)
%o A083563 (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))};
%Y A083563 Column k=2 of A319539.
%Y A083563 Cf. A000108, A001190, A001699.
%K A083563 easy,eigen,nonn
%O A083563 0,2
%A A083563 Doug McIlroy (doug(AT)cs.dartmouth.edu), Jun 12 2003

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE