1,4

Comment from David Callan, Nov 02 2006: a(n) = number of (unlabeled, rooted) ordered trees on n-1 vertices in which all outdegrees are <=2 and, for each vertex of outdegree 2, the sizes of its two subtrees are weakly increasing left to right (n>=2). The number b(n) of such trees on n vertices satisfies the recurrence b[1]=1; b[n_]/;n>=2 := b[n] = b[n-1] + Sum[b[i]b[n-1-i],{i,Floor[(n-1)/2]}], the first term counting trees whose root has outdegree 1 and the sum counting trees whose root has outdegree 2 by size of the left subtree. This recurrence generates b(n)=a(n+1), n>=1. For example, the a(5)=3 such trees are:

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

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

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

Contribution from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 27 2009: (Start)

The connection with the Rayleigh polynomials Phi(2n,x) of A158616 is that Phi(2n,x)= sum_{i=1..a(n)} 2^(n_i) product_{j=2..n-1} (x+j)^(n_ij), as described by Kishore.

So a(n) counts the terms in the representation of the Polynomial Phi(2n,x) as a sum over these "base" polynomials.

For example Phi(12,x) = 2^4*(x+2)^2*(x+3) +2^2*(x+2)*(x+3)^2 +2^3*(x+2)*(x+3)*(x+4) + 2^3*(x+2)*(x+3)*(x+5) +2^2*(x+2)*(x+4)*(x+5) +2*(x+3)^2*(x+5) has a(6)=6 terms. (End)

N. Kishore, A structure of the Rayleigh polynomial, Duke Math. J., 31 (1964), 513-518.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..200

al := 1/2; M1 := 30; a[ 0 ] := 1; for n from 0 to M1 do n0 := floor(al*n);

a[ n+1 ] := sum( a[ i ]*a[ n-i ], i=0..n0); i := 'i'; od: [ seq(a[ j ], j=0..M1) ];

Also called "1/2-Catalans", compare recurrence for A000108.

A093637 counts above trees without the restriction that all outdegrees are <=2.

Cf. A001190, A124973.

Sequence in context: A123465 A000055 A006787 this_sequence A036648 A047750 A072187

Adjacent sequences: A000989 A000990 A000991 this_sequence A000993 A000994 A000995

nonn,easy,nice

N. J. A. Sloane (njas(AT)research.att.com).