A109033 Number of permutations in S_n avoiding the patterns 1342 and 2143.
1, 1, 2, 6, 22, 88, 368, 1584, 6968, 31192, 141656, 651136, 3023840, 14166496, 66876096, 317809216, 1519163456, 7299577216, 35237444736, 170812433536, 831127053696, 4057858988416, 19873611712896, 97609555091456
Offset: 0
Keywords
Examples
a(4) = 22 because all permutations of 1234 qualify with the exception of 1342 and 2143.
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..300
- Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
- Christian Bean, Émile Nadeau, and Henning Ulfarsson, Enumeration of Permutation Classes and Weighted Labelled Independent Sets, arXiv:1912.07503 [math.CO], 2019.
- 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.
- Ian Le, Wilf classes of pairs of permutations of length 4, Electron. J. Combin., 12(1) (2005), R25, 26 pages.
- E. Rowland and R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635 [math.NT], 2013-2014.
- Wikipedia, Permutation classes avoiding two patterns of length 4.
Crossrefs
Cf. A109034.
Programs
-
Maple
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);
-
Mathematica
CoefficientList[Series[(1-Sqrt[1-8x+16x^2-8x^3])/(4x(1-x)), {x,0,30}], x] (* Harvey P. Dale, Jul 02 2011 *)
Formula
G.f.: (1-sqrt(1-8*x+16*x^2-8*x^3))/(4*x*(1-x)).
From Paul Barry, Dec 15 2008: (Start)
G.f.: (1-x)*c(2*x*(1-x)^2), where c(x) is the g.f. of A000108;
a(n) = sum{k=0..n, (-1)^(n-k)*C(2k+1,n-k)*2^k*A000108(k)}. (End)
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
a(n) = Sum_{k=0..n} A091866(n,k)*2^(n-k). - Philippe Deléham, Nov 27 2009
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
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
G.f. A(x) satisfies: A(x) = (1 - x) * (1 + 2*x*A(x)^2). - Ilya Gutkovskiy, Jun 30 2020
Comments