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

1, 1, 1, 2, 5, 21, 117, 792, 6205, 55005, 543597, 5922930, 70518905, 910711193, 12678337945, 189252400480, 3015217932073, 51067619064873, 916176426422089, 17355904144773970, 346195850534379613, 7252654441500887309

Offset

0,4

Comments

For positive n, a(n) equals the permanent of the n X n matrix with 0's along the superdiagonal and the subdiagonal, and 1's everywhere else. [John M. Campbell, Jul 09 2011]

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 223.

N. S. Mendelsohn, The asymptotic series for a certain class of permutation problems, Canadian Journal of Mathematics, vol. VIII, No.2, 1956, p.238 (Example 5).

Formula

G.f.: 1/(1-x^2)*Sum_{n>=0} n!*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 26 2007

Asymptotic (N. S. Mendelsohn, 1956): a(n)/n! -> 1/e^2

Recurrence: a(n) = n*a(n-1) - (n-2)*a(n-3) - a(n-4), for n>=5

Mathematica

(* Explicit formula: *) Table[Sum[Sum[(-1)^k*(i-k)!*Binomial[2i-k, k], {k, 0, i}], {i, 0, n}], {n, 0, 21}] (* Vaclav Kotesovec, Mar 28 2011 *)

Crossrefs

Cf. A000179, A000271.

Column k=0 of A320582.

Column k=1 of A306512.

Sequence in context: A129582 A152576 A328286 * A212922 A243272 A139153

Adjacent sequences: A078477 A078478 A078479 * A078481 A078482 A078483

Keyword

easy,nonn

Author

Vladeta Jovovic, Jan 03 2003

Status

approved