A141253 Number of permutations that lie in the cyclic closure of Av(132)--i.e., at least one cyclic rotation of the permutation avoids the pattern 132.

1, 2, 6, 24, 100, 408, 1631, 6440, 25263, 98790, 385803, 1506156, 5881057, 22974406, 89804910, 351279584, 1375035208, 5386203792, 21113167346, 82816267480, 325055630634, 1276635121388, 5016837177052, 19725798613152, 77601159558800

Offset

1,2

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000

M. D. Atkinson, M. H. Albert, R. E. L. Aldred, H. P. van Ditmarsch, C. C. Handley, D. A. Holton, D. J. McCaughan, C. Monteith, Cyclically closed pattern classes of permutations, Australasian J. Combinatorics 38 (2007), 87-100.

R. Brignall, S. Huczynska, V. Vatter, Simple permutations and algebraic generating functions, J. Combinatorial Theory, Series A 115 (2008), 423-441.

Formula

G.f.: (1-4*x+4*x^2-4*x^3-(1-2*x)*sqrt(1-4*x))/(2*x*(1-x)^2*sqrt(1-4*x)).

a(n) = n(C(n) - C(n-1) - ... - C(1)), where C(n) denotes the n-th Catalan number.

a(n) ~ 2^(2*n+1)/(3*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 20 2014

D-finite with recurrence -3*(n+1)*(n-3)*a(n) +n*(17*n-43)*a(n-1) +2*(-11*n^2+35*n-30)*a(n-2) +4*(n-2)*(2*n-5)*a(n-3)=0. - R. J. Mathar, Aug 19 2022

D-finite with recurrence (n-1)*(n-3)*(n+1)*a(n) -n*(5*n^2-16*n+9)*a(n-1) +2*n*(n-1)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Aug 19 2022

Example

a(5)=100 because 100 permutations of length 5 have at least one cyclic rotation which avoids 132.

Mathematica

Rest[CoefficientList[Series[(1-4*x+4*x^2-4*x^3-(1-2*x)*Sqrt[1-4*x]) / (2*x*(1-x)^2*Sqrt[1-4*x]), {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 20 2014 *)

Prog

(PARI) x='x+O('x^50); Vec((1-4*x+4*x^2-4*x^3-(1-2*x)*sqrt(1-4*x))/(2*x*(1-x)^2*sqrt(1-4*x))) \\ G. C. Greubel, Mar 21 2017

Crossrefs

Cf. A141254.

Sequence in context: A060725 A150299 A094012 * A306672 A324063 A078486

Adjacent sequences: A141250 A141251 A141252 * A141254 A141255 A141256

Keyword

nonn

Author

Vincent Vatter, Jun 17 2008

Status

approved