A319027 Number of preimages of 321-avoiding permutations of [n] under West's stack-sorting map.

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

Table of n, a(n) for n=1..25.

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

Sequence in context: A329788 A177518 A369832 * A228397 A164871 A226436

Adjacent sequences: A319024 A319025 A319026 * A319028 A319029 A319030

Keyword

nonn,more

Author

Colin Defant, Sep 08 2018

Extensions

Terms a(10) and beyond from Yonah Biers-Ariel, May 27 2020

Status

approved