login
This site is supported by donations to The OEIS Foundation.

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000992 "Half-Catalan numbers": a(n) = Sum_{k=1 ... floor(n/2)} a(k)a(n-k) with a(1) = 1.
(Formerly M0793 N0300)
16
1, 1, 1, 2, 3, 6, 11, 24, 47, 103, 214, 481, 1030, 2337, 5131, 11813, 26329, 60958, 137821, 321690, 734428, 1721998, 3966556, 9352353, 21683445, 51296030, 119663812, 284198136, 666132304, 1586230523, 3734594241, 8919845275 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

From David Callan, Nov 02 2006: (Start)

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:

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

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

.|.............. (End)

From R. J. Mathar, 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)

From Wolfdieter Lang, Jan 06 2012: (Start)

The o.g.f. G(x):=sum(a(n)*x^n,n=0..infty), with a(0)=0, satisfies the relation (G(x))^2 - 2*G(x) + G2(x^2) + 2*x = 0,

  with the o.g.f. G2(x):=sum(a(n)^2*x^n,n=0..infty) of the squares. This can be proved from the connection to the half-convolution of the sequence with itself (for this notion see a comment on A201204, where also the rule for the o.g.f. is given). (End)

From Stanislav Sykora, Oct 13 2014: (Start)

For n>1, a(n) is the number of rooted binary trees with n leaves or, equivalently, the number of rooted binary trees with n-1 internal vertices.

Also, a symmetric binary operation f(x,y) = f(y,x) can be used to form at most a(n) non-equivalent expressions over n distinct arguments (when f(x,y) has additional properties such as f(x,f(y,z))=f(y,f(x,z), the count can be smaller).

(End)

Limit n->infinity (a(n))^(1/n) = 2.49086422... . - Vaclav Kotesovec, Oct 15 2014

REFERENCES

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).

LINKS

T. D. Noe and Vaclav Kotesovec, Table of n, a(n) for n = 1..2500 (first 200 terms from T. D. Noe)

E. Bohl, P. Lancaster, Implementation of a Markov model for phylogenetic trees, J. Theor. Biol. 239 (3) (2006) 324-333

T. Feil, K.Hutson, R. J. Kretchmar, Tree traversals and permutations, Congr. Numer. 175 (2005) 201-221 (mentions the sequence only in the references, not in the text)

EXAMPLE

From Stanislav Sykora, Oct 13 2014: (Start)

The a(5)=3 rooted binary trees with 5 leaves are:

   (1,((1,1),(1,1))); (1,(1,(1,(1,1)))); (1,((1,1),(1,(1,1)));

The corresponding expressions on 5 arguments x1,x2,x3,x4,x5 based on a binary operation f(x,y)=f(y,x) are:

   f(x1,f(f(x2,x3),f(x4,x5)));

   f(x1,f(x2,f(x3,f(x4,x5))));

   f(f(x1,x2),f(x3,f(x4,x5))));

These are equivalent for f(x,y)=x+y or f(x,y)=xy, but non-equivalent in more general cases, such as f(x,y)=f(y,x)=x^2+y^2.

(End)

MAPLE

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) ];

MATHEMATICA

a[1]=1; a[n_]:=a[n]=Sum[a[k] a[n-k], {k, 1, Floor[n/2]}]; Table[a[n], {n, 1, 32}] (* Jean-Fran├žois Alcover, Mar 21 2011 *)

PROG

(PARI) A000992_list(n)={for(i=4, #n=vector(n, i, 1), n[i]=sum(j=1, i\2, n[j]*n[i-j])); n}  \\ - M. F. Hasler, Dec 20 2011

(Haskell)

a000992 n = a000992_list !! (n-1)

a000992_list = 1 : f 1 0 [1] where

   f x y zs = z : f (x + y) (1 - y) (z:zs) where

     z = sum $ take x $ zipWith (*) zs $ reverse zs

-- Reinhard Zumkeller, Dec 21 2011

CROSSREFS

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

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

Cf. A001190, A124973, A248748.

Sequence in context: A217312 A006787 A176425 * A036648 A047750 A072187

Adjacent sequences:  A000989 A000990 A000991 * A000993 A000994 A000995

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 1 07:47 EDT 2014. Contains 248888 sequences.