login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A109033 Number of permutations in S_n avoiding the patterns 1342 and 2143. 5
1, 1, 2, 6, 22, 88, 368, 1584, 6968, 31192, 141656, 651136, 3023840, 14166496, 66876096, 317809216, 1519163456, 7299577216, 35237444736, 170812433536, 831127053696, 4057858988416, 19873611712896, 97609555091456 (list; graph; refs; listen; history; text; internal format)
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, 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, 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 08:10 EDT 2021. Contains 347577 sequences. (Running on oeis4.)