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.

A143897 Triangle read by rows: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, n>=0, fibonacci(n+2)<=k<=2^n.

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 4, 1, 16, 32, 44, 60, 70, 56, 28, 8, 1, 128, 448, 864, 1552, 2720, 4288, 6312, 9004, 11992, 14372, 15400, 14630, 11968, 8104, 4376, 1820, 560, 120, 16, 1, 4096, 22528, 67584, 159744, 334080, 644992, 1195008, 2158912, 3811904, 6617184
Offset: 0

Views

Author

Alois P. Heinz, Sep 04 2008

Keywords

Examples

			There are 2 AVL trees of height 2 with 3 (leaf-) nodes:
       o       o
      / \     / \
     o   N   N   o
    / \         / \
   N   N       N   N
Triangle begins:
  1
  . 1
  . . 2 1
  . . . . 4 6 4  1
  . . . . . . . 16 32 44 60 70  56  28   8    1
  . . . . . . .  .  .  .  .  . 128 448 864 1552 2720 ...

References

  • F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.
  • D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Links

Crossrefs

Row sums give: A029758.
Column sums give: A006265.
Column sums of first 5 or 6 rows give: A036662 or A134306.
First elements of rows give: A174677.
First, last elements of columns give: A217299, A217300.
Row lengths give: 1+A008466(n).
Column heights give: A217710(k).
Triangle read by columns gives: A217298.
Cf. A000045, A000079.

Programs

  • Maple
    T:= proc(n,k) local B, z; B:= proc(x,y,d) if d>=1 then x+B(x^2+2*x*y, x, d-1) else x fi end; if n=0 then if k=1 then 1 else 0 fi else coeff(B(z,0,n), z,k) -coeff(B(z,0,n-1), z,k) fi end: fib:= m-> (Matrix([[1,1], [1,0]])^m)[1,2]: seq(seq(T(n,k), k=fib(n+2)..2^n), n=0..6);
  • Mathematica
    t[n_, k_] := Module[{ b, z }, b[x_, y_, d_] := If[d >= 1, x + b[x^2 + 2*x*y, x, d-1], x]; If[n == 0, If[k == 1, 1, 0], Coefficient[b[z, 0, n], z, k] - Coefficient [b[z, 0, n-1], z, k]]]; fib[m_] := MatrixPower[{{1, 1}, {1, 0}}, m][[1, 2]]; Table[Table[t[n, k], {k, fib[n+2], 2^n}], {n, 0, 6}] // Flatten (* Jean-François Alcover, Dec 05 2013, translated from Alois P. Heinz's Maple program *)

Formula

See program.

A217298 Triangle read by columns: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 4, 1, 16, 32, 44, 60, 70, 56, 128, 28, 448, 8, 864, 1, 1552, 2720, 4288, 6312, 9004, 11992, 4096, 14372, 22528, 15400, 67584, 14630, 159744, 11968, 334080, 8104, 644992, 4376, 1195008, 1820, 2158912, 560, 3811904, 120, 6617184, 16, 11307904
Offset: 1

Views

Author

Alois P. Heinz, Mar 17 2013

Keywords

Examples

			There are 2 AVL trees of height 2 with 3 (leaf-) nodes:
       o       o
      / \     / \
     o   N   N   o
    / \         / \
   N   N       N   N
Triangle begins:
  1
  . 1
  . . 2 1
  . . . . 4 6 4  1
  . . . . . . . 16 32 44 60 70  56  28   8    1
  . . . . . . .  .  .  .  .  . 128 448 864 1552 2720 ...

References

  • F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.
  • D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Links

Crossrefs

Triangle read by rows gives: A143897.
Row sums give: A029758.
Column sums give: A006265.
First elements of rows give: A174677.
First, last elements of columns give: A217299, A217300.
Row lengths give: 1+A008466(n).
Column heights give: A217710(k).
Cf. A029837, A072649.

A228152 Triangle read by rows: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, n>=0, fibonacci(n+2)<=k<=2^n.

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 24, 25, 30, 35, 40, 44, 49, 54, 59, 64, 50, 56, 62, 68, 73, 79, 85, 91, 97, 102, 107, 113, 119, 125, 131, 136, 142, 148, 154, 160, 96, 103, 110, 117, 123, 130, 137, 144, 151, 157, 163, 170, 177, 184, 191, 197, 204, 211, 218, 225, 231
Offset: 0

Views

Author

Herbert Eberle, Aug 13 2013

Keywords

Comments

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

Examples

			T(2,3) = 5 because in the (two) AVL trees of height 2 with 3 (leaf-) nodes one has depth 1 and two have depth 2:
       o       o
      / \     / \
     o   1   1   o
    / \         / \
   2   2       2   2
so that the sum of depths is 5 for both trees.
Triangle begins:
  0
  . 2
  . . 5 8
  . . . . 12 16 20 24
  . . . .  .  .  . 25 30 35 40 44 49 54 59 64
  . . . .  .  .  .  .  .  .  .  . 50 56 62 68 73 79 85 91 97 102 ...
  . . . .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 96 103 ...

References

  • D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Links

Crossrefs

Row maxima give: n*2^n = A036289(n).
Row minima give: A067331(n-1) for n>0 or A166106(n+2).
Row lengths give: 1+A008466(n).
Number of AVL trees read by rows gives: A143897.
Triangle read by columns gives: A228153.
The infimum of all external path lengths of binary trees with k (leaf-) nodes is: A003314(k) for k>0.
Column maxima give: A228155(k).
Column heights give: A217710(k).
Number of AVL trees read by columns gives: A217298.

Programs

  • Maple
    with(combinat): F:=fibonacci:
T:= proc(n, k) option remember; `if`(n<1, 0, max(seq([k+T(n-1,t)+
      T(n-1,k-t), k+T(n-1,t) +T(n-2,k-t)][], t=F(n+1)..k-1)))
    end:
seq(seq(T(n, k), k=F(n+2)..2^n), n=0..7);  # Alois P. Heinz, Aug 14 2013
  • Mathematica
    maxNods = 100; Clear[T, A029837, A072649, A036289, A228155]; T[0, 1] = 0; A029837[1] = 0; A072649[1] = 1; A228155[1] = 0; For[k = 2, k <= maxNods, k++, A029837[k] = maxNods; A072649[k] = 0; A228155u = 0; For[kL = 1, kL <= Floor[k/2], kL++, For[hL = A029837[kL], hL <= A072649[kL] - 1, hL++, For[hR = Max[hL - 1, A029837[k - kL]], hR <= Min[hL + 1, A072649[k - kL] - 1], hR++, maxDepthSum = k + T[hL, kL] + T[hR, k - kL]; A228155u = Max[maxDepthSum, A228155u]; h = Max[hL, hR] + 1; If[ !IntegerQ[T[h, k]], T[h, k] = maxDepthSum, T[h, k] = Max[maxDepthSum, T[h, k]]]; A029837[k] = Min[h, A029837[k]]; If[ !IntegerQ[A036289[h]], A036289[h] = maxDepthSum, A036289[h] = Max[maxDepthSum, A036289[h]]]; A072649[k] = Max[h + 1, A072649[k]]; ]]]; A228155[k] = A228155u]; k =.; Table[T[n, k], {n, 0, maxNods}, {k, 1, maxNods}] // Flatten // Select[#, IntegerQ]& (* Jean-François Alcover, Aug 14 2013, translated and adapted from Herbert Eberle's MuPAD program *)
  • MuPAD
    maxNods:=100: // max number of leaves (= external nodes)
// Triangle T for all AVL trees with <= maxNods leaves:
delete T:
// table T indexed [h, k] (h=height, k=number of leaves):
T[0, 1]:=0:
// A029837 indexed [k], min height of tree with k leaves:
A029837:=array(1..maxNods): A029837[1]:=0:
// A072649 indexed [k], 1+max height of AVL tree with k leaves:
A072649:=array(1..maxNods): A072649[1]:=1:
// A036289 indexed [h], max depthsum of all height h AVL trees:
A036289:=array(1..maxNods):
// A228155 indexed [k], max depthsum of all AVL trees with k leaves:
A228155:=array(1..maxNods): A228155[1]:=0:
for k from 2 to maxNods do:
  A029837[k]:=maxNods: // try infinity for the min height
  A072649[k]:=0:
  A228155u:=0:
  // Put together 2 AVL trees:
  for kL from 1 to floor(k/2) do:
    // kL leaves in the left tree
    for hL from A029837[kL] to A072649[kL]-1 do:
      for hR from max(hL-1, A029837[k-kL])
               to min(hL+1, A072649[k-kL]-1) do:
        // k-kL leaves in the right subtree
        maxDepthSum:=T[hL, kL]+T[hR, k-kL]+k:
        A228155u:=max(maxDepthSum, A228155u):
        h:=max(hL, hR)+1:
        if type(T[h, k]) <> DOM_INT then // T[h, k] uninit
          T[h, k]:=maxDepthSum:
        else
          T[h, k]:=max(maxDepthSum, T[h, k]):
        end_if:
        A029837[k]:=min(h, A029837[k]):
        if type(A036289[h]) <> DOM_INT then
          A036289[h]:=maxDepthSum:
        else
          A036289[h]:=max(maxDepthSum, A036289[h]):
        end_if:
        A072649[k]:=max(h+1, A072649[k]):
      end_for: // hR
    end_for: // hL
  end_for: // kL
  A228155[k]:=A228155u:
end_for: // k

A228153 Triangle read by columns: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 24, 25, 30, 35, 40, 44, 49, 50, 54, 56, 59, 62, 64, 68, 73, 79, 85, 91, 97, 96, 102, 103, 107, 110, 113, 117, 119, 123, 125, 130, 131, 137, 136, 144, 142, 151, 148, 157, 154, 163, 160, 170, 177, 184, 180, 191, 188, 197, 196, 204, 204
Offset: 1

Views

Author

Herbert Eberle, Aug 13 2013

Keywords

Comments

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

Examples

			In the (two) AVL trees of height 2 the 3 external nodes (leaves) have once depth 1 and twice depth 2:
       o       o
      / \     / \
     o   1   1   o
    / \         / \
   2   2       2   2
so that the sum of depths is 5 for both trees.
Triangle begins:
  0
  . 2
  . . 5 8
  . . . . 12 16 20 24
  . . . .  .  .  . 25 30 35 40 44 49 54 59 64
  . . . .  .  .  .  .  .  .  .  . 50 56 62 68 73 79 85 91 97 102 ...
  . . . .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 96 103 ...

References

  • D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Links

Crossrefs

Triangle read by rows gives: A228152.
Row maxima give: n*2^n = A036289(n).
Row minima give: A067331(n-1) for n>0 or A166106(n+2).
Row lengths give: 1+A008466(n).
Number of AVL trees read by rows gives: A143897.
The infimum of all external path lengths of binary trees with k (leaf-) nodes is: A003314(k) for k>0.
Column maxima give: A228155(k).
Column heights give: A217710(k).
Number of AVL trees read by columns gives: A217298.

Programs

  • Mathematica
    maxNods = 100; Clear[T, A029837, A072649, A036289, A228155]; T[0, 1] = 0; A029837[1] = 0; A072649[1] = 1; A228155[1] = 0; For[k = 2, k <= maxNods, k++, A029837[k] = maxNods; A072649[k] = 0; A228155u = 0; For[kL = 1, kL <= Floor[k/2], kL++, For[hL = A029837[kL], hL <= A072649[kL] - 1, hL++, For[hR = Max[hL - 1, A029837[k - kL]], hR <= Min[hL + 1, A072649[k - kL] - 1], hR++, maxDepthSum = k + T[hL, kL] + T[hR, k - kL]; A228155u = Max[maxDepthSum, A228155u]; h = Max[hL, hR] + 1; If[ !IntegerQ[T[h, k]], T[h, k] = maxDepthSum, T[h, k] = Max[maxDepthSum, T[h, k]]]; A029837[k] = Min[h, A029837[k]]; If[ !IntegerQ[A036289[h]], A036289[h] = maxDepthSum, A036289[h] = Max[maxDepthSum, A036289[h]]]; A072649[k] = Max[h + 1, A072649[k]]; ]]]; A228155[k] = A228155u]; k =.; Table[ Select[ Table[T[n, k], {n, A029837[k], A072649[k] - 1}], IntegerQ], {k, 1, maxNods}] // Flatten (* Jean-François Alcover, Aug 19 2013, translated and adapted from Herbert Eberle's MuPAD program *)
  • MuPAD
    maxNods:=100: // max number of leaves (= external nodes)
// Triangle T for all AVL trees with <= maxNods leaves:
delete T:
// table T indexed [h, k] (h=height, k=number of leaves):
T[0, 1]:=0:
// A029837 indexed [k], min height of tree with k leaves:
A029837:=array(1..maxNods): A029837[1]:=0:
// A072649 indexed [k], 1+max height of AVL tree with k leaves:
A072649:=array(1..maxNods): A072649[1]:=1:
// A036289 indexed [h], max depthsum of all height h AVL trees:
A036289:=array(1..maxNods):
// A228155 indexed [k], max depthsum of all AVL trees with k leaves:
A228155:=array(1..maxNods): A228155[1]:=0:
for k from 2 to maxNods do:
  A029837[k]:=maxNods: // try infinity for the min height
  A072649[k]:=0:
  A228155u:=0:
  // Put together 2 AVL trees:
  for kL from 1 to floor(k/2) do:
    // kL leaves in the left tree
    for hL from A029837[kL] to A072649[kL]-1 do:
      for hR from max(hL-1, A029837[k-kL])
               to min(hL+1, A072649[k-kL]-1) do:
        // k-kL leaves in the right subtree
        maxDepthSum:=T[hL, kL]+T[hR, k-kL]+k:
        A228155u:=max(maxDepthSum, A228155u):
        h:=max(hL, hR)+1:
        if type(T[h, k]) <> DOM_INT then // T[h, k] uninit
          T[h, k]:=maxDepthSum:
        else
          T[h, k]:=max(maxDepthSum, T[h, k]):
        end_if:
        A029837[k]:=min(h, A029837[k]):
        if type(A036289[h]) <> DOM_INT then
          A036289[h]:=maxDepthSum:
        else
          A036289[h]:=max(maxDepthSum, A036289[h]):
        end_if:
        A072649[k]:=max(h+1, A072649[k]):
      end_for: // hR
    end_for: // hL
  end_for: // kL
  A228155[k]:=A228155u:
end_for: // k

A228155 Maximal external path length of AVL trees with n (leaf-) nodes.

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 25, 30, 35, 40, 44, 50, 56, 62, 68, 73, 79, 85, 91, 97, 103, 110, 117, 123, 130, 137, 144, 151, 157, 163, 170, 177, 184, 191, 197, 204, 211, 219, 227, 235, 243, 250, 257, 265, 273, 281, 289, 296, 304, 312, 320, 328, 335, 342, 349, 356
Offset: 1

Views

Author

Herbert Eberle, Aug 14 2013

Keywords

Comments

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

Examples

			The (two) AVL trees with 3 (leaf-) nodes have one with depth 1 and two with depth 2:
       o       o
      / \     / \
     o   1   1   o
    / \         / \
   2   2       2   2
so a(3) = 5.

References

  • D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Links

Crossrefs

Column maxima of triangles A228152, A228153.
Row maxima give: n*2^n = A036289(n).
Row minima give: A067331(n-1) for n>0 or A166106(n+2).
Row lengths give: 1+A008466(n).
Column heights give: A217710(k).
Number of AVL trees read by rows gives: A143897.
The infimum of all external path lengths of all binary trees with k (leaf-) nodes is: A003314(k) for k>0.
Number of AVL trees read by columns gives: A217298.

Programs

  • Mathematica
    maxNods = 100; Clear[T, A029837, A072649, A036289, A228155]; T[0, 1] = 0; A029837[1] = 0; A072649[1] = 1; A228155[1] = 0; For[k = 2, k <= maxNods, k++, A029837[k] = maxNods; A072649[k] = 0; A228155u = 0; For[kL = 1, kL <= Floor[k/2], kL++, For[hL = A029837[kL], hL <= A072649[kL] - 1, hL++, For[hR = Max[hL - 1, A029837[k - kL]], hR <= Min[hL + 1, A072649[k - kL] - 1], hR++, maxDepthSum = k + T[hL, kL] + T[hR, k - kL]; A228155u = Max[maxDepthSum, A228155u]; h = Max[hL, hR] + 1; If[ !IntegerQ[T[h, k]], T[h, k] = maxDepthSum, T[h, k] = Max[maxDepthSum, T[h, k]]]; A029837[k] = Min[h, A029837[k]]; If[ !IntegerQ[A036289[h]], A036289[h] = maxDepthSum, A036289[h] = Max[maxDepthSum, A036289[h]]]; A072649[k] = Max[h + 1, A072649[k]]; ]]]; A228155[k] = A228155u]; k =.; Table[A228155[k], {k, 1, maxNods}] (* Jean-François Alcover, Aug 19 2013, translated and adapted from Herbert Eberle's MuPAD program *)
  • MuPAD
    maxNods:=100: // max number of leaves (= external nodes)
// Triangle T for all AVL trees with <= maxNods leaves:
delete T:
// table T indexed [h, k] (h=height, k=number of leaves):
T[0, 1]:=0:
// A029837 indexed [k], min height of tree with k leaves:
A029837:=array(1..maxNods): A029837[1]:=0:
// A072649 indexed [k], 1+max height of AVL tree with k leaves:
A072649:=array(1..maxNods): A072649[1]:=1:
// A036289 indexed [h], max depthsum of all height h AVL trees:
A036289:=array(1..maxNods):
// A228155 indexed [k], max depthsum of all AVL trees with k leaves:
A228155:=array(1..maxNods): A228155[1]:=0:
for k from 2 to maxNods do:
  A029837[k]:=maxNods: // try infinity for the min height
  A072649[k]:=0:
  A228155u:=0:
  // Put together 2 AVL trees:
  for kL from 1 to floor(k/2) do:
    // kL leaves in the left tree
    for hL from A029837[kL] to A072649[kL]-1 do:
      for hR from max(hL-1, A029837[k-kL])
               to min(hL+1, A072649[k-kL]-1) do:
        // k-kL leaves in the right subtree
        maxDepthSum:=T[hL, kL]+T[hR, k-kL]+k:
        A228155u:=max(maxDepthSum, A228155u):
        h:=max(hL, hR)+1:
        if type(T[h, k]) <> DOM_INT then // T[h, k] uninit
          T[h, k]:=maxDepthSum:
        else
          T[h, k]:=max(maxDepthSum, T[h, k]):
        end_if:
        A029837[k]:=min(h, A029837[k]):
        if type(A036289[h]) <> DOM_INT then
          A036289[h]:=maxDepthSum:
        else
          A036289[h]:=max(maxDepthSum, A036289[h]):
        end_if:
        A072649[k]:=max(h+1, A072649[k]):
      end_for: // hR
    end_for: // hL
  end_for: // kL
  A228155[k]:=A228155u:
end_for: // k
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.