A117226 -id:A117226 - cp's OEIS frontend

A177478 Permutations avoiding the consecutive patterns 4312 and 4213.

1, 1, 2, 6, 22, 100, 540, 3388, 24248, 195048, 1742860, 17127880, 183617280, 2132433940, 26669752928, 357375269160, 5108084756320, 77574769941760, 1247401873186560, 21172559509803520, 378282904982091200, 7096584257305845120, 139471475802695196160

Offset: 0

Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

nonn

a(n) gives the number of permutations of [n] which avoid both the pattern 4312 and 4213 consecutively. Also the number avoiding the pairs {2134, 3124}, {1243, 1342}, or {3421, 2431} (by symmetry).

This can also be considered avoiding a partially ordered pattern: Suppose p

The Baxter-Nakamura-Zeilberger paper has an associated Maple package. See Links.

Alois P. Heinz, Table of n, a(n) for n = 0..120 (terms n = 1..40 from Ray Chandler)
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.

Cf. A117226, A117156.

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

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

a(n) ~ c * d^n * n!, where d = 0.89333294588184091624317413051..., c = 1.4839698712287023868073431417... . - Vaclav Kotesovec, Aug 24 2014

More terms, succinct title, additional comments, new references from Andrew Baxter, Jan 21 2011

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

A176730 Denominators of coefficients of a series, called f, related to Airy functions.

Original entry on oeis.org

1, 6, 180, 12960, 1710720, 359251200, 109930867200, 46170964224000, 25486372251648000, 17891433320656896000, 15565546988971499520000, 16437217620353903493120000, 20710894201645918401331200000, 30693545206839251070772838400000, 52854284846177190343870827724800000

Offset: 0

Wolfdieter Lang, Jul 14 2010

The numerators are always 1.
Let f(z) = Sum_{n>=0} (1/a(n))*z^(3*n) and g(z) = Sum_{n>=0}(1/b(n))*z^(3*n+1) with b(n) = A176731(n) build the two independent Airy functions Ai(z) = c[1]*f(z) - c[2]*g(z) and Bi(z) = sqrt(3)*(c[1]*f(z) + c[2]*g(z)) with c[1] = 1/(3^(2/3)*Gamma(2/3)), approximately 0.35502805388781723926 and c[2] = 1/(3^(1/3)*Gamma(1/3)), approximately 0.25881940379280679840.
If y = Sum_{n >= 0} x^(3*n)/a(n), then y'' = x*y. - Michael Somos, Jul 12 2019
Define W(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^(3*n+1)/(a(n)*(3*n+1)). Then W(z) satisfies the o.d.e. W'''(z) + z*W'(z) = 0 with W(0) = 1, W'(0) = -1, and W''(0) = 0. The function 1/W(z) is the e.g.f. of A117226, which is the number of permutations of [n] avoiding the consecutive pattern 1243. In other words, Sum_{n >= 0} A117226(n)*z^n/n! = 1/W(z). See Theorem 4.3 (Case 1243 with u = 0) in Elizalde and Noy (2003). - Petros Hadjicostas, Nov 01 2019
If y = Sum_{n >= 0} a(n)*x^(3*n+1)/(3*n+1)!, then y' = 1 + x^2*y. - Michael Somos, May 22 2022

			Rational f-coefficients: 1, 1/6, 1/180, 1/12960, 1/1710720, 1/359251200, 1/109930867200, 1/46170964224000, ....

G. C. Greubel, Table of n, a(n) for n = 0..200
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972, 10.4.2 - 5. [alternative scanned copy].
Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125; see p. 120.
Wolfdieter Lang, The first 20 terms of the f(z) and g(z) functions.
NIST's Digital Library of Mathematical Functions, Airy and Related Functions (Maclaurin Series) by Frank W. J. Olver.

Cf. A014402, A117226, A176731.

Column k=3 of A329070.

a := proc (n) option remember; if n = 0 then 1 else 3*n*(3*n-1)*a(n-1) end if; end proc: seq(a(n), n = 0..20); # Peter Bala, Dec 13 2021

a[ n_] := If[ n < 0, 0, 1 / (3^(2/3) Gamma[2/3] SeriesCoefficient[ AiryAi[x], {x, 0, 3*n}])]; (* Michael Somos, Oct 14 2011 *)
a[ n_] := If[ n < 0, 0, (3*n)! / Product[ k, {k, 1, 3*n - 2, 3}]]; (* Michael Somos, Oct 14 2011 *)

{a(n) = if( n<0, 0, (3*n)! / prod( k=0, n-1, 3*k + 1))}; /* Michael Somos, Oct 14 2011 */

a(n) = denominator((3^n)*risefac(1/3,n)/(3*n)!) with the rising factorials risefac(k,n) = Product_{j=0..n-1} (k+j) and risefac(k,0)=1.
From Peter Bala, Dec 13 2021: (Start)
a(n) = 3*n*(3*n - 1)*a(n-1) with a(0) = 1.
a(n) = (3*n + 1)!/(n!*3^n)*Sum_{k = 0..n} (-1)^k*binomial(n,k)/(3*k + 1).
a(n) = (3*n + 1)!/(n!*3^n)*hypergeom([-n, 1/3], [4/3], 1).
a(n) = (2*Pi*sqrt(3))/9 * 1/(3^n) * Gamma(3*n+2)/(Gamma(2/3)*Gamma(n+4/3)).
(End)
a(n) = (9^n*n!*(n-1/3)!)/(-1/3)!. - Peter Luschny, Dec 20 2021
a(n) = A014402(2*n). - Michael Somos, May 22 2022

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

A327722 Number T(m,n) of permutations of [n] avoiding the consecutive pattern 12...(m+1)(m+3)(m+2), where m, n >= 0; array read by ascending antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 2, 6, 16, 1, 1, 2, 6, 23, 63, 1, 1, 2, 6, 24, 110, 296, 1, 1, 2, 6, 24, 119, 630, 1623, 1, 1, 2, 6, 24, 120, 708, 4204, 10176, 1, 1, 2, 6, 24, 120, 719, 4914, 32054, 71793, 1, 1, 2, 6, 24, 120, 720, 5026, 38976, 274914, 562848

Offset: 0

Petros Hadjicostas, Nov 02 2019

By taking complements of permutations, we see that T(m,n) is also the number of permutations of [n] avoiding the consecutive pattern (m+3)(m+2)...(3)(1)(2). [The complement of permutation (c_1,c_2,...,c_n) of [n] is (n + 1 - c_1, n + 1 - c_2, ..., n + 1 - c_n).]
If we let S(n,k) = T(n-k, k) for n >= 0 and 0 <= k <= n, we get a triangular array shown in the Example section below.
Note that lim_{n -> oo} S(n,k) = k! = A000142(k) for k >= 0.
By using the ratio test and the Stirling approximation to the Gamma function, we may show that the radius of convergence of the power series W_m(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^((m+2)*n + 1)/(b(n, m+2)*((m + 2)*n + 1)) is infinity (for each m >= 0). Thus, the function W_m(z) (as defined by the power series) is entire.

			Array T(m, n) (with rows m >= 0 and columns n >= 0) begins as follows:
  1, 1, 2, 5, 16,  63, 296, 1623, 10176,  71793, ...
  1, 1, 2, 6, 23, 110, 630, 4204, 32054, 274914, ...
  1, 1, 2, 6, 24, 119, 708, 4914, 38976, 347765, ...
  1, 1, 2, 6, 24, 120, 719, 5026, 40152, 360864, ...
  1, 1, 2, 6, 24, 120, 720, 5039, 40304, 362664, ...
  1, 1, 2, 6, 24, 120, 720, 5040, 40319, 362862, ...
  ...
Triangular array S(n, k) = T(n-k, k) (with rows n >= 0 and columns k >= 0) begins as follows:
  1;
  1, 1;
  1, 1, 2;
  1, 1, 2, 5;
  1, 1, 2, 6, 16;
  1, 1, 2, 6, 23,  63;
  1, 1, 2, 6, 24, 110, 296;
  1, 1, 2, 6, 24, 119, 630, 1623;
  1, 1, 2, 6, 24, 120, 708, 4204, 10176;
  1, 1, 2, 6, 24, 120, 719, 4914, 32054,  71793;
  1, 1, 2, 6, 24, 120, 720, 5026, 38976, 274914, 562848;
  ...

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 Theorem 3.2 (p. 116) with u = 0 and m and a in the theorem equal to our m + 1.
Eric Weisstein's World of Mathematics, Pochhammer Symbol.
Wikipedia, Falling and rising factorials.

Rows include A111004 (m = 0, pattern 132), A117226 (m = 1, pattern 1243), A202213 (m = 2, pattern 12354).

Cf. A000142, A033312, A242569, A329070.

E.g.f for row m >= 0: 1/W_m(z), where W_m(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^((m+2)*n + 1)/(b(n, m+2)*((m + 2)*n + 1)) with b(n, k) = A329070(n, k) = (k*n)!/(k^n * (1/k)_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_m(z) satisfies the o.d.e. W_m^(m+2)(z) + z*W_m'(z) = 0 with W_m(0) = 1, W_m'(0) = -1, and W_m^(s)(0) = 0 for s = 2..(m + 1).
T(m, n) = Sum_{s = 0..floor((n - 1)/(m + 2))} (-(m + 2))^s * (1/(m + 2))_s * binomial(n, (m + 2)*s + 1) * T(m, n - (m + 2)*s - 1) for n >= 1 with T(m, 0) = 1.
T(m, n) = n! for 0 <= n <= m + 2.
T(m, m+3) = (m + 3)! - 1 = A000142(m + 3) - 1 = A033312(m + 3) for m >= 0. [In the set of permutations of [m + 3] there is exactly one permutation that contains the pattern 12...(m+1)(m+3)(m+2).]
Conjecture: T(m, m + 4) = A242569(m + 4) = (m + 4)! - 2*(m + 4) for m >= 0.
Limit_{m -> oo} T(m, n) = n! = A000142(n) for n >= 0.

Showing 1-10 of 11 results. Next

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

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

A177478 Permutations avoiding the consecutive patterns 4312 and 4213.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A176730 Denominators of coefficients of a series, called f, related to Airy functions.

Views