login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A019497 Number of ternary search trees on n keys. 8
1, 1, 1, 3, 6, 16, 42, 114, 322, 918, 2673, 7875, 23457, 70551, 213846, 652794, 2004864, 6190612, 19207416, 59850384, 187217679, 587689947, 1850692506, 5845013538, 18509607753, 58759391013, 186958014766, 596108115402, 1904387243796, 6095040222192, 19540540075824 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

LINKS

Table of n, a(n) for n=0..30.

J. A. Fill and R. P. Dobrow, The number of m-ary search trees on n keys, Combin. Probab. Comput. 6 (1997), 435-453.

Index entries for sequences related to rooted trees

FORMULA

a(0)=a(1)=1 and for n>=2 a(n)= sum( i+j+k=n-2, a(i)*a(j)*a(k) ) (i, j, k>=0). - Benoit Cloitre, Jun 14 2004

G.f. A(x) satisfies A(x)= 1+ x+ x^2*A(x)^3. - Michael Somos, Mar 29 2007

Given g.f. A(x), then x*A(-x) is series reversion of A025262(n-1). - Michael Somos, Mar 29 2007

a(n) = Sum_{k=0..n-1} C(n-k,k)/(n-k) * C(3*k,n-k-1) for n>0 with a(0)=1. - Paul D. Hanna, Jun 16 2009

a(n) ~ (8 + 3*sqrt(3))^(1/4) * 3^(n/2 - 3/8) * (3 + sqrt(9 + 8*sqrt(3)))^(n + 1/2) / (sqrt(Pi) * n^(3/2) * 2^(2*n + 2)). - Vaclav Kotesovec, Jul 31 2021

MAPLE

A:= proc(n) option remember; if n=0 then 1 else convert(series(1+x+x^2*A(n-1)^3, x=0, n+1), polynom) fi end: a:= n-> coeff(A(n), x, n): seq(a(n), n=0..27); # Alois P. Heinz, Aug 22 2008

MATHEMATICA

a[0] = 1; a[n_] := Sum[Binomial[1*(n-k), k]/(n-k)*Binomial[3*k, n-k-1], {k, 0, n-1}]; Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Apr 07 2015, after Paul D. Hanna *)

PROG

(PARI) v=vector(50, j, 1); for(n=3, 50, A=sum(i=1, n, sum(j=1, n, sum(k=1, n, if(i+j+k-n, 0, v[i]*v[j]*v[k])))); v[n]=A); a(n)=v[n+1];

(PARI) {a(n)= local(A); if(n<0, 0, A= 1+O(x); forstep(k= 1, n, 2, A= 1+x+x*x*A^3); polcoeff(A, n))} /* Michael Somos, Mar 29 2007 */

(PARI) {a(n)= if(n<0, 0, (-1)^n* polcoeff( serreverse((1-sqrt(1-4*x+4*x^3+x^2*O(x^n)))/2), n+1))} /* Michael Somos, Mar 29 2007 */

(PARI) a(n)=if(n==0, 1, sum(k=0, n-1, binomial(1*(n-k), k)/(n-k)*binomial(3*k, n-k-1))) \\ Paul D. Hanna, Jun 16 2009

CROSSREFS

Sequence in context: A027088 A027102 A218207 * A091488 A202839 A007561

Adjacent sequences:  A019494 A019495 A019496 * A019498 A019499 A019500

KEYWORD

nonn

AUTHOR

James Fill (jimfill(AT)jhu.edu)

EXTENSIONS

More terms from Olivier Gérard, July 1997

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 25 02:55 EDT 2022. Contains 354047 sequences. (Running on oeis4.)