cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A138156 Sum of the path lengths of all binary trees with n edges.

Original entry on oeis.org

0, 2, 14, 74, 352, 1588, 6946, 29786, 126008, 527900, 2195580, 9080772, 37392864, 153434536, 627778954, 2562441466, 10438340104, 42449348236, 172376641924, 699100282156, 2832205421824, 11462854280536, 46354571222164
Offset: 0

Views

Author

Emeric Deutsch, Mar 20 2008

Keywords

Comments

a(n) = 2*A006419(n).
If (2*n+3) prime, then A138156(n) mod (2*n+3) == 0. - Alzhekeyev Ascar M, Jul 19 2011

Examples

			a(1) = 2 because the trees with one edge are (i) root with a left child and (ii) root with a right child, each having path length 1.

References

  • D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1997, Vol. 1, p. 405 (exercise 5) and p. 595 (solution).

Links

Crossrefs

Cf. A095830, A138157, A006419.

Programs

  • Maple
    a:= n-> 4^(n+1)-(3*n+4)*binomial(2*n+2, n+1)/(n+2): seq(a(n), n=0..22);
  • Mathematica
    Table[4^(n+1)-(3n+4) Binomial[2n+2,n+1]/(n+2),{n,0,30}] (* Harvey P. Dale, Dec 14 2014 *)

Formula

a(n) = 4^(n+1) - (3*n+4) * C(2*n+2,n+1)/(n+2).
G.f.: 1/(z*(1-4*z)) - ((1-z)/sqrt(1-4*z)-1)/z^2.
D-finite with recurrence (n+2)*a(n) +(-9*n-10)*a(n-1) +2*(12*n+1)*a(n-2) +8*(-2*n+3)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

A275670 G.f. A(x,y) satisfies: A(x,y) = x*y + A(x,x*y)^2, with A(0,y) = 1.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 4, 0, 8, 1, 0, 16, 4, 0, 32, 14, 0, 64, 40, 0, 128, 108, 2, 0, 256, 272, 12, 0, 512, 664, 52, 0, 1024, 1568, 188, 0, 2048, 3632, 608, 1, 0, 4096, 8256, 1816, 12, 0, 8192, 18528, 5128, 76, 0, 16384, 41088, 13856, 360, 0, 32768, 90304, 36176, 1446, 0, 65536, 196864, 91856, 5192, 4, 0, 131072, 426368, 227968, 17192, 42, 0, 262144, 918016, 555040, 53504, 284, 0, 524288, 1966848, 1329696, 158588, 1496, 0, 1048576, 4195328, 3141632, 451824, 6704, 0, 2097152, 8914432, 7334208, 1245936, 26772, 6
Offset: 0

Views

Author

Paul D. Hanna, Aug 04 2016

Keywords

Comments

Compare g.f. to G(x,y) = x*y + G(x*y,y)^2 with G(0,y) = 0, which generates triangle A138157.
Apparently, the g.f. of column n equals y^n*x^A033156(n) * P(n,x)/Q(n,x), where:
Q(n,x) = Product_{k=1..n} (1 - 2*x^k)^floor(n/k),
and P(n,x) is of degree A024916(n) - A033156(n).

Examples

			G.f.: A(x,y) = 1 + y*x + 2*y*x^2 + 4*y*x^3 + (y^2 + 8*y)*x^4 + (4*y^2 + 16*y)*x^5 + (14*y^2 + 32*y)*x^6 + (40*y^2 + 64*y)*x^7 + (2*y^3 + 108*y^2 + 128*y)*x^8 + (12*y^3 + 272*y^2 + 256*y)*x^9 + (52*y^3 + 664*y^2 + 512*y)*x^10 + (188*y^3 + 1568*y^2 + 1024*y)*x^11 + (y^4 + 608*y^3 + 3632*y^2 + 2048*y)*x^12 +...
such that A(x,y) = x*y + A(x,x*y)^2, with A(0,y) = 1; further,
A(x,y) = x*y + ( x^2*y + A(x,x^2*y)^2 )^2,
A(x,y) = x*y + ( x^2*y + ( x^3*y + A(x,x^3*y)^2 )^2 )^2, etc.
This table of coefficients in g.f. A(x,y) begins:
1;
0, 1;
0, 2;
0, 4;
0, 8, 1;
0, 16, 4;
0, 32, 14;
0, 64, 40;
0, 128, 108, 2;
0, 256, 272, 12;
0, 512, 664, 52;
0, 1024, 1568, 188;
0, 2048, 3632, 608, 1;
0, 4096, 8256, 1816, 12;
0, 8192, 18528, 5128, 76;
0, 16384, 41088, 13856, 360;
0, 32768, 90304, 36176, 1446;
0, 65536, 196864, 91856, 5192, 4;
0, 131072, 426368, 227968, 17192, 42;
0, 262144, 918016, 555040, 53504, 284;
0, 524288, 1966848, 1329696, 158588, 1496;
0, 1048576, 4195328, 3141632, 451824, 6704;
0, 2097152, 8914432, 7334208, 1245936, 26772, 6;
0, 4194304, 18876416, 16943680, 3342784, 98060, 80;
0, 8388608, 39848960, 38785536, 8761720, 335704, 636;
0, 16777216, 83890176, 88063616, 22508448, 1088496, 3844;
0, 33554432, 176166912, 198506624, 56822624, 3375096, 19492;
0, 67108864, 369106944, 444562432, 141270272, 10080760, 87184, 4;
0, 134217728, 771764224, 989807872, 346507120, 29167000, 354628, 80;
0, 268435456, 1610629120, 2192154880, 839762496, 82113648, 1338376, 812;
0, 536870912, 3355467776, 4831741952, 2013427136, 225746384, 4753320, 5916;
0, 1073741824, 6979354624, 10603063808, 4781027584, 607828752, 16052296, 35000;
0, 2147483648, 14495563776, 23174734336, 11254280416, 1606760304, 51954808, 178904, 1; ...
Row polynomials begin:
n=0: 1;
n=1: y;
n=2: 2*y;
n=3: 4*y;
n=4: 8*y + y^2;
n=5: 16*y + 4*y^2;
n=6: 32*y + 14*y^2;
n=7: 64*y + 40*y^2;
n=8: 128*y + 108*y^2 + 2*y^3;
n=9: 256*y + 272*y^2 + 12*y^3;
n=10: 512*y + 664*y^2 + 52*y^3;
n=11: 1024*y + 1568*y^2 + 188*y^3;
n=12: 2048*y + 3632*y^2 + 608*y^3 + y^4;
n=13: 4096*y + 8256*y^2 + 1816*y^3 + 12*y^4;
n=14: 8192*y + 18528*y^2 + 5128*y^3 + 76*y^4;
n=15: 16384*y + 41088*y^2 + 13856*y^3 + 360*y^4;
n=16: 32768*y + 90304*y^2 + 36176*y^3 + 1446*y^4;
n=17: 65536*y + 196864*y^2 + 91856*y^3 + 5192*y^4 + 4*y^5; ...
the first row in which y^m appears is given by n = A033156(m), where A033156 begins:
[1, 4, 8, 12, 17, 22, 27, 32, 38, 44, 50, 56, 62, 68, 74, 80, 87, 94, 101, 108, 115, 122, 129, 136, 143, 150, 157, 164, 171, 178, 185, 192, 200, ...].
Generating functions of initial columns.
G.f. of column 0: 1
G.f. of column 1: y*x/(1-2*x).
G.f. of column 2: y^2*x^4/((1-2*x)^2*(1-2*x^2)).
G.f. of column 3: y^3*2*x^8/((1-2*x)^3*(1-2*x^2)*(1-2*x^3)).
G.f. of column 4: y^4*x^12*(1 + 4*x - 10*x^3)/((1-2*x)^4*(1-2*x^2)^2*(1-2*x^3)*(1-2*x^4)).
G.f. of column 5: y^5*x^17*(4 + 2*x + 8*x^2 - 28*x^4)/((1-2*x)^5*(1-2*x^2)^2*(1-2*x^3)*(1-2*x^4)*(1-2*x^5)).
G.f. of column 6: y^6*x^22*(6 + 8*x - 20*x^3 - 24*x^4 - 36*x^5 - 56*x^6 + 16*x^7 + 176*x^8 + 224*x^9 - 336*x^11)/((1-2*x)^6*(1-2*x^2)^3*(1-2*x^3)^2*(1-2*x^4)*(1-2*x^5)*(1-2*x^6)).
G.f. of column 7: y^7*x^27*(4 + 24*x + 4*x^2 - 12*x^3 - 72*x^5 - 112*x^6 - 96*x^7 + 112*x^8 - 64*x^9 + 64*x^10 + 496*x^11 + 576*x^12 - 1056*x^14) / ((1-2*x)^7*(1-2*x^2)^3*(1-2*x^3)^2*(1-2*x^4)*(1-2*x^5)*(1-2*x^6)*(1-2*x^7)).
G.f. of column 8: y^8*x^32*(1 + 24*x + 36*x^2 - 4*x^3 - 88*x^4 - 202*x^5 - 14*x^6 - 82*x^7 - 168*x^8 + 400*x^9 + 440*x^10 + 892*x^11 + 1292*x^12 - 660*x^13 - 800*x^14 - 688*x^15 - 1776*x^16 - 1136*x^17 - 4504*x^18 - 2672*x^19 + 4672*x^20 + 5664*x^21 + 12672*x^22 - 13728*x^24) / ((1-2*x)^8*(1-2*x^2)^4*(1-2*x^3)^2*(1-2*x^4)^2*(1-2*x^5)*(1-2*x^6)*(1-2*x^7)*(1-2*x^8)).
G.f. of column 9: y^9*x^38*(8 + 60*x + 72*x^2 + 16*x^3 - 238*x^4 - 584*x^5 - 232*x^6 + 172*x^7 + 328*x^8 + 52*x^9 + 1012*x^10 + 2636*x^11 + 1464*x^12 + 520*x^13 - 2040*x^14 - 664*x^15 - 2360*x^16 - 8712*x^17 - 13008*x^18 - 3696*x^19 + 12080*x^20 + 15392*x^21 + 1456*x^22 - 11040*x^23 + 18112*x^24 + 37728*x^25 + 47040*x^26 - 34304*x^27 - 78144*x^28 - 73216*x^29 + 91520*x^31) / ((1-2*x)^9*(1-2*x^2)^4*(1-2*x^3)^3*(1-2*x^4)^2*(1-2*x^5)*(1-2*x^6)*(1-2*x^7)*(1-2*x^8)*(1-2*x^9)).
G.f. of column 10: y^10*x^44*(28 + 96*x + 198*x^2 - 160*x^3 - 864*x^4 - 596*x^5 - 856*x^6 - 384*x^7 + 3652*x^8 + 4752*x^9 + 696*x^10 - 2972*x^11 + 3928*x^12 + 4848*x^13 - 8360*x^14 - 18768*x^15 - 11000*x^16 - 14184*x^17 - 9896*x^18 + 17184*x^19 + 23664*x^20 + 7904*x^21 + 34480*x^22 + 53472*x^23 + 54160*x^24 + 68160*x^25 + 10560*x^26 - 166208*x^27 - 203488*x^28 - 86720*x^29 - 23552*x^30 + 13632*x^31 + 67584*x^32 - 95232*x^33 - 232256*x^34 + 129536*x^35 + 677632*x^36 + 624000*x^37 + 355840*x^38 - 67584*x^39 - 988416*x^40 - 1464320*x^41 + 1244672*x^43) / ((1-2*x)^10*(1-2*x^2)^5*(1-2*x^3)^3*(1-2*x^4)^2*(1-2*x^5)^2*(1-2*x^6)*(1-2*x^7)*(1-2*x^8)*(1-2*x^9)*(1-2*x^10)).
...
The g.f. of column n, y^n * x^A033156(n) * P(n,x)/Q(n,x), appears to have the following denominator:
Q(n,x) = Product_{k=1..n} (1 - 2*x^k)^floor(n/k), with
P(n,x) being a polynomial of degree A024916(n) - A033156(n),
where A024916(n) = Sum_{k=1..n} k*floor(n/k).
...

Links

Crossrefs

Cf. A274965 (row sums), A275691 (antidiagonal sums), A033156.
Cf. variant: A138157.

Programs

  • PARI
    /* Print first N rows of this triangle: */ N=32;
{a(n) = my(A=1 +x*O(x^n)); for(k=0, n, A = A^2 + y*x^(n+1-k)); polcoeff(A, n)}
{for(n=0, N, for(k=0,n, if(k==0,print1(polcoeff(a(n)+y*O(y^n),k,y)", "), if(polcoeff(a(n)+y*O(y^n),k,y)==0,break,print1(polcoeff(a(n)+y*O(y^n),k,y),", "))));print(""))}

Formula

G.f. A(x,y) satisfies: 1 = ...(((((A(x,y) - x*y)^(1/2) - x^2*y)^(1/2) - x^3*y)^(1/2) - x^4*y)^(1/2) - x^5*y)^(1/2) -...- x^n*y)^(1/2) -..., an infinite series of nested square roots.

A171793 Triangle read by rows: T(n,k) is the number of ternary trees with n edges and path length k; 0<=k<=n(n-1)/2.

Original entry on oeis.org

1, 1, 0, 3, 0, 0, 3, 9, 0, 0, 0, 1, 18, 9, 27, 0, 0, 0, 0, 0, 9, 45, 57, 54, 27, 81, 0, 0, 0, 0, 0, 0, 0, 36, 87, 270, 81, 297, 171, 162, 81, 243, 0, 0, 0, 0, 0, 0, 0, 0, 0, 84, 261, 567, 756, 936, 585, 972, 729, 891, 513, 486, 243, 729, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 126, 774, 1080
Offset: 0

Views

Author

Paul D. Hanna, Jan 29 2010

Keywords

Examples

			G.f.: A(x,q) = 1 + x + (3*q)*x^2 + (3*q^2 + 9*q^3)*x^3 + (q^3 + 18*q^4 + 9*q^5 + 27*q^6)*x^4 +...
A(x,q)^3 = 1 + 3*x + (3 + 9*q)*x^2 + (1 + 18*q + 9*q^2 + 27*q^3)*x^3 +...
Triangle begins:
1;
1;
0,3;
0,0,3,9;
0,0,0,1,18,9,27;
0,0,0,0,0,9,45,57,54,27,81;
0,0,0,0,0,0,0,36,87,270,81,297,171,162,81,243;
0,0,0,0,0,0,0,0,0,84,261,567,756,936,585,972,729,891,513,486,243,729;
0,0,0,0,0,0,0,0,0,0,0,126,774,1080,2817,2682,4383,1998,4941,3294,3780,2241,4374,2187,2673,1539,1458,729,2187; ...

Crossrefs

Cf. A001764 (row sums), A132331 (column sums), A138157 (variant).

Programs

  • PARI
    {T(n,k)=local(A=1+x);for(i=1,n,A=1+x*subst(A,x,q*x+x*O(x^n))^3); polcoeff(polcoeff(A,n,x)+O(q^(n*(n-1)/2+1)),k,q)}

Formula

G.f. satisfies: A(x,q) = 1 + x*A(q*x,q)^3.
Row sums equal A001764, which enumerates ternary trees and has g.f.: G(x) = 1 + x*G(x)^3.
Column sums equal A132331(k), which is the number of ternary trees of path length k.
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.