cp's OEIS Frontend

A359413 Triangle read by rows: T(n, k) is the number of permutations of size n that require exactly k iterations of the pop-stack sorting map to reach the identity, for n >= 1, 0 <= k <= n-1.

%I A359413 #28 Dec 31 2022 11:44:32
%S A359413 1,1,1,1,3,2,1,7,8,8,1,15,26,46,32,1,31,80,191,262,155,1,63,234,735,
%T A359413 1440,1737,830,1,127,664,2752,6924,12314,12432,5106,1,255,1850,10114,
%U A359413 31928,73122,112108,98156,35346,1,511,5088,36564,145199,404758,816401,1104042,844038,272198
%N A359413 Triangle read by rows: T(n, k) is the number of permutations of size n that require exactly k iterations of the pop-stack sorting map to reach the identity, for n >= 1, 0 <= k <= n-1.
%C A359413 When k is fixed, T(n, k) has a rational g.f. (see A. Claesson and B. A. Guðmundsson).
%H A359413 Bjarki Ágúst Guðmundsson, <a href="/A359413/b359413.txt">Rows n=1..16 of triangle, flattened</a>
%H A359413 M. Albert and V. Vatter, <a href="https://arxiv.org/abs/2012.05275">How many pop-stacks does it take to sort a permutation?</a>, arXiv:2012.05275 [math.CO], 2020.
%H A359413 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 A359413 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 A359413 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.
%F A359413 T(n, 0) = 1.
%F A359413 T(n, 1) = 2^(n-1)-1 for n >= 2 (see L. Pudwell and R. Smith).
%F A359413 T(n, 2) = A224232(n) - A011782(n) for n >= 3.
%F A359413 T(n, 3) = A293774(n) - A224232(n) for n >= 4.
%F A359413 T(n, 4) = A293775(n) - A293774(n) for n >= 5.
%F A359413 T(n, 5) = A293776(n) - A293775(n) for n >= 6.
%F A359413 T(n, 6) = A293784(n) - A293776(n) for n >= 7.
%F A359413 T(n, n-1) = A348905(n).
%F A359413 T(n, k) = 0 when k >= n (see M. Albert and V. Vatter).
%e A359413 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 T(4,3) = 8 permutations of size 4 that require 3 iterations, namely 2341, 3241, 3412, 3421, 4123, 4132, 4231, 4312.
%e A359413 Triangle T(n,k) begins:
%e A359413 [1]  1;
%e A359413 [2]  1,  1;
%e A359413 [3]  1,  3,  2;
%e A359413 [4]  1,  7,  8,   8;
%e A359413 [5]  1, 15, 26,  46,  32;
%e A359413 [6]  1, 31, 80, 191, 262, 155;
%e A359413 ...
%o A359413 (Python)
%o A359413 from itertools import permutations
%o A359413 def ps(lst):  # pop-stack sorting operator [cf. Claesson, Guðmundsson]
%o A359413     out, stack = [], []
%o A359413     for i in range(len(lst)):
%o A359413         if len(stack) == 0 or stack[-1] < lst[i]:
%o A359413             out.extend(stack[::-1])
%o A359413             stack = []
%o A359413         stack.append(lst[i])
%o A359413     return out + stack[::-1]
%o A359413 def psops(t):
%o A359413     c, lst, srtdlst = 0, list(t), sorted(t)
%o A359413     if lst == srtdlst: return 0
%o A359413     while lst != srtdlst:
%o A359413         lst = ps(lst)
%o A359413         c += 1
%o A359413     return c
%o A359413 def T(n,k):
%o A359413     return sum(1 for p in permutations(range(n), n) if psops(p) == k)
%o A359413 print([T(n,k) for n in range(1, 9) for k in range(n)]) # _Michael S. Branicky_, Nov 09 2021 (adapted from A348905 by _Bjarki Ágúst Guðmundsson_, Dec 30 2022)
%Y A359413 Cf. A011782, A224232, A224232, A293774, A293775, A293776, A293784, A348905.
%K A359413 nonn,tabl
%O A359413 1,5
%A A359413 _Bjarki Ágúst Guðmundsson_, Dec 30 2022