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:

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

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

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

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

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

njas