1,3

Comment from David Callan (callan(AT)stat.wisc.edu), Mar 30 2007: (Start) a(n) = number of vertex-labeled ordered trees (A000108) on n vertices, in which each non-leaf vertex is labeled with a positive integer <= its outdegree. Example. a(3)=3 counts the trees on 3 vertices with labels as shown (ignore the dots; the 2 edges in each tree are shown, you have to visualize the vertices).

.1.....2....1

/.\.../.\...|1

............|

Proof. Let F(x) = x+x^2+3x^3+... denote the gf for these trees, with x marking number of vertices. Counting these trees by degree of the root leads to F = x + Sum_{k>=1}k*x*F^k, or F = x + x*F/(1-F)^2. This is the same equation as that satisfied by the reversion of x*(1-x)*(1-x^2)*(1-x^3)/(1-x^6) = x*(1-x)^2/(1-x+x^2). (End)

N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

G.f. A(x) satisfies 0=f(x, A(x)) where f(x, y)=x*(1-y+y^2)-y*(1-y)^2.

G.f. A(x) satisfies 0=f(x, A(x)) where f(x, y)=y*(1-y)*((1-y)/x+1)-1.

(PARI) {a(n)=if(n<1, 0, polcoeff( serreverse(x*(1-x)*(1-x^2)*(1-x^3)/(1-x^6)+x*O(x^n)), n))}

Sequence in context: A119244 A052893 A052818 this_sequence A046632 A063029 A044048

Adjacent sequences: A109078 A109079 A109080 this_sequence A109082 A109083 A109084

nonn

Michael Somos, Jun 17 2005