A165536 - OEIS

A165536

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

1, 1, 2, 6, 22, 88, 365, 1540, 6568, 28269, 122752, 537708, 2375500, 10579400, 47469377, 214454528, 974870969, 4456401809, 20474068387, 94490731125, 437872264778, 2036621291113, 9504521228442, 44491624811512, 208853221780315, 982922903896966, 4636873292528606, 21922022211195195

COMMENTS

These permutations have an enumeration scheme of depth 5.

FORMULA

G.f.: (2 - 8*x + 2*x^2 + 17*x^3 - 15*x^4 + 4*x^5 - (2 - 10*x + 16*x^2 - 9*x^3 + 2*x^4)*sqrt(1 - 6*x + 5*x^2))/(2*x*(2 - x)^2*(1 - 2*x)*(1 - 3*x + x^2)). - 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[(2 - 8*x + 2*x^2 + 17*x^3 - 15*x^4 + 4*x^5 - (2 - 10*x + 16*x^2 - 9*x^3 + 2*x^4)*Sqrt[1 - 6*x + 5*x^2])/(2*x*(2 - x)^2*(1 - 2*x)*(1 - 3*x + x^2)), {x, 0, 30}], x] (* G. C. Greubel, Oct 22 2018 *)

PROG

(PARI) x='x+O('x^30); Vec((2 - 8*x + 2*x^2 + 17*x^3 - 15*x^4 + 4*x^5 - (2 - 10*x + 16*x^2 - 9*x^3 + 2*x^4)*sqrt(1 - 6*x + 5*x^2))/(2*x*(2 - x)^2*(1 - 2*x)*(1 - 3*x + x^2))) \\ G. C. Greubel, Oct 22 2018

(Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!((2 - 8*x + 2*x^2 + 17*x^3 - 15*x^4 + 4*x^5 - (2 - 10*x + 16*x^2 - 9*x^3 + 2*x^4)*Sqrt(1 - 6*x + 5*x^2))/(2*x*(2 - x)^2*(1 - 2*x)*(1 - 3*x + x^2)))); // G. C. Greubel, Oct 22 2018

EXTENSIONS

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