A368984 Number of graphs with loops (symmetric relations) on n unlabeled vertices in which each connected component has an equal number of vertices and edges.

1, 1, 2, 5, 12, 29, 75, 191, 504, 1339, 3610, 9800, 26881, 74118, 205706, 573514, 1606107, 4513830, 12727944, 35989960, 102026638, 289877828, 825273050, 2353794251, 6724468631, 19239746730, 55123700591, 158133959239, 454168562921, 1305796834570, 3758088009136

Offset

0,3

Comments

The graphs considered here can have loops but not parallel edges.

Also the number of unlabeled loop-graphs with n edges and n vertices such that it is possible to choose a different vertex from each edge. - Gus Wiseman, Jan 25 2024

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

Formula

Euler transform of A368983.

Example

Representatives of the a(3) = 5 graphs are:
   {{1,2}, {1,3}, {2,3}},
   {{1}, {1,2}, {1,3}},
   {{1}, {1,2}, {2,3}},
   {{1}, {2}, {2,3}},
   {{1}, {2}, {3}}.
The graph with 4 vertices and edges {{1}, {2}, {1,2}, {3,4}} is included by A368599 but not by this sequence.

Mathematica

brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n], {1, 2}], {n}], Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]]], {n, 0, 5}] (* Gus Wiseman, Jan 25 2024 *)

Crossrefs

The case of a unique choice is A000081.

Without loops we have A137917, labeled A137916.

The labeled version appears to be A333331.

Without the choice condition we have A368598, covering A368599.

The complement is counted by A368835, labeled A368596 (covering A368730).

Row sums of A368926, labeled A368924.

The connected case is A368983.

A000085, A100861, A111924 count set partitions into singletons or pairs.

A000666 counts unlabeled loop-graphs, covering A322700.

A006125 counts simple graphs, unlabeled A000088.

A006129 counts covering graphs, connected A001187, unlabeled A002494.

A322661 counts labeled covering loop-graphs, connected A062740.

Cf. A014068, A057500, A116508, A129271, A133686, A367863, A367869, A367902, A368597, A368601, A368836.

Sequence in context: A152171 A132807 A261234 * A324787 A333888 A228516

Adjacent sequences: A368981 A368982 A368983 * A368985 A368986 A368987

Keyword

nonn

Author

Andrew Howroyd, Jan 11 2024

Status

approved