login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A246747 The number of binary heaps on n elements whose breadth-first search reading word avoids 231. 2
1, 1, 1, 2, 3, 7, 14, 37, 80, 222, 544, 1601, 4095, 12416, 33785, 105769, 293747, 935184, 2717376, 8848014, 26134254, 86210716, 262068267, 877833206, 2695238060, 9109101156, 28619396967, 97879220771, 310021153392, 1067906857449, 3440140082033, 11957123227292 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
Also, the number of binary heaps on n elements whose breadth-first search reading word avoids 312.
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
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 .
FORMULA
a(n) = Sum_{i=0..floor((n-1)/2))} A000108(i)*a(n-i-1).
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
May be equal to A245899.
Sequence in context: A364593 A123777 A245899 * A090828 A296416 A049367
KEYWORD
nonn
AUTHOR
Manda Riehl, Sep 04 2014
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 09:44 EDT 2024. Contains 371268 sequences. (Running on oeis4.)