A323799 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 3.

0, 10, 47, 157, 503, 1669, 5472, 17531, 55135, 172134, 535510, 1660795, 5133470, 15826173, 48706210, 149721544, 459820058, 1411142937, 4328181110, 13269541967, 40669595890, 124617708274, 381776661185, 1169438884559, 3581781480980, 10969462410857, 33592685042253

Offset

3,2

Links

Alois P. Heinz, Table of n, a(n) for n = 3..1000

Index entries for linear recurrences with constant coefficients, signature (4,-2,-2,6,-17,-16,-30,6,32,48,12,-16,-16,-9,2,-2,-2,2,1).

Formula

G.f.: x^4 *(x^11+x^10-3*x^9+x^8+4*x^7-4*x^6-4*x^5-5*x^4+11*x^3+11*x^2-7*x-10) / ((x-1) *(x^5 -2*x^3 -2*x+1) *(x^13 +3*x^12 +3*x^11 +5*x^10 +9*x^9 +7*x^8 -3*x^7 -19*x^6 -21*x^5 -13*x^4 -3*x^3 -3*x^2-x+1)).

a(n) = A002526(n) - A002524(n).

Example

a(4) = 10: 2341, 2431, 3241, 3421, 4123, 4132, 4213, 4231, 4312, 4321.

Mathematica

Drop[CoefficientList[Series[x^4(x^11+x^10-3x^9+x^8+4x^7-4x^6-4x^5-5x^4+11x^3+11x^2-7x-10)/((x-1)(x^5-2x^3-2x+1)(x^13+3x^12+3x^11+ 5x^10+9x^9+ 7x^8-3x^7- 19x^6-21x^5-13x^4-3x^3-3x^2-x+1)), {x, 0, 30}], x], 3] (* or *) LinearRecurrence[{4, -2, -2, 6, -17, -16, -30, 6, 32, 48, 12, -16, -16, -9, 2, -2, -2, 2, 1}, {0, 10, 47, 157, 503, 1669, 5472, 17531, 55135, 172134, 535510, 1660795, 5133470, 15826173, 48706210, 149721544, 459820058, 1411142937, 4328181110}, 30] (* Harvey P. Dale, Sep 16 2025 *)

Crossrefs

Column k=3 of A130152.

Cf. A002524, A002526.

Sequence in context: A253477 A143895 A281767 * A213575 A319491 A034443

Adjacent sequences: A323796 A323797 A323798 * A323800 A323801 A323802

Keyword

nonn,easy

Author

Alois P. Heinz, Jan 28 2019

Status

approved