login
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

%I #15 Aug 12 2022 09:17:55

%S 0,0,0,2,2,27,214,1695,15482,159019,1775664,21542628,282722448,

%T 3989526469,60239477384,969280731152

%N 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.

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

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

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/2309850">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?</a>

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

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

%o (Haskell)

%o pairs l = zip l (drop 1 l)

%o d n = filter (all (uncurry (/=)) . zip [1..]) $ Data.List.permutations [1..n]

%o a n = length $ filter (all ((1<) . abs . uncurry (-)) . pairs) $ d n

%Y Cf. A002464 is analogous without the fixed point restriction.

%Y Cf. A000166.

%K nonn,more

%O 1,4

%A _Peter Kagey_, Jun 06 2017

%E a(12)-a(16) from _Lars Blomberg_, Jul 05 2017