A201692 -id:A201692 - cp's OEIS frontend

A117158 Number of permutations avoiding the consecutive pattern 1234.

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

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

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)

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

A113229 Number of permutations avoiding the consecutive pattern 3412.

Original entry on oeis.org

1, 1, 2, 6, 23, 110, 631, 4223, 32301, 277962, 2657797, 27954521, 320752991, 3987045780, 53372351265, 765499019221, 11711207065229, 190365226548070, 3276401870322033, 59523410471007913, 1138295039078030599, 22856576346825690128, 480807130959249565541

Offset: 0

David Callan, Oct 19 2005

nonn

a(n) is the number of permutations on [n] that avoid the consecutive pattern 3412 (also number that avoid 2143).

			The 5! - a(5) = 10 permutations on [5] not counted by a(5) are 14523, 24513, 34125, 34512, 35124, 43512, 45123, 45132, 45231, 53412.

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
V. Dotsenko and A. Khoroshkin, Shuffle algebras, homology, and consecutive pattern avoidance, arXiv preprint arXiv:1109.2690 [math.CO], 2011.
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.
S. Elizalde and M. 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. A113228, A117156, A117158, A117226, A201692, A201693.

Column k=0 of A264319.

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

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

The Dotsenko et al. reference gives a g.f. There is an associated triangle of numbers c_{n,l} that should be added to the OEIS if it is not already present.

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

A201693 Number of permutations that avoid the consecutive pattern 2413.

Original entry on oeis.org

1, 1, 2, 6, 23, 110, 632, 4237, 32465, 279828, 2679950, 28232972, 324470844, 4039771856, 54165468774, 778128659247, 11923645252411, 194131328012012, 3346615262190736, 60897160676005110, 1166446154857250412, 23459656378909613446, 494290181112325561351

Offset: 0

N. J. A. Sloane, Dec 03 2011

Alois P. Heinz, Table of n, a(n) for n = 0..140 (first 61 terms from Ray Chandler)
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
V. Dotsenko and A. Khoroshkin, Shuffle algebras, homology, and consecutive pattern avoidance, arXiv preprint arXiv:1109.2690, 2011

Cf. A113228, A113229, A117156, A117158, A117226, A201692.

The reference gives a g.f. There is an associated triangle of numbers c_{n,l} that should be added to the OEIS if it is not already present.

More terms from Ray Chandler, Dec 06 2011

cp's OEIS Frontend

A117158 Number of permutations avoiding the consecutive pattern 1234.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A117156 Number of permutations avoiding the consecutive pattern 1342.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A113229 Number of permutations avoiding the consecutive pattern 3412.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A201693 Number of permutations that avoid the consecutive pattern 2413.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions