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,3

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.

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

Example

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

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

Crossrefs

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

Column k=127 of A242784.

Sequence in context: A226439 A248840 A072131 * A067455 A033646 A319549

Adjacent sequences: A230048 A230049 A230050 * A230052 A230053 A230054

Keyword

nonn

Author

Alois P. Heinz, Oct 07 2013

Status

approved