A288208 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

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.

KEYWORD

nonn,more

AUTHOR

Peter Kagey, Jun 06 2017

EXTENSIONS

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

STATUS

approved