|
|
A000992
|
|
"Half-Catalan numbers": a(n) = Sum_{k=1..floor(n/2)} a(k)*a(n-k) with a(1) = 1.
(Formerly M0793 N0300)
|
|
30
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
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)
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)
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
|
|
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
|
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
|
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 + ...
|
|
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:
|
|
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
|
|
CROSSREFS
|
Compare recurrence for A000108 (the Catalan numbers).
A093637 counts above trees without the restriction that all outdegrees are <= 2.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|