A209322 Number of derangements of [n] with no succession.
1, 0, 1, 0, 4, 14, 102, 682, 5484, 49288, 492812, 5418154, 64993966, 844658714, 11822116868, 177292309424, 2836140479376, 48206588630826, 867597809813018, 16482372327022854, 329612875955466784, 6921235129197714036, 152254880756288024536, 3501612401180417830334, 84033374067657870984810, 2100715696249652623708150
Offset: 0
Keywords
Examples
For n=4 we have 2143, 2413, 3142 and 4321, so a(4) = 4.
Links
- Max Alekseyev, Table of n, a(n) for n = 0..30
Programs
-
Maple
F:= proc(S) add(G(S minus {s}, s-1), s = S minus {nops(S)}) end proc: G:= proc(S,t) option remember; if S = {} then return 1 fi; add(procname(S minus {s},s-1), s = S minus {t, nops(S)}) end proc: 1,seq(F({$1..n}), n=1..19); # Robert Israel, Mar 02 2017 -
Mathematica
F[{}] = 1; F[S_] := Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {Length[S]}}]; G[{}, ] = 1; G[S, t_] := G[S, t] = Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {t, Length[S]}}]; 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 *) -
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
Formula
a(n) = n! - A207819(n).
Extensions
a(11)-a(14) from Alois P. Heinz, Jan 19 2013
a(15)-a(20) from Robert Israel, Mar 02 2017
a(21)-a(23) from Alois P. Heinz, Jul 04 2021
Terms a(24) onward from Max Alekseyev, Apr 03 2025
Comments