|
|
A118537
|
|
Number of functions f: {1, 2, ..., n} --> {1, 2, ..., n} such that f(1) != f(2), f(2) != f(3), ..., f(n-1) != f(n), f(n) != f(1).
|
|
4
|
|
|
2, 6, 84, 1020, 15630, 279930, 5764808, 134217720, 3486784410, 99999999990, 3138428376732, 106993205379060, 3937376385699302, 155568095557812210, 6568408355712890640, 295147905179352825840, 14063084452067724991026
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
a(n) is also the number of circuits of length n in the complete graph on n vertices. - Thibaut Lienart (syncthib(AT)gmail.com), Jan 29 2010
Circuits are allowed to be self-intersecting and are directional with a designated start node. The number of (self-avoiding) directed cycles is given by A124355. - Andrew Howroyd, Sep 05 2018
a(n) is also the number of graph colorings of the cycle graph C_n with n colors. - Orson R. L. Peters, Jul 27 2020
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (n-1)^n + (-1)^n*(n-1).
|
|
MATHEMATICA
|
a[n_]:=(n-1)^n + (-1)^n*(n-1); Array[a, 50, {2, 51}] (* Stefano Spezia, Sep 07 2018 *)
|
|
PROG
|
(Magma) [(n-1)^n + (-1)^n*(n-1) : n in [2..20]]; // Wesley Ivan Hurt, Jul 27 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|