A288208 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.

1, 0, 0, 0, 2, 2, 27, 214, 1695, 15482, 159019, 1775664, 21542628, 282722448, 3989526469, 60239477384, 969280731152, 16558273230450, 299319139977198, 5708394302035014, 114547714715532531, 2412649672553637772, 53220018152831892175, 1227013593901474460674, 29512839964990444892407

Offset: 0

Author

Peter Kagey, Jun 06 2017

Keywords

• nonn

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.

Examples

			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].
a(6) = 27: 241635, 246135, 246315, 251364, 264135, 314625, 315264, 351624, 351642, 352614, 352641, 361524, 362514, 415263, 415362, 462513, 462531, 514263, 531624, 531642, 536142, 536241, 631524, 635142, 635241, 642513, 642531.
		

Links

• Max Alekseyev, Table of n, a(n) for n = 0..30
• Fine et al., 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?, Mathematics StackExchange, 2017.
• Robert P. P. McKone, The permutations n=4 to n=9.

Crossrefs

Cf. A002464 is analogous without the fixed point restriction.

Cf. A000142, A000166, A209322, A381461.

Programs

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

Maple

b:= proc(s, l) option remember; (n-> `if`(n=0, 1, add(
     `if`(j=n or abs(l-j)<2, 0, b(s minus {j}, j)), j=s)))(nops(s))
    end:
a:= n-> b({$1..n}, -1):
seq(a(n), n=0..17);  # Alois P. Heinz, Feb 08 2025

Mathematica

Clear[permCount]; permCount[s_, last_] := permCount[s, last] = Module[{n, j}, n = Length[s]; If[n == 0, 1, Total[Table[If[j == n || Abs[last - j] < 2, 0, permCount[Complement[s, {j}], j]], {j, s}]]]]; Table[permCount[Range[n], -2], {n, 0, 12}] (* Robert P. P. McKone, Mar 22 2025 *)

PARI

{ a288208(n) = my(A = matrix(n,n,i,j,abs(i-j)>1)); parsum(s=1,2^n-1, my(M=vecextract(A,s,s), d=matsize(M)[1], v=vectorv(d,i,1), pos=bitand(s,1)); if(pos,v[1]=0); for(k=1,n-1, v=M*v; if(bitand(s>>k,1), v[pos++]=0)); (-1)^(n-d)*vecsum(v) ); } \\ Max Alekseyev, Feb 08 2025

Extensions

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

Terms a(17) onward from Max Alekseyev, Feb 07 2025

a(0)=1 prepended by Alois P. Heinz, Feb 08 2025