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).

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,3

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

Alois P. Heinz, Columns k = 1..1500, flattened

Ralf Hinze, Functional Pearls: Purely functional 1-2 brother trees, Journal of Functional Programming, 19(6):633-644, 2009, DOI: 10.1017/S0956796809007333.

R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.

Wikipedia, AVL tree

Index entries for sequences related to rooted trees

Example

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 ...

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.

Sequence in context: A345135 A291057 A143897 * A217299 A333340 A217300

Adjacent sequences: A217295 A217296 A217297 * A217299 A217300 A217301

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Mar 17 2013

Status

approved