OFFSET
0,4
COMMENTS
Cycles have at least 2 edges, and the multigraph has no loops. For this sequence, a pair p,q of cycles is equivalent if the edge-sequence of q can be formed by rotating and possibly reversing the edge sequence of p. Note that this definition ignores the starting vertex of a loop, which halves the number of distinct cycles of length >2.
LINKS
S. Donnelly, Table of n, a(n) for n=0..400
Eric W. Weisstein, Multigraph
FORMULA
a(n) = n*(n-1)/2 + Sum_{k=4..n:2 divides k} (n!/((n-k)!*2*k)).
EXAMPLE
for n = 4 there are 4 choose 2 = 6 distinct cycles of length 2, plus 3 of length 4: 0123, 0132, 0213. Hence a(4) = 6 + 3 = 9.
PROG
(Python)
def trfact_(n, k):
return reduce(lambda x, y: x*y, range(k+1, n+1), 1)
def choose_(n, k):
if k > n/2:
return trfact_(n, k)/trfact_(n-k, 1)
else:
return trfact_(n, n-k)/trfact_(k, 1)
def a_(n):
return choose_(n, 2) + sum(trfact_(n, n-k)/(2*k) for k in range(4, n+1, 2))
(PARI) a(n) = n*(n-1)/2 + sum(k=4, n, if(k%2==0, (n!/((n-k)!*2*k)), 0)); \\ Joerg Arndt, Oct 11 2015
CROSSREFS
KEYWORD
easy,nonn,walk
AUTHOR
Simon R. Donnelly, May 18 2010
EXTENSIONS
First comment and program corrected by Simon R. Donnelly, Oct 10 2015
More terms from Joerg Arndt, Oct 11 2015
STATUS
approved