A083563 - OEIS

%I #19 Sep 07 2019 15:11:01

%S 0,2,3,6,18,54,183,636,2316,8610,32763,126582,495981,1964718,7857939,

%T 31682202,128644290,525573252,2158930398,8911295286,36942107373,

%U 153742174722,642088530453,2690224616904,11304554951127,47630390054802,201181338802308,851690762495448

%N 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 With a(1)=k, the same recurrence enumerates expressions in at most k variables. In particular, k=1 yields A001190.

%H Andrew Howroyd, <a href="/A083563/b083563.txt">Table of n, a(n) for n = 0..500</a>

%H 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 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 G.f.: A(x) = 2x + (1/2)*(A(x)^2 + A(x^2)).

%F 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 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 G.f. = 2*x + 3*x^2 + 6*x^3 + 18*x^4 + 54*x^5 + 183*x^6 + 636*x^7 + ...

%p a:= proc(n) option remember; `if`(n<2, 2*n, `if`(n::odd, 0,

%p       (t-> t*(1-t)/2)(a(n/2)))+add(a(i)*a(n-i), i=1..n/2))

%p     end:

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, Sep 23 2018

%t 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 a /@ Range[0, 30] (* _Jean-François Alcover_, Sep 07 2019, after _Alois P. Heinz_ *)

%o (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 Column k=2 of A319539.

%Y Cf. A000108, A001190, A001699.

%K easy,eigen,nonn

%O 0,2

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