login
Number of distinct cycles without repeated edges on the multigraph with 2 vertices connected by n edges.
3

%I #19 Nov 20 2015 16:44:36

%S 0,0,1,3,12,40,225,1071,8848,56232,616185,4880755,66475596,629398848,

%T 10238194057,112690225935,2130537219840,26719024870576,

%U 575573407212753,8099650628337987,195807849389362540,3054957193416951480,81892400673047263761,1402819397613793354063,41294565798306731368272,770446268109598573215000

%N Number of distinct cycles without repeated edges on the multigraph with 2 vertices connected by n edges.

%C 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.

%H Simon R. Donnelly, <a href="/A263102/b263102.txt">Table of n, a(n) for n = 0..448</a>

%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/Multigraph.html">Multigraph</a>

%F a(n) = n*(n-1)/2 + Sum_{k=4..n:2 divides k} (n!/((n-k)!*k)).

%e For n=3, there are C(3,2) = 3 edge pairs, each forming a distinct cycle. a(3) = 3.

%e 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.

%o (Python)

%o def trfact(n, k):

%o return reduce(lambda x, y: x*y, range(k+1,n+1),1)

%o def a(n):

%o return sum(trfact(n,n-k)/k for k in range(2, n+1, 2))

%o (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

%Y A178061 uses a different (incorrect) definition of equivalence for cycles.

%Y Equals 2 times A178061 minus C(n,2).

%Y A263103, A263104, A263105 concern the number of cycles on multigraphs with 3 vertices.

%K nonn,easy,walk

%O 0,4

%A _Simon R. Donnelly_, Oct 09 2015