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

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

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

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

Crossrefs

Column k=4 of A276837.

Cf. A276720.

Sequence in context: A289161 A118038 A240428 * A364424 A022917 A189855

Adjacent sequences: A276835 A276836 A276837 * A276839 A276840 A276841

Keyword

nonn,easy

Author

Alois P. Heinz, Sep 20 2016

Status

approved