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

Author

Andrew Howroyd, Jan 11 2024

Keywords

• nonn

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

Examples

			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.
		

Links

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

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.

Programs

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 *)

Formula

Euler transform of A368983.