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_{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
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.
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:
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 *)
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
(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
CROSSREFS
KEYWORD
nonn,easy,nice,changed
AUTHOR
STATUS
approved