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,3

Comments

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

Hankel transform is 2^floor(n^2/3) (see A134751). - Paul Barry, Dec 15 2008

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.

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

Example

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

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

Crossrefs

Cf. A109034.

Sequence in context: A165537 A165538 A165539 * A049135 A049127 A199481

Adjacent sequences: A109030 A109031 A109032 * A109034 A109035 A109036

Keyword

nonn

Author

Emeric Deutsch, Jun 16 2005

Status

approved