|
Search: id:A083563
|
|
|
| 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
1
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
With a(1)=k, the same recurrence enumerates expressions in at most k variables. In particular, k=1 yields A001190.
|
|
FORMULA
|
G.f. A(x)=1-sqrt(1-4x-A(x^2)) satisfies A(x)^2-2*A(x)+4x+A(x^2)=0, 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(2n-1)=a(1)a(2n-2)+a(2)a(2n-3)+...+a(n-1)a(n), a(2n)=a(1)a(2n-1)+a(2)a(2n-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).
|
|
PROGRAM
|
(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
|
Cf. A000108, A001190, A001699.
Sequence in context: A080338 A057581 A089424 this_sequence A038056 A072241 A093468
Adjacent sequences: A083560 A083561 A083562 this_sequence A083564 A083565 A083566
|
|
KEYWORD
|
easy,eigen,nonn
|
|
AUTHOR
|
Doug McIlroy (doug(AT)cs.dartmouth.edu), Jun 12 2003
|
|
|
Search completed in 0.002 seconds
|
