login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A019497 Number of ternary search trees on n keys. 5

%I

%S 1,1,1,3,6,16,42,114,322,918,2673,7875,23457,70551,213846,652794,

%T 2004864,6190612,19207416,59850384,187217679,587689947,1850692506,

%U 5845013538,18509607753,58759391013,186958014766,596108115402

%N Number of ternary search trees on n keys.

%H J. A. Fill and R. P. Dobrow, <a href="http://journals.cambridge.org/article_S0963548397003118">The number of m-ary search trees on n keys</a>, Combin. Probab. Comput. 6 (1997), 435-453.

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F 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

%F G.f. A(x) satisfies A(x)= 1+ x+ x^2*A(x)^3. - _Michael Somos_, Mar 29 2007

%F Given g.f. A(x), then x*A(-x) is series reversion of A025262(n-1). - _Michael Somos_, Mar 29 2007

%F 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

%p 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

%t 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_ *)

%o (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];

%o (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 */

%o (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 */

%o (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

%K nonn

%O 0,4

%A James Fill (jimfill(AT)jhu.edu)

%E More terms from _Olivier Gérard_, July 1997

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 21:47 EST 2020. Contains 331066 sequences. (Running on oeis4.)