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.

A036662 Shapes of height-balanced AVL trees of height at most 5 with n nodes.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 6, 4, 17, 32, 44, 60, 70, 184, 476, 872, 1553, 2720, 4288, 6312, 9004, 11992, 14372, 15400, 14630, 11968, 8104, 4376, 1820, 560, 120, 16, 1
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

References

  • F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.

Links

Crossrefs

Cf. A006265, A143897.

Programs

  • Maple
    a:= proc(n) 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; coeff(B(z,0,5), z,n) end: seq(a(n), n=0..32); # Alois P. Heinz, Aug 27 2008
  • Mathematica
    a[n_] := Module[{B, z}, B[x_, y_, d_] := If[d >= 1, x+B[x^2+2*x*y, x, d-1], x];  Coefficient[B[z, 0, 5], z, n]]; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Feb 24 2015, after Alois P. Heinz *)

Formula

a(n) = Sum_{h=0..5} A143897(h,n). - Alois P. Heinz, Mar 17 2013

A134306 Number of shapes of height-balanced AVL trees of height at most 6 with n nodes.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 6, 4, 17, 32, 44, 60, 70, 184, 476, 872, 1553, 2720, 4288, 6312, 9004, 16088, 36900, 82984, 174374, 346048, 653096, 1199384, 2160732, 3812464, 6617304, 11307920, 18978577, 31327104, 50882720, 80963520, 125489856, 188637520, 273984664
Offset: 0

Views

Author

Alois P. Heinz, Aug 27 2008

Keywords

References

  • F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.

Links

Crossrefs

Cf. A006265, A036662.

Programs

  • Maple
    a:= proc(n) 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; coeff(B(z,0,6), z,n) end: seq(a(n), n=0..64);
  • Mathematica
    a[n_] := Module[{B, z}, B[x_, y_, d_] := B[x, y, d] = If[d >= 1, x+B[x^2+2*x*y, x, d-1], x]; Coefficient[B[z, 0, 6], z, n]]; Table[a[n], {n, 0, 64}] (* Jean-François Alcover, Mar 05 2014, after Alois P. Heinz *)

Formula

a(n) = Sum_{h=0..6} A143897(h,n).

A296103 Number of shapes of left-leaning height-balanced AVL trees with n (inner) nodes.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 2, 3, 5, 7, 9, 11, 13, 17, 26, 42, 66, 97, 134, 180, 241, 321, 424, 564, 774, 1111, 1661, 2545, 3925, 6012, 9079, 13480, 19678, 28296, 40212, 56701, 79599, 111469, 155795, 217301, 302590, 421396, 588782, 828633, 1178919, 1699502, 2483695
Offset: 0

Views

Author

Katarzyna Matylla, Dec 04 2017

Keywords

Comments

A left-leaning AVL tree is a binary rooted tree where at any node, the height of left subtree is equal to the height of right subtree or greater by 1.

Links

Crossrefs

Cf. A006265.

Programs

  • Maple
    B:= proc(x, y, d, a, b) option remember; `if`(a+b<=d,
      B(x^2+x*y, x, d, a+b, a)+x, x)
    end:
a:= n-> coeff(B(z, 0, n+1, 1, 1), z, n+1):
seq(a(n), n=0..60);  # Alois P. Heinz, Dec 05 2017
  • Mathematica
    B[x_, y_, d_, a_, b_] := B[x, y, d, a, b] = If[a + b <= d, B[x^2 + x*y, x, d, a + b, a] + x, x];
a[n_] :=  Coefficient[B[z, 0, n+1, 1, 1], z, n+1];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, May 31 2019, after Alois P. Heinz *)
  • Python
    # see link above
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.