A395499 Number of derangements of [n] with 3 ascents.

0, 0, 0, 0, 0, 8, 104, 896, 5984, 34520, 180416, 881152, 4099168, 18402472, 80448280, 344696896, 1454453824, 6065128824, 25062002736, 102827682240, 419567098560, 1704570004680, 6901736685000, 27870866931200, 112315638404000, 451879751658008, 1815731435901344, 7288642807769216

Offset

0,6

Links

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (16,-101,298,-278,-656,1854,-676,-2581,2744,935,-2422,460,696,-288).

Formula

a(n) = A219836(n,n-4).

G.f.: 8 * x^5 * (1-3*x+5*x^2-29*x^3+63*x^4-46*x^5+33*x^6-36*x^7)/((1-x^2)^4 * (1-2*x)^3 * (1-3*x)^2 * (1-4*x)).

a(n) = 16*a(n-1) - 101*a(n-2) + 298*a(n-3) - 278*a(n-4) - 656*a(n-5) + 1854*a(n-6) - 676*a(n-7) - 2581*a(n-8) + 2744*a(n-9) + 935*a(n-10) - 2422*a(n-11) + 460*a(n-12) + 696*a(n-13) - 288*a(n-14) for n > 13.

Example

For n=5, the a(5) = 8 derangements are: [2, 3, 4, 5, 1] (2<3, 3<4, 4<5), [2, 3, 5, 1, 4] (2<3, 3<5, 1<4), [2, 4, 5, 1, 3] (2<4, 4<5, 1<3), [2, 5, 1, 3, 4] (2<5, 1<3, 3<4), [3, 4, 5, 1, 2] (3<4, 4<5, 1<2), [3, 5, 1, 2, 4] (3<5, 1<2, 2<4), [4, 5, 1, 2, 3] (4<5, 1<2, 2<3), and [5, 1, 2, 3, 4] (1<2, 2<3, 3<4).

Prog

(PARI) my(N=30, x='x+O('x^N)); concat([0, 0, 0, 0, 0], Vec(8*x^5*(1-3*x+5*x^2-29*x^3+63*x^4-46*x^5+33*x^6-36*x^7)/((1-x^2)^4*(1-2*x)^3*(1-3*x)^2*(1-4*x))))

Crossrefs

Column k=3 of A395497.

Cf. A219836, A395482.

Sequence in context: A138430 A366653 A164760 * A335608 A109774 A001657

Adjacent sequences: A395496 A395497 A395498 * A395500 A395501 A395502

Keyword

nonn

Author

Seiichi Manyama, Apr 25 2026

Status

approved