Bjarki Ágúst Guðmundsson has authored 7 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.
Original entry on oeis.org
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
Offset: 1
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;
...
- 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.
-
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)
A309993
Triangle read by rows: T(n,k) is the number of permutations of length n composed of exactly k overlapping adjacent runs (for n >= 1 and 1 <= k <= n).
Original entry on oeis.org
1, 1, 0, 1, 2, 0, 1, 8, 2, 0, 1, 22, 26, 0, 0, 1, 52, 168, 42, 0, 0, 1, 114, 804, 692, 42, 0, 0, 1, 240, 3270, 6500, 1866, 0, 0, 0, 1, 494, 12054, 46304, 34078, 3060, 0, 0, 0, 1, 1004, 41708, 279566, 413878, 122830, 3060, 0, 0, 0, 1, 2026, 138320, 1514324
Offset: 1
For n = 3 the permutations with overlapping runs are 123, 132, 213. The first has k = 1 runs, the other two have k = 2 runs. Thus T(3,1) = 1, T(3,2) = 2, T(3,3) = 0.
Triangle begins:
1;
1, 0;
1, 2, 0;
1, 8, 2, 0;
1, 22, 26, 0, 0;
1, 52, 168, 42, 0, 0;
1, 114, 804, 692, 42, 0, 0;
1, 240, 3270, 6500, 1866, 0, 0, 0;
1, 494, 12054, 46304, 34078, 3060, 0, 0, 0;
1, 1004, 41708, 279566, 413878, 122830, 3060, 0, 0, 0;
...
- Bjarki Ágúst Guðmundsson, Table of n, a(n) for n = 1..5050
- Andrei Asinowski, Cyril Banderier, Sara Billey, Benjamin Hackl, Svante Linusson, Pop-stack sorting and its image: Permutations with overlapping runs (2019), preprint.
- Anders Claesson, Bjarki Ágúst Guðmundsson, Jay Pantone, Counting pop-stacked permutations in polynomial time, arXiv:1908.08910 [math.CO], 2019.
A295873
Number of permutations of length n which avoid the patterns 1342, 2413, 3124 and 3142.
Original entry on oeis.org
1, 1, 2, 6, 20, 68, 231, 781, 2629, 8821, 29530, 98706, 329592, 1099792, 3668127, 12230505, 40771337, 135895689, 452914658, 1509385902, 5029980252, 16761785436, 55855539047, 186125915029, 620217261197, 2066704787645, 6886704234970, 22947920663130, 76467083518464
Offset: 0
- Colin Barker, Table of n, a(n) for n = 0..1000
- Christian Bean, Bjarki Gudmundsson, Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.
- Index entries for linear recurrences with constant coefficients, signature (7,-16,14,-5,1).
A293776
Number of permutations of length n sortable by 5 passes through a pop-stack.
Original entry on oeis.org
1, 1, 2, 6, 24, 120, 720, 4210, 22782, 117270, 592121, 2986213, 15143820, 77271338, 395695883, 2028110765, 10390216994, 53191249148, 272166257616, 1392326537756, 7122760574924, 36440848056190, 186448403204159, 953990833404741, 4881270461542350
Offset: 0
A293775
Number of permutations of length n sortable by 4 passes through a pop-stack.
Original entry on oeis.org
1, 1, 2, 6, 24, 120, 565, 2473, 10468, 44148, 187363, 799605, 3418967, 14615713, 62439735, 266643093, 1138577340, 4862025964, 20763336212, 88672294260, 378685960241, 1617214869969, 6906440938924, 29494450730730, 125958207787945, 537914052728909
Offset: 0
A293774
Number of permutations of length n sortable by 3 passes through a pop-stack.
Original entry on oeis.org
1, 1, 2, 6, 24, 88, 303, 1033, 3544, 12220, 42164, 145364, 500954, 1726408, 5950050, 20507364, 70680192, 243602952, 839588620, 2893682172, 9973219220, 34373198420, 118468937648, 408309065104, 1407257423576, 4850182474912
Offset: 0
A293784
Number of permutations of length n sortable by 6 passes through a pop-stack.
Original entry on oeis.org
1, 1, 2, 6, 24, 120, 720, 5040, 35214, 229378, 1408522, 8370900, 49154431, 288653307, 1703668022, 10115769088, 60332300930, 360602808068, 2156022737216, 12883491408374, 76929443106701, 459100718065735, 2739019173150040, 16339850317888878, 97481064340012333
Offset: 0
Comments