A230051 Number of permutations of [n] avoiding adjacent step pattern {up}^7.

1, 1, 2, 6, 24, 120, 720, 5040, 40319, 362863, 3628550, 39913170, 478947480, 6226179960, 87164597520, 1307440134000, 20918580896069, 355608034188517, 6400803479701178, 121612584595293870, 2432198062707745560, 51075033128533094520, 1123625953230764250960

Offset: 0

Author

Alois P. Heinz, Oct 07 2013

Keywords

• nonn

Examples

			a(8) = 40319 = 8!-1: only permutation 12345678 does not avoid {up}^7.
		

References

• R. E. L. Aldred, M. D. Atkinson, D. J. McCaughan, Avoiding consecutive patterns in permutations. Adv. in Appl. Math., 45(3), 449-461, 2010.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450
• Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
• Mingjia Yang, Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.

Crossrefs

Cf. A049774, A117158, A177523, A177533, A177553.

Column k=127 of A242784.

Programs

Maple

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

Mathematica

nn=20;r=7;a=Apply[Plus,Table[Normal[Series[y x^(r+1)/(1-Sum[y x^i,{i,1,r}]),{x,0,nn}]][[n]]/(n+r)!,{n,1,nn-r}]]/.y->-1;Range[0,nn]! CoefficientList[Series[1/(1-x-a),{x,0,nn}],x] (* Geoffrey Critzer, Feb 25 2014 *)
CoefficientList[Series[4/(E^(-x) + Cos[x] - Sin[x] + 2*Cos[x/Sqrt[2]] * Cosh[x/Sqrt[2]] - Sqrt[2] * Cos[x/Sqrt[2]] * Sinh[x/Sqrt[2]] - Sqrt[2] * Cosh[x/Sqrt[2]] * Sin[x/Sqrt[2]]),{x,0,20}],x] * Range[0,20]! (* Vaclav Kotesovec, Aug 23 2014 *)

Formula

E.g.f.: 1 / Sum_{n>=0} (8*n+1-x)*x^(8*n)/(8*n+1)!.

E.g.f. (Aldred, Atkinson, McCaughan, 2010): 4/(exp(-x) + cos(x) - sin(x) + 2*cos(x/sqrt(2))*cosh(x/sqrt(2)) - sqrt(2)*cos(x/sqrt(2))*sinh(x/sqrt(2)) - sqrt(2)*cosh(x/sqrt(2))*sin(x/sqrt(2))). - Vaclav Kotesovec, Aug 23 2014

a(n)/n! ~ c / r^n, where r = 1.0000220496837836995332841475679738951237308817759821845322... is the root of the equation exp(-r) + cos(r) - sin(r) + 2*cos(r/sqrt(2)) * cosh(r/sqrt(2)) - sqrt(2)*cos(r/sqrt(2)) * sinh(r/sqrt(2)) - sqrt(2) * cosh(r/sqrt(2)) * sin(r/sqrt(2)) = 0, c = 2*sqrt(2) / (r*sqrt(2 + cosh(sqrt(2)*r) - cos(2*r) + 2*cosh(r/sqrt(2)) * (2*sqrt(2)*sin(r) * sin(r/sqrt(2)) - cos(sqrt(2)*r) * cosh(r/sqrt(2))))) = 1.0001516144914746839400607922657094772985420791612537... . - Vaclav Kotesovec, Aug 23 2014, updated Feb 01 2015