A240885 -id:A240885 - cp's OEIS frontend

A049774 Number of permutations of n elements not containing the consecutive pattern 123.

1, 1, 2, 5, 17, 70, 349, 2017, 13358, 99377, 822041, 7477162, 74207209, 797771521, 9236662346, 114579019469, 1516103040833, 21314681315998, 317288088082405, 4985505271920097, 82459612672301846, 1432064398910663705, 26054771465540507273, 495583804405888997218

Offset: 0

Tuwani A. Tshifhumulo (tat(AT)caddy.univen.ac.za)

Permutations on n letters without double falls. A permutation w has a double fall at k if w(k) > w(k+1) > w(k+2) and has an initial fall if w(1) > w(2).
Hankel transform is A055209. - Paul Barry, Jan 12 2009
Increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of outdegree 2 except those vertices on the path from the root to the leftmost leaf. - Wenjin Woan, May 21 2011

			Permutations without double increase and without pattern 123:
a(3) = 5: 132, 213, 231, 312, 321.
a(4) = 17: 1324, 1423, 1432, 2143, 2314, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312, 4321.

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, New York, 1962, pp. 156-157.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (5.2.17).

Alois P. Heinz, Table of n, a(n) for n = 0..464 (first 201 terms from Ray Chandler)
Martin Aigner, Catalan and other numbers: a recurrent theme, in Algebraic Combinatorics and Computer Science, a Tribute to Gian-Carlo Rota, pp.347-390, Springer, 2001.
Juan S. Auli, Pattern Avoidance in Inversion Sequences, Ph. D. thesis, Dartmouth College, ProQuest Dissertations Publishing (2020), 27964164.
Juan S. Auli, Sergi Elizalde, Consecutive Patterns in Inversion Sequences, arXiv:1904.02694 [math.CO], 2019. See Table 1.
Paul Barry, Constructing Exponential Riordan Arrays from Their A and Z Sequences, Journal of Integer Sequences, 17 (2014), #14.2.6.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Nicolas Basset, Counting and generating permutations using timed languages, HAL Id: hal-00820373, 2013.
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes; Local copy [Pdf file only, no active links].
S. Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns arXiv:math/0505254 [math.CO], 2015.
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-123.
Steven Finch, Pattern-Avoiding Permutations [Archived version]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
Ira M. Gessel and Yan Zhuang, Counting permutations by alternating descents , arXiv:1408.1886 [math.CO], 2014. See Eq. (3). - _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 and Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.
Christopher Zhu, Enumerating Permutations and Rim Hooks Characterized by Double Descent Sets, arXiv:1910.12818 [math.CO], 2019.

Cf. A065429, A080635, A111004, A117158, A177523, A177533.
Column k=0 of A162975.
Column k=3 of A242784.
Equals 1 + A000303. - Greg Dresden, Feb 22 2020

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

Table[Simplify[ n! SeriesCoefficient[ Series[ Sqrt[3] Exp[x/2]/(Sqrt[3] Cos[Sqrt[3]/2 x] - Sin[Sqrt[3]/2 x]), {x, 0, n}], n] ], {n, 0, 40}]
(* Second program: *)
b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u] + o < k, 0, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}] + Sum[b[u - j, o + j - 1, 1, k], {j, 1, u}]]];
a[n_] := b[0, n, 0, 2] - b[0, n, 0, 3] + 1;
a /@ Range[0, 40] (* Jean-François Alcover, Nov 09 2020, after Alois P. Heinz in A000303 *)

E.g.f.: 1/Sum_{i>=0} (x^(3*i)/(3*i)! - x^(3*i+1)/(3*i+1)!). [Corrected g.f. --> e.g.f. by Vaclav Kotesovec, Feb 15 2015]
Equivalently, e.g.f.: exp(x/2) * r / sin(r*x + (2/3)*Pi) where r = sqrt(3)/2. This has simple poles at (3*m+1)*x0 where x0 = Pi/sqrt(6.75) = 1.2092 approximately and m is an arbitrary integer. This yields the asymptotic expansion a(n)/n! ~ x0^(-n-1) * Sum((-1)^m * E^(3*m+1) / (3*m+1)^(n+1)) where E = exp(x0/2) = 1.8305+ and m ranges over all integers. - Noam D. Elkies, Nov 15 2001
E.g.f.: sqrt(3)*exp(x/2)/(sqrt(3)*cos(x*sqrt(3)/2) - sin(x*sqrt(3)/2) ); a(n+1) = Sum_{k=0..n} binomial(n, k)*a(k)*b(n-k) where b(n) = number of n-permutations without double falls and without initial falls. - Emanuele Munarini, Feb 28 2003
O.g.f.: A(x) = 1/(1 - x - x^2/(1 - 2*x - 4*x^2/(1 - 3*x - 9*x^2/(1 - ... - n*x - n^2*x^2/(1 - ...))))) (continued fraction). - Paul D. Hanna, Jan 17 2006
a(n) = leftmost column term of M^n*V, where M = an infinite tridiagonal matrix with (1,2,3,...) in the super, sub, and main diagonals and the rest zeros. V = the vector [1,0,0,0,...]. - Gary W. Adamson, Jun 16 2011
E.g.f.: A(x)=1/Q(0); Q(k)=1-x/((3*k+1)-(x^2)*(3*k+1)/((x^2)-3*(3*k+2)*(k+1)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 25 2011
a(n) ~ n! * exp(Pi/(3*sqrt(3))) * (3*sqrt(3)/(2*Pi))^(n+1). - Vaclav Kotesovec, Jul 28 2013
E.g.f.: T(0)/(1-x), where T(k) = 1 - x^2*(k+1)^2/( x^2*(k+1)^2 - (1-x-x*k)*(1-2*x-x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 17 2013

Corrected and extended by Vladeta Jovovic, Apr 14 2001

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

Original entry on oeis.org

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

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

A022552 Numbers that are not the sum of 2 squares and a nonnegative cube.

Original entry on oeis.org

7, 15, 22, 23, 39, 55, 70, 71, 78, 87, 94, 103, 111, 115, 119, 120, 139, 167, 211, 254, 263, 267, 279, 286, 302, 311, 312, 331, 335, 342, 391, 403, 435, 454, 455, 470, 475, 499, 518, 559, 590, 595, 598, 622, 643, 659, 691, 695, 715, 727, 771

Offset: 1

N. J. A. Sloane, Will Jagy

nonn

There are 434 terms < 6 * 10^7 of which the largest is 5042631 ~= 5 * 10^6. Is this sequence finite? - David A. Corneth, Jun 23 2018
No more terms < 10^10. - Mauro Fiorentini, Jan 26 2019
For n = 1..434, a(n) + 2 is a term of A022551. Zhi-Wei Sun conjectures that Any n can be written as x^2 + y^2 + z^3 + 0(or 2). - XU Pingya, Jun 02 2020

R. J. Mathar, David A. Corneth, Table of n, a(n) for n = 1..434 (First 325 terms from R. J. Mathar, now terms < 6 * 10^7)
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
W. Jagy and I. Kaplansky, Sums of Squares, Cubes and Higher Powers, Experimental Mathematics, vol. 4 (1995) pp. 169-173.
Zhi-Wei Sun, New Conjectures on Representations of Integers (I), Nanjing Univ. J. Math. Biquarterly 34(2017), No.2, p. 110.
Index entries for sequences related to sums of squares

Complement of A022551.

isA022552 := proc(n)
    not isA022551(n) ;
end proc:
n := 1:
for c from 0 do
    if isA022552(c) then
        printf("%d %d\n",n,c);
        n := n+1 ;
    end if;
end do: # R. J. Mathar, Sep 02 2016

max = 10^6;
Table[x^2 + y^2 + z^3, {x, 0, Sqrt[max]}, {y, x, Sqrt[max - x^2]}, {z, 0, (max - x^2 - y^2)^(1/3)}] // Flatten // Union // Select[#, # <= max&]& // Complement[Range[max], #]& (* Jean-François Alcover, Mar 23 2020 *)

A117156 Number of permutations avoiding the consecutive pattern 1342.

Original entry on oeis.org

1, 1, 2, 6, 23, 110, 630, 4210, 32150, 276210, 2636720, 27687440, 317169270, 3936056080, 52603684760, 753241509900, 11504852242400, 186705357825800, 3208160592252000, 58188413286031600, 1110946958902609400

Offset: 0

Steven Finch, Apr 26 2006

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 1342. It is the same as the number of permutations which avoid 2431, 4213, 3124, 1432, 2341, 4123 or 3214.

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.

Alois P. Heinz, Table of n, a(n) for n = 0..200 (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
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]

Cf. A113228, A113229, A117158, A117226, A201692, A201693, A231166.

Cf. A052324.

a[n_]:=Coefficient[Series[1/(1-Integrate[Exp[ -t^3/6],{t,0,x}]),{x,0,30}],x^n]*n!
(* Second program: *)
m = 21; gf = 1/(1-Sum[If[Mod[k, 3] == 0, (-1)^Mod[k, 6]/(6^(k/3)*(k/3)!), 0]* (x^(k+1)/(k+1)), {k, 0, m}]);
CoefficientList[gf + O[x]^m, x]*Range[0, m-1]! (* Jean-François Alcover, May 11 2019 *)

a(n) ~ c * d^n * n!, where d = 1/r = 0.9546118344740519430556804334164431663486451742931588346372174751881329..., where r = 1.04754620033697244977759528695194261... is the root of the equation integral_{x,0,r} exp(-x^3/6) dx = 1, and c = 1.1561985648406071020520797542907648300587978482957199521032311960968187467... . - Vaclav Kotesovec, Aug 23 2014

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

A117226 Number of permutations of [n] avoiding the consecutive pattern 1243.

Original entry on oeis.org

1, 1, 2, 6, 23, 110, 630, 4204, 32054, 274914, 2619692, 27459344, 313990182, 3889585408, 51888955808, 741668212080, 11307669002720, 183174676857608, 3141820432768752, 56882461258572976, 1084056190235653304, 21692744773505849952, 454758269790599361968

Offset: 0

Steven Finch, Apr 26 2006

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 1243. It is the same as the number of permutations which avoid 3421, 4312 or 2134.

Alois P. Heinz, Table of n, a(n) for n = 0..200 (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, 2011.
Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125; see p. 120.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. Appl. Math. 36 (2006), 138-155.
Steven Finch, Pattern-Avoiding Permutations. [Archived copy]
Steven Finch, Pattern-Avoiding Permutations. [Cached copy, with permission]
Eric Weisstein's World of Mathematics, Pochhammer Symbol.
Wikipedia, Falling and rising factorials.

Cf. A113228, A113229, A117156, A117158, A176730, A201692, A201693, A231166.

Row m = 1 of A327722.

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

A[x_]:=Integrate[AiryAi[ -t],{t,0,x}]; B[x_]:=Integrate[AiryBi[ -t],{t,0,x}];
c=-3^(2/3)*Gamma[2/3]/2; d=-3^(1/6)*Gamma[2/3]/2;
a[n_]:=SeriesCoefficient[1/(c*A[x]+d*B[x]+1),{x,0,n}]*n!; Table[a[n],{n,0,10}] (* fixed by Vaclav Kotesovec, Aug 23 2014 *)
(* constant d: *) 1/x/.FindRoot[3^(2/3)*Gamma[2/3]/2 * Integrate[AiryAi[-t],{t,0,x}] + 3^(1/6)*Gamma[2/3]/2 * Integrate[AiryBi[-t],{t,0,x}]==1,{x,1},WorkingPrecision->50] (* Vaclav Kotesovec, Aug 23 2014 *)

a(n) ~ c * d^n * n!, where d = 0.952891423325053197208702817349165942637814..., c = 1.169657787464830219717093446929792145316... . - Vaclav Kotesovec, Aug 23 2014
From Petros Hadjicostas, Nov 01 2019: (Start)
E.g.f.: 1/W(z), where W(z) := 1 + Sum_{n >= 0} (-1)^(n+1)* z^(3*n+1)/(b(n)*(3*n+1)) with b(n) = A176730(n) = (3*n)!/(3^n*(1/3)_n). (Here (x)_n = x*(x + 1)*...*(x + n - 1) is the Pochhammer symbol, or rising factorial, which is denoted by (x)^n in some papers and books.) The function W(z) satisfies the o.d.e. W'''(z) + z*W'(z) = 0 with W(0) = 1, W'(0) = -1, and W''(0) = 0. [See Theorem 4.3 (Case 1243 with u = 0) in Elizalde and Noy (2003).]
a(n) = Sum_{m = 0..floor((n-1)/3)} (-3)^m * (1/3)_m * binomial(n, 3*m+1) * a(n-3*m-1) for n >= 1 with a(0) = 1. (End)

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

Original entry on oeis.org

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

A113227 Number of permutations of [n] avoiding the pattern 1-23-4.

Original entry on oeis.org

1, 1, 2, 6, 23, 105, 549, 3207, 20577, 143239, 1071704, 8555388, 72442465, 647479819, 6083742438, 59885558106, 615718710929, 6595077685263, 73424063891526, 847916751131054, 10138485386085013, 125310003360265231

Offset: 0

David Callan, Oct 19 2005

nonn

a(n) is the number of permutations on [n] that avoid the mixed consecutive/scattered pattern 1-23-4 (also number that avoid 4-32-1).
From David Callan, Jul 25 2008: (Start)
a(n) appears to also count vertical-marked parallelogram polyominoes of perimeter 2n+2; vertical-marked means that for each vertical line that splits the polyomino into two nonempty polyominoes one of the unit segments on the common boundary is marked.
....._
..._|.|
._|...|
|.._|
For example, the polyomino above, with n=5, has two such vertical lines, the left line giving only one choice for marking and the right line giving two choices. (End)

			12534 contains a scattered 1-2-3-4 pattern (1234 itself) but not a 1-23-4 because the 2 and 3 are not adjacent in the permutation.

Alois P. Heinz, Table of n, a(n) for n = 0..250
Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020.
A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for vincular patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini, and Simone Rinaldi, Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers, arXiv:1808.04114 [math.CO], 2018.
David Callan, A bijection to count (1-23-4)-avoiding permutations, arXiv:1008.2375 [math.CO], 2010.
Matteo Cervetti, A generating tree with a single label for permutations avoiding the vincular pattern 1-32-4, arXiv:2103.00246 [math.CO], 2021.
Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, Patterns in Inversion Sequences I, arXiv:1510.05434 [math.CO], 2015.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
Andrea Frosini, Veronica Guerrini, and Simone Rinaldi, Constrained Underdiagonal Paths and pattern Avoiding Permutations, Preprints:202411.1611 (2024). See pp. 9, 12.
Zhicong Lin and Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation (2020), Vol. 364, 124672.
Zhicong Lin and Shishuo Fu, On 120-avoiding inversion and ascent sequences, arXiv:2003.11813 [math.CO], 2020.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024. See p. 2.

v[n_, a_] := v[n, a] = Sum[StirlingS2[a-1, i-1]i^(n-a), {i, a}];
u[0]=u[1]=1; u[n_]/; n>=2 := u[n] = Sum[u[n, a], {a, n}];
u[1, 1]=u[2, 1]=u[2, 2]=1;
u[n_, a_]/; n>=3 && a==n := u[n-1];
u[n_, a_]/; n>=3 && a=3 && k==2 && a=3 && k>=3 && a=3 && k>=3 && a

In the recurrence coded in Mathematica below, v[n, a] is the number of permutations on [n] that avoid the 3-letter pattern 1-23 and start with a; u[n, a, m, k] is the number of 1-23-4-avoiding permutations on [n] that start with a, have n in position k and for which m is the minimum of the first k-1 entries. In the last sum, j is the number of entries lying strictly between a and n both in value and position.
From Gary W. Adamson, Jul 08 2011: (Start)
a(n) = the upper left term in M^n, M = the production matrix:
  1, 1
  1, 2, 1
  1, 2, 3, 1
  1, 2, 3, 4, 1
  1, 2, 3, 4, 5, 1
  ...
(End)
G.f.: 1+x/(U(0)-x) where U(k) = 1 - x*k - x/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 10 2012
Conjecture: a(n) = R(n-1, 0) for n > 0 with a(0) = 1 where R(n, q) = R(n-1, q+1) + Sum_{j=0..q} (j+1)*R(n-1, j) for n > 0, q >= 0 with R(0, q) = 1 for q >= 0. - Mikhail Kurkov, Jan 05 2024

A113228 a(n) is the number of permutations of [1..n] that avoid the consecutive pattern 1324 (equally, the permutations that avoid 4231).

Original entry on oeis.org

1, 1, 2, 6, 23, 110, 632, 4229, 32337, 278204, 2659223, 27959880, 320706444, 3985116699, 53328433923, 764610089967, 11693644958690, 190015358010114, 3269272324528547, 59373764638615449, 1135048629795612125, 22783668363316052016, 479111084084119883217

Offset: 0

David Callan, Oct 19 2005

nonn

			In 24135, the entries 2435 are in relative order 1324 but they do not occur consecutively and 24135 avoids the consecutive 1324 pattern.

Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n = 0..60 from Ray Chandler)
Andrew Baxter, Brian Nakamura, and Doron Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
Colin Defant, Noah Kravitz, and Nathan Williams, The Ungar Games, arXiv:2302.06552 [math.CO], 2023.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]

Cf. A113229, A117156, A117158, A117226, A201692, A201693, A231166.

Column k=0 of A264173.

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

Clear[u, v, w]; w[0]=1; w[1]=1;w[2]=2; w[n_]/;n>=3 := w[n] = Sum[w[n, a], {a, n}]; w[1, 1] = w[2, 1] = w[2, 2] = 1; w[n_, a_]/;n>=3 && 1<=a<=n := Sum[u[n, a, b], {b, a+1, n}] + v[n, a]; v[1, 1]=1; v[n_, a_]/;n>=2 && a==1 := 0; v[n_, a_]/;n>=2 && 2<=a<=n := wCumulative[n-1, a-1]; wCumulative[n_, k_]/;Not[1<=k<=n] := 0; wCumulative[n_, k_]/;1<=k<=n := wCumulative[n, k] = Sum[w[n, a], {a, k}]; u[n_, a_, b_]/;Not[1<=a=4 && 1<=a0 && j < t, -j, 0]], {j, 1, u}] + Sum[b[u+j-1, o-j, j], {j, 1, If[t<0, Min[-t-1, o], o]}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 19 2017, after Alois P. Heinz *)

In the recurrence coded in Mathematica below, w[n, a] = #1324-avoiding permutations on [n] with first entry a; u[n, a, b] is the number that start with an ascent a=2). The main sum for u[n, a, b] counts by length k of the longest initial increasing subsequence. The cases k=2, k=3, k>=4 are considered separately.

a(n) ~ c * d^n * n!, where d = 0.9558503134742499886507376383060906722796..., c = 1.15104449887019137479444895134035262624... . - Vaclav Kotesovec, Aug 23 2014

cp's OEIS Frontend

A049774 Number of permutations of n elements not containing the consecutive pattern 123.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A117158 Number of permutations avoiding the consecutive pattern 1234.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A022552 Numbers that are not the sum of 2 squares and a nonnegative cube.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A117156 Number of permutations avoiding the consecutive pattern 1342.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A061552 Number of 1324-avoiding permutations of length n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A117226 Number of permutations of [n] avoiding the consecutive pattern 1243.

Views

Author

Keywords

Comments

Links