login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 11
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 07:39 EDT 2021. Contains 348048 sequences. (Running on oeis4.)