|
|
A209322
|
|
Number of derangements of [n] with no succession.
|
|
3
|
|
|
1, 0, 1, 0, 4, 14, 102, 682, 5484, 49288, 492812, 5418154, 64993966, 844658714, 11822116868, 177292309424, 2836140479376, 48206588630826, 867597809813018, 16482372327022854, 329612875955466784, 6921235129197714036, 152254880756288024536, 3501612401180417830334
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
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.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For n=4 we have 2143, 2413, 3142 and 4321, so a(4) = 4.
|
|
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:
|
|
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]}}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|