OFFSET
0,5
COMMENTS
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.
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].
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.
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 *)
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
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Peter Kagey, Jun 06 2017
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
STATUS
approved