login
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.
2

%I #14 Aug 19 2022 11:46:25

%S 1,2,6,24,100,408,1631,6440,25263,98790,385803,1506156,5881057,

%T 22974406,89804910,351279584,1375035208,5386203792,21113167346,

%U 82816267480,325055630634,1276635121388,5016837177052,19725798613152,77601159558800

%N 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.

%H G. C. Greubel, <a href="/A141253/b141253.txt">Table of n, a(n) for n = 1..1000</a>

%H 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, <a href="https://ajc.maths.uq.edu.au/pdf/38/ajc_v38_p087.pdf">Cyclically closed pattern classes of permutations</a>, Australasian J. Combinatorics 38 (2007), 87-100.

%H R. Brignall, S. Huczynska, V. Vatter, <a href="https://doi.org/10.1016/j.jcta.2007.06.007">Simple permutations and algebraic generating functions</a>, J. Combinatorial Theory, Series A 115 (2008), 423-441.

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

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

%F a(n) ~ 2^(2*n+1)/(3*sqrt(Pi*n)). - _Vaclav Kotesovec_, Mar 20 2014

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

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

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

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

%o (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

%Y Cf. A141254.

%K nonn

%O 1,2

%A _Vincent Vatter_, Jun 17 2008