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!)
A134664 Number of 3-stack sortable permutations on n letters. 3
1, 2, 6, 24, 114, 606, 3494, 21426, 137901, 922862, 6377818, 45281958, 328969075, 2437728712, 18378435667, 140675908516, 1091364628837, 8569030580864, 68010267723813, 545061073269660, 4407108705811905, 35922134951424486, 294968178121716449 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

It is known that 8.65970 < lim_{n--> infinity} a(n)^{1/n} < 12.53296. - Colin Defant, Sep 15 2018

Lim_{n->infinity} a(n)^(1/n) >= 9.4854... (a new rigorous lower bound). Lim_{n->infinity} = 9.69963634535... (conjecture). [Defant, Elvey Price, Guttmann, 2020] - Vaclav Kotesovec, Jun 12 2021, following a suggestion of Anthony Guttmann

LINKS

Colin Defant, Andrew Elvey Price, and Anthony J. Guttmann, Table of n, a(n) for n = 1..1000

M. Bona, Stack words and a bound for 3-stack sortable permutations, arXiv:1903.04113 [math.CO], 2019.

M. Bona, A survey of stack-sorting disciplines, Electron. J. Combin., 9 (2003), Article #A1.

Colin Defant, Preimages under the stack-sorting algorithm, arXiv:1511.05681 [math.CO], 2015-2018; Graphs Combin., 33 (2017), 103-122.

Colin Defant, Counting 3-Stack-Sortable Permutations, arXiv:1903.09138 [math.CO], 2019.

Colin Defant, Andrew Elvey Price, and Anthony J. Guttmann, Asymptotics of 3-stack-sortable permutations, arXiv:2009.10439 [math.CO], 2020.

FORMULA

See the paper "Counting 3-Stack-Sortable Permutations" for a recurrence that generates this sequence. - Colin Defant, Mar 18 2019

EXAMPLE

a(5) = 114 because all but the 6 permutations 23451, 24351, 32451, 34251, 42351, 43251 on 5 letters become 12345 after at most 3 passes through the stack sorter.

CROSSREFS

Cf. A000139, A324917, A324918. Rows sums of A324916.

Sequence in context: A228907 A209625 A054872 * A324133 A171448 A068199

Adjacent sequences:  A134661 A134662 A134663 * A134665 A134666 A134667

KEYWORD

nonn

AUTHOR

Eric Rowland, Jan 25 2008

EXTENSIONS

More terms from Colin Defant, Mar 18 2019

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 20 20:15 EDT 2021. Contains 347590 sequences. (Running on oeis4.)