A276838 Number of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most four elements.

1, 1, 2, 6, 24, 60, 150, 399, 1145, 3132, 8420, 22716, 62128, 169536, 460885, 1251777, 3406238, 9272354, 25229036, 68622196, 186682470, 507925571, 1381929921, 3759616968, 10228269080, 27827267544, 75707898304, 205971928848, 560368255081, 1524544463441

Offset: 0

Author

Alois P. Heinz, Sep 20 2016

Keywords

• nonn
• easy

Comments

a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>5} of length 5. That is, the number of length n permutations having no subsequences of length 5 in which the first element is larger than the fifth element. - Sergey Kitaev, Dec 11 2020

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• 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.
• Index entries for linear recurrences with constant coefficients, signature (1,2,2,12,8,-2,-5,-1).

Crossrefs

Column k=4 of A276837.

Cf. A276720.

Programs

Mathematica

CoefficientList[Series[-(x - 1) (x + 1)/(x^8 + 5 x^7 + 2 x^6 - 8 x^5 - 12 x^4 - 2 x^3 - 2 x^2 - x + 1), {x, 0, 29}], x] (* Michael De Vlieger, Oct 14 2017 *)

Formula

G.f.: -(x-1)*(x+1)/(x^8+5*x^7+2*x^6-8*x^5-12*x^4-2*x^3-2*x^2-x+1).