A369200 - OEIS

A369200

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

1, 1, 3, 7, 18, 43, 112, 282, 740, 1940, 5182, 13916, 37826, 103391, 284815, 788636, 2195414, 6137025, 17223354, 48495640, 136961527, 387819558, 1100757411, 3130895452, 8922294498, 25470279123, 72823983735, 208515456498, 597824919725, 1716072103910, 4931540188084

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

These are covering loop-graphs with at most one cycle (unicyclic) in each connected component.

LINKS

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

FORMULA

First differences of A369145.

Euler transform of A369289 with A369289(1) = 1. - Andrew Howroyd, Feb 02 2024

EXAMPLE

Representatives of the a(1) = 1 through a(4) = 18 loop-graphs (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,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[Select[Tuples[#], UnsameQ@@#&]]!=0&]]], {n, 0, 4}]

CROSSREFS

Without the choice condition we have A322700, labeled A322661.

Without loops we have A368834, covering case of A134964.

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

The labeled version is A369140, covering case of A368927.

The labeled complement is A369142, covering case of A369141.

This is the covering case of A369145.

The complement is counted by A369147, covering case of A369146.

The complement without loops is A369202, covering case of A140637.

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

A000666 counts unlabeled loop-graphs, labeled A006125 (shifted left).

A006129 counts covering graphs, unlabeled A002494.

A007716 counts non-isomorphic multiset partitions, connected A007718.

A129271 counts connected choosable simple graphs, unlabeled A005703.

A133686 counts choosable labeled graphs, covering A367869.

Cf. A000088, A000612, A006649, A014068, A055621, A137916, A137917, A368835, A369194, A369199.

Sequence in context: A091621 A129921 A036670 * A262321 A182995 A027967

Adjacent sequences: A369197 A369198 A369199 * A369201 A369202 A369203

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jan 23 2024

EXTENSIONS

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

STATUS

approved