login
a(n) is the number of permutations avoiding 312 that can be realized on increasing unary-binary trees with n nodes.
3

%I #23 Dec 11 2019 07:35:06

%S 1,1,2,3,7,14,37,80

%N a(n) is the number of permutations avoiding 312 that can be realized on increasing unary-binary trees with n nodes.

%C The number of permutations avoiding 312 in the classical sense which can be realized as labels on an increasing unary-binary tree read in the order they appear in a breadth-first search. (Note that breadth-first search reading word is equivalent to reading the tree left to right by levels, starting with the root.)

%C In some cases, more than one tree results in the same breadth-first search reading word, but here we count the permutations, not the trees.

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

%e For example, when n=4, a(n)=3. The permutations 1234, 1243, and 1324 all avoid 312 in the classical sense and occur as breadth-first search reading words on an increasing unary-binary tree with 4 nodes:

%e 1 1 1

%e / \ / \ / \

%e 2 3 2 4 3 2

%e | | |

%e 4 3 4

%Y A245902 appears to be the odd-indexed terms of this sequence.

%Y Cf. A245889 (the number of increasing unary-binary trees whose breadth-first reading word avoids 312).

%K nonn,more

%O 1,3

%A _Manda Riehl_, Aug 06 2014