login
A319027
Number of preimages of 321-avoiding permutations of [n] under West's stack-sorting map.
0
1, 2, 6, 24, 117, 652, 3988, 26112, 180126, 1295090, 9631656, 73676572, 577180996, 4615090192, 37562920238, 310523535692, 2602546111313, 22080769557894, 189403492226689, 1640772609911156, 14341379756793722, 126376359608556754, 1121937445109205927, 10028423238950860458, 90203410822880721480
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
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
Sequence in context: A329788 A177518 A369832 * A228397 A164871 A226436
KEYWORD
nonn,more
AUTHOR
Colin Defant, Sep 08 2018
EXTENSIONS
Terms a(10) and beyond from Yonah Biers-Ariel, May 27 2020
STATUS
approved