A019497
Number of ternary search trees on n keys.
Original entry on oeis.org
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
Offset: 0
James Fill (jimfill(AT)jhu.edu)
-
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
-
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 *)
-
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];
-
{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 */
-
{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 */
-
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
A137953
G.f. satisfies A(x) = 1 + x*(1 + x*A(x)^2)^3.
Original entry on oeis.org
1, 1, 3, 9, 34, 132, 546, 2327, 10191, 45534, 206788, 951723, 4429182, 20808186, 98550468, 470038119, 2255684699, 10883852112, 52769785320, 256960840946, 1256147650818, 6162349332204, 30328107189312, 149698391878458
Offset: 0
-
Flatten[{1,Table[Sum[Binomial[3*(n-k), k]/(n-k)*Binomial[2*k, n-k-1],{k,0,n-1}],{n,1,20}]}] (* Vaclav Kotesovec after Paul D. Hanna, Mar 25 2014 *)
-
{a(n)=local(A=1+x*O(x^n));for(i=0,n,A=1+x*(1+x*A^2)^3);polcoeff(A,n)}
-
a(n)=if(n==0,1,sum(k=0,n-1,binomial(3*(n-k),k)/(n-k)*binomial(2*k,n-k-1))) \\ Paul D. Hanna, Jun 16 2009
A137966
G.f. satisfies A(x) = 1+x + x^2*A(x)^6.
Original entry on oeis.org
1, 1, 1, 6, 21, 86, 396, 1812, 8607, 41958, 207333, 1040234, 5281965, 27078756, 140021248, 729369474, 3823598232, 20158251814, 106809280563, 568471343322, 3037782047947, 16292380484454, 87669285293451, 473172657154822
Offset: 0
-
Flatten[{1, Table[Sum[Binomial[n-k,k]/(n-k) * Binomial[6*k,n-k-1], {k,0,n-1}], {n,1,30}]}] (* Vaclav Kotesovec, Nov 18 2017 *)
-
{a(n)=local(A=1+x*O(x^n));for(i=0,n,A=1+x*(1+x*A^6)^1);polcoeff(A,n)}
-
a(n)=if(n==0,1,sum(k=0,n-1,binomial(n-k,k)/(n-k)*binomial(6*k,n-k-1))) \\ Paul D. Hanna, Jun 16 2009
A137955
G.f. satisfies A(x) = 1 + x*(1 + x*A(x)^4)^2.
Original entry on oeis.org
1, 1, 2, 9, 36, 172, 842, 4310, 22676, 121896, 666884, 3699973, 20771096, 117765084, 673367034, 3878538930, 22483446152, 131070712924, 767929882240, 4519387797894, 26704456819984, 158367557278412, 942285096541344, 5623496055739052, 33653373190735484
Offset: 0
-
Flatten[{1,Table[Sum[Binomial[2*(n-k),k]/(n-k)*Binomial[4*k,n-k-1],{k,0,n-1}],{n,1,20}]}] (* Vaclav Kotesovec, Sep 18 2013 *)
-
{a(n)=local(A=1+x*O(x^n));for(i=0,n,A=1+x*(1+x*A^4)^2);polcoeff(A,n)}
-
a(n)=if(n==0,1,sum(k=0,n-1,binomial(2*(n-k),k)/(n-k)*binomial(4*k,n-k-1))) \\ Paul D. Hanna, Jun 16 2009
A137959
G.f. satisfies A(x) = 1 + x + x^2*A(x)^5.
Original entry on oeis.org
1, 1, 1, 5, 15, 55, 220, 876, 3645, 15485, 66735, 292155, 1293456, 5782320, 26071435, 118402495, 541150155, 2487204315, 11488482130, 53302256250, 248293549685, 1160794446445, 5444674773325, 25614768620105, 120837493137460
Offset: 0
-
Flatten[{1,Table[Sum[Binomial[n-k,k]/(n-k)*Binomial[5*k,n-k-1],{k,0,n-1}],{n,1,20}]}] (* Vaclav Kotesovec, Sep 18 2013 *)
-
{a(n)=local(A=1+x*O(x^n));for(i=0,n,A=1+x*(1+x*A^5));polcoeff(A,n)}
-
a(n)=if(n==0,1,sum(k=0,n-1,binomial(n-k,k)/(n-k)*binomial(5*k,n-k-1))) \\ Paul D. Hanna, Jun 16 2009
A366558
G.f. A(x) satisfies A(x) = 1 + x + x^4*A(x)^4.
Original entry on oeis.org
1, 1, 0, 0, 1, 4, 6, 4, 5, 28, 84, 140, 162, 304, 1018, 2644, 4760, 7364, 15540, 42680, 102059, 195904, 356542, 782880, 1950844, 4467288, 9011156, 17960676, 39984254, 94642292, 212395260, 444063984, 931300500, 2082762572, 4796413292, 10681800072, 22892593021
Offset: 0
-
a(n) = sum(k=0, n\4, binomial(3*k+1, n-4*k)*binomial(4*k, k)/(3*k+1));
A295404
G.f. A(x) satisfies: A(x) = A(x)^2 - x*A(x)^3 + x^2.
Original entry on oeis.org
1, 1, 1, 4, 10, 32, 95, 306, 978, 3235, 10767, 36470, 124514, 429648, 1492944, 5225700, 18396350, 65115694, 231555165, 826956617, 2964543205, 10664540170, 38484972969, 139281469165, 505408580484, 1838442927937, 6702466323520, 24486411113076, 89630823136513, 328680670354328, 1207323483992684, 4441801238353311, 16365832987077134, 60384021404260146, 223087697417538491
Offset: 0
G.f.: A(x) = 1 + x + x^2 + 4*x^3 + 10*x^4 + 32*x^5 + 95*x^6 + 306*x^7 + 978*x^8 + 3235*x^9 + 10767*x^10 + 36470*x^11 + 124514*x^12 + 429648*x^13 + 1492944*x^14 + 5225700*x^15 + 18396350*x^16 + 65115694*x^17 + 231555165*x^18 + 826956617*x^19 + 2964543205*x^20 +...
such that A(x) = A(x)^2 - x*A(x)^3 + x^2.
RELATED SERIES.
1/A(x) = 1 - x - 3*x^3 - 3*x^4 - 16*x^5 - 32*x^6 - 121*x^7 - 329*x^8 - 1138*x^9 - 3546*x^10 - 12097*x^11 - 40112*x^12 +...
A(x)^2 = 1 + 2*x + 3*x^2 + 10*x^3 + 29*x^4 + 92*x^5 + 290*x^6 + 946*x^7 + 3114*x^8 + 10438*x^9 + 35332*x^10 + 120968*x^11 + 417551*x^12 +...
A(x)^3 = 1 + 3*x + 6*x^2 + 19*x^3 + 60*x^4 + 195*x^5 + 640*x^6 + 2136*x^7 + 7203*x^8 + 24565*x^9 + 84498*x^10 + 293037*x^11 + 1023184*x^12 +...
where A(x) = 1 + x*A(x)^2 - x^2/A(x).
Series_Reversion(x*A(x)) = x - x^2 + x^3 - 4*x^4 + 10*x^5 - 32*x^6 + 107*x^7 - 360*x^8 + 1270*x^9 - 4544*x^10 + 16537*x^11 - 61092*x^12 + 228084*x^13 - 860056*x^14 + 3269994*x^15 +...+ (-1)^(n-1)*A137954(n-1)*x^n +...
-
{a(n)=local(A=1+x); for(i=1, n, A = 1 + x*A^2 - x^2/A +x*O(x^n)); polcoeff(G=A, n)}
for(n=0,40,print1(a(n),", "))
A371607
G.f. satisfies A(x) = ( 1 + x * (1 + x*A(x)^2) )^2.
Original entry on oeis.org
1, 2, 3, 10, 29, 92, 314, 1078, 3830, 13844, 50746, 188554, 707667, 2679960, 10227940, 39294772, 151859858, 589943516, 2302462140, 9023681820, 35498194465, 140122652960, 554827907272, 2203135245820, 8771143399104, 35003747271444, 140002994665366
Offset: 0
-
a(n, r=2, s=1, t=0, u=4) = r*sum(k=0, n, binomial(t*k+u*(n-k)+r, k)*binomial(s*k, n-k)/(t*k+u*(n-k)+r));
A366557
G.f. A(x) satisfies A(x) = 1 + x + x^3*A(x)^4.
Original entry on oeis.org
1, 1, 0, 1, 4, 6, 8, 29, 84, 162, 360, 1074, 2808, 6444, 16464, 45629, 118244, 297450, 790184, 2138438, 5624136, 14778068, 39767024, 107287122, 286593800, 768920084, 2083170960, 5642886852, 15250029552, 41369986008, 112681853344, 306930498205, 836259756612
Offset: 0
-
a(n) = sum(k=0, n\3, binomial(3*k+1, n-3*k)*binomial(4*k, k)/(3*k+1));
A366593
G.f. A(x) satisfies A(x) = 1 + x^2*(1+x)^3*A(x)^4.
Original entry on oeis.org
1, 0, 1, 3, 7, 25, 82, 278, 992, 3552, 12985, 48107, 179977, 680079, 2589915, 9931573, 38319117, 148640195, 579349123, 2267818509, 8911575579, 35141656433, 139018921717, 551557089103, 2194155973751, 8750097458849, 34973989188202, 140085055366350
Offset: 0
-
a(n) = sum(k=0, n\2, binomial(3*k, n-2*k)*binomial(4*k, k)/(3*k+1));
Showing 1-10 of 10 results.