OFFSET
1,2
COMMENTS
Let s denote West's stack-sorting map. Let Av_n(tau) be the set of permutations of [n] that avoid the pattern tau. The only length-3 pattern tau for which there is no known formula for |s^{-1}(Av_n(tau))| is 321.
It is known that 8.4199 <= lim_{n--> infinity} a(n)^{1/n} <= 11.6569.
LINKS
Yonah Biers-Ariel, Flexible_Scheme Maple package
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
EXAMPLE
Let s denote West's stack-sorting map. Among the permutations of [5], the only permutations pi for which s(pi) contains the pattern 321 are 35241, 34251, and 45231. The term a(5) = 117 counts all of the other permutations of [5].
MAPLE
(requires Flexible_Scheme package -- see links)
read `Flexible_Scheme.mpl`:
s:= {[[], []], [[1], []], [[2, 1], []], [[2, 1, 3], []], [[2, 3, 1], []], [[2, 3, 1, 4], []], [[1, 2], [[[0, 0, 0], 1]], 1], [[1, 2, 3], [[[0, 0, 0, 0], 1]], 1], [[1, 3, 2], [[[0, 0, 0, 0], 1]], 1], [[3, 1, 2], [[[0, 0, 0, 0], 2]], 1], [[3, 2, 1], [[[0, 1, 1, 0], 0]], 2], [[2, 1, 3, 4], [[[0, 0, 0, 0, 0], 3]], 1], [[2, 1, 4, 3], [[[0, 0, 0, 1, 0], 1]], 3], [[2, 3, 4, 1], [[[0, 0, 0, 0, 0], 1]], 1], [[2, 4, 1, 3], [[[0, 0, 0, 1, 0], 1], [[0, 0, 1, 0, 0], 1]], 4], [[2, 4, 3, 1], [[[0, 0, 0, 1, 0], 1], [[0, 0, 1, 0, 0], 1]], 2], [[4, 2, 1, 3], [[[0, 1, 1, 0, 0], 0]], 2], [[4, 2, 3, 1], [[[0, 0, 0, 1, 0], 2], [[0, 1, 0, 0, 0], 0]], 1], [[2, 3, 1, 4, 5], [[[0, 0, 0, 0, 0, 0], 4]], 1], [[2, 3, 1, 5, 4], [[[0, 0, 0, 0, 1, 0], 1], [[0, 0, 1, 0, 0, 0], 1]], 4], [[2, 3, 5, 1, 4], [[[0, 0, 0, 0, 0, 0], 1]], 1], [[2, 5, 3, 1, 4], [[[0, 0, 0, 0, 1, 0], 1], [[0, 0, 0, 1, 0, 0], 1], [[0, 0, 1, 0, 0, 0], 1]], 2], [[5, 2, 3, 1, 4], [[[0, 0, 0, 1, 0, 0], 2], [[0, 1, 0, 0, 0, 0], 0]], 1]}:
#let n be the number of terms desired
SeqS(s, n); # Yonah Biers-Ariel, May 27 2020
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Colin Defant, Sep 08 2018
EXTENSIONS
Terms a(10) and beyond from Yonah Biers-Ariel, May 27 2020
STATUS
approved