A165533 Number of permutations of length n which avoid the patterns 4213 and 1432.

1, 1, 2, 6, 22, 87, 352, 1434, 5861, 24019, 98677, 406291, 1676009, 6924618, 28646875, 118638038, 491765865, 2039944740, 8467475533, 35166107745, 146115418937, 607353499821, 2525443862594, 10504254304765, 43702642447260, 181865873468907, 756979080521743, 3151341504417932

Offset

0,3

Links

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

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.

Sam Miner, Enumeration of several two-by-four classes, arXiv:1610.01908 [math.CO], 2016.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Formula

G.f.: 1 + x*(1 - x)*(1 - 2*x)*(1 - 7*x + 17*x^2 - 16*x^3 + 4*x^4 + (1 - 3*x + 3*x^2)*sqrt(1 - 4*x))/(2 - 22*x + 96*x^2 - 220*x^3 + 282*x^4 - 196*x^5 + 64*x^6 - 8*x^7). - G. C. Greubel, Oct 22 2018

Example

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

Mathematica

CoefficientList[Series[1 + x*(1 - x)*(1 - 2*x)*(1 - 7*x + 17*x^2 - 16*x^3 + 4*x^4 + (1 - 3*x + 3*x^2)*Sqrt[1 - 4*x])/(2 - 22*x + 96*x^2 - 220*x^3 + 282*x^4 - 196*x^5 + 64*x^6 - 8*x^7), {x, 0, 50}], x] (* G. C. Greubel, Oct 22 2018 *)

Prog

(PARI) x='x+O('x^50); Vec(1 + x*(1-x)*(1-2*x)*(1-7*x+17*x^2-16*x^3+4*x^4 + (1-3*x+3*x^2)*sqrt(1-4*x))/(2-22*x+96*x^2-220*x^3+282*x^4-196*x^5 + 64*x^6-8*x^7)) \\ G. C. Greubel, Oct 22 2018
(Magma) m:=50; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!(1 + x*(1-x)*(1-2*x)*(1-7*x+17*x^2-16*x^3+4*x^4 +(1-3*x + 3*x^2)*Sqrt(1 - 4*x))/(2-22*x+96*x^2-220*x^3+282*x^4-196*x^5+64*x^6-8*x^7))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A165531 A150260 A165532 * A164651 A279566 A367413

Adjacent sequences: A165530 A165531 A165532 * A165534 A165535 A165536

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

a(0)=1 prepended by Alois P. Heinz, Dec 09 2015

a(13)-a(15) from Lars Blomberg, Apr 26 2018

Terms a(16) onward added by G. C. Greubel, Oct 22 2018

Status

approved