A165525 Number of permutations of length n which avoid the patterns 4321 and 2143.

1, 2, 6, 22, 86, 333, 1235, 4339, 14443, 45770, 138988, 407134, 1157576, 3212157, 8740499, 23416169, 61973483, 162492830, 423077186, 1095978346, 2829227612, 7287399119, 18748151799, 48213813401, 124015241701, 319200003734, 822375826202, 2121215940232, 5478421803252, 14167748769035, 36687397002789, 95122416842861

Offset

1,2

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

M. H. Albert, M. D. Atkinson, Robert Brignall, The enumeration of three pattern classes using monotone grid classes, The Electronic Journal of Combinatorics, vol.19, no.3, (2012).

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.

Wikipedia, Permutation classes avoiding two patterns of length 4

Index entries for linear recurrences with constant coefficients, signature (18,-147,721,-2369,5505,-9305,11579,-10602,7049,-3304,1032,-192,16).

Formula

G.f.: x*p/((1-2*x)^4*(1-x)^7*(1-3*x+x^2)) where p = 1 - 16*x + 117*x^2 - 513*x^3 + 1499*x^4 - 3074*x^5 + 4530*x^6 - 4827*x^7 + 3691*x^8 - 1968*x^9 + 690*x^10 - 150*x^11 + 16*x^12. - Joerg Arndt, Aug 16 2012

Example

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

Maple

A165525 := proc(n)
    -84-29*n+n^3+263/90*n^2+1/45*n^6+19/18*n^4
    +2^n*(n^2/2-110*n/3+72+n^3/6)
    +8*A001519(n+2) ;
    %/4 ;
end proc:
seq(A165525(n), n=0..20) ; # R. J. Mathar, Aug 19 2022

Mathematica

CoefficientList[Series[(1 -16*x +117*x^2 -513*x^3 +1499*x^4 -3074*x^5 +4530*x^6 -4827*x^7 +3691*x^8 -1968*x^9 +690*x^10 -150*x^11 +16*x^12) / ((1-2*x)^4*(1-x)^7*(1-3*x+x^2)), {x, 0, 100}], x] (* Vincenzo Librandi, Aug 18 2012 *)

Prog

(PARI)
p=1-16*x+117*x^2-513*x^3+1499*x^4-3074*x^5+4530*x^6 -4827*x^7 +3691*x^8 -1968*x^9+690*x^10-150*x^11+16*x^12;
/* coefficient of x^5 is given as 3064 in Albert et al. reference */
gf=x*p/((1-2*x)^4*(1-x)^7*(1-3*x+x^2));
vA165525=Vec(gf + O('x^33))
/* Joerg Arndt, Aug 16 2012 */
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1 -16*x +117*x^2 -513*x^3 +1499*x^4 -3074*x^5 +4530*x^6 -4827*x^7 +3691*x^8 -1968*x^9 +690*x^10 -150*x^11 +16*x^12) / ((1-2*x)^4*(1-x)^7*( 1-3*x+x^2)))); // G. C. Greubel, Oct 21 2018

Crossrefs

Sequence in context: A116708 A116706 A165524 * A165526 A165527 A165528

Adjacent sequences: A165522 A165523 A165524 * A165526 A165527 A165528

Keyword

nonn,easy

Author

Vincent Vatter, Sep 21 2009

Extensions

More terms from Joerg Arndt, Aug 16 2012

Status

approved