A071077 -id:A071077 - cp's OEIS frontend

A071075 Number of permutations that avoid the generalized pattern 132-4.

1, 1, 2, 6, 23, 107, 585, 3671, 25986, 204738, 1776327, 16824237, 172701135, 1909624371, 22626612450, 285982186662, 3840440707485, 54603776221965, 819424594880559, 12942757989763101, 214626518776190178, 3728112755679416898, 67692934780306842501, 1282399636333412178531, 25303124674163685176793

Offset: 0

Sergey Kitaev, May 26 2002

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..460
Juan S. Auli, Pattern Avoidance in Inversion Sequences, Ph. D. thesis, Dartmouth College, ProQuest Dissertations Publishing (2020), 27964164.
Juan S. Auli and Sergi Elizalde, Consecutive Patterns in Inversion Sequences, arXiv:1904.02694 [math.CO], 2019. See Table 1.
Andrew M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
Andrew M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv:1108.2642 [math.CO], 2011.
Sergey Kitaev, Partially Ordered Generalized Patterns, preprint.
Sergey Kitaev, Partially Ordered Generalized Patterns, Discrete Math. 298 (2005), no. 1-3, 212-229.
Yan Wang, Qi Fang, Shishuo Fu, Sergey Kitaev, and Haijun Li, Consecutive and quasi-consecutive patterns: des-Wilf classifications and generating functions, arXiv:2502.10128 [math.CO], 2025. See p. 6.

Cf. A071088, A071076, A071077, A111004.

A(y) := 1/(1-int(exp(-t^2/2),t=0..y)); B(x) := exp(int(A(y),y=0..x)); series(B(x),x=0,30);

CoefficientList[Series[E^(Integrate[1/(1-Integrate[E^(-t^2/2), {t,0,y}]), {y,0,x}]), {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Aug 23 2014 *)

N=66; x='x+O('x^N);
A=1/(1-intformal(exp(-x^2/2)));
egf=exp(intformal(A));
Vec(serlaplace(egf))
\\ Joerg Arndt, Aug 28 2014

E.g.f.: exp(int(A(y), y=0..x)), where A(y) = 1/(1 - int(exp(-t^2/2), t=0..y)).
a(n) ~ c * d^n * n! / n^f, where d = 1/A240885 = 1/(sqrt(2)*InverseErf(sqrt(2/Pi))) = 0.7839769312035474991242486548698125357473282..., f = 1.2558142944089303287268746534354522944538722816671534535062816..., c = 0.2242410644782853722452053227678681810005068... . - Vaclav Kotesovec, Aug 23 2014
Let b(n) = A111004(n) = number of permutations of [n] that avoid the consecutive pattern 132. Then a(n) = Sum_{i = 0..n-1} binomial(n-1,i)*b(i)*a(n-1-i) with a(0) = b(0) = 1. [See the recurrence for A_n and B_n in the proof of Theorem 13 in Kitaev's papers.] - Petros Hadjicostas, Nov 01 2019

Link and a(11)-a(20) from Andrew Baxter, May 17 2011

Typo in first formula corrected by Vaclav Kotesovec, Aug 23 2014

A071076 Number of permutations that avoid the generalized pattern 123-4.

Original entry on oeis.org

1, 1, 2, 6, 23, 108, 598, 3815, 27532, 221708, 1970251, 19150132, 202064380, 2300071071, 28092017668, 366425723926, 5083645400819, 74745472084176, 1160974832572274, 18995175706664735, 326531476287842760, 5883736110875887560, 110893188848753125475

Offset: 0

Sergey Kitaev, May 26 2002

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..450
A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
Sergey Kitaev, Partially Ordered Generalized Patterns, preprint.
Sergey Kitaev, Partially Ordered Generalized Patterns, Discrete Math. 298 (2005), no. 1-3, 212-229.
Yan Wang, Qi Fang, Shishuo Fu, Sergey Kitaev, and Haijun Li, Consecutive and quasi-consecutive patterns: des-Wilf classifications and generating functions, arXiv:2502.10128 [math.CO], 2025. See p. 9.

Cf. A049774, A071088, A071075, A071077.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(
      `if`(t=1 and o>j, 0, b(u+j-1, o-j, t+1)), j=1..o)+
       add(b(u-j, o+j-1, 0), j=1..u))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 14 2015

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Sum[If[t == 1 && o > j, 0, b[u + j - 1, o - j, t + 1]], {j, 1, o}] + Sum[b[u - j, o + j - 1, 0], {j, 1, u}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 01 2016, after Alois P. Heinz *)

E.g.f.: exp(int(A(y), y=0..x)), where A(y) = (sqrt(3)/2)*exp(y/2)/cos((sqrt(3)/2)*y + Pi/6).

Let b(n) = A049774(n) = number of permutations of [n] that avoid the consecutive pattern 123. Then a(n) = Sum_{i = 0..n-1} binomial(n-1,i)*b(i)*a(n-1-i) with a(0) = b(0) = 1. [See the recurrence for A_n and B_n in the proof of Theorem 13 in Kitaev's papers.] -

More terms from Vladeta Jovovic, May 28 2002
Link added by Andrew Baxter, May 17 2011
Typos in formula corrected by Vaclav Kotesovec, Aug 23 2014

A071088 Number of permutations that avoid the generalized pattern 12345-6.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 719, 5022, 40064, 359400, 3580896, 39233867, 468818397, 6067548429, 84551873634, 1262188317534, 20095114167065, 339883289813330, 6086154606429378, 115025120586250896, 2288119443771888504, 47787869441095495395, 1045507132393256095282

Offset: 0

Sergey Kitaev, May 26 2002

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..450
Sergey Kitaev, Partially Ordered Generalized Patterns, preprint.
Sergey Kitaev, Partially Ordered Generalized Patterns, Discrete Math. 298 (2005), no. 1-3, 212-229.

Cf. A071075, A071076, A071077, A177523.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, add(
      `if`(t=3 and o>j, 0, b(u+j-1, o-j, t+1)), j=1..o)+
       add(b(u-j, o+j-1, 0), j=1..u))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 14 2015

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[If[t == 3 && o > j, 0, b[u+j-1, o-j, t+1]], {j, 1, o}] + Sum[b[u-j, o+j-1, 0], {j, 1, u}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 25] (* Jean-François Alcover, Nov 02 2020, after Alois P. Heinz *)

E.g.f.: exp(int(A(y), y=0..x)), where A(y) = 1/(Sum_{i>=0} y^{5*i}/(5*i)! - Sum_{i>=0} y^{5*i+1}/(5*i+1)!).

Let b(n) = A177523(n) = number of permutations of [n] that avoid the consecutive pattern 12345. Then a(n) = Sum_{i = 0..n-1} binomial(n-1,i)*b(i)*a(n-1-i) with a(0) = b(0) = 1. [See the recurrence for A_n and B_n in the proof of Theorem 13 in Kitaev's papers.] - Petros Hadjicostas, Nov 01 2019

More terms from Vladeta Jovovic, May 28 2002

cp's OEIS Frontend

A071075 Number of permutations that avoid the generalized pattern 132-4.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A071076 Number of permutations that avoid the generalized pattern 123-4.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A071088 Number of permutations that avoid the generalized pattern 12345-6.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions