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

%I #26 Feb 16 2025 08:33:23

%S 1,1,2,3,7,16,45,111,318,881,2686,8033,25470,80480,263977,862865,

%T 2891344,9706757,33178076,113784968,395303480,1379160685,4859274472,

%U 17195407935,61310096228,219520467207,790749207801,2859542098634,10391610220375,37897965144166

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

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

%C For more information on heaps, see A056971.

%H D. Levin, L. Pudwell, M. Riehl, A. Sandberg, <a href="http://www.etsu.edu/cas/math/pp2014/documents/talks/riehl.pdf">Pattern Avoidance on k-ary Heaps</a>, Slides of Talk, 2014. [broken link]

%H Manda Riehl (joint work with Derek Levin, Lara Pudwell, and Adam Sandberg), <a href="/A246747/a246747_1.png">Page 92 of the Permutation Patterns 2014 Abstract Book</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>

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

%Y Cf. A056971, A246747.

%K nonn,changed

%O 1,3

%A _Manda Riehl_, Sep 04 2014