A369145 Number of unlabeled loop-graphs with up to n vertices such that it is possible to choose a different vertex from each edge (choosable).

1, 2, 5, 12, 30, 73, 185, 467, 1207, 3147, 8329, 22245, 60071, 163462, 448277, 1236913, 3432327, 9569352, 26792706, 75288346, 212249873, 600069431, 1700826842, 4831722294, 13754016792, 39224295915, 112048279650, 320563736148, 918388655873, 2634460759783, 7566000947867

Offset

0,2

Comments

a(n) is the number of graphs with loops on n unlabeled vertices with every connected component having no more edges than vertices. - Andrew Howroyd, Feb 02 2024

Links

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

Formula

Partial sums of A369200.

Euler transform of A369289. - Andrew Howroyd, Feb 02 2024

Example

The a(0) = 1 through a(3) = 12 loop-graphs (loops shown as singletons):
  {}  {}     {}           {}
      {{1}}  {{1}}        {{1}}
             {{1,2}}      {{1,2}}
             {{1},{2}}    {{1},{2}}
             {{1},{1,2}}  {{1},{1,2}}
                          {{1},{2,3}}
                          {{1,2},{1,3}}
                          {{1},{2},{3}}
                          {{1},{2},{1,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{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}]], Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]]], {n, 0, 4}]

Crossrefs

Without the choice condition we get A000666, labeled A006125 (shifted left).

The case of a unique choice is A087803, labeled A088957.

Without loops we have A134964, labeled A133686 (covering A367869).

For exactly n edges and no loops we have A137917, labeled A137916.

The labeled version is A368927, covering A369140.

The labeled complement is A369141, covering A369142.

For exactly n edges we have A368984, labeled A333331 (maybe).

The complement for exactly n edges is A368835, labeled A368596.

The complement is counted by A369146, labeled A369141 (covering A369142).

The covering case is A369200.

The complement for exactly n edges and no loops is A369201, labeled A369143.

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

A006129 counts covering graphs, unlabeled A002494.

A054548 counts graphs covering n vertices with k edges, with loops A369199.

A129271 counts connected choosable simple graphs, unlabeled A005703.

A322661 counts labeled covering loop-graphs, unlabeled A322700.

A367867 counts non-choosable labeled graphs, covering A367868.

A368927 counts choosable labeled loop-graphs, covering A369140.

Cf. A000088, A006649, A062740, A140638, A368924, A369194.

Sequence in context: A052109 A157748 A046170 * A262320 A062423 A118649

Adjacent sequences: A369142 A369143 A369144 * A369146 A369147 A369148

Keyword

nonn

Author

Gus Wiseman, Jan 22 2024

Extensions

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

Status

approved