A277221 Number of permutations of length n which avoid the patterns 4123, 1324, and 3124.

1, 1, 2, 6, 21, 78, 297, 1143, 4419, 17119, 66386, 257621, 1000407, 3887666, 15119991, 58856167, 229312425, 894263633, 3490636794, 13637575699, 53327459013, 208703945330, 817447047177, 3204204114421, 12568821046236, 49336156718513, 193783005926727, 761604774463568

Offset

0,3

Comments

a(n) is also the number of permutations of length n which avoid the patterns 4123, 1324, and 1423.

Links

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

D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 [math.CO] (2017), Table 1 No 231.

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

Formula

G.f.: (1 - 3x) * (1 + sqrt(1 - 4x)) / (2 * (1 - 3x + x^2) * sqrt(1 - 4x)).

a(n) ~ 2^(2*n+1) / (5*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 07 2016

n*(n-3)*a(n) +(-7*n^2+23*n-12)*a(n-1) +(13*n^2-45*n+36)*a(n-2) -2*(2*n-3)*(n-2)*a(n-3)=0. - R. J. Mathar, Nov 09 2017

Mathematica

CoefficientList[Series[(1-3*x)*(1+Sqrt[1-4*x])/(2*(1-3*x+x^2)*Sqrt[1- 4*x]), {x, 0, 50}], x] (* G. C. Greubel, Apr 09 2017 *)

Prog

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

Crossrefs

Cf. A116830, A116832, A277222.

Sequence in context: A355152 A363813 A124292 * A360168 A129776 A129775

Adjacent sequences: A277218 A277219 A277220 * A277222 A277223 A277224

Keyword

nonn,easy

Author

Sam Miner, Oct 05 2016

Status

approved