A306523 Number of permutations p of [n] having no index i with |p(i)-i| = 2.

1, 1, 2, 3, 9, 34, 176, 1106, 8241, 70371, 676098, 7204713, 84252233, 1072010712, 14738107136, 217656602456, 3435793029849, 57721548509705, 1028183730411650, 19354550056977555, 383876766917923073, 8001053425278668706, 174828593537337033648, 3996207024319062050994

Offset

0,3

Links

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

Wikipedia, Permutation

Formula

a(n) = n! - A306524(n).

Example

a(3) = 3: 123, 132, 213.
a(4) = 9: 1234, 1243, 1324, 2134, 2143, 2341, 4123, 4231, 4321.
a(5) = 34: 12345, 12354, 12435, 13245, 13254, 13452, 15234, 15342, 15432, 21345, 21354, 21435, 23415, 23451, 25314, 25341, 25431, 41235, 41352, 42315, 42351, 43215, 43251, 45231, 45312, 51234, 51342, 51432, 52314, 52341, 52431, 53214, 53241, 53412.

Mathematica

b[s_, k_] := b[s, k] = With[{n = Length[s]}, If[n == 0, 1, Sum[If[Abs[i-n] == k, 0, b[s~Complement~{i}, k]], {i, s}]]];
A[n_, k_] := If[k >= n, n!, b[Range[n], k]];
a[n_] := A[n, 2];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 23}] (* Jean-François Alcover, Oct 31 2021, after Alois P. Heinz in A306512 *)

Crossrefs

Column k=2 of A306512.

Cf. A000142, A306524.

Sequence in context: A296263 A064020 A204442 * A095412 A074428 A328436

Adjacent sequences: A306520 A306521 A306522 * A306524 A306525 A306526

Keyword

nonn

Author

Alois P. Heinz, Feb 21 2019

Status

approved