A165540 Number of permutations of length n which avoid the patterns 1234 and 2341.

1, 2, 6, 22, 89, 376, 1611, 6901, 29375, 123996, 518971, 2155145, 8888348, 36442184, 148669894, 603984658, 2445184835, 9870338447, 39746337616, 159728191141, 640811439917, 2567220813272, 10272592695691, 41064215020977, 164014588869574, 654627778362521, 2611244306191009, 10410752330836178, 41488934932279847, 165282459721996836, 658248561748273483

Offset

1,2

Comments

These permutations have an enumeration scheme of depth 6.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

David Bevan, The permutation classes Av(1234,2341) and Av(1243,2314), arXiv:1407.0570 [math.CO], 2014.

Darla Kremer, and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

V. Vatter, Enumeration schemes for restricted permutations, Combin., Prob. and Comput. 17 (2008), 137-159.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Formula

G.f.: ((2-10*z+9*z^2+7*z^3-4*z^4)*sqrt(1-4*z) - (2-16*z+41*z^2-39*z^3+12*z^4)) / ((1-4*z)*(1-3*z+z^2)*((1-z)*sqrt(1-4*z) + (1-3*z))). - David Bevan, Jun 23 2014

a(n) ~ 2^(2*n+1)/sqrt(Pi*n). - Vaclav Kotesovec, Aug 23 2014

Conjecture: +(14681*n+187954)*(n+3) *a(n) +(14681*n^2-2696783*n-4897218) *a(n-1) +(-888761*n^2+12771539*n+5490342) *a(n-2) +2*(1635223*n^2-14850835*n+13281012) *a(n-3) +2*(-1908503*n^2+15402653*n-25889820) *a(n-4) +156*(2*n-7)*(3301*n-14374) *a(n-5)=0. - R. J. Mathar, Jun 14 2016

Example

There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

Mathematica

Rest[CoefficientList[ Series[ ((2-10z+9z^2+7z^3-4z^4) Sqrt[1-4z] -(2-16z+41z^2-39z^3+12z^4)) / ((1-4z) (1-3z+z^2) ((1-z) Sqrt[1-4z] +(1-3z))), {z, 0, 40}], z]] (* David Bevan, Jun 23 2014 *)

Crossrefs

Sequence in context: A165522 A150267 A271388 * A363809 A111053 A165541

Adjacent sequences: A165537 A165538 A165539 * A165541 A165542 A165543

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

More terms from David Bevan, Jun 23 2014

Status

approved