A165531 - OEIS

%I #29 Sep 08 2022 08:45:48

%S 1,1,2,6,22,87,348,1374,5335,20462,77988,296787,1130969,4321239,

%T 16559467,63633036,245113705,946140207,3658715938,14170931497,

%U 54966429252,213487762758,830195102515,3232062132146,12596093756080,49137833964185,191862494482159

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

%H Alois P. Heinz, <a href="/A165531/b165531.txt">Table of n, a(n) for n = 0..1000</a>

%H M. D. Atkinson, Bruce E. Sagan and Vincent Vatter, <a href="https://doi.org/10.1016/j.ejc.2011.06.006">Counting (3+1)-avoiding permutations</a>, European J. Combin. 33 (2012), 49--61. Also <a href="https://arxiv.org/abs/1102.5568">arXiv preprint</a>, arXiv:1102.5568 [math.CO], 2011.

%H Darla Kremer and Wai Chee Shiu, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00042-6">Finite transition matrices for permutations avoiding pairs of length four patterns</a>, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_4">Permutation classes avoiding two patterns of length 4</a>.

%F 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)).

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

%p 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)):

%p a:= n-> coeff (series(f, x, n+5), x, n):

%p seq(a(n), n=0..30);

%t 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 *)

%o (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);};

%o x='x+O('x^50); Vec(f) \\ _G. C. Greubel_, Oct 22 2018

%o (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

%K nonn

%O 0,3

%A _Vincent Vatter_, Sep 21 2009

%E Reference corrected by _Vincent Vatter_, Sep 04 2012