cp's OEIS Frontend

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.

%I A288208 #43 Apr 03 2025 21:17:44
%S A288208 1,0,0,0,2,2,27,214,1695,15482,159019,1775664,21542628,282722448,
%T A288208 3989526469,60239477384,969280731152,16558273230450,299319139977198,
%U A288208 5708394302035014,114547714715532531,2412649672553637772,53220018152831892175,1227013593901474460674,29512839964990444892407
%N 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.
%C A288208 a(n) is bounded above both by A002464 and A000166.
%C A288208 The Mathematics Stack Exchange link claims that the limit as n goes to infinity of A000166(n)/a(n) = e^2.
%H A288208 Max Alekseyev, <a href="/A288208/b288208.txt">Table of n, a(n) for n = 0..30</a>
%H A288208 Fine et al., <a href="https://math.stackexchange.com/q/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>, Mathematics StackExchange, 2017.
%H A288208 Robert P. P. McKone, <a href="/A288208/a288208.txt">The permutations n=4 to n=9.</a>
%e A288208 For n = 4 the a(4) = 2 solutions are [2,4,1,3] and [3,1,4,2].
%e A288208 For n = 5 the a(5) = 2 solutions are [3,1,5,2,4] and [2,4,1,5,3].
%e A288208 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.
%p A288208 b:= proc(s, l) option remember; (n-> `if`(n=0, 1, add(
%p A288208      `if`(j=n or abs(l-j)<2, 0, b(s minus {j}, j)), j=s)))(nops(s))
%p A288208     end:
%p A288208 a:= n-> b({$1..n}, -1):
%p A288208 seq(a(n), n=0..17);  # _Alois P. Heinz_, Feb 08 2025
%t A288208 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 *)
%o A288208 (Haskell)
%o A288208 pairs l = zip l (drop 1 l)
%o A288208 d n = filter (all (uncurry (/=)) . zip [1..]) $ Data.List.permutations [1..n]
%o A288208 a n = length $ filter (all ((1<) . abs . uncurry (-)) . pairs) $ d n
%o A288208 (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
%Y A288208 Cf. A002464 is analogous without the fixed point restriction.
%Y A288208 Cf. A000142, A000166, A209322, A381461.
%K A288208 nonn
%O A288208 0,5
%A A288208 _Peter Kagey_, Jun 06 2017
%E A288208 a(12)-a(16) from _Lars Blomberg_, Jul 05 2017
%E A288208 Terms a(17) onward from _Max Alekseyev_, Feb 07 2025
%E A288208 a(0)=1 prepended by _Alois P. Heinz_, Feb 08 2025