Kassie Archer - cp's OEIS frontend

A382574 a(n) is the number of shallow permutations of length n that avoid 123.

1, 1, 2, 5, 13, 35, 90, 225, 525, 1181, 2526, 5289, 10729, 21583, 42566, 83909, 163225, 318713, 616122, 1198029, 2309829, 4483643, 8635314, 16750761, 32247973, 62538517, 120378518, 233428337, 449294497, 871206887, 1676835486, 3251439501, 6258092337, 12134600945

Offset: 0

Kassie Archer, Mar 31 2025

A shallow permutation is a permutation that satisfies the lower bound of the Diaconis-Graham inequality (i.e., so that the total displacement is equal to the sum of the length and reflection length).

Michael De Vlieger, Table of n, a(n) for n = 0..3494
Kassie Archer, Aaron Geary, and Robert Laudone, Pattern-avoiding shallow permutations, arXiV:2412.11999 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, signature (4,-2,-12,22,-12,-2,4,-1).

Cf. A062869, A301897.

CoefficientList[Series[(1 - 3*x + 11*x^3 - 13*x^4 + 7*x^5 + 6*x^6 + 3*x^7)/((1 - x)^4*(1 - 4*x^2 + x^4)), {x, 0, 33}], x] (* Michael De Vlieger, Apr 01 2025 *)

G.f.: (1-3*x+11*x^3-13*x^4+7*x^5+6*x^6+3*x^7) / ((1-x)^4 * (1-4*x^2+x^4)).

A382570 a(n) is the number of shallow permutations of length n that avoid 231.

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 121, 355, 1037, 3025, 8824, 25746, 75130, 219246, 639805, 1867066, 5448412, 15899370, 46397015, 135394275, 395103258, 1152977744, 3364582879, 9818418346, 28651794889, 83610752932, 243990229487, 712004497223, 2077748790043, 6063220178075

Offset: 0

Kassie Archer, Mar 31 2025

A shallow permutation is a permutation that satisfies the lower bound of the Diaconis-Graham inequality (i.e., so that the total displacement is equal to the sum of the length and reflection length).

Michael De Vlieger, Table of n, a(n) for n = 0..2151
Kassie Archer, Aaron Geary, and Robert P. Laudone, Pattern-avoiding shallow permutations, arXiV:2412.11999 [math.CO], 2024
Index entries for linear recurrences with constant coefficients, signature (4,-4,2,1,1).

Cf. A062869, A301897.

CoefficientList[Series[(1 - 3*x + 2*x^2 - x^3 - x^4 - x^5)/(1 - 4*x + 4*x^2 - 2*x^3 -x^4 - x^5), {x, 0, 29}], x] (* Michael De Vlieger, Apr 01 2025 *)

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

A381859 a(n) is the number of permutations that avoid 312 and 4321 and whose square avoids 321.

Original entry on oeis.org

1, 1, 2, 5, 11, 23, 50, 109, 236, 511, 1108, 2402, 5206, 11284, 24459, 53016, 114914, 249081, 539894, 1170243, 2536551, 5498082, 11917326, 25831309, 55990457, 121361689, 263056605, 570186341, 1235903062, 2678872272, 5806569196, 12585984849, 27280655629

Offset: 0

Kassie Archer, Mar 10 2025

			The 11 permutations of length 4 are: 1234, 1243, 1324, 1342, 1432, 2134, 2143, 2314, 2341, 3214, 3421.

Michael De Vlieger, Table of n, a(n) for n = 0..2977
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See p. 8.
Index entries for linear recurrences with constant coefficients, signature (2,0,1,0,-1).

Cf. A001590 (with square avoiding 312), A001590 (with square avoiding 132).

CoefficientList[Series[(1 - x)/(1 - 2*x - x^3 + x^5), {x, 0, 32}], x] (* Michael De Vlieger, May 13 2025 *)

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

a(n) = a(n-3) + a(n-4) + Sum_{j=0..n-1} a(j).

A381858 a(n) is the number of permutations of [n] that avoid 312 and 4321 and whose square avoids 231.

Original entry on oeis.org

1, 1, 2, 5, 12, 26, 56, 125, 279, 618, 1367, 3030, 6720, 14896, 33013, 73173, 162198, 359525, 796900, 1766366, 3915256, 8678393, 19236131, 42637934, 94509351, 209485238, 464335636, 1029225640, 2281335673, 5056707001, 11208471338, 24844197877, 55068541516

Offset: 0

Kassie Archer, Mar 10 2025

Michael De Vlieger, Table of n, a(n) for n = 0..2893
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See p. 8.
Index entries for linear recurrences with constant coefficients, signature (1,1,2,3,2).

LinearRecurrence[{1,1,2,3,2},{1, 1, 2, 5, 12},33] (* James C. McMahon, Mar 10 2025 *)

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

A370686 a(n) is the number of 132-avoiding permutations p so that p^3 is the identity permutation.

Original entry on oeis.org

1, 1, 1, 3, 5, 7, 17, 31, 49, 107, 201, 339, 699, 1327, 2327, 4643, 8843, 15895, 31099, 59251, 108239, 209239, 398355, 735619, 1411351, 2684147, 4993111, 9533775, 18112735, 33863375, 64457715, 122348279, 229537011, 436029791, 827012339, 1555314327, 2950532447, 5592873575, 10536068991

Offset: 0

Kassie Archer, Feb 26 2024

nonn

a(n) is the number of 132-avoiding permutations composed only of 3-cycles and fixed points.

Kassie Archer and Robert P. Laudone, Pattern-restricted permutations of small order, arXiv:2402.15463 [math.CO], 2024.

Cf. A000108, A309331.

my(N=44,x='x+O('x^N),C(x)=(1-sqrt(1-4*x))/(2*x)); Vec(C(x^3)/(sqrt(C(x^3)*(4-3*C(x^3)))-x*C(x^3))) \\ Joerg Arndt, Feb 27 2024

G.f.: c(x^3)/(sqrt(c(x^3)*(4-3*c(x^3)))-x*c(x^3)) where c(x) is the generating function for the Catalan numbers.

A368299 a(n) is the number of permutations pi of [n] that avoid {231,321} so that pi^4 avoids 132.

Original entry on oeis.org

0, 1, 2, 4, 7, 13, 23, 41, 72, 127, 223, 392, 688, 1208, 2120, 3721, 6530, 11460, 20111, 35293, 61935, 108689, 190736, 334719, 587391, 1030800, 1808928, 3174448, 5570768, 9776017, 17155714, 30106180, 52832663, 92714861, 162703239, 285524281, 501060184, 879299327

Offset: 0

Kassie Archer, Dec 20 2023

Number of compositions of n of the form d_1+d_2+...+d_k=n where d_i is in {1,2,4} if i>1 and d_1 is any positive integer.

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1,-1).

Cf. A000071 (d_i in {1,2}), A077868 (d_i in {1,3}), A274110, A303666.

Partial sums of A181532.

a:= proc(n) option remember;
     `if`(n<1, 0, 1+add(a(n-j), j=[1, 2, 4]))
    end:
seq(a(n), n=0..37);  # Alois P. Heinz, Dec 20 2023

LinearRecurrence[{2,0,-1,1,-1},{0,1,2,4,7},38] (* Stefano Spezia, Dec 21 2023 *)

G.f.: x/((1-x)*(1-x-x^2-x^4)).
a(n) = Sum_{m=0..n-1} Sum_{r=0..floor(m/4)} Sum_{j=0..floor((m-4*r)/2)} binomial(m-3*r-j,r)*binomial(m-4*r-j,j).
a(n) = 1+a(n-1)+a(n-2)+a(n-4) where a(0)=0, a(1)=1, a(2)=2, a(3)=4.
a(n) = A274110(n+1) - 1.

A353133 Coefficients of expansion of f(x) = (1+xm(x))^5(x^2(xm(x))'+1) where m(x) is the generating function for A001006.

Original entry on oeis.org

1, 5, 16, 47, 136, 392, 1130, 3262, 9434, 27337, 79364, 230815, 672380, 1961635, 5730860, 16763685, 49093260, 143924943, 422352816, 1240529133, 3646710456, 10728322770, 31584554610, 93048320820, 274292367650, 809044988695, 2387642856380, 7050001551361, 20826624824612, 61552574382856

Offset: 0

Kassie Archer, Apr 25 2022

nonn

2*x^7*f(x) is the generating function for the number of Dyck paths with L(D)=7 where L(D) is the product of binomial coefficients (u_i(D)+d_i(D) choose u_i(D)), where u_i(D) is the number of up-steps between the i-th and (i+1)-st down step and d_i(D) is the number of down-steps between the i-th and (i+1)-st up step.

Kassie Archer and Christina Graves, Pattern-restricted permutations composed of 3-cycles, arXiv:2104.12664 [math.CO], 2021.
Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.

Cf. A001006, A005717, A005773, A025565, A225034.

m(x) = (1-x-sqrt(1-2*x-3*(x^2)))/(2*(x^2));
my(x='x+O('x^30)); Vec((1+x*m(x))^5*(x^2*(x*m(x))'+1)) \\ Michel Marcus, Apr 25 2022

A352916 a(n) = A025179(n-2) + A102839(n-4), for n >= 4, with a(0) = a(2) = 0 and a(1) = a(3) = 1.

Original entry on oeis.org

0, 1, 0, 1, 1, 5, 13, 41, 121, 366, 1100, 3319, 10015, 30253, 91433, 276475, 836291, 2530321, 7657317, 23175867, 70150875, 212349687, 642803631, 1945819299, 5890003539, 17828324220, 53961228258, 163314594513, 494238394601, 1495593167851, 4525366817455

Offset: 0

Kassie Archer, Apr 26 2022

nonn

a(n) + 2*A025565(n) is the number of Dyck paths of semilength n+2 with L(D) = 4 where L(D) is the product of binomial coefficients (u_i(D)+d_i(D) choose u_i(D)), where u_i(D) is the number of up-steps between the i-th and (i+1)-st down step and d_i(D) is the number of down-steps between the i-th and (i+1)-st up step.

Kassie Archer and Christina Graves, Pattern-restricted permutations composed of 3-cycles, arXiv:2104.12664 [math.CO], 2021.
Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.

Cf. A001006, A025179, A025565, A102839.

a:= proc(n) option remember; `if`(n<4, irem(n, 2),
     ((3*(n-4))*(n^4+6*n^3-41*n^2+18*n+76)*a(n-2)+
      (2*n^5+3*n^4-136*n^3+525*n^2-658*n+132)*a(n-1))/
      ((n^4+2*n^3-53*n^2+114*n+12)*(n-1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, May 19 2022

m[n_] := m[n] = If[n == 0, 1, m[n-1] + Sum[m[k]*m[n-2-k], {k, 0, n-2}]];
a[n_] := Switch[n, 0|2, 0, 1|3|4, 1, _, m[n-3] + Binomial[n-3, 2]*m[n-5] + 2*Sum[(i+1)*m[i]*m[n-5-i], {i, 0, n-5}]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 26 2022 *)

m(n) = polcoeff( ( 1 - x - sqrt((1 - x)^2 - 4 * x^2 + x^3 * O(x^n))) / (2 * x^2), n); \\ A001006
a(n) = if (n<=3, n%2, m(n-3) + binomial(n-3,2)*m(n-5) + 2*sum(i=0, n-5, (i+1)*m(i)*m(n-5-i))); \\ Michel Marcus, May 19 2022

a(n) = m(n-3) + binomial(n-3,2)*m(n-5) + 2*Sum_{i=0..n-5} (i+1)*m(i)*m(n-5-i) for n>=3, where m(n) = A001006(n) is the n-th Motzkin number.
a(n) ~ sqrt(n) * 3^(n - 7/2) / (4*sqrt(Pi)). - Vaclav Kotesovec, Jun 03 2022
D-finite with recurrence (n-1)*(n-69)*a(n) +(n^2+221*n-513)*a(n-1) +(-37*n^2+356*n-312)*a(n-2) +(47*n^2-859*n+2820)*a(n-3) +12*(7*n-30)*(n-6)*a(n-4)=0. - R. J. Mathar, Jul 17 2023

A350665 Number of permutations avoiding 321 of length 3n composed of only 3-cycles.

Original entry on oeis.org

1, 2, 10, 60, 388, 2606, 17890, 124512, 874562, 6182198, 43903044, 312843918, 2235028210, 15999423988, 114710881886, 823463493632, 5917220509358

Offset: 0

Kassie Archer, Jan 10 2022

Sum over all Dyck paths D of L(D)*2^h(D), where h(D) is the number of times the Dyck path hits the x-axis and L(D) is the product of binomial coefficients (u_i(D)+d_i(D) choose u_i(D)), where u_i(D) is the number of up-steps between the i-th and (i+1)-st down step and d_i(D) is the number of down-steps between the i-th and (i+1)-st up step.

			For n=2, the ten permutations (in one-line notation and cycle notation) are:
  [2, 3, 1, 5, 6, 4] (1,2,3)(4,5,6)
  [3, 1, 2, 5, 6, 4] (1,3,2)(4,5,6)
  [2, 3, 1, 6, 4, 5] (1,2,3)(4,6,5)
  [3, 1, 2, 6, 4, 5] (1,3,2)(4,6,5)
  [4, 1, 6, 2, 3, 5] (1,4,2)(3,6,5)
  [2, 4, 6, 1, 3, 5] (1,2,4)(3,6,5)
  [4, 1, 5, 2, 6, 3] (1,4,2)(3,5,6)
  [5, 6, 1, 2, 3, 4] (1,5,3)(2,6,4)
  [2, 4, 5, 1, 6, 3] (1,2,4)(3,5,6)
  [3, 4, 5, 6, 1, 2] (1,3,5)(2,4,6)

Kassie Archer and Christina Graves, Pattern-restricted permutations composed of 3-cycles, arXiv:2104.12664 [math.CO], 2021.

Cf. A350645.

A350645 Number of permutations avoiding 132 of length 3n composed of only 3-cycles.

Original entry on oeis.org

1, 2, 8, 36, 170, 824, 4060, 20232, 101664, 514140, 2613468, 13340496, 68335644, 351087128, 1808405600, 9335697424, 48289295226, 250213951992, 1298517484804, 6748250144600, 35114221973600, 182924946400680, 953931045159000, 4979398271047200, 26014703727203100

Offset: 0

Kassie Archer, Jan 09 2022

nonn

Also the number of permutations avoiding 213 of length 3n composed of only 3-cycles.

			For n=2, the eight permutations (in one-line notation and cycle notation) are:
  [6, 5, 2, 1, 3, 4] (1,6,4)(2,5,3)
  [6, 4, 2, 3, 1, 5] (1,6,5)(2,4,3)
  [6, 3, 4, 2, 1, 5] (1,6,5)(2,3,4)
  [5, 6, 1, 2, 3, 4] (1,5,3)(2,6,4)
  [3, 4, 5, 6, 1, 2] (1,3,5)(2,4,6)
  [4, 3, 5, 6, 2, 1] (1,4,6)(2,3,5)
  [5, 3, 4, 2, 6, 1] (1,5,6)(2,3,4)
  [5, 4, 2, 3, 6, 1] (1,5,6)(2,4,3) .

Kassie Archer and Christina Graves, Pattern-restricted permutations composed of 3-cycles, arXiv:2104.12664 [math.CO], 2021.

Cf. A000108, A001006, A127632.

G.f.: c(x*c(x))/(2-c(x*c(x))) where c(x) is the generating function for Catalan numbers. Notice c(x*c(x)) is given in A127632.

G.f.: (1+A(x))/(1-A(x)) where A(x) = (c(x)-1)*c(m(x)-1) where c(x) is the generating function for Catalan numbers and m(x) is the generating function for the Motzkin numbers.

cp's OEIS Frontend

User: Kassie Archer

A382574 a(n) is the number of shallow permutations of length n that avoid 123.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A382570 a(n) is the number of shallow permutations of length n that avoid 231.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A381859 a(n) is the number of permutations that avoid 312 and 4321 and whose square avoids 321.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A381858 a(n) is the number of permutations of [n] that avoid 312 and 4321 and whose square avoids 231.

Views

Author

Keywords

Links

Programs

Mathematica

Formula

A370686 a(n) is the number of 132-avoiding permutations p so that p^3 is the identity permutation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A368299 a(n) is the number of permutations pi of [n] that avoid {231,321} so that pi^4 avoids 132.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A353133 Coefficients of expansion of f(x) = (1+x*m(x))^5*(x^2*(x*m(x))'+1) where m(x) is the generating function for A001006.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A352916 a(n) = A025179(n-2) + A102839(n-4), for n >= 4, with a(0) = a(2) = 0 and a(1) = a(3) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A353133 Coefficients of expansion of f(x) = (1+xm(x))^5(x^2(xm(x))'+1) where m(x) is the generating function for A001006.