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

A242784 Number A(n,k) of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of k, where 1=up and 0=down; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 4, 1, 1, 1, 1, 2, 5, 8, 1, 1, 1, 1, 2, 6, 17, 16, 1, 1, 1, 1, 2, 6, 21, 70, 32, 1, 1, 1, 1, 2, 6, 19, 90, 349, 64, 1, 1, 1, 1, 2, 6, 21, 70, 450, 2017, 128, 1, 1, 1, 1, 2, 6, 23, 90, 331, 2619, 13358, 256, 1, 1

Offset: 0

Alois P. Heinz, May 22 2014

			A(4,5) = 19 because there are 4! = 24 permutations of {1,2,3,4} and only 5 of them do not avoid the consecutive step pattern up, down, up given by the binary expansion of 5 = 101_2: (1,3,2,4), (1,4,2,3), (2,3,1,4), (2,4,1,3), (3,4,1,2).
Square array A(n,k) begins:
  1, 1,   1,     1,     1,     1,     1,     1,     1, ...
  1, 1,   1,     1,     1,     1,     1,     1,     1, ...
  1, 1,   2,     2,     2,     2,     2,     2,     2, ...
  1, 1,   4,     5,     6,     6,     6,     6,     6, ...
  1, 1,   8,    17,    21,    19,    21,    23,    24, ...
  1, 1,  16,    70,    90,    70,    90,   111,   116, ...
  1, 1,  32,   349,   450,   331,   450,   642,   672, ...
  1, 1,  64,  2017,  2619,  1863,  2619,  4326,  4536, ...
  1, 1, 128, 13358, 17334, 11637, 17334, 33333, 34944, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns give: 0, 1: A000012, 2: A011782, 3: A049774, 4, 6: A177479, 5: A177477, 7: A117158, 8, 14: A177518, 9: A177519, 10: A177520, 11, 13: A177521, 12: A177522, 15: A177523, 16, 30: A177524, 17: A177525, 18, 22: A177526, 19, 25: A177527, 20, 26: A177528, 21: A177529, 23, 29: A177530, 24, 28: A177531, 27: A177532, 31: A177533, 32, 62: A177534, 33: A177535, 34, 46: A177536, 35, 49: A177537, 36, 54: A177538, 37, 41: A177539, 38: A177540, 39, 57: A177541, 40, 58: A177542, 42: A177543, 43, 53: A177544, 44, 50: A177545, 45: A177546, 47, 61: A177547, 48, 60: A177548, 51: A177549, 52: A177550, 55, 59: A177551, 56: A177552, 63: A177553, 127: A230051, 255: A230231, 511: A230232, 1023: A230233, 2047: A254523.
Main diagonal gives A242785.
Cf. A242783, A335308.

A:= proc(n, k) option remember; local b, m, r, h;
      if k<2 then return 1 fi;
      m:= iquo(k, 2, 'r'); h:= 2^ilog2(k);
      b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
      `if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
      end; forget(b);
      b(n, 0, 0)
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);

Clear[A]; A[n_, k_] := A[n, k] = Module[{b, m, r, h}, If[k < 2, Return[1]]; {m, r} = QuotientRemainder[k, 2]; h = 2^Floor[Log[2, k]]; b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, If[t == m && r == 0, 0, Sum[b[u - j, o + j - 1, Mod[2*t, h]], {j, 1, u}]] + If[t == m && r == 1, 0, Sum[b[u + j - 1, o - j, Mod[2*t + 1, h]], {j, 1, o}]]]; b[n, 0, 0]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Sep 22 2014, translated from Maple *)

A177523 Number of permutations of 1..n avoiding adjacent step pattern up, up, up, up.

Original entry on oeis.org

1, 1, 2, 6, 24, 119, 709, 4928, 39144, 349776, 3472811, 37928331, 451891992, 5832672456, 81074690424, 1207441809209, 19181203110129, 323753459184738, 5785975294622694, 109149016813544376, 2167402030585724571, 45190632809497874161, 987099099863360190632

Offset: 0

R. H. Hardin, May 10 2010

nonn

a(n) is the number of permutations of length n that avoid the consecutive pattern 12345 (or equivalently 54321).

			E.g.f.: A(x) = 1 + x + 2*x^2/2! + 6*x^3/3! + 24*x^4/4! + 119*x^5/5! + 709*x^6/6! +...
where A(x) = 1/(1 - x + x^5/5! - x^6/6! + x^10/10! - x^11/11! + x^15/15! - x^16/16! + x^20/20! +...).

Alois P. Heinz, Table of n, a(n) for n = 0..400 (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
Ira M. Gessel, Yan Zhuang, Counting permutations by alternating descents , 2014. See displayed equation before Eq. (3), and set m=5. - _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. A080635, A049774, A117158, A177533.

Column k=15 of A242784.

Table[n!*SeriesCoefficient[1/(Sum[x^(5*k)/(5*k)!-x^(5*k+1)/(5*k+1)!,{k,0,n}]),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Dec 11 2013 *)
FullSimplify[CoefficientList[Series[10*E^((1+Sqrt[5])*x/4) / ((5+Sqrt[5]) * Cos[Sqrt[(5-Sqrt[5])/2]*x/2] + (5-Sqrt[5]) * E^(Sqrt[5]*x/2) * Cos[Sqrt[(5+Sqrt[5])/2]*x/2] - Sqrt[2*(5-Sqrt[5])] * Sin[Sqrt[(5-Sqrt[5])/2]*x/2] - Sqrt[2*(5+Sqrt[5])] * E^(Sqrt[5]*x/2) * Sin[Sqrt[(5+Sqrt[5])/2]*x/2]),{x,0,20}],x]*Range[0,20]!] (* Vaclav Kotesovec, Aug 29 2014 *)

{a(n)=n!*polcoeff(1/sum(m=0, n\5+1, x^(5*m)/(5*m)!-x^(5*m+1)/(5*m+1)!+x^2*O(x^n)), n)}

E.g.f.: 1/( Sum_{n>=0} x^(5*n)/(5*n)! - x^(5*n+1)/(5*n+1)! ).
a(n)/n! ~ c * (1/r)^n, where r = 1.007187547786015395418998654... is the root of the equation Sum_{n>=0} (r^(5*n)/(5*n)! - r^(5*n+1)/(5*n+1)!) = 0, c = 1.02806793756750152.... - Vaclav Kotesovec, Dec 11 2013
Equivalently, r = 1.00718754778601539541899865400272701484... is the root of the equation (5+sqrt(5)) * cos(sqrt((5-sqrt(5))/2)*r/2) + (5-sqrt(5)) * exp(sqrt(5)*r/2) * cos(sqrt((5+sqrt(5))/2)*r/2) - sqrt(2*(5-sqrt(5))) * sin(sqrt((5-sqrt(5))/2)*r/2) - sqrt(2*(5+sqrt(5))) * exp(sqrt(5)*r/2) * sin(sqrt((5+sqrt(5))/2)*r/2) = 0. - Vaclav Kotesovec, Aug 29 2014
E.g.f.: 10*exp((1+sqrt(5))*x/4) / ((5+sqrt(5)) * cos(sqrt((5-sqrt(5))/2)*x/2) + (5-sqrt(5)) * exp(sqrt(5)*x/2) * cos(sqrt((5+sqrt(5))/2)*x/2) - sqrt(2*(5-sqrt(5))) * sin(sqrt((5-sqrt(5))/2)*x/2) - sqrt(2*(5+sqrt(5))) * exp(sqrt(5)*x/2) * sin(sqrt((5+sqrt(5))/2)*x/2)). - Vaclav Kotesovec, Aug 29 2014
In closed form, c = 5*exp((1+sqrt(5))*r/4) / (r*((5 + sqrt(5)) * cos(sqrt((5 - sqrt(5))/2)*r/2) + (5 - sqrt(5)) * exp(sqrt(5)*r/2) * cos(sqrt((5 + sqrt(5))/2)*r/2))) = 1.0280679375675015201596831656779442465978511664638... . Vaclav Kotesovec, Feb 01 2015

More terms from Ray Chandler, Dec 06 2011

a(0)=1 prepended by Alois P. Heinz, Jan 13 2015

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

A022558 Number of permutations of length n avoiding the pattern 1342.

Original entry on oeis.org

1, 1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, 3475090, 22214707, 144640291, 956560748, 6411521056, 43478151737, 297864793993, 2059159989914, 14350039389022, 100726680316559, 711630547589023, 5057282786190872, 36132861123763276, 259423620328055093

Offset: 0

Miklos Bona

Differs from A117156 which counts permutations avoiding the *consecutive* pattern 1342. - Ray Chandler, Dec 06 2011
Also, number of permutation of length n avoiding the pattern 3142 (see Stankova (1994) below). - Alexander Burstein, Aug 09 2013
Conjecture: a(n) is the number of permutations of length n simultaneously avoiding patterns 2143 and 415263. - Alexander Burstein, Mar 21 2019

			a(4) = 23 because obviously all permutations of length 4 with the exception of 1342 avoid 1342.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 768, Th. 12.1.14.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.48.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
Miklos Bona, Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps, arXiv:math/9702223 [math.CO], 1997.
Miklos Bona, Exact enumeration of 1342-avoiding permutations; A close link with labeled trees and planar maps, J. Combinatorial Theory, A80 (1997), 257-272.
Alexander Burstein and Jay Pantone, Two examples of unbalanced Wilf-equivalence, J. Combin. 6 (2015), no. 1-2, 55-67.
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. R. Conway and A. J. Guttmann, On 1324-avoiding permutations, Adv. Appl. Math. 64 (2015), 50-69.
A. L. L. Gao, S. Kitaev, and P. B. Zhang. On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint arXiv:1410.2657 [math.CO], 2014.
Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
W. Mlotkowski, K. A. Penson, A Fuss-type family of positive definite sequences, arXiv:1507.07312 (2015), eq. (36).
Z. E. Stankova, Forbidden subsequences, Discrete Math., 132 (1994), no. 1-3, 291-316.
Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001. See Fig. 11.

Essentially the same as A004040.
Cf. A117158.
A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).

a := proc (n) options operator, arrow: (1/2)*(-1)^(n-1)*(7*n^2-3*n-2)+3*(sum((-1)^(n-i)*2^(i+1)*factorial(2*i-4)*binomial(n-i+2, 2)/(factorial(i)*factorial(i-2)), i = 2 .. n)) end proc: seq(a(n), n = 0 .. 30); # Emeric Deutsch, Oct 15 2014

Table[SeriesCoefficient[32*x/(1+20*x-8*x^2-(1-8*x)^(3/2)),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 07 2012 *)
Table[1/2*(-1)^(n-1) * (-2-3*n+7*n^2) + 1/4*(-1)^n * (1+n) * (-2-13*n+(n+2) * Hypergeometric2F1[-3/2,-n,-2-n,-8]),{n,0,20}] (* Vaclav Kotesovec, Aug 24 2014 *)

x='x+O('x^66); Vec( 32*x/(1+20*x-8*x^2-(1-8*x)^(3/2)) ) \\ Joerg Arndt, May 04 2013

a(n) = (7*n^2-3*n-2)/2 * (-1)^(n-1) + 3*Sum_{i=2..n} 2^(i+1) * (2*i-4)!/(i!*(i-2)!) * binomial(n-i+2, 2) * (-1)^(n-i).
G.f.: 32*x/(1 + 20*x - 8*x^2 - (1 - 8*x)^(3/2)). - Emeric Deutsch, Mar 13 2004
Recurrence: n*a(n) = (7*n-22)*a(n-1) + 4*(2*n-1)*a(n-2). - Vaclav Kotesovec, Oct 07 2012
a(n) ~ 2^(3*n+6)/(243*sqrt(Pi)*n^(5/2)). - Vaclav Kotesovec, Oct 07 2012

Minor edits by Vaclav Kotesovec, Aug 24 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)

A177533 Number of permutations of 1..n avoiding adjacent step pattern up, up, up, up, up.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 719, 5027, 40168, 361080, 3606480, 39623760, 474915803, 6166512899, 86227808578, 1291868401830, 20645144452320, 350547210173280, 6302294420371031, 119600213982762899, 2389140113204434900, 50111866901959213980, 1101140993932295832120

Offset: 0

R. H. Hardin, May 10 2010

nonn

a(n) is the number of permutations of length n that avoid the consecutive pattern 123456 (or equivalently 654321).

Alois P. Heinz, Table of n, a(n) for n = 0..450 (terms n = 1..30 from Ray Chandler)
R. E. L. Aldred, M. D. Atkinson, D. J. McCaughan, Avoiding consecutive patterns in permutations Adv. in Appl. Math., 45(3), 449-461, 2010.
A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
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=6. - _N. J. A. Sloane_, Aug 11 2014
Mingjia Yang, Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.

Cf. A049774, A117158, A177523.

Column k=31 of A242784.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<4, 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

Table[n!*SeriesCoefficient[1/(Sum[x^(6*k)/(6*k)!-x^(6*k+1)/(6*k+1)!,{k,0,n}]),{x,0,n}],{n,1,20}] (* Vaclav Kotesovec, Dec 11 2013 *)
Rest[CoefficientList[Series[3/(E^(x/2) * Cos[x*Sqrt[3]/2+Pi/3] + Sqrt[3] * E^(-x/2) * Cos[x*Sqrt[3]/2+Pi/6] + E^(-x)),{x,0,20}],x] * Range[0,20]!] (* Vaclav Kotesovec, Aug 23 2014 *)

a(n)/n! ~ 1.005827831279392186... * (1/r)^n, where r = 1.0011988273240623031887... is the root of the equation Sum_{n>=0} (r^(6*n)/(6*n)! - r^(6*n+1)/(6*n+1)!) = 0. - Vaclav Kotesovec, Dec 11 2013
Equivalently, a(n)/n! ~ c * (1/r)^n, where r = 1.00119882732406230318870210972855430833421618931012450844128... is the root of the equation 2 + exp(r/2) * (3 + exp(r)) * cos(sqrt(3)*r/2) = 2 * sqrt(3) * exp(r) * cosh(r/2) * sin(sqrt(3)*r/2), c = sqrt(3) / (2 * r * cosh(r/2) * sin(sqrt(3)*r/2)) = 1.0058278312793921866941324506580803251270892126827302878865925027445... . - Vaclav Kotesovec, Aug 23 2014
E.g.f. (Aldred, Atkinson, McCaughan, 2010): 3/(exp(x/2) * cos(x*sqrt(3)/2+Pi/3) + sqrt(3) * exp(-x/2) * cos(x*sqrt(3)/2+Pi/6) + exp(-x)). - Vaclav Kotesovec, Aug 23 2014

More terms from Ray Chandler, Dec 06 2011
Minor edits by Vaclav Kotesovec, Aug 29 2014
a(0)=1 prepended by Alois P. Heinz, Aug 08 2018

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

A242784 Number A(n,k) of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of k, where 1=up and 0=down; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A177523 Number of permutations of 1..n avoiding adjacent step pattern up, up, up, up.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A117156 Number of permutations avoiding the consecutive pattern 1342.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A022558 Number of permutations of length n avoiding the pattern 1342.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A177533 Number of permutations of 1..n avoiding adjacent step pattern up, up, up, up, up.

Views

Author

Keywords

Comments