|
%I M0793 N0300 #90 Oct 27 2023 18:03:19
%S 1,1,1,2,3,6,11,24,47,103,214,481,1030,2337,5131,11813,26329,60958,
%T 137821,321690,734428,1721998,3966556,9352353,21683445,51296030,
%U 119663812,284198136,666132304,1586230523,3734594241,8919845275,21075282588,50441436842
%N "Half-Catalan numbers": a(n) = Sum_{k=1..floor(n/2)} a(k)*a(n-k) with a(1) = 1.
%C From _David Callan_, Nov 02 2006: (Start)
%C 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:
%C .|....|...../\..
%C .|.../.\.....|..
%C .|.............. (End)
%C From _R. J. Mathar_, Mar 27 2009: (Start)
%C 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.
%C So a(n) counts the terms in the representation of the polynomial Phi(2n,x) as a sum over these "base" polynomials.
%C 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)
%C From _Wolfdieter Lang_, Jan 06 2012: (Start)
%C 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)
%C Limit_{n->infinity} a(n)^(1/n) = 2.49086422... . - _Vaclav Kotesovec_, Oct 15 2014
%C 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
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vaclav Kotesovec, <a href="/A000992/b000992.txt">Table of n, a(n) for n = 1..2500</a> (first 200 terms from T. D. Noe)
%H E. Bohl, P. Lancaster, <a href="http://dx.doi.org/10.1016/j.jtbi.2005.08.001">Implementation of a Markov model for phylogenetic trees</a>, J. Theor. Biol. 239 (3) (2006) 324-333.
%H J. T. Butler, <a href="/A006447/a006447.pdf">Letter to N. J. A. Sloane, Jun. 1975</a>.
%H David S. Evans, <a href="https://ui.adsabs.harvard.edu/abs/1968QJRAS...9..388E/abstract">Stars of Higher Multiplicity</a>, Quarterly Journal of the Royal Astronomical Society, Vol. 9 (1968), pp. 388-400.
%H T. Feil, K.Hutson, R. J. Kretchmar, <a href="http://personal.denison.edu/~kretchmar/pubs/TreeTraversals.pdf">Tree traversals and permutations</a>, Congr. Numer. 175 (2005) 201-221 (mentions the sequence only in the references, not in the text).
%H N. Kishore, <a href="http://dx.doi.org/10.1215/S0012-7094-64-03150-3">A structure of the Rayleigh polynomial</a>, Duke Math. J., 31 (1964), 513-518.
%e 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 + ...
%p al := 1/2; M1 := 30; a[ 0 ] := 1; for n from 0 to M1 do n0 := floor(al*n);
%p a[ n+1 ] := sum( a[ i ]*a[ n-i ], i=0..n0); i := 'i'; od: [ seq(a[ j ],j=0..M1) ];
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n=1, 1,
%p add(a(j)*a(n-j), j=1..n/2))
%p end:
%p seq(a(n), n=1..42); # _Alois P. Heinz_, Sep 22 2019
%t 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 *)
%o (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
%o (Haskell)
%o a000992 n = a000992_list !! (n-1)
%o a000992_list = 1 : f 1 0 [1] where
%o f x y zs = z : f (x + y) (1 - y) (z:zs) where
%o z = sum $ take x $ zipWith (*) zs $ reverse zs
%o -- _Reinhard Zumkeller_, Dec 21 2011
%Y Compare recurrence for A000108 (the Catalan numbers).
%Y A093637 counts above trees without the restriction that all outdegrees are <= 2.
%Y Cf. A001190, A124973, A248748.
%K nonn,easy,nice
%O 1,4
%A _N. J. A. Sloane_
| 