Colin Defant - cp's OEIS frontend

A350681 Triangle read by rows. T(n,k) is the number of hitomezashi loops of width 2(n-k)+1 and height 2k+1 for 0 <= k <= n.

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 1, 4, 4, 1, 0, 0, 1, 8, 11, 8, 1, 0, 0, 1, 16, 27, 27, 16, 1, 0, 0, 1, 32, 64, 76, 64, 32, 1, 0

Offset: 0

Colin Defant, Jan 11 2022

The Defant--Kravitz paper proves that every hitomezashi loop has odd width and odd height.

			Triangle T(n,k) begins:
  1;
  0, 0;
  0, 1,  0;
  0, 1,  1,  0;
  0, 1,  2,  1,  0;
  0, 1,  4,  4,  1,  0;
  0, 1,  8, 11,  8,  1,  0;
  0, 1, 16, 27, 27, 16,  1, 0;
  0, 1, 32, 64, 76, 64, 32, 1, 0;
  ...

Colin Defant and Noah Kravitz, Loops and Regions in Hitomezashi Patterns, arXiv:2201.03461 [math.CO], 2022.

T(2n,n) gives: A350680.

T(n,k) = T(n,n-k).

A350680 Number of hitomezashi loops of width 2n+1 and height 2n+1.

Original entry on oeis.org

1, 1, 2, 11, 76, 600

Offset: 0

Colin Defant, Jan 11 2022

The Defant--Kravitz paper proves that every hitomezashi loop has odd width and odd height.

Colin Defant and Noah Kravitz, Loops and regions in hitomezashi patterns, arXiv:2201.03461 [math.CO], 2022.

Cf. A121790, A350681.

a(n) = A350681(2n,n).

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

Original entry on oeis.org

1, 1, 2, 8, 32, 155, 830, 5106, 35346, 272198, 2344944, 22070987, 230156314, 2590636217, 31914293380, 420241717802

Offset: 1

Colin Defant, Nov 03 2021

			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.

M. Albert and V. Vatter, How many pop-stacks does it take to sort a permutation? Comput. J., (2021).
A. Asinowski, C. Banderier, and B. Hackl, Flip-sort and combinatorial aspects of pop-stack sorting. Discrete Math. Theor. Comput. Sci., 22 (2021).
A. Claesson and B. A. Gudmundsson, Enumerating permutations sortable by k passes through a pop-stack. Adv. Appl. Math., 108 (2019), 79-96.
L. Pudwell and R. Smith, Two-stack-sorting with pop stacks. Australas. J. Combin., 74 (2019), 179-195.

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 a(n):
    return sum(1 for p in permutations(range(n), n) if psops(p) == n-1)
print([a(n) for n in range(1, 9)]) # Michael S. Branicky, Nov 09 2021

a(10)-a(12) from Michael S. Branicky, Nov 09 2021

a(13)-a(16) from Bjarki Ágúst Guðmundsson, Dec 30 2022

A337522 Number of permutations of length n that are sorted to the identity by a consecutive-312-avoiding-stack followed by a classical-21-avoiding stack.

Original entry on oeis.org

1, 1, 2, 5, 15, 50, 179, 675, 2649, 10734

Offset: 0

Colin Defant, Aug 30 2020

			Sending the permutation 132 through a consecutive-312-avoiding stack results in 231, and a classical 21-avoiding stack then sends 231 to 213, which is not the identity 123. Applying this procedure to any permutation of length 3 other than 132 results in 123, so a(3)=5.

C. Defant and K. Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.

Cf. A033321, A001006, A337495, A011782, A001405

A337495 Maximum number of preimages that a permutation of length n can have under the consecutive-123-avoiding stack-sorting map.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 7, 11, 16, 26, 42

Offset: 0

Colin Defant, Aug 29 2020

			The consecutive-123-avoiding stack-sorting map acts on permutations of length 3 by reversing every permutation except 321, which gets sent to 213. The permutation 213 has 2 preimages under this map (namely, 312 and 321), and every other permutation of length 3 has at most one preimage. Hence, a(3)=2.

Colin Defant and Kai Zheng, Stack-sorting with consecutive-pattern-avoiding stacks, arXiv:2008.12297 [math.CO], 2020.

A309331 Expansion of (x+x^3+x^5)/(1-x-3*x^3-x^5).

Original entry on oeis.org

0, 1, 1, 2, 5, 9, 16, 32, 61, 114, 219, 418, 792, 1510, 2878, 5473, 10421, 19847, 37776, 71917, 136931, 260680, 496278, 944847, 1798804, 3424569, 6519790, 12412480, 23631034, 44989208, 85651217, 163064109, 310444213, 591028898, 1125210433

Offset: 0

Colin Defant, Jul 23 2019

a(n) is the number of 231-avoiding permutations of length n that have order 1 or 3.

Amanda Burcroff and Colin Defant, Pattern-Avoiding Permutation Powers, arXiv:1907.09451 [math.CO], 2019.
Index entries for linear recurrences with constant coefficients, signature (1,0,3,0,1).

G.f.: (1-x+x^2)*(1+x+x^2)/(1-x-3*x^3-x^5).

A307788 Number of valid hook configurations of permutations of [n] that avoid the patterns 231 and 321.

Original entry on oeis.org

1, 1, 1, 2, 5, 12, 29, 72, 182, 466, 1207, 3158, 8334, 22158, 59299, 159614, 431838, 1173710, 3203244, 8774780, 24118522, 66497316, 183858411, 509670494, 1416231616, 3944027402, 11006186760, 30772507128, 86191006746, 241815195292

Offset: 0

Colin Defant, Apr 28 2019

nonn

Essentially the same as A217333 and A025273. - R. J. Mathar, May 17 2019

Colin Defant, Motzkin intervals and valid hook configurations, arXiv preprint arXiv:1904.10451 [math.CO], 2019.

Cf. A307786, A307787.

my(x='x+O('x^35)); Vec((1 - 2*x + 2*x^2 - sqrt(1 - 4*x + 4*x^2 - 4*x^3 + 4*x^4))/(2*x^2)) \\ Michel Marcus, May 08 2019

G.f.: (1 - 2*x + 2*x^2 - sqrt(1 - 4*x + 4*x^2 - 4*x^3 + 4*x^4)) / (2*x^2).

D-finite with recurrence: (n+2)*a(n) +2*(-2*n-1)*a(n-1) +4*(n-1)*a(n-2) +2*(-2*n+5)*a(n-3) +4*(n-4)*a(n-4)=0. - R. J. Mathar, May 17 2019

A307787 Number of valid hook configurations of 132-avoiding permutations of [n].

Original entry on oeis.org

1, 1, 1, 2, 5, 14, 43, 140, 477, 1683, 6106, 22664, 85735, 329572, 1284440, 5065828, 20188877, 81201801, 329281059, 1345059602, 5530600618, 22876354484, 95137126194, 397610249052, 1669285639455, 7037395810149, 29782584966376

Offset: 0

Colin Defant, Apr 28 2019

nonn

Also the number of valid hook configurations of 231-avoiding permutations of [n].

For n > 0, a(n) is the number of intervals in the Motzkin-Tamari poset introduced by Fang.

Colin Defant, Motzkin intervals and valid hook configurations, arXiv preprint arXiv:1904.10451 [math.CO], 2019.
Wenjie Fang, A partial order on Motzkin paths, arXiv preprint arXiv:1801.04809 [math.CO], 2018.

Cf. A001006, A344498.

m = 30; A[_] = 0;
Do[A[x_] = (-x^4 A[x]^5 - 4x^3 A[x]^4 + x^2 (-8x^2 + 9x - 6) A[x]^3 + x (14x^2 + 19x - 4) A[x]^2 - (x + 1)^2 (8x - 1))/(16x^4 + 28x^3 - 11x + 1) + O[x]^m, {m}];
CoefficientList[A[x], x] (* Jean-François Alcover, Sep 28 2019 *)

O.g.f. A(x) satisfies (-1 + 6 x + 15 x^2 + 8 x^3) + (1 - 11 x + 28 x^3 + 16 x^4)*A(x) + (4 x - 19 x^2 - 14 x^3)*A(x)^2 + (6 x^2 - 9 x^3 + 8 x^4)*A(x)^3 + 4 x^3*A(x)^4 + x^4*A(x)^5 = 0.
a(n) ~ (b*r^n)/((Pi*n^5)^(1/2)), where b = 0.805810... is the unique positive real root of 41472*x^6 - 34749*x^4 + 5472*x^2 - 256 and r = 4.658905... is the unique real root of 256*x^3 - 645*x^2 - 2112*x - 2048.
D-finite with recurrence -40*(148331*n-97009)*(4*n+3)*(2*n+3)*(4*n+5)*(n+2) *a(n) +(416275187*n^5 +1198175440*n^4 +714804925*n^3 -286654300*n^2 -249009732*n -17183760)*a(n-1) +60*(28713647*n^5 -13727276*n^4 -42761251*n^3 +18500340*n^2 +16274828*n -6917680)*a(n-2) +128*(n-2)*(2*n-3) *(7934261*n^3 -428899*n^2 -4370812*n -1585650)*a(n-3) +2048*(2*n-5)*(60637*n +16808)*(n-2)*(n-3)*(2*n-3)*a(n-4)=0. - R. J. Mathar, Jan 25 2023

A307786 Number of valid hook configurations of 312-avoiding permutations of [n].

Original entry on oeis.org

1, 1, 2, 5, 14, 44, 148, 528, 1972, 7647, 30605, 125801, 529131, 2270481, 9914870, 43973755, 197744417, 900327160, 4145285618, 19280282194, 90507546094, 428476211848, 2044274855774, 9823314566417, 47516954475991, 231260870664189

Offset: 0

Colin Defant, Apr 28 2019

nonn

The class of a Motzkin path is the set of indices i such that the i-th non-down step is an east step. For n > 0, a(n) is the number of pairs (P,Q) of Motzkin paths such that P and Q have the same class and P lies below or is equal to Q.
Conjecture: This sequence is the binomial transform of A151347.
The Defant article gives a functional equation that defines a generating function Q(x,y,z) such that Q(x,0,0) is the ordinary generating function of this sequence.

Colin Defant, Motzkin intervals and valid hook configurations, arXiv preprint arXiv:1904.10451 [math.CO], 2019.
Wenjie Fang, A partial order on Motzkin paths, arXiv preprint arXiv:1801.04809 [math.CO], 2018.

Appears to be the binomial transform of A151347.

A307789 Number of valid hook configurations of permutations of [n] that avoid the patterns 231 and 1243.

Original entry on oeis.org

1, 1, 1, 2, 5, 13, 35, 96, 267, 750, 2123, 6046, 17303, 49721, 143365, 414584, 1201917, 3492117, 10165779, 29643870, 86574831, 253188111, 741365049, 2173243128, 6377181825, 18730782252, 55062586341, 161995031226, 476941691177, 1405155255055

Offset: 0

Colin Defant, Apr 28 2019

nonn

Essentially the same as A005773. - R. J. Mathar, May 06 2019

Colin Defant, Motzkin intervals and valid hook configurations, arXiv preprint arXiv:1904.10451 [math.CO], 2019.

Cf. A005773, A064189.

G.f.: 1 + 2*x^2/(3*x - 1 + sqrt(1 - 2*x - 3*x^2)).
D-finite with recurrence: +(-n+1)*a(n) +2*(n-1)*a(n-1) +3*(n-3)*a(n-2)=0. - R. J. Mathar, Jan 27 2020
a(n) = Sum_{k=0..n-2} A064189(n-2,k) for n>=2. - Alois P. Heinz, Aug 29 2022

cp's OEIS Frontend

User: Colin Defant

A350681 Triangle read by rows. T(n,k) is the number of hitomezashi loops of width 2(n-k)+1 and height 2k+1 for 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A350680 Number of hitomezashi loops of width 2n+1 and height 2n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

References

Links

Programs

Python

Extensions

A337522 Number of permutations of length n that are sorted to the identity by a consecutive-312-avoiding-stack followed by a classical-21-avoiding stack.

Views

Author

Keywords

Examples

Links

Crossrefs

A337495 Maximum number of preimages that a permutation of length n can have under the consecutive-123-avoiding stack-sorting map.

Views

Author

Keywords

Examples

Links

A309331 Expansion of (x+x^3+x^5)/(1-x-3*x^3-x^5).

Views

Author

Keywords

Comments

Links

Formula

A307788 Number of valid hook configurations of permutations of [n] that avoid the patterns 231 and 321.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A307787 Number of valid hook configurations of 132-avoiding permutations of [n].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A307786 Number of valid hook configurations of 312-avoiding permutations of [n].

Views

Author

Keywords

Comments

Links

Crossrefs

A307789 Number of valid hook configurations of permutations of [n] that avoid the patterns 231 and 1243.

Views

Author

Keywords