|
%I #25 Jun 09 2018 06:17:48
%S 1,2,6,22,84,330,1308,5210,20796,83100,332232,1328598,5313732,
%T 21253620,85011864,340042246,1360158564
%N a(n) is the number of permutations avoiding 231 and 312 realizable on increasing strict binary trees with 2n-1 nodes.
%C The number of permutations avoiding 231 and 312 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. A strict binary tree is a tree graph where each node has 0 or 2 children. The permutation is found by reading the labels 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.
%e For example, when n=3, the permutations 12543, 12435, 13245, 13254, 12345,and 12354. all avoid 231 and 312 in the classical sense and occur as breadth-first search reading words on an increasing strict binary tree with 5 nodes.
%e . 1 1 1 1 1 1
%e . / \ / \ / \ / \ / \ / \
%e . 2 5 2 4 3 2 3 2 2 3 2 3
%e . / \ / \ / \ / \ / \ / \
%e . 4 3 3 5 4 5 5 4 4 5 5 4
%Y A bisection of A002083.
%K nonn,more
%O 1,2
%A _Manda Riehl_, Aug 05 2014
%E More terms from _N. J. A. Sloane_, Jul 07 2015
| 