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

1, 1, 2, 6, 22, 87, 348, 1374, 5335, 20462, 77988, 296787, 1130969, 4321239, 16559467, 63633036, 245113705, 946140207, 3658715938, 14170931497, 54966429252, 213487762758, 830195102515, 3232062132146, 12596093756080, 49137833964185, 191862494482159

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

M. D. Atkinson, Bruce E. Sagan and Vincent Vatter, Counting (3+1)-avoiding permutations, European J. Combin. 33 (2012), 49--61. Also arXiv preprint, arXiv:1102.5568 [math.CO], 2011.

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.

Formula

G.f. = 1/(1-g), where g = (1- 2*x- sqrt(1-4*x)) /(2*x) -(1-13*x +74*x^2 -247*x^3 +539*x^4 -805*x^5 +834*x^6 -595*x^7 +283*x^8 -80*x^9 +8*x^10) *x^2/ ((1-x)^7 *(1-2*x) *(1-6*x +12*x^2 -9*x^3 +x^4)).

Example

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

Maple

f:= 1/(1-g): g:= (1- 2*x- sqrt(1-4*x)) /(2*x) -(1-13*x +74*x^2 -247*x^3 +539*x^4 -805*x^5 +834*x^6 -595*x^7 +283*x^8 -80*x^9 +8*x^10) *x^2/ ((1-x)^7 *(1-2*x) *(1-6*x +12*x^2 -9*x^3 +x^4)):
a:= n-> coeff (series(f, x, n+5), x, n):
seq(a(n), n=0..30);

Mathematica

With[{g = (1-2*x -Sqrt[1-4*x])/(2*x) - (1-13*x+74*x^2-247*x^3+539*x^4 - 805*x^5+834*x^6-595*x^7+283*x^8-80*x^9+8*x^10)*x^2/((1-x)^7*(1-2*x)*(1 -6*x +12*x^2 -9*x^3 +x^4))}, CoefficientList[Series[1/(1 - g), {x, 0, 50}], x]] (* G. C. Greubel, Oct 22 2018 *)

Prog

(PARI) {g = (1-2*x -sqrt(1-4*x))/(2*x) - (1-13*x+74*x^2 -247*x^3 +539*x^4 - 805*x^5+834*x^6-595*x^7+283*x^8-80*x^9 +8*x^10 )*x^2/((1-x)^7*(1 -2*x)*(1 -6*x +12*x^2 -9*x^3 +x^4)); f=1/(1-g); };
x='x+O('x^50); Vec(f) \\ G. C. Greubel, Oct 22 2018
(Magma) m:=50; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!(1/(1- (1-2*x -Sqrt(1-4*x))/(2*x) + (1-13*x+74*x^2 -247*x^3 +539*x^4 - 805*x^5+834*x^6-595*x^7+283*x^8-80*x^9 +8*x^10 )*x^2/((1-x)^7*(1 -2*x)*(1 -6*x +12*x^2 -9*x^3 +x^4)) ))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A299021 A153475 A150259 * A150260 A165532 A165533

Adjacent sequences: A165528 A165529 A165530 * A165532 A165533 A165534

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

Reference corrected by Vincent Vatter, Sep 04 2012

Status

approved