A000992 "Half-Catalan numbers": a(n) = Sum_{k=1..floor(n/2)} a(k)*a(n-k) with a(1) = 1.

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, 21075282588, 50441436842

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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_{i=1..floor((n-1)/2)} b[i]b[n-1-i], 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_{n>=0} a(n)*x^n, 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_{n>=0} a(n)^2*x^n 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)

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

This sequence diverges from A001190 for n >= 8. A001190(n) gives the number of unlabeled binary trees with n leaves and n-1 internal nodes. - Andrew Howroyd, Apr 01 2023

Examples

			G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 24*x^8 + 47*x^9 + ...
		

References

• 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

• 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.
• J. T. Butler, Letter to N. J. A. Sloane, Jun. 1975.
• David S. Evans, Stars of Higher Multiplicity, Quarterly Journal of the Royal Astronomical Society, Vol. 9 (1968), pp. 388-400.
• 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).
• N. Kishore, A structure of the Rayleigh polynomial, Duke Math. J., 31 (1964), 513-518.

Crossrefs

Compare recurrence for A000108 (the Catalan numbers).

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

Cf. A001190, A124973, A248748.

Programs

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

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) ];
# second Maple program:
a:= proc(n) option remember; `if`(n=1, 1,
      add(a(j)*a(n-j), j=1..n/2))
    end:
seq(a(n), n=1..42);  # Alois P. Heinz, Sep 22 2019

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

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

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A000992(n): return sum(A000992(k)*A000992(n-k) for k in range(1,(n>>1)+1)) if n>1 else 1 # Chai Wah Wu, Nov 04 2024