A331563 Number of labeled cyclic graphs with n edges and 2n vertices.

0, 0, 20, 1610, 129654, 11688369, 1194822915, 137766789810, 17758192128830, 2535895233070628, 397875362655895761, 68087081506276861665, 12626853606957534296975, 2523446241515288646389325

Offset

1,3

Links

Table of n, a(n) for n=1..14.

Eric Weisstein's World of Mathematics, Paw Graph

Formula

a(n) = A331505(2n) - A302112(n).

Example

a(4) = 1610 since we have 3 non-isomorphic cyclic graphs with 4 edges and 8 nodes. (See illustration below.)
To compute a(4) we can consult A057500, which provides the number of labeled connected unicycles. Because A057500(4)=15, and knowing that there are 3 labeled squares, we have 15-3 = 12 Paw Graphs [see Weisstein link]. So graph 1 is labeled in 12 * C(8,4) = 840 ways. Graph 2 is labeled in 3* C(8,4) = 210 ways. A105599 gives 10 as the number of labeled forests with 5 nodes and 4 components, so graph 3 is labeled in 10 * C(8,3) = 560 ways. We have 840 + 210 + 560 = 1610.
.
  graph 1    graph 2    graph 3 (triangle + forest with
                                 5 nodes and 4 components)
   *--*       *--*       *--* *
   | /|       |  |       | /  |
   |/ |       |  |       |/   |
   *  *       *--*       *    *
  * * * *    * * * *      * * *

Crossrefs

Cf. A331505, A302112, A057500, A105599.

Sequence in context: A177608 A177610 A130040 * A250018 A177604 A177621

Adjacent sequences: A331560 A331561 A331562 * A331564 A331565 A331566

Keyword

nonn

Author

Washington Bomfim, Jan 20 2020

Status

approved