A113228 -id:A113228 - 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

A264173 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive pattern 1324; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2-1)), read by rows.

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 110, 10, 632, 86, 2, 4229, 782, 29, 32337, 7571, 407, 5, 278204, 78726, 5856, 94, 2659223, 882997, 84351, 2215, 14, 27959880, 10657118, 1251246, 48234, 322, 320706444, 137977980, 19318314, 984498, 14322, 42, 3985116699, 1910131680, 311306106

Offset: 0

Alois P. Heinz, Nov 06 2015

Pattern 4231 gives the same triangle.

			T(4,1) = 1: 1324.
T(6,2) = 2: 132546, 142536.
T(8,3) = 5: 13254768, 13264758, 14253768, 14263758, 15263748.
T(10,4) = 14: 132547698(10), 132548697(10), 132647598(10), 132648597(10), 132748596(10), 142537698(10), 142538697(10), 142637598(10), 142638597(10), 142738596(10), 152637498(10), 152638497(10), 152738496(10), 162738495(10).
Triangle T(n,k) begins:
00 :        1;
01 :        1;
02 :        2;
03 :        6;
04 :       23,      1;
05 :      110,     10;
06 :      632,     86,     2;
07 :     4229,    782,    29;
08 :    32337,   7571,   407,    5;
09 :   278204,  78726,  5856,   94;
10 :  2659223, 882997, 84351, 2215, 14;

Alois P. Heinz, Rows n = 0..120, flattened

Columns k=0-10 give: A113228, A264174, A264175, A264176, A264177, A264178, A264179, A264180, A264181, A264182, A264183.
Row sums give A000142.
T(2n+2,n) gives A000108(n) for n>0.
Cf. A004526, A061206, A264319 (pattern 3412).

b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
      add(b(u-j, o+j-1, `if`(t>0 and j (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..14);

b[u_, o_, t_] := b[u, o, t] = Expand[If[u + o == 0, 1, Sum[b[u - j, o + j - 1, If[t > 0 && j < t, -j, 0]], {j, 1, u}] + Sum[b[u + j - 1, o - j, j] * If[t < 0 && -j <= t, x, 1], {j, 1, o}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, 0, 0]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Apr 30 2017, translated from Maple *)

Sum_{k>0} k * T(n,k) = ceiling((n-3)*n!/4!) = A061206(n-3) (for n>3).

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)

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

A201692 Number of permutations that avoid the consecutive pattern 1423.

Original entry on oeis.org

1, 1, 2, 6, 23, 110, 631, 4218, 32221, 276896, 2643883, 27768955, 318174363, 3949415431, 52794067318, 756137263377, 11551672922816, 187507250145806, 3222662529113641, 58464560588277289, 1116469710152742025, 22386721651323946628, 470259350616967829363

Offset: 0

N. J. A. Sloane, Dec 03 2011

Alois P. Heinz, Table of n, a(n) for n = 0..250 (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, 2011

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

c := proc(n,l)
    if n = 1 then
        if l = 0 then
            1;
        else
            0;
        end if;
    elif n= 2 or n = 3 then
        0;
    else
        a := 0 ;
        for k from 1 to (n-2)/2 do
            a := a+procname(n-2*k-1,l-k)*binomial(n-k-2,k) ;
        end do:
        a ;
    end if;
end proc:
A201693 := proc(nmax)
    g := 1-t ;
    for n from 2 to nmax do
        for l from 0 to n/2 do
            g := g-c(n,l)*t^n*(-1)^l/n! ;
        end do:
    end do:
    taylor(1/g,t=0,nmax) ;
end proc:
nmax := 25 ;
egf := A201693(nmax) ;
for n from 0 to nmax-1 do
    printf("%d,",coeftayl(egf,t=0,n)*n!) ;
end do: # R. J. Mathar, Dec 04 2011
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, `if`(0 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[0Jean-François Alcover, Mar 18 2014, after Alois P. Heinz *)

The reference gives an e.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.95482605094987833345080179991528996596888600981..., c = 1.1567436851576902067739566662625378535625602... . - Vaclav Kotesovec, Sep 11 2014

Definition corrected by N. J. A. Sloane, Mar 15 2015

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

A231166 Number of permutations of [n] avoiding simultaneously consecutive patterns 1243, 1342, and 1324.

Original entry on oeis.org

1, 1, 2, 6, 21, 91, 467, 2755, 18523, 139740, 1169616, 10763807, 108028386, 1174391384, 13748315494, 172439034531, 2306986699190, 32792999417180, 493559520202535, 7841127918788283, 131127477517244419, 2302491655047553206, 42355105188617740229

Offset: 0

Alois P. Heinz, Nov 04 2013

nonn

			a(4) = 24 - 3 = 21 because 1243, 1342, 1324 are avoided.

Alois P. Heinz, Table of n, a(n) for n = 0..70
A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes, 2011.
S. Kitaev and T. Mansour, On multi-avoidance of generalized patterns, arXiv:math/0209340 [math.CO], 2002.

Cf. A113228, A117156, A117226.

b:= proc(u, o, s, t) option remember; `if`(u+o=0, 1,
       add(b(u-j, o+j-1, `if`(t>0, t, 0), `if`(t>0, -j, 0)),
           j=`if`(s>0 and t>0,s+t-1,1)..u)+
       add(b(u+j-1, o-j, `if`(t>0, t, 0), +j),
           j=1..`if`(s>0 and t<0 and -t b(n, 0$3):
seq(a(n), n=0..25);

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

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

A264173 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive pattern 1324; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2-1)), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

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

A201692 Number of permutations that avoid the consecutive pattern 1423.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A201693 Number of permutations that avoid the consecutive pattern 2413.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A231166 Number of permutations of [n] avoiding simultaneously consecutive patterns 1243, 1342, and 1324.

Views