A165532 Number of permutations of length n which avoid the patterns 4231 and 3214.

1, 1, 2, 6, 22, 87, 352, 1428, 5768, 23156, 92416, 367007, 1451780, 5725959, 22535868, 88566290, 347742688, 1364637732, 5353992916, 21005649217, 82425637860, 323523434437, 1270281675368, 4989615315114, 19607400037358, 77084254889327, 303184014866196, 1193001145648675

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.: (2 - 13*x + 26*x^2 - 17*x^3 + 4*x^4 - x*(1 - 2*x - x^2)*sqrt(1 - 4*x))/(2*sqrt(1 - 4*x)*(1 - 3*x + x^2)^2). - G. C. Greubel, Oct 22 2018

a(n) ~ 2^(2*n + 4) / (25*sqrt(Pi*n)). - Vaclav Kotesovec, Jul 07 2024

Example

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

Mathematica

CoefficientList[Series[(2 - 13*x + 26*x^2 - 17*x^3 + 4*x^4 - x*(1 - 2*x - x^2)*Sqrt[1 - 4*x])/(2*Sqrt[1 - 4*x]*(1 - 3*x + x^2)^2), {x, 0, 50}], x] (* G. C. Greubel, Oct 22 2018 *)

Prog

(PARI) x='x+O('x^50); Vec((2 - 13*x + 26*x^2 - 17*x^3 + 4*x^4 - x*(1 - 2*x - x^2)*sqrt(1 - 4*x))/(2*sqrt(1 - 4*x)*(1 - 3*x + x^2)^2)) \\ G. C. Greubel, Oct 22 2018
(Magma) m:=50; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!((2 - 13*x + 26*x^2 - 17*x^3 + 4*x^4 - x*(1 - 2*x - x^2)*Sqrt(1 - 4*x))/( 2*Sqrt(1 - 4*x)*(1 - 3*x + x^2)^2))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A165531 A374542 A150260 * A165533 A164651 A279566

Adjacent sequences: A165529 A165530 A165531 * A165533 A165534 A165535

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