The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 1
 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, 1440, 1737, 830, 1, 127, 664, 2752, 6924, 12314, 12432, 5106, 1, 255, 1850, 10114, 31928, 73122, 112108, 98156, 35346, 1, 511, 5088, 36564, 145199, 404758, 816401, 1104042, 844038, 272198 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,5 COMMENTS When k is fixed, T(n, k) has a rational g.f. (see A. Claesson and B. A. Guðmundsson). LINKS Bjarki Ágúst Guðmundsson, Rows n=1..16 of triangle, flattened M. Albert and V. Vatter, How many pop-stacks does it take to sort a permutation?, arXiv:2012.05275 [math.CO], 2020. 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. FORMULA T(n, 0) = 1. T(n, 1) = 2^(n-1)-1 for n >= 2 (see L. Pudwell and R. Smith). T(n, 2) = A224232(n) - A011782(n) for n >= 3. T(n, 3) = A293774(n) - A224232(n) for n >= 4. T(n, 4) = A293775(n) - A293774(n) for n >= 5. T(n, 5) = A293776(n) - A293775(n) for n >= 6. T(n, 6) = A293784(n) - A293776(n) for n >= 7. T(n, n-1) = A348905(n). T(n, k) = 0 when k >= n (see M. Albert and V. Vatter). 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 T(4,3) = 8 permutations of size 4 that require 3 iterations, namely 2341, 3241, 3412, 3421, 4123, 4132, 4231, 4312. Triangle T(n,k) begins: [1] 1; [2] 1, 1; [3] 1, 3, 2; [4] 1, 7, 8, 8; [5] 1, 15, 26, 46, 32; [6] 1, 31, 80, 191, 262, 155; ... 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 T(n, k): return sum(1 for p in permutations(range(n), n) if psops(p) == k) 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) CROSSREFS Cf. A011782, A224232, A224232, A293774, A293775, A293776, A293784, A348905. Sequence in context: A130462 A059380 A145035 * A192020 A367564 A171128 Adjacent sequences: A359410 A359411 A359412 * A359414 A359415 A359416 KEYWORD nonn,tabl AUTHOR Bjarki Ágúst Guðmundsson, Dec 30 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 18 22:18 EDT 2024. Contains 371782 sequences. (Running on oeis4.)