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-5 of 5 results.

A108643 Number of binary rooted trees with n nodes and internal path length n.

Original entry on oeis.org

1, 1, 0, 2, 0, 1, 4, 0, 4, 2, 8, 6, 8, 8, 8, 40, 4, 29, 40, 52, 56, 64, 116, 112, 200, 86, 296, 366, 360, 432, 652, 800, 840, 1470, 1116, 2048, 2356, 3052, 3524, 4220, 5648, 6964, 9660, 8688, 14128, 17024, 19432, 23972, 32784, 37873, 44912, 59672, 67560, 93684
Offset: 0

Views

Author

N. J. A. Sloane and Nadia Heninger, Jul 08 2005

Keywords

Comments

Self-convolution equals A095830 (number of binary trees of path length n). - Paul D. Hanna, Aug 20 2007

References

  • Knuth Vol. 1 Sec. 2.3.4.5, Problem 5.

Links

Programs

  • Maple
    A:= proc(n,k) option remember; if n=0 then 1 else convert(series(1+ x^k*A(n-1, k+1)^2, x,n+1), polynom) fi end: a:= n-> coeff(A(n,1), x,n): seq(a(n), n=0..60);  # Alois P. Heinz, Aug 22 2008
  • Mathematica
    A[n_, k_] := A[n, k] = If[n==0, 1, 1+x^k*A[n-1, k+1]^2 + O[x]^(n+1) // Normal]; a[n_] := SeriesCoefficient[A[n, 1], {x, 0, n}]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Mar 14 2017, after Alois P. Heinz *)
  • PARI
    {a(n)=local(A=1+x*O(x^n)); for(j=0,n-1,A=1+x^(n-j)*A^2);polcoeff(A,n)} \\ Paul D. Hanna, Aug 20 2007

Formula

G.f. = B(w, w) where B(w, z) is defined in A095830.
G.f.: A(x) = 1 + x*(A_2)^2; A_2 = 1 + x^2*(A_3)^2; A_3 = 1 + x^3*(A_4)^2; ... A_n = 1 + x^n*(A_{n+1})^2 for n>=1 with A_1 = A(x). - Paul D. Hanna, Aug 20 2007

Extensions

More terms from Vladeta Jovovic, Jul 08 2005

A106182 Number of inequivalent binary sequences of length n, where two sequences are said to be equivalent if they have the same set of phrases in their Ziv-Lempel encodings (the phrases can appear in a different order in the two sequences).

Original entry on oeis.org

1, 2, 3, 6, 8, 14, 20, 32, 48, 60, 109, 138, 200, 296, 404, 576, 776, 1170, 1480, 2144, 2912, 3888, 5578, 7204, 10032, 13276
Offset: 0

Views

Author

N. J. A. Sloane, Aug 23 2005

Keywords

Comments

The Ziv-Lempel encoding scans the sequence from left to right and inserts a comma when the current phrase is an extension by one bit of an earlier phrase. In any case the scan ends with a comma. The phrases are the segments between the commas.
Equivalent sequences necessarily have the same Hamming weight.

Examples

			The Ziv-Lempel encodings of the strings of lengths 1 through 3 are:
0,
1, so a(1)=2;
0,0,
0,1,
1,0, (same phrases as in previous line)
1,1, so a(2)=3;
0,00,
0,01,
0,1,0,
1,0,0, (same phrases as in previous line)
0,1,1,
1,0,1, (same phrases as in previous line)
1,10,
1,11, so a(3)=6; ...

References

  • J. Ziv and A. Lempel, A universal algorithm for sequential data compression. IEEE Trans. Information Theory IT-23 (1977), 337-343.

Links

Crossrefs

Row sums of A109338. Cf. A109337.
Cf. A095830.

Programs

  • Tcl
    proc compress_phrases {vec} {set cur []; foreach v $vec {lappend cur $v
if {![info exists phrases($cur)]} {set phrases($cur) 1; set cur []}}
set plist [array names phrases]; if {[llength $cur]} {lappend plist $cur}
return [lsort $plist]}
proc enum {n vec} {if {$n == 0} {global phraselists
set phraselists([compress_phrases $vec]) 1} else {incr n -1
enum $n [concat $vec [list 0]];enum $n [concat $vec [list 1]]}}
proc doit {} {global phraselists; set n 0; while {1} {array unset phraselists
enum $n []; puts -nonewline "[array size phraselists],"; flush stdout; incr n}}
doit
# David Applegate

Formula

Seroussi shows that a(n) is asymptotically 2^{2cn/log_2(n)(1+o(1))}, where c = 0.11... is the inverse entropy function of 1/2.

Extensions

Terms from a(6) onwards from David Applegate, Aug 29 2005
Terms a(0)-a(20) confirmed and a(21)-a(25) added by John W. Layman, Sep 20 2010

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

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

Original entry on oeis.org

1, 0, 2, 0, 0, 1, 4, 0, 0, 0, 0, 4, 2, 8, 0, 0, 0, 0, 0, 0, 6, 8, 8, 4, 16, 0, 0, 0, 0, 0, 0, 0, 0, 4, 24, 4, 28, 16, 16, 8, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 24, 36, 48, 24, 56, 40, 56, 32, 32, 16, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 60, 72, 144, 26, 168, 104, 128, 64, 176, 80, 112
Offset: 0

Views

Author

Emeric Deutsch, Mar 20 2008

Keywords

Comments

Row n has 1+n*(n+1)/2 terms.
Row sums are the Catalan numbers (A000108).
Column sums yield A095830.
Sum_{k>=0} k*T(n,k) = A138156(n).
The g.f. B(w,z) in the Knuth reference is related to the above G(t,z) through B(t,z)=1+zG(t,z).

Examples

			T(2,3) = 4 because we have the path trees LL, LR, RL and RR, where L (R) denotes a left (right) edge; each of these four trees has path length 3.
Triangle starts:
  1;
  0,2;
  0,0,1,4;
  0,0,0,0,4,2,8;
  0,0,0,0,0,0,6,8,8,4,16;
  0,0,0,0,0,0,0,0,4,24,4,28,16,16,8,32;

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. A000108, A095830, A138156.

Programs

  • Maple
    P[0]:=1: for n to 7 do P[n]:=sort(expand(t^n*(2*P[n-1]+add(P[i]*P[n-2-i],i= 0..n-2)))) end do: for n from 0 to 7 do seq(coeff(P[n],t,j),j=0..(1/2)*n*(n+1)) end do; # yields sequence in triangular form
  • Mathematica
    p[n_] := p[n] = t^n*(2p[n-1] + Sum[p[i]*p[n-2-i], {i, 0, n-2}]); p[0] = 1; Flatten[ Table[ CoefficientList[ p[n], t], {n, 0, 7}]] (* Jean-François Alcover, Jul 22 2011, after Maple prog. *)

Formula

G.f.: G(t,z) satisfies G(t,z) = 1 + 2*t*z*G(t,t*z) + (t*z*G(t,t*z))^2. The row generating polynomials P[n] = P[n](t) (n=1,2,...) are given by P[n] = t^n*(2*P[n-1] + Sum_{i=0..n-2} P[i]*P[n-2-i]); P[0] = 1.

A132331 G.f.: A(x) = (A_1)^3 where A_1 = 1 + x*(A_2)^3; A_2 = 1 + x^2*(A_3)^3; A_3 = 1 + x^3*(A_4)^3; ... A_n = 1 + x^n*(A_{n+1})^3 for n>=1.

Original entry on oeis.org

1, 3, 3, 10, 18, 18, 72, 93, 141, 381, 423, 990, 1701, 2304, 4998, 7275, 12960, 21195, 34812, 58860, 90576, 163603, 239445, 413964, 669096, 1017918, 1768608, 2639988, 4383036, 6880680, 10911267, 17411292, 26930250, 43797420, 66324909, 107180772
Offset: 0

Views

Author

Paul D. Hanna, Aug 20 2007

Keywords

Crossrefs

Cf. A132330 (cube-root); A001764; A095830 (variant).

Programs

  • PARI
    {a(n)=local(A=1+x*O(x^n)); for(j=0,n-1,A=1+x^(n-j)*A^3);polcoeff(A^3,n)}

Formula

Self-convolution cube of A132330.
Showing 1-5 of 5 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.