A288208 The number of permutations of a sequence of length n such that there are no fixed points, and no term is next to a term it was next to originally.

0, 0, 0, 2, 2, 27, 214, 1695, 15482, 159019, 1775664, 21542628, 282722448, 3989526469, 60239477384, 969280731152

Offset

1,4

Comments

a(n) is bounded above both by A002464 and A000166.

The Mathematics Stack Exchange link claims that the limit as n goes to infinity of A000166(n)/a(n) = e^2.

Links

Table of n, a(n) for n=1..16.

Mathematics Stack Exchange, If some series of n terms is deranged, what is the probability that no term stands next to a term it was next to originally?

Example

For n = 4 the a(4) = 2 solutions are [2,4,1,3] and [3,1,4,2].
For n = 5 the a(5) = 2 solutions are [3,1,5,2,4] and [2,4,1,5,3].

Prog

(Haskell)
pairs l = zip l (drop 1 l)
d n = filter (all (uncurry (/=)) . zip [1..]) $ Data.List.permutations [1..n]
a n = length $ filter (all ((1<) . abs . uncurry (-)) . pairs) $ d n

Crossrefs

Cf. A002464 is analogous without the fixed point restriction.

Cf. A000166.

Sequence in context: A371639 A094347 A236286 * A024577 A121222 A125067

Adjacent sequences: A288205 A288206 A288207 * A288209 A288210 A288211

Keyword

nonn,more

Author

Peter Kagey, Jun 06 2017

Extensions

a(12)-a(16) from Lars Blomberg, Jul 05 2017

Status

approved