cp's OEIS Frontend

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

%I A348905 #33 Dec 30 2022 11:06:48
%S A348905 1,1,2,8,32,155,830,5106,35346,272198,2344944,22070987,230156314,
%T A348905 2590636217,31914293380,420241717802
%N A348905 Number of permutations of size n that require exactly n-1 iterations of the pop-stack sorting map to reach the identity.
%D A348905 M. Albert and V. Vatter, How many pop-stacks does it take to sort a permutation? Comput. J., (2021).
%D A348905 A. Asinowski, C. Banderier, and B. Hackl, Flip-sort and combinatorial aspects of pop-stack sorting. Discrete Math. Theor. Comput. Sci., 22 (2021).
%D A348905 A. Claesson and B. A. Gudmundsson, Enumerating permutations sortable by k passes through a pop-stack. Adv. Appl. Math., 108 (2019), 79-96.
%D A348905 L. Pudwell and R. Smith, Two-stack-sorting with pop stacks. Australas. J. Combin., 74 (2019), 179-195.
%H A348905 A. Claesson and B. A. Guðmundsson, <a href="https://arxiv.org/abs/1710.04978">Enumerating permutations sortable by k passes through a pop-stack</a>, arXiv:1710.04978 [math.CO], 2017-2019.
%H A348905 L. Pudwell and R. Smith, <a href="https://arxiv.org/abs/1801.05005">Two-stack-sorting with pop stacks</a>, arXiv:1801.05005 [math.CO], 2018.
%H A348905 Peter Ungar, <a href="http://dx.doi.org/10.1016/0097-3165(82)90045-0">2N noncollinear points determine at least 2N directions</a>, J. Combin. Theory Ser. A, 33:3 (1982), pp. 343-347.
%e A348905 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.
%o A348905 (Python)
%o A348905 from itertools import permutations
%o A348905 def ps(lst):  # pop-stack sorting operator [cf. Claesson, Guðmundsson]
%o A348905     out, stack = [], []
%o A348905     for i in range(len(lst)):
%o A348905         if len(stack) == 0 or stack[-1] < lst[i]:
%o A348905             out.extend(stack[::-1])
%o A348905             stack = []
%o A348905         stack.append(lst[i])
%o A348905     return out + stack[::-1]
%o A348905 def psops(t):
%o A348905     c, lst, srtdlst = 0, list(t), sorted(t)
%o A348905     if lst == srtdlst: return 0
%o A348905     while lst != srtdlst:
%o A348905         lst = ps(lst)
%o A348905         c += 1
%o A348905     return c
%o A348905 def a(n):
%o A348905     return sum(1 for p in permutations(range(n), n) if psops(p) == n-1)
%o A348905 print([a(n) for n in range(1, 9)]) # _Michael S. Branicky_, Nov 09 2021
%K A348905 nonn,more
%O A348905 1,3
%A A348905 _Colin Defant_, Nov 03 2021
%E A348905 a(10)-a(12) from _Michael S. Branicky_, Nov 09 2021
%E A348905 a(13)-a(16) from _Bjarki Ágúst Guðmundsson_, Dec 30 2022