A369145 - OEIS

%I #10 Feb 02 2024 16:11:53

%S 1,2,5,12,30,73,185,467,1207,3147,8329,22245,60071,163462,448277,

%T 1236913,3432327,9569352,26792706,75288346,212249873,600069431,

%U 1700826842,4831722294,13754016792,39224295915,112048279650,320563736148,918388655873,2634460759783,7566000947867

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

%C 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

%H Andrew Howroyd, <a href="/A369145/b369145.txt">Table of n, a(n) for n = 0..500</a>

%F Partial sums of A369200.

%F Euler transform of A369289. - _Andrew Howroyd_, Feb 02 2024

%e The a(0) = 1 through a(3) = 12 loop-graphs (loops shown as singletons):

%e   {}  {}     {}           {}

%e       {{1}}  {{1}}        {{1}}

%e              {{1,2}}      {{1,2}}

%e              {{1},{2}}    {{1},{2}}

%e              {{1},{1,2}}  {{1},{1,2}}

%e                           {{1},{2,3}}

%e                           {{1,2},{1,3}}

%e                           {{1},{2},{3}}

%e                           {{1},{2},{1,3}}

%e                           {{1},{1,2},{1,3}}

%e                           {{1},{1,2},{2,3}}

%e                           {{1,2},{1,3},{2,3}}

%t brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]}, {i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];

%t Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{1,2}]], Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]]],{n,0,4}]

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

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

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

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

%Y The labeled version is A368927, covering A369140.

%Y The labeled complement is A369141, covering A369142.

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

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

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

%Y The covering case is A369200.

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

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

%Y A006129 counts covering graphs, unlabeled A002494.

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

%Y A129271 counts connected choosable simple graphs, unlabeled A005703.

%Y A322661 counts labeled covering loop-graphs, unlabeled A322700.

%Y A367867 counts non-choosable labeled graphs, covering A367868.

%Y A368927 counts choosable labeled loop-graphs, covering A369140.

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

%K nonn

%O 0,2

%A _Gus Wiseman_, Jan 22 2024

%E a(7) onwards from _Andrew Howroyd_, Feb 02 2024