A370166 Number of unlabeled loop-graphs covering n vertices without a non-loop edge with loops at both ends.

1, 1, 3, 9, 36, 180, 1313, 14709, 277755, 9304977, 568315345, 63806703305, 13200565313255, 5042653259803433, 3567050969262370941, 4688444463558713135201, 11491940559865490367844649, 52719458629883487816297211441, 454220675869975957947658748125099

Offset

0,3

Links

Table of n, a(n) for n=0..18.

Formula

First differences of A339832 (the non-covering version).

Example

Representatives of the a(0) = 1 through a(3) = 9 loop-graphs (loops shown as singletons):
  {}  {{1}}  {{1,2}}      {{1},{2,3}}
             {{1},{2}}    {{1,2},{1,3}}
             {{1},{1,2}}  {{1},{2},{3}}
                          {{1},{2},{1,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{1,2},{1,3},{2,3}}
                          {{1},{2},{1,3},{2,3}}
                          {{1},{1,2},{1,3},{2,3}}

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}]], Union@@#==Range[n] && !MatchQ[#, {___, {x_}, ___, {y_}, ___, {x_, y_}, ___}]&]]], {n, 0, 4}]

Crossrefs

Without loops we have A002494, labeled A006129, connected A001349.

The non-covering version is A339832.

The labeled version is A370165, non-covering A079491 (apparently).

A000666 counts unlabeled loop-graphs, covering A322700.

A006125 counts labeled loop-graphs (shifted left), covering A322661.

Cf. A000085, A001187, A048291, A062740, A116539.

Sequence in context: A237653 A070960 A030834 * A030893 A030936 A030870

Adjacent sequences: A370163 A370164 A370165 * A370167 A370168 A370169

Keyword

nonn

Author

Gus Wiseman, Feb 12 2024

Status

approved