|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|