cp's OEIS Frontend

A209322 Number of derangements of [n] with no succession.

%I A209322 #50 Apr 04 2025 01:17:09
%S A209322 1,0,1,0,4,14,102,682,5484,49288,492812,5418154,64993966,844658714,
%T A209322 11822116868,177292309424,2836140479376,48206588630826,
%U A209322 867597809813018,16482372327022854,329612875955466784,6921235129197714036,152254880756288024536,3501612401180417830334,84033374067657870984810,2100715696249652623708150
%N A209322 Number of derangements of [n] with no succession.
%C A209322 A derangement is a permutation with no fixed points. A succession of a permutation p is a position i such that p(i+1)-p(i) = 1.
%H A209322 Max Alekseyev, <a href="/A209322/b209322.txt">Table of n, a(n) for n = 0..30</a>
%F A209322 a(n) = n! - A207819(n).
%e A209322 For n=4 we have 2143, 2413, 3142 and 4321, so a(4) = 4.
%p A209322 F:= proc(S) add(G(S minus {s}, s-1), s = S minus {nops(S)}) end proc:
%p A209322 G:= proc(S,t) option remember;
%p A209322 if S = {} then return 1 fi;
%p A209322 add(procname(S minus {s},s-1), s = S minus {t, nops(S)})
%p A209322 end proc:
%p A209322 1,seq(F({$1..n}), n=1..19); # _Robert Israel_, Mar 02 2017
%t A209322 F[{}] = 1; F[S_] := Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {Length[S]}}];
%t A209322 G[{}, _] = 1; G[S_, t_] := G[S, t] = Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {t, Length[S]}}];
%t A209322 Table[a[n] = F[Range[n]]; Print[n, " ", a[n]]; a[n], {n, 0, 20}] (* _Jean-François Alcover_, Mar 05 2019, after _Robert Israel_ *)
%o A209322 (PARI) { a209322(n) = if(n==0, return(1)); my(A=matrix(n, n, i, j, i-j!=1 && i!=j)); 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_, Apr 03 2025
%Y A209322 Cf. A000166, A002467, A180191, A207819, A207821, A209325, A209326, A288208.
%K A209322 nonn
%O A209322 0,5
%A A209322 _Jon Perry_, Jan 19 2013
%E A209322 a(11)-a(14) from _Alois P. Heinz_, Jan 19 2013
%E A209322 a(15)-a(20) from _Robert Israel_, Mar 02 2017
%E A209322 a(21)-a(23) from _Alois P. Heinz_, Jul 04 2021
%E A209322 Terms a(24) onward from _Max Alekseyev_, Apr 03 2025