login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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: A221988 A329788 A177518 * 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 28 11:24 EDT 2020. Contains 337393 sequences. (Running on oeis4.)