A078509 Number of permutations p of {1,2,...,n} such that p(i)-i != 1 and p(i)-i != 2 for all i.

1, 1, 1, 1, 5, 23, 131, 883, 6859, 60301, 591605, 6405317, 75843233, 974763571, 13512607303, 200949508327, 3190881283415, 53880906258521, 964039575154409, 18217997734199113, 362584510633666621, 7580578211464070863, 166099466140519353035, 3806162403831340850651

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..450

Formula

From Vladeta Jovovic, Jul 16 2007: (Start)

G.f.: x/(1+x)*Sum_{n>=0} (n+1)!*(x/(1+x)^2)^n.

a(n) = Sum_{k=1..n} (-1)^(n-k)*k!*binomial(n+k-2,2*k-2). (End)

a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Aug 25 2014

Maple

a:= proc(n) option remember; `if`(n<4, 1,
      (n-1)*a(n-1) +(n-3)*a(n-2) +a(n-3))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 10 2014

Mathematica

a = DifferenceRoot[Function[{y, n}, {-y[n] - n y[n+1] - (n+2) y[n+2] + y[n+3] == 0, y[0] == 1, y[1] == 1, y[2] == 1, y[3] == 1}]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 20 2020, after Alois P. Heinz *)

Crossrefs

Cf. A000255, A055790, A001883, A001887, A075851, A075852.

Sequence in context: A293088 A186755 A009321 * A239820 A077240 A281231

Adjacent sequences: A078506 A078507 A078508 * A078510 A078511 A078512

Keyword

nonn

Author

Vladimir Baltic, Vladeta Jovovic, Jan 05 2003

Extensions

More terms from Alois P. Heinz, Jan 10 2014

Status

approved