A022558 -id:A022558 - cp's OEIS frontend

A005802 Number of permutations in S_n with longest increasing subsequence of length <= 3 (i.e., 1234-avoiding permutations); vexillary permutations (i.e., 2143-avoiding).

1, 1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, 3763290, 24792705, 167078577, 1148208090, 8026793118, 56963722223, 409687815151, 2981863943718, 21937062144834, 162958355218089, 1221225517285209, 9225729232653663, 70209849031116183, 537935616492552297

Offset: 0

N. J. A. Sloane, Simon Plouffe

Also the dimension of SL(3)-invariants in V^n tensor (V^*)^n, where V is the standard 3-dimensional representation of SL(3) and V^* is its dual. - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
Also the number of doubly-alternating permutations of length 2n with no four-term increasing subsequence (i.e., 1234-avoiding doubly-alternating permutations). The doubly-alternating permutations (counted by sequence A007999) are those permutations w such that both w and w^(-1) have descent set {2, 4, 6, ...}. - Joel B. Lewis, May 21 2009
Any permutation without an increasing subsequence of length 4 has a decreasing subsequence of length >= n/3, where n is the length of the sequence, by the Erdős-Szekeres theorem. - Charles R Greathouse IV, Sep 26 2012
Also the number of permutations of length n simultaneously avoiding patterns 1324 and 3416725 (or 1324 and 3612745). - Alexander Burstein, Jan 31 2014

Eric S. Egge, Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics, pp. 65-82 of "A Century of Advancing Mathematics", ed. S. F. Kennedy et al., MAA Press 2015.
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.16(e), p. 453.

Alois P. Heinz, Table of n, a(n) for n = 0..1060
Michael Albert and Mireille Bousquet-Mélou, Permutations sortable by two stacks in parallel and quarter plane walks, arXiv:1312.4487 [math.CO], 2014-2015.
Michael Albert and Mireille Bousquet-Mélou, Permutations sortable by two stacks in parallel and quarter plane walks, European Journal of Combinatorics 43 (2015), 131-164.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
A. Burstein and J. Pantone, Two examples of unbalanced Wilf-equivalence, arXiv preprint arXiv:1402.3842 [math.CO], 2014.
CombOS - Combinatorial Object Server, Generate pattern-avoiding permutations
Andrew R. Conway and Anthony J. Guttmann, On 1324-avoiding permutations, Advances in Applied Mathematics, Volume 64, March 2015, p. 50-69.
Andrew R. Conway and Anthony J. Guttmann, Counting occurrences of patterns in permutations, arXiv:2306.12682 [math.CO], 2023. See p. 18.
Tom Denton, Algebraic and Affine Pattern Avoidance, arXiv preprint arXiv:1303.3767 [math.CO], 2013.
Eric S. Egge, Defying God: The Stanley-Wilf Conjecture, Stanley-Wilf Limits, and a Two-Generation Explosion of Combinatorics, MAA Focus, August/September 2015, pp. 33-34. [Annotated scanned copy]
Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r, arXiv:1504.02513 [math.CO], 2015.
Steven Finch, Pattern-Avoiding Permutations [Cached copy at the Wayback Machine]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
A. L. L. Gao, S. Kitaev, and P. B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory A 53 (1990), 257-285.
O. Guibert and E. Pergola, Enumeration of vexillary involutions which are equal to their mirror/complement, Discrete Math., Vol. 224 (2000), pp. 281-287.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
J. Noonan and D. Zeilberger, The Enumeration of Permutations With A Prescribed Number of "Forbidden" Patterns.
J. Noonan and D. Zeilberger, The Enumeration of Permutations With A Prescribed Number of "Forbidden" Patterns, Advances in Applied Mathematics, Vol. 17, 1996, pp. 381-407.
J. Noonan and D. Zeilberger, The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns, arXiv:math/9808080 [math.CO], 1998.
Erik Ouchterlony, Pattern avoiding doubly alternating permutations
Permutation Pattern Avoidance Library (PermPAL), 0123
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
Anders Bjorner and Richard P. Stanley, A combinatorial miscellany
R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.

A column of A047888. See also A224318, A223034, A223905.
Column k=3 of A214015.
A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).

a:= n-> 2*add(binomial(2*k,k)*(binomial(n,k))^2*(3*k^2+2*k+1-n-2*k*n)/ (k+1)^2/(k+2)/(n-k+1),k=0..n);
A005802:=rsolve({a(0) = 1, a(1) = 1, (n^2 + 8*n + 16)*a(n + 2) = (10*n^2 + 42*n + 41)*a(n + 1) - (9*n^2 + 18*n + 9)*a(n)},a(n),makeproc): # Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

a[n_] := 2Sum[Binomial[2k, k]Binomial[n, k]^2(3k^2+2k+1-n-2k*n)/((k+1)^2(k+2)(n-k+1)), {k, 0, n}]
(* Second program:*)
a[0] = a[1] = 1; a[n_] := a[n] = ((10*n^2+2*n-3)*a[n-1] + (-9*n^2+18*n-9)* a[n-2])/(n+2)^2; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 20 2017 *)
Table[HypergeometricPFQ[{1/2, -1 - n, -n}, {2, 2}, 4] / (n+1), {n, 0, 25}] (* Vaclav Kotesovec, Jun 07 2021 *)

a(n)=2*sum(k=0,n,binomial(2*k,k)*binomial(n,k)^2*(3*k^2+2*k+1-n-2*k*n)/(k+1)^2/(k+2)/(n-k+1)) \\ Charles R Greathouse IV, Sep 26 2012

a(n) = 2 * Sum_{k=0..n} binomial(2*k, k) * (binomial(n, k))^2 * (3*k^2 + 2*k+1 - n - 2*k*n)/((k+1)^2 * (k+2) * (n-k+1)).
(4*n^2 - 2*n + 1)*(n + 2)^2*(n + 1)^2*a(n) = (44*n^3 - 14*n^2 - 11*n + 8)*n*(n + 1)^2*a(n - 1) - (76*n^4 + 42*n^3 - 49*n^2 - 24*n + 24)*(n - 1)^2*a(n - 2) + 9*(4*n^2 + 6*n + 3)*(n - 1)^2*(n - 2)^2*a(n - 3). - Vladeta Jovovic, Jul 16 2004
a(0) = 1, a(1) = 1, (n^2 + 8*n + 16)*a(n + 2) = (10*n^2 + 42*n + 41) a(n + 1) - (9*n^2 + 18*n + 9) a(n). - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
a(n) = ((18*n+45)*A002893(n) - (7+2*n)*A002893(n+1)) / (6*(n+2)^2). - Mark van Hoeij, Jul 02 2010
G.f.: (1+5*x-(1-9*x)^(3/4)*(1-x)^(1/4)*hypergeom([-1/4, 3/4],[1],64*x/((x-1)*(1-9*x)^3)))/(6*x^2). - Mark van Hoeij, Oct 25 2011
a(n) ~ 3^(2*n+9/2)/(16*Pi*n^4). - Vaclav Kotesovec, Jul 29 2013
a(n) = Sum_{k=0..n} binomial(2k,k)*binomial(n+1,k+1)*binomial(n+2,k+1)/((n+1)^2*(n+2)). [Conway and Guttmann, Adv. Appl. Math. 64 (2015) 50]
For n > 0, (n+2)^2*a(n) - n^2*a(n-1) = 4*A086618(n). - Zhi-Wei Sun, Nov 16 2017
a(n) = hypergeom([1/2, -1 - n, -n], [2, 2], 4) / (n+1). - Vaclav Kotesovec, Jun 07 2021

Additional comments from Emeric Deutsch, Dec 06 2000
More terms from Naohiro Nomoto, Jun 18 2001
Edited by Dean Hickerson, Dec 10 2002
More terms from Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005

A064062 Generalized Catalan numbers C(2; n).

Original entry on oeis.org

1, 1, 3, 13, 67, 381, 2307, 14589, 95235, 636925, 4341763, 30056445, 210731011, 1493303293, 10678370307, 76957679613, 558403682307, 4075996839933, 29909606989827, 220510631755773, 1632599134961667, 12133359132082173

Offset: 0

Wolfdieter Lang, Sep 13 2001

a(n+1) = Y_{n}(n+1) = Z_{n}, n >= 0, in the Derrida et al. 1992 reference (see A064094) for alpha=2, beta=1 (or alpha=1, beta=2).
a(n) = number of Dyck n-paths (A000108) in which each upstep (U) not at ground level is colored red (R) or blue (B). For example, a(3)=3 counts URDD, UBDD, UDUD (D=downstep). - David Callan, Mar 30 2007
The Hankel transform of this sequence is A002416. - Philippe Deléham, Nov 19 2007
The sequence a(n)/2^n, with g.f. 1/(1-xc(x)/2), has Hankel transform 1/2^n. - Paul Barry, Apr 14 2008
The REVERT transform of the odd numbers [1,3,5,7,9,...] is [1, -3, 13, -67, 381, -2307, 14589, -95235, 636925, ...] - N. J. A. Sloane, May 26 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..200
J. Abate and W. Whitt, Brownian Motion and the Generalized Catalan Numbers, J. Int. Seq. 14 (2011) # 11.2.6, example section 3.
Jean-Luc Baril, Sergey Kirgizov, and Mehdi Naima, A lattice on Dyck paths close to the Tamari lattice, arXiv:2309.00426 [math.CO], 2023.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. - From _N. J. A. Sloane_, Oct 08 2012
J. Bloom and S. Elizalde, Pattern avoidance in matchings and partitions, arXiv:1211.3442 [math.CO] (2012) Theorem 6.1.
N. Bonichon, C. Gavoille and N. Hanusse, Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation, In Proceedings of WG'03, volume 2880 of LNCS, pp. 81-92, 2003.
Alexander Burstein, Sergi Elizalde and Toufik Mansour, Restricted Dumont permutations, Dyck paths and noncrossing partitions, arXiv:math/0610234 [math.CO], 2006.
Xiang-Ke Chang, X.-B. Hu, H. Lei and Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).
Simone Fioravanti, Steve Hanneke, Shay Moran, Hilla Schefler, and Iska Tsubari, Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem, arXiv:2407.07765 [cs.LG], 2024. See p. 44.
Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.
N. J. A. Sloane, Transforms
A. Vieru, Agoh's conjecture: its proof, its generalizations, its analogues, arXiv preprint arXiv:1107.2938 [math.NT], 2011-2012.

Generalized Catalan numbers C(m; n): A000012 (m = 0), A000108 (m = 1), A064063 (m = 3) and A064087 - A064093 (m = 4 thru 10); A064310 (m = -1), A064311 (m = -2) and A064325 - A064333 (m = -3 thru -11).

Cf. A064334, A119529.

R:=PowerSeriesRing(Rationals(), 30);
Coefficients(R!( (3 - Sqrt(1-8*x))/(2*(1+x)) )); // G. C. Greubel, Sep 27 2024

1, seq(simplify(hypergeom([1-n,n],[-n],2)), n=1..100); # Robert Israel, Nov 30 2014

a[0]=1; a[1]=1; a[n_]/;n>=2 := a[n] = a[n-1] + Sum[(a[k] + a[k-1])a[n-k],{k,n-1}]; Table[a[n],{n,0,10}] (* David Callan, Aug 27 2009 *)
a[n_] := 2*Sum[ (-1)^j*2^(n-j-1)*Binomial[2*(n-j-1), n-j-1]/(n-j), {j, 0, n-1}] + (-1)^n; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Jul 03 2013 *)

{a(n)=polcoeff((3-sqrt(1-8*x+x*O(x^n)))/(2+2*x),n)}

{a(n)=local(A=1+x); for(i=1, n, A=1+A^4*intformal(1/(A^2+x*O(x^n)))); polcoeff(A, n)} \\ Paul D. Hanna, Dec 24 2013
for(n=0, 25, print1(a(n), ", "))

{a(n)=polcoeff(1/(1 - serreverse(x-2*x^2 +x^2*O(x^n))),n)}
for(n=0,30,print1(a(n),", ")) \\ Paul D. Hanna, Nov 30 2014

def a(n):
    if n==0: return 1
    return hypergeometric([1-n, n], [-n], 2).simplify()
[a(n) for n in range(22)] # Peter Luschny, Dec 01 2014

G.f.: (1 + 2*x*C(2*x)) / (1+x) = 1/(1 - x*C(2*x)) with C(x) g.f. of Catalan numbers A000108.
a(n) = A062992(n-1) = Sum_{m = 0..n-1} (n-m)*binomial(n-1+m, m)*(2^m)/n, n >= 1, a(0) = 1.
a(n) = Sum_{k = 0..n} A059365(n, k)*2^(n-k). - Philippe Deléham, Jan 19 2004
G.f.: 1/(1-x/(1-2x/(1-2x/(1-2x/(1-.... = 1/(1-x-2x^2/(1-4x-4x^2/(1-4x-4x^2/(1-.... (continued fractions). - Paul Barry, Jan 30 2009
a(n) = (32/Pi)*Integral_{x = 0..1} (8*x)^(n-1)*sqrt(x*(1-x)) / (8*x+1). - Groux Roland, Dec 12 2010
a(n+2) = 8^(n+2)*( c(n+2)-c(1)*c(n+1) - Sum_{i=0..n-1} 8^(-i-2)*c(n-i)*a(i+2) ) with c(n) = Catalan(n+2)/2^(2*n+1). - Groux Roland, Dec 12 2010
a(n) = the upper left term in M^n, M = the production matrix:
  1, 1
  2, 2, 1
  4, 4, 2, 1
  8, 8, 4, 2, 1
  ... - Gary W. Adamson, Jul 08 2011
D-finite with recurrence: n*a(n) + (12-7n)*a(n-1) + 4*(3-2n)*a(n-2) = 0. - R. J. Mathar, Nov 16 2011 (This follows easily from the generating function. - Robert Israel, Nov 30 2014)
G.f. satisfies: A(x) = 1 + A(x)^4 * Integral 1/A(x)^2 dx. - Paul D. Hanna, Dec 24 2013
G.f. satisfies: Integral 1/A(x)^2 dx = x - x^2*G(x), where G(x) is the o.g.f. of A000257, the number of rooted bicubic maps. - Paul D. Hanna, Dec 24 2013
G.f. A(x) satisfies: A(x - 2*x^2) = 1/(1-x). - Paul D. Hanna, Nov 30 2014
a(n) = hypergeometric([1-n, n], [-n], 2) for n > 0. - Peter Luschny, Nov 30 2014
G.f.: (3 - sqrt(1-8*x))/(2*(x+1)). - Robert Israel, Nov 30 2014
a(n) ~ 2^(3*n+1) / (9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Dec 22 2014
O.g.f. A(x) =  1 + series reversion of (x*(1 - x)/(1 + x)^2). Logarithmically differentiating (A(x) - 1)/x gives 3 + 17*x + 111*x^2 + ..., essentially a g.f for A119259. - Peter Bala, Oct 01 2015
From Peter Bala, Jan 06 2022: (Start)
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 6*x^3 + 23*x^4 + ... is a g.f. for A022558.
The Gauss congruences a(n*p^k) == a(n^p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. (End)

A117158 Number of permutations avoiding the consecutive pattern 1234.

Original entry on oeis.org

1, 1, 2, 6, 23, 111, 642, 4326, 33333, 288901, 2782082, 29471046, 340568843, 4263603891, 57482264322, 830335952166, 12793889924553, 209449977967081, 3630626729775362, 66429958806679686, 1279448352687538463, 25874432578888440471, 548178875969847203202

Offset: 0

Steven Finch, Apr 26 2006

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 1234. It is the same as the number of permutations which avoid 4321.

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, New York, 1962, pages 156-157.

Alois P. Heinz, Table of n, a(n) for n = 0..450 (terms n = 0..60 from Ray Chandler)
A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. Appl. Math. 36 (2006), 138-155.
Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.
Steven Finch, Pattern-Avoiding Permutations. [Archived version]
Steven Finch, Pattern-Avoiding Permutations. [Cached copy, with permission]
Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory A 53 (1990), 257-285.
Ira M. Gessel, Yan Zhuang, Counting permutations by alternating descents, arXiv:1408.1886 [math.CO], 2014. See displayed equation before Eq. (3) and set m=4. - _N. J. A. Sloane_, Aug 11 2014
Kaarel Hänni, Asymptotics of descent functions, arXiv:2011.14360 [math.CO], Nov 29 2020, p. 14.
Mingjia Yang, Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.
Mingjia Yang, An experimental walk in patterns, partitions, and words, Ph. D. Dissertation, Rutgers University (2020).

Cf. A022558, A049774, A111004, A113228, A113229, A117156, A117226, A177523, A177533, A201692, A201693, A230051, A324132.
Column k=0 of A220183.
Column k=7 of A242784.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<2, add(b(u+j-1, o-j, t+1), j=1..o), 0)+
      add(b(u-j, o+j-1, 0), j=1..u))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013

a[n_]:=Coefficient[Series[2/(Cos[x]-Sin[x]+Exp[ -x]),{x,0,30}],x^n]*n!
(* second program: *)
b[u_, o_, t_] := b[u, o, t] = If[u+o==0, 1, If[t<2, Sum[b[u+j-1, o-j, t+1], {j, 1, o}], 0] + Sum[b[u-j, o+j-1, 0], {j, 1, u}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 23 2015, after Alois P. Heinz *)

From Sergei N. Gladkovskii, Nov 30 2011: (Start)
E.g.f.: 2/(exp(-x) + cos(x) - sin(x)) = 1/W(0) with continued fraction
W(k) = 1 + (x^(2*k))/(f + f*x/(4*k + 1 - x - (4*k + 1)*b/R)), where R := x^(2*k) + b -(x^(4*k+1))/(c + (x^(2*k+1)) + x*c/T); T := 4*k + 3 - x - (4*k + 3)*d/(d +(x^(2*k+1))/W(k+1)), and
f := (4*k)!/(2*k)!; b := (4*k + 1)!/(2*k + 1)!; c := (4*k + 2)!/(2*k + 1)!; and d :=(4*k + 3)!/(2*k + 2)!. (End)
a(n) ~ n! / (sin(r)*r^(n+1)), where r = 1.0384156372665563... is the root of the equation exp(-r) + cos(r) = sin(r). - Vaclav Kotesovec, Dec 11 2013

A099952 Number of Wilf classes in S_n.

Original entry on oeis.org

1, 1, 1, 3, 16, 91, 595

Offset: 1

N. J. A. Sloane, Nov 12 2004

Z. Stankova and J. West, A new class of Wilf-equivalent permutations, J. Algeb. Combin., 15 (2002), 271-290.

A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
A. M. Baxter and A. D. Jaggard, Pattern avoidance by even permutations, arXiv preprint arXiv:1106.3653, 2011
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152. See Fig. 9.

Representatives for the three Wilf classes in S_4 are A005802, A022558, A061552. - N. J. A. Sloane, Mar 15 2015

Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208. - N. J. A. Sloane, Mar 19 2015

A061552 Number of 1324-avoiding permutations of length n.

Original entry on oeis.org

1, 1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, 3824112, 25431452, 173453058, 1209639642, 8604450011, 62300851632, 458374397312, 3421888118907, 25887131596018, 198244731603623, 1535346218316422, 12015325816028313, 94944352095728825, 757046484552152932, 6087537591051072864

Offset: 0

Darko Marinov (marinov(AT)lcs.mit.edu), May 17 2001

nonn

			a(4)=23 because all 24 permutations of length 4, except 1324 itself, avoid the pattern 1324.

Miklós Bóna, Combinatorics of Permutations. Discrete Mathematics and its Applications (Boca Raton), 2nd edn. CRC Press, Boca Raton (2012).

David Bevan, Table of n, a(n) for n = 0..50 (from the Conway/Guttmann reference; terms 0..31 by Joerg Arndt, taken from the Johansson/Nakamura reference; terms 37..50 by Bjarki Ágúst Guðmundsson, taken from the Conway/Guttmann/Zinn-Justin reference).
M. H. Albert, M. Elder, A. Rechnitzer, P. Westcott, and M. Zabrocki, On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia, arXiv:math/0502504 [math.CO], 2005.
R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern., Electron. J. Combin. 6, N1 (1999).
David Bevan, Permutations avoiding 1324 and patterns in Łukasiewicz paths, arXiv:1406.2890 [math.CO], 2014-2015.
David Bevan, Robert Brignall, Andrew Elvey Price and Jay Pantone, A structural characterisation of Av(1324) and new bounds on its growth rate, European J. Combin. 88 (2020).
Miklós Bóna, A new upper bound for 1324-avoiding permutations, arXiv:1207.2379 [math.CO], 2012.
Miklós Bóna, A new upper bound for 1324-avoiding permutations, Combin. Probab. Comput. 23(5), 717-724 (2014).
Miklós Bóna, A new record for 1324-avoiding permutations, arXiv:1404.4033 [math.CO], 2014.
Miklós Bóna, A new record for 1324-avoiding permutations, European Journal of Mathematics (2015) 1:198-206, DOI 10.1007/s40879-014-0020-6.
A. Claesson, V. Jelínek, and E. Steingrímsson, Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns. J. Combin. Theory Ser. A 119(8), 1680-1691 (2012).
Andrew R. Conway and Anthony J. Guttmann, On the growth rate of 1324-avoiding permutations, arXiv:1405.6802 [math.CO], (2014).
Andrew R. Conway, Anthony J. Guttmann and Paul Zinn-Justin, 1324-avoiding permutations revisited, arXiv preprint arXiv:1709.01248 [math.CO], 2017.
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
A. L. L. Gao, S. Kitaev, and P. B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
Ruth Hoffmann, Özgür Akgün, and Christopher Jefferson, Composable Constraint Models for Permutation Enumeration, arXiv:2311.17581 [cs.DM], 2023.
Fredrik Johansson and Brian Nakamura, Using functional equations to enumerate 1324-avoiding permutations, arXiv:1309.7117 [math.CO], (2013).
A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107(1), 153-160 (2004).
B. K. Nakamura, Computational methods in permutation patterns, PhD Dissertation, Rutgers University, May 2013.
Brian Nakamura and Doron Zeilberger, Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes, arXiv preprint arXiv:1209.2353 [math.CO], 2012.
Anthony Zaleski and Doron Zeilberger, On the Intriguing Problem of Counting (n+1,n+2)-Core Partitions into Odd Parts, arXiv:1712.10072 [math.CO], 2017.

A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).

count1324 := proc(n::nonnegint) if (n<4) then return n!; fi; if (n=4) then return 23; fi; return nodes([5,5,5,5], n-5) + nodes([5,3,5,5], n-5) + nodes([5,4,4,5], n-5) + nodes([5,5,4,5], n-5) + nodes([4,3,4], n-5) + nodes([5,3,4,5], n-5); end:
nodes := proc(p, h) option remember; local i, j, s, l; if (h=0) then return convert(p, `+`); fi; s := 0; for j to nops(p) do l := p[j]+1; for i from 2 to j do l := l, `min`(j+1, p[i]); od; for i from j+1 to p[j] do l := l, p[i-1]+1; od; s := s+nodes([l], h-1); od; return s; end:

a[n_] := n!/;n<4; a[4]=23; a[n_] := Total[nodes[#,n-5]&/@{{4,3,4},{5,3,4,5},{5,3,5,5},{5,4,4,5},{5,5,4,5},{5,5,5,5}}]; nodes[p_,0]:=Total[p]; nodes[p_,h_] := nodes[p,h] = Sum[nodes[Join[{p[[j]]+1}, Min[j+1,#]&/@p[[2;;j]], p[[j;;p[[j]]-1]]+1],h-1], {j,Length[p]}]; Array[a,12] (* David Bevan, May 25 2012 *)

More terms from Vincent Vatter, Feb 26 2005

a(23)-a(25) added from the Albert et al. paper by N. J. A. Sloane, Mar 29 2013

A342840 Irregular triangle: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 4213. 0 <= k <= A342646(n).

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 103, 10, 6, 1, 512, 77, 69, 30, 21, 5, 6, 2740, 548, 598, 330, 335, 123, 174, 58, 58, 37, 26, 3, 9, 1, 15485, 3799, 4686, 2970, 3411, 1676, 2338, 1040, 1317, 878, 777, 363, 608, 230, 252, 165, 133, 30, 93, 26, 31, 4, 1, 3, 4, 91245, 26165, 35148, 24550, 30182, 17185, 24685, 12976, 16867, 12248, 12360, 7203, 11086, 5692, 6391, 5194, 5006, 2751, 3917, 2019, 2482, 1622, 1371, 812, 1233, 490, 495, 416, 360, 157, 282, 54, 78, 41, 29, 22, 49, 7, 4, 0, 6

Offset: 0

Peter Kagey, Mar 24 2021

The sequence is the same for the patterns 1342, 2431, and 3124.
The sequence appears to be the same for the patterns 1423, 2314, 3241, and 4132.
First column is given by A022558. Row sums given by n!.

			Triangle begins:
n\k |    0    1    2    3    4    5    6   7   8   9  10 11 12 13
----+-------------------------------------------------------------
  0 |    1;
  1 |    1;
  2 |    2;
  3 |    6;
  4 |   23,   1;
  5 |  103,  10,   6,   1;
  6 |  512,  77,  69,  30,  21,   5,   6;
  7 | 2740, 548, 598, 330, 335, 123, 174, 58, 58, 37, 26, 3, 9, 1;

Peter Kagey, Rows n = 0..13, flattened, based on Anders Kaseorg's Rust program at the Code Golf Stack Exchange link.
FindStat, St000750: The number of occurrences of the pattern 4213 in a permutation.
Anders Kaseorg, Answer: Patterns in Permutations, Code Golf Stack Exchange.
Rob Pratt, Greatest number of occurrences of the pattern 4213 in a permutation, Mathematics Stack Exchange.
Eric Weisstein's World of Mathematics, Permutation Pattern

Cf. A022558, A342646.

Cf. A263771 (analogous for 312).

Join@@Array[Table[Length@Select[Permutations@Range@#,Length@Select[Subsets[#,{4}],Ordering@Ordering@#=={4,2,1,3}&]==k&],{k,0,Binomial[n+1,4]}]//.{a__,0}:>{a}&,8,0] (* Giorgos Kalogeropoulos, Mar 25 2021 *)

A342860 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 2413. 0 <= k <= A342854(n).

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 103, 9, 8, 512, 62, 82, 34, 28, 2, 2740, 402, 612, 384, 466, 94, 232, 42, 60, 8, 15485, 2593, 4187, 3036, 4356, 1746, 3132, 1064, 1918, 909, 654, 333, 612, 144, 104, 22, 24, 1, 91245, 16921, 28065, 21638, 33274, 17598, 31180, 12942, 24000, 14290, 15434, 7770, 15692, 5965, 6896, 3947, 5660, 2226, 3674, 1314, 1512, 516, 508, 204, 332, 37, 40

Offset: 0

Peter Kagey, Mar 26 2021

Equivalently the table for the pattern 3142.

First column is A022558.

			Triangle begins:
  n\k|       0       1        2        3        4        5        6
  ---+------------------------------------------------------------------
   0 |       1;
   1 |       1;
   2 |       2;
   3 |       6;
   4 |      23,      1;
   5 |     103,      9,       8;
   6 |     512,     62,      82,      34,      28,       2;
   7 |    2740,    402,     612,     384,     466,      94,     232, ...
   8 |   15485,   2593,    4187,    3036,    4356,    1746,    3132, ...
   9 |   91245,  16921,   28065,   21638,   33274,   17598,   31180, ...
  10 |  555662, 112196,  188514,  149946,  237128,  140954,  257686, ...
  11 | 3475090, 755920, 1278590, 1036826, 1658064, 1041598, 1933438, ...

Peter Kagey, Rows n = 0..13, flattened, based on Anders Kaseorg's Rust program in the Code Golf Stack Exchange link.
Anders Kaseorg, Answer: Patterns in Permutations, Code Golf Stack Exchange.

Cf. A022558, A342854.

Analogous for other patterns: A008302 (12), A138159 (321), A263771 (312), A342840 (1342), A342861 (1324), A342862 (2143), A342863 (1243), A342864 (1432), A342865 (1234).

cp's OEIS Frontend

A005802 Number of permutations in S_n with longest increasing subsequence of length <= 3 (i.e., 1234-avoiding permutations); vexillary permutations (i.e., 2143-avoiding).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A064062 Generalized Catalan numbers C(2; n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

A117158 Number of permutations avoiding the consecutive pattern 1234.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A099952 Number of Wilf classes in S_n.

Views

Author

Keywords

References

Links

Crossrefs

A061552 Number of 1324-avoiding permutations of length n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A342840 Irregular triangle: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 4213. 0 <= k <= A342646(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A342860 Irregular table read by rows: T(n,k) is the number of permutations in S_n that have exactly k occurrences of the pattern 2413. 0 <= k <= A342854(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs