A348905 Number of permutations of size n that require exactly n-1 iterations of the pop-stack sorting map to reach the identity.

1, 1, 2, 8, 32, 155, 830, 5106, 35346, 272198, 2344944, 22070987, 230156314, 2590636217, 31914293380, 420241717802

Offset

1,3

References

M. Albert and V. Vatter, How many pop-stacks does it take to sort a permutation? Comput. J., (2021).

A. Asinowski, C. Banderier, and B. Hackl, Flip-sort and combinatorial aspects of pop-stack sorting. Discrete Math. Theor. Comput. Sci., 22 (2021).

A. Claesson and B. A. Gudmundsson, Enumerating permutations sortable by k passes through a pop-stack. Adv. Appl. Math., 108 (2019), 79-96.

L. Pudwell and R. Smith, Two-stack-sorting with pop stacks. Australas. J. Combin., 74 (2019), 179-195.

Links

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

A. Claesson and B. A. Guðmundsson, Enumerating permutations sortable by k passes through a pop-stack, arXiv:1710.04978 [math.CO], 2017-2019.

L. Pudwell and R. Smith, Two-stack-sorting with pop stacks, arXiv:1801.05005 [math.CO], 2018.

Peter Ungar, 2N noncollinear points determine at least 2N directions, J. Combin. Theory Ser. A, 33:3 (1982), pp. 343-347.

Example

The pop-stack sorting map acts by reversing the descending runs of a permutation. For example, it sends 3412 to 3142, it sends 3142 to 1324, and it sends 1324 to 1234. This shows that if we start with the permutation 3412, then we require 4-1=3 iterations to reach the identity permutation. There are 8 permutations of size 4 that require 3 iterations (all others require fewer than 3 iterations), namely 2341, 3241, 3412, 3421, 4123, 4132, 4231, 4312.

Prog

(Python)
from itertools import permutations
def ps(lst):  # pop-stack sorting operator [cf. Claesson, Guðmundsson]
    out, stack = [], []
    for i in range(len(lst)):
        if len(stack) == 0 or stack[-1] < lst[i]:
            out.extend(stack[::-1])
            stack = []
        stack.append(lst[i])
    return out + stack[::-1]
def psops(t):
    c, lst, srtdlst = 0, list(t), sorted(t)
    if lst == srtdlst: return 0
    while lst != srtdlst:
        lst = ps(lst)
        c += 1
    return c
def a(n):
    return sum(1 for p in permutations(range(n), n) if psops(p) == n-1)
print([a(n) for n in range(1, 9)]) # Michael S. Branicky, Nov 09 2021

Crossrefs

Sequence in context: A150864 A202814 A054116 * A131785 A347363 A359398

Adjacent sequences: A348902 A348903 A348904 * A348906 A348907 A348908

Keyword

nonn,more

Author

Colin Defant, Nov 03 2021

Extensions

a(10)-a(12) from Michael S. Branicky, Nov 09 2021

a(13)-a(16) from Bjarki Ágúst Guðmundsson, Dec 30 2022

Status

approved