login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A178061 Number of distinct cycles without repeated edges on the multigraph consisting of two vertices joined by n edges. 2
0, 0, 1, 3, 9, 25, 120, 546, 4438, 28134, 308115, 2440405, 33237831, 314699463, 5119097074, 56345113020, 1065268609980, 13359512435356, 287786703606453, 4049825314169079, 97903924694681365, 1527478596708475845, 40946200336523631996, 701409698806896677158 (list; graph; refs; listen; history; text; internal format)
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

A263102 uses a more correct definition of cycle equivalence.

Sequence in context: A192371 A192465 A012771 * A120284 A074440 A006204

Adjacent sequences:  A178058 A178059 A178060 * A178062 A178063 A178064

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 28 10:48 EDT 2021. Contains 347714 sequences. (Running on oeis4.)