A246829 The number of binary heaps on n elements whose breadth-first search reading word avoids 321.

1, 1, 2, 3, 7, 16, 45, 111, 318, 881, 2686, 8033, 25470, 80480, 263977, 862865, 2891344, 9706757, 33178076, 113784968, 395303480, 1379160685, 4859274472, 17195407935, 61310096228, 219520467207, 790749207801, 2859542098634, 10391610220375, 37897965144166

Offset

1,3

Comments

Note that a breadth-first search reading word is equivalent to reading the tree labels left to right by levels, starting with the root.

For more information on heaps, see A056971.

Links

Table of n, a(n) for n=1..30.

D. Levin, L. Pudwell, M. Riehl, A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.

Manda Riehl (joint work with Derek Levin, Lara Pudwell, and Adam Sandberg), Page 92 of the Permutation Patterns 2014 Abstract Book

Eric Weisstein's World of Mathematics, Heap

Example

A heap on 4 elements is pictured in the 2nd link, and has breadth first reading word abcd. Then for n = 4 the a(4) = 3 heaps have reading words 1234, 1243, and 1324.

Crossrefs

Cf. A056971, A246747.

Sequence in context: A301902 A332885 A122031 * A296231 A089125 A289051

Adjacent sequences: A246826 A246827 A246828 * A246830 A246831 A246832

Keyword

nonn

Author

Manda Riehl, Sep 04 2014

Status

approved