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

Author

Moa Apagodu, Mar 20 2000

Keywords

• nonn

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.

Extensions

More terms from Andrew Baxter, May 20 2011