A109033 - OEIS

%I #50 Oct 23 2023 08:34:15

%S 1,1,2,6,22,88,368,1584,6968,31192,141656,651136,3023840,14166496,

%T 66876096,317809216,1519163456,7299577216,35237444736,170812433536,

%U 831127053696,4057858988416,19873611712896,97609555091456

%N Number of permutations in S_n avoiding the patterns 1342 and 2143.

%C Also number of permutations in S_n avoiding the patterns 3142 and 2341. Partial sums of A109034.

%C Hankel transform is 2^floor(n^2/3) (see A134751). - _Paul Barry_, Dec 15 2008

%H Vincenzo Librandi, <a href="/A109033/b109033.txt">Table of n, a(n) for n = 0..300</a>

%H Christian Bean, <a href="https://hdl.handle.net/20.500.11815/1184">Finding structure in permutation sets</a>, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.

%H Christian Bean, Émile Nadeau, and Henning Ulfarsson, <a href="https://arxiv.org/abs/1912.07503">Enumeration of Permutation Classes and Weighted Labelled Independent Sets</a>, arXiv:1912.07503 [math.CO], 2019.

%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 Ian Le, <a href="http://www.combinatorics.org/Volume_12/Abstracts/v12i1r25.html">Wilf classes of pairs of permutations of length 4</a>, Electron. J. Combin., 12(1) (2005), R25, 26 pages.

%H E. Rowland and R. Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, arXiv preprint arXiv:1310.8635 [math.NT], 2013-2014.

%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-sqrt(1-8*x+16*x^2-8*x^3))/(4*x*(1-x)).

%F From _Paul Barry_, Dec 15 2008: (Start)

%F G.f.: (1-x)*c(2*x*(1-x)^2), where c(x) is the g.f. of A000108;

%F a(n) = sum{k=0..n, (-1)^(n-k)*C(2k+1,n-k)*2^k*A000108(k)}. (End)

%F G.f.: 1/(1-x/(1-x/(1-2x/(1-x/(1-x/(1-2x/(1-x/(1-x/(1-2x...... (continued fraction). - _Paul Barry_, Dec 15 2008

%F a(n) = Sum_{k=0..n} A091866(n,k)*2^(n-k). - _Philippe Deléham_, Nov 27 2009

%F Recurrence: (n+1)*a(n) = 3*(3*n-1)*a(n-1) - 12*(2*n-3)*a(n-2) + 12*(2*n-5) * a(n-3) - 4*(2*n-7)*a(n-4). - _Vaclav Kotesovec_, Oct 24 2012

%F a(n) ~ sqrt(5-sqrt(5))*(sqrt(5)+3)^n/(2*sqrt(2*Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 24 2012. Equivalently, a(n) ~ 5^(1/4) * 2^(n-1) * phi^(2*n - 1/2) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - _Vaclav Kotesovec_, Dec 10 2021

%F G.f. A(x) satisfies: A(x) = (1 - x) * (1 + 2*x*A(x)^2). - _Ilya Gutkovskiy_, Jun 30 2020

%e a(4) = 22 because all permutations of 1234 qualify with the exception of 1342 and 2143.

%p G:=(1-sqrt(1-8*x+16*x^2-8*x^3))/4/x/(1-x): Gser:=series(G,x=0,30): 1,seq(coeff(Gser,x^n),n=1..27);

%t CoefficientList[Series[(1-Sqrt[1-8x+16x^2-8x^3])/(4x(1-x)), {x,0,30}], x] (* _Harvey P. Dale_, Jul 02 2011 *)

%Y Cf. A109034.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Jun 16 2005