A370169 Number of unlabeled loop-graphs covering n vertices with at most n edges.

1, 1, 3, 7, 19, 48, 135, 373, 1085, 3184, 9590, 29258, 90833, 285352, 908006, 2919953, 9487330, 31111997, 102934602, 343389708, 1154684849, 3912345408, 13353796977, 45906197103, 158915480378, 553897148543, 1943627750652, 6865605601382, 24411508473314, 87364180212671, 314682145679491

Offset

0,3

Links

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

Example

The a(0) = 1 through a(4) = 19 loop-graph edge sets (loops shown as singletons):
  {}  {{1}}  {{1,2}}      {{1},{2,3}}          {{1,2},{3,4}}
             {{1},{2}}    {{1,2},{1,3}}        {{1},{2},{3,4}}
             {{1},{1,2}}  {{1},{2},{3}}        {{1},{1,2},{3,4}}
                          {{1},{2},{1,3}}      {{1},{2,3},{2,4}}
                          {{1},{1,2},{1,3}}    {{1},{2},{3},{4}}
                          {{1},{1,2},{2,3}}    {{1,2},{1,3},{1,4}}
                          {{1,2},{1,3},{2,3}}  {{1,2},{1,3},{2,4}}
                                               {{1},{2},{3},{1,4}}
                                               {{1},{2},{1,2},{3,4}}
                                               {{1},{2},{1,3},{1,4}}
                                               {{1},{2},{1,3},{2,4}}
                                               {{1},{2},{1,3},{3,4}}
                                               {{1},{1,2},{1,3},{1,4}}
                                               {{1},{1,2},{1,3},{2,4}}
                                               {{1},{1,2},{2,3},{2,4}}
                                               {{1},{1,2},{2,3},{3,4}}
                                               {{1},{2,3},{2,4},{3,4}}
                                               {{1,2},{1,3},{1,4},{2,3}}
                                               {{1,2},{1,3},{2,4},{3,4}}

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]&&Length[#]<=n&]]], {n, 0, 5}]

Prog

(PARI) \\ G defined in A070166.
a(n)=my(A=O(x*x^n)); if(n==0, 1, polcoef((G(n, A)-G(n-1, A))/(1-x), n)) \\ Andrew Howroyd, Feb 19 2024

Crossrefs

The case of equality is A368599, covering case of A368598.

The labeled version is A369194, covering case of A066383.

This is the covering case of A370168.

The loopless version is the covering case of A370315, labeled A369192.

This is the loopless version is A370316, labeled A369191.

A006125 counts graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

A322661 counts covering loop-graphs, unlabeled A322700.

Cf. A000666, A005703, A014068, A062740, A116508, A368597, A368927, A369141, A369196, A369197, A369199.

Sequence in context: A387783 A293733 A073063 * A007288 A191824 A191757

Adjacent sequences: A370166 A370167 A370168 * A370170 A370171 A370172

Keyword

nonn

Author

Gus Wiseman, Feb 16 2024

Extensions

a(7) onwards from Andrew Howroyd, Feb 19 2024

Status

approved