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

%I #33 Mar 25 2020 15:58:35

%S 1,1,2,6,24,120,720,5040,40319,362863,3628550,39913170,478947480,

%T 6226179960,87164597520,1307440134000,20918580896069,355608034188517,

%U 6400803479701178,121612584595293870,2432198062707745560,51075033128533094520,1123625953230764250960

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

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

%H Alois P. Heinz, <a href="/A230051/b230051.txt">Table of n, a(n) for n = 0..450</a>

%H Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, Jean-Marie Maillard, <a href="https://arxiv.org/abs/2001.00393">Stieltjes moment sequences for pattern-avoiding permutations</a>, arXiv:2001.00393 [math.CO], 2020.

%H Mingjia Yang, Doron Zeilberger, <a href="https://arxiv.org/abs/1805.06077">Increasing Consecutive Patterns in Words</a>, arXiv:1805.06077 [math.CO], 2018.

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

%F 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

%F 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

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

%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1,

%p `if`(t<6, add(b(u+j-1, o-j, t+1), j=1..o), 0)+

%p add(b(u-j, o+j-1, 0), j=1..u))

%p end:

%p a:= n-> b(n, 0, 0):

%p seq(a(n), n=0..30);

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

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

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

%Y Column k=127 of A242784.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Oct 07 2013