A053617 Number of permutations of length n which avoid the patterns 1234 and 1324.

1, 1, 2, 6, 22, 90, 396, 1837, 8864, 44074, 224352, 1163724, 6129840, 32703074, 176351644, 959658200, 5262988330, 29057961666, 161374413196, 900792925199, 5050924332096, 28434661250454, 160644331001476, 910455895039056, 5174722258676440, 29486753617569684

Offset

0,3

Comments

These permutations have an "enumeration scheme" of depth 4, see D. Zeilberger's article in the links.

G.f. conjectured to be non-D-finite (see Albert et al. link). - Jay Pantone, Oct 01 2015

a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>2, 1>3, 2>4, 3>4} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the first element is the largest and the fourth element is the smallest. - Sergey Kitaev, Dec 10 2020

Links

Andrew Baxter and Jay Pantone, Table of n, a(n) for n = 0..600 (terms n=1..100 from Andrew Baxter)

Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.

Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

Kremer, Darla and Shiu, Wai Chee, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

Wikipedia, Permutation classes avoiding two patterns of length 4.

D. Zeilberger, Enumeration schemes and more importantly their automatic generation, Annals of Combinatorics 2 (1998) 185-195. The link is to an overview on Doron Zeilberger's home page; there is a local copy here [Pdf file only, no active links]

Crossrefs

Cf. A032351, A053614, A106228, A165542, A165545, A257561, A257562.

Sequence in context: A340892 A165546 A279568 * A089449 A264601 A374551

Adjacent sequences: A053614 A053615 A053616 * A053618 A053619 A053620

Keyword

nonn

Author

Moa Apagodu, Mar 20 2000

Extensions

More terms from Andrew Baxter, May 20 2011

Status

approved