OFFSET
0,4
COMMENTS
The multigraph has no loops. Cycles have length at least 2, and may repeat vertices but not edges. Cycles p,q are equivalent if the vertex-edge sequence of q can be made by rotating or reversing that of p. Because no edge can be repeated, the maximum length of a cycle is n.
LINKS
Simon R. Donnelly, Table of n, a(n) for n = 0..448
Eric W. Weisstein, Multigraph
FORMULA
a(n) = n*(n-1)/2 + Sum_{k=4..n:2 divides k} (n!/((n-k)!*k)).
EXAMPLE
For n=3, there are C(3,2) = 3 edge pairs, each forming a distinct cycle. a(3) = 3.
For n=4, there are C(4,2) = 6 edge pairs forming cycles of length 2, and 6 cycles of length 4: a0b1a2b3a, a0b1a3b2a, a0b2a1b3a, a0b2a3b1a, a0b3a1b2a, a0b3a2b1a. a(4) = 12.
PROG
(Python)
def trfact(n, k):
return reduce(lambda x, y: x*y, range(k+1, n+1), 1)
def a(n):
return sum(trfact(n, n-k)/k for k in range(2, n+1, 2))
(PARI) a(n) = n*(n-1)/2 + sum(k=4, n, if(k%2==0, (n!/((n-k)!*k)), 0)); \\ Joerg Arndt, Oct 11 2015
CROSSREFS
KEYWORD
nonn,easy,walk
AUTHOR
Simon R. Donnelly, Oct 09 2015
STATUS
approved