A293775 -id:A293775 - cp's OEIS frontend

A224232 a(n) = n! if n <= 3, otherwise a(n) = 2*(a(n-1) + a(n-3)) + a(n-2).

1, 1, 2, 6, 16, 42, 112, 298, 792, 2106, 5600, 14890, 39592, 105274, 279920, 744298, 1979064, 5262266, 13992192, 37204778, 98926280, 263041722, 699419280, 1859732842, 4944968408, 13148508218, 34961450528, 92961346090, 247181159144, 657246565434, 1747596982192, 4646802848106, 12355695809272, 32853388431034, 87356078367552, 232276936784682

Offset: 0

N. J. A. Sloane, Apr 11 2013

Also the number of permutations that are sortable after two passes through a pop stack. (See the Pudwell-Smith link.) - Lara Pudwell, Jun 01 2017

Colin Barker, Table of n, a(n) for n = 0..1000
G. Aleksandrowich et al., Permutations with forbidden patterns and polyominoes on a twisted cylinder of width 3, Discrete Math., 313 (2013), 1078-1086.
Anders Claesson and Bjarki Ágúst Guðmundsson, Enumerating permutations sortable by k passes through a pop-stack, arXiv:1710.04978 [math.CO], 2017.
Lara Pudwell and Rebecca Smith, Sorting with Pop Stacks, Special Session on Algebraic and Enumerative Combinatorics with Applications, AMS Central Section Spring Meeting, 2017.
Lara Pudwell and Rebecca Smith, Two-stack-sorting with pop stacks, arXiv:1801.05005 [math.CO], 2018.
Index entries for linear recurrences with constant coefficients, signature (2,1,2).

Cf. A077996, A293774, A293775, A293776, A293784.

CoefficientList[Series[(x^3 + x^2 + x - 1)/(2 x^3 + x^2 + 2 x - 1), {x, 0, 35}], x] (* Michael De Vlieger, Jun 01 2017 *)
LinearRecurrence[{2,1,2},{1,1,2,6},40] (* Harvey P. Dale, Aug 28 2023 *)

Vec((x^3+x^2+x-1)/(2*x^3+x^2+2*x-1) + O(x^100)) \\ Colin Barker, Jun 07 2015

G.f.: (x^3 + x^2 + x - 1) / (2*x^3 + x^2 + 2*x - 1). - Colin Barker, Jun 07 2015

a(n) = (b(n) + b(n-1))/2 for b(n) = A077996(n). - Hanzhang Fang, Aug 27 2022

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

Bjarki Ágúst Guðmundsson, Oct 16 2017

Bjarki Ágúst Guðmundsson, Table of n, a(n) for n = 0..1000
Anders Claesson, Bjarki Ágúst Guðmundsson, Enumerating permutations sortable by k passes through a pop-stack, arXiv:1710.04978 [math.CO], 2017.

Cf. A224232, A293775, A293776, A293784.

Vec((2*x^10 + 4*x^9 + 2*x^8 + 5*x^7 + 11*x^6 + 8*x^5 + 6*x^4 + 6*x^3 + 2*x^2 + x - 1)/(4*x^10 + 8*x^9 + 4*x^8 + 10*x^7 + 22*x^6 + 16*x^5 + 8*x^4 + 6*x^3 + 2*x^2 + 2*x - 1) + O(x^30))

G.f.: (2*x^10 + 4*x^9 + 2*x^8 + 5*x^7 + 11*x^6 + 8*x^5 + 6*x^4 + 6*x^3 + 2*x^2 + x - 1) / (4*x^10 + 8*x^9 + 4*x^8 + 10*x^7 + 22*x^6 + 16*x^5 + 8*x^4 + 6*x^3 + 2*x^2 + 2*x - 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

Bjarki Ágúst Guðmundsson, Oct 16 2017

Bjarki Ágúst Guðmundsson, Table of n, a(n) for n = 0..1000
Anders Claesson, Bjarki Ágúst Guðmundsson, Enumerating permutations sortable by k passes through a pop-stack, arXiv:1710.04978 [math.CO], 2017.

Cf. A224232, A293774, A293775, A293784.

Vec((524288*x^71 + 917504*x^70 + 786432*x^69 + 2588672*x^68 - 19726336*x^67 - 82804736*x^66 - 54296576*x^65 + 85213184*x^64 - 8978432*x^63 - 412958720*x^62 - 355459072*x^61 + 1089468416*x^60 + 3425873920*x^59 + 4027930624*x^58 + 436686848*x^57 - 5849393152*x^56 - 9755746304*x^55 - 8115352576*x^54 - 2907128832*x^53 + 1761573888*x^52 + 2556718848*x^51 - 2397270272*x^50 - 10331146496*x^49 - 14480336384*x^48 - 14117642496*x^47 - 16712557440*x^46 - 24583730624*x^45 - 29752371008*x^44 - 27336113856*x^43 - 22273917088*x^42 - 18768569728*x^41 - 14707182816*x^40 - 8272263856*x^39 - 1547391248*x^38 + 2681619488*x^37 + 3713037632*x^36 + 2652279328*x^35 + 1290053752*x^34 + 767471104*x^33 + 658459312*x^32 + 241589520*x^31 - 214754576*x^30 - 275309640*x^29 - 46250392*x^28 + 157768032*x^27 + 179763512*x^26 + 77153080*x^25 - 24370310*x^24 - 59928968*x^23 - 39748982*x^22 - 8046256*x^21 + 9532032*x^20 + 12163840*x^19 + 7067740*x^18 + 1840948*x^17 - 499000*x^16 - 689228*x^15 - 174174*x^14 + 157680*x^13 + 204210*x^12 + 129485*x^11 + 56769*x^10 + 24169*x^9 + 10229*x^8 + 3320*x^7 + 1124*x^6 + 357*x^5 + 77*x^4 + 22*x^3 + 4*x^2 + x - 1)/(1048576*x^71 + 1835008*x^70 + 1572864*x^69 + 5177344*x^68 - 39452672*x^67 - 165609472*x^66 - 108593152*x^65 + 169508864*x^64 - 15761408*x^63 - 817233920*x^62 - 721018880*x^61 + 2118733824*x^60 + 6785392640*x^59 + 8125251584*x^58 + 1145022464*x^57 - 11405879296*x^56 - 19522508800*x^55 - 16701201408*x^54 - 6439882752*x^53 + 3456700416*x^52 + 5991042560*x^51 - 3742200320*x^50 - 20812231680*x^49 - 30494889216*x^48 - 29510720000*x^47 - 33025129216*x^46 - 47875423616*x^45 - 59333567872*x^44 - 56599781120*x^43 - 47747449984*x^42 - 40510396544*x^41 - 31575130240*x^40 - 18658277632*x^39 - 6166474240*x^38 + 1470207296*x^37 + 3749860352*x^36 + 2608531712*x^35 + 849740576*x^34 + 201853568*x^33 + 4875024*x^32 - 620150944*x^31 - 1095819008*x^30 - 866800328*x^29 - 291500856*x^28 + 94151032*x^27 + 140066312*x^26 + 7755328*x^25 - 110265380*x^24 - 133344480*x^23 - 84534456*x^22 - 27292370*x^21 + 4515366*x^20 + 11865598*x^19 + 6558266*x^18 + 393432*x^17 - 1933760*x^16 - 1556200*x^15 - 539312*x^14 + 54468*x^13 + 205596*x^12 + 152006*x^11 + 67606*x^10 + 26954*x^9 + 10905*x^8 + 3194*x^7 + 962*x^6 + 304*x^5 + 61*x^4 + 20*x^3 + 4*x^2 + 2*x - 1) + O(x^30))

G.f.: (524288*x^71 + 917504*x^70 + 786432*x^69 + 2588672*x^68 - 19726336*x^67 - 82804736*x^66 - 54296576*x^65 + 85213184*x^64 - 8978432*x^63 - 412958720*x^62 - 355459072*x^61 + 1089468416*x^60 + 3425873920*x^59 + 4027930624*x^58 + 436686848*x^57 - 5849393152*x^56 - 9755746304*x^55 - 8115352576*x^54 - 2907128832*x^53 + 1761573888*x^52 + 2556718848*x^51 - 2397270272*x^50 - 10331146496*x^49 - 14480336384*x^48 - 14117642496*x^47 - 16712557440*x^46 - 24583730624*x^45 - 29752371008*x^44 - 27336113856*x^43 - 22273917088*x^42 - 18768569728*x^41 - 14707182816*x^40 - 8272263856*x^39 - 1547391248*x^38 + 2681619488*x^37 + 3713037632*x^36 + 2652279328*x^35 + 1290053752*x^34 + 767471104*x^33 + 658459312*x^32 + 241589520*x^31 - 214754576*x^30 - 275309640*x^29 - 46250392*x^28 + 157768032*x^27 + 179763512*x^26 + 77153080*x^25 - 24370310*x^24 - 59928968*x^23 - 39748982*x^22 - 8046256*x^21 + 9532032*x^20 + 12163840*x^19 + 7067740*x^18 + 1840948*x^17 - 499000*x^16 - 689228*x^15 - 174174*x^14 + 157680*x^13 + 204210*x^12 + 129485*x^11 + 56769*x^10 + 24169*x^9 + 10229*x^8 + 3320*x^7 + 1124*x^6 + 357*x^5 + 77*x^4 + 22*x^3 + 4*x^2 + x - 1) / (1048576*x^71 + 1835008*x^70 + 1572864*x^69 + 5177344*x^68 - 39452672*x^67 - 165609472*x^66 - 108593152*x^65 + 169508864*x^64 - 15761408*x^63 - 817233920*x^62 - 721018880*x^61 + 2118733824*x^60 + 6785392640*x^59 + 8125251584*x^58 + 1145022464*x^57 - 11405879296*x^56 - 19522508800*x^55 - 16701201408*x^54 - 6439882752*x^53 + 3456700416*x^52 + 5991042560*x^51 - 3742200320*x^50 - 20812231680*x^49 - 30494889216*x^48 - 29510720000*x^47 - 33025129216*x^46 - 47875423616*x^45 - 59333567872*x^44 - 56599781120*x^43 - 47747449984*x^42 - 40510396544*x^41 - 31575130240*x^40 - 18658277632*x^39 - 6166474240*x^38 + 1470207296*x^37 + 3749860352*x^36 + 2608531712*x^35 + 849740576*x^34 + 201853568*x^33 + 4875024*x^32 - 620150944*x^31 - 1095819008*x^30 - 866800328*x^29 - 291500856*x^28 + 94151032*x^27 + 140066312*x^26 + 7755328*x^25 - 110265380*x^24 - 133344480*x^23 - 84534456*x^22 - 27292370*x^21 + 4515366*x^20 + 11865598*x^19 + 6558266*x^18 + 393432*x^17 - 1933760*x^16 - 1556200*x^15 - 539312*x^14 + 54468*x^13 + 205596*x^12 + 152006*x^11 + 67606*x^10 + 26954*x^9 + 10905*x^8 + 3194*x^7 + 962*x^6 + 304*x^5 + 61*x^4 + 20*x^3 + 4*x^2 + 2*x - 1)

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

Bjarki Ágúst Guðmundsson, Oct 16 2017

Bjarki Ágúst Guðmundsson, Table of n, a(n) for n = 0..1000
Anders Claesson, Bjarki Ágúst Guðmundsson, Enumerating permutations sortable by k passes through a pop-stack, arXiv:1710.04978 [math.CO], 2017.
Bjarki Ágúst Guðmundsson, generating function.
Bjarki Ágúst Guðmundsson, PARI script.

Cf. A224232, A293774, A293775, A293776.

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

Bjarki Ágúst Guðmundsson, Dec 30 2022

When k is fixed, T(n, k) has a rational g.f. (see A. Claesson and B. A. Guðmundsson).

			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.

Cf. A011782, A224232, A224232, A293774, A293775, A293776, A293784, A348905.

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)

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).

cp's OEIS Frontend

A224232 a(n) = n! if n <= 3, otherwise a(n) = 2*(a(n-1) + a(n-3)) + a(n-2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A293774 Number of permutations of length n sortable by 3 passes through a pop-stack.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A293776 Number of permutations of length n sortable by 5 passes through a pop-stack.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A293784 Number of permutations of length n sortable by 6 passes through a pop-stack.

Views

Author

Keywords

Links

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula