%I #27 May 27 2020 14:44:54
%S 1,2,6,24,117,652,3988,26112,180126,1295090,9631656,73676572,
%T 577180996,4615090192,37562920238,310523535692,2602546111313,
%U 22080769557894,189403492226689,1640772609911156,14341379756793722,126376359608556754,1121937445109205927,10028423238950860458,90203410822880721480
%N Number of preimages of 321-avoiding permutations of [n] under West's stack-sorting map.
%C 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.
%C It is known that 8.4199 <= lim_{n--> infinity} a(n)^{1/n} <= 11.6569.
%H Yonah Biers-Ariel, <a href="https://sites.math.rutgers.edu/~yb165/Thesis/Flexible_Scheme.mpl">Flexible_Scheme Maple package</a>
%H Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%e 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].
%p (requires Flexible_Scheme package -- see links)
%p read `Flexible_Scheme.mpl`:
%p 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]}:
%p #let n be the number of terms desired
%p SeqS(s,n); # _Yonah Biers-Ariel_, May 27 2020
%K nonn,more
%O 1,2
%A _Colin Defant_, Sep 08 2018
%E Terms a(10) and beyond from _Yonah Biers-Ariel_, May 27 2020
|