login
A369202
Number of unlabeled simple graphs covering n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).
5
0, 0, 0, 0, 2, 13, 95, 826, 11137, 261899, 11729360, 1006989636, 164072166301, 50336940172142, 29003653625802754, 31397431814146891910, 63969589218557753075156, 245871863137828405124380563, 1787331789281458167615190373076, 24636021675399858912682459601585276
OFFSET
0,5
COMMENTS
These are simple graphs covering n vertices such that some connected component has at least two cycles.
LINKS
FORMULA
First differences of A140637.
a(n) = A002494(n) - A368834(n).
EXAMPLE
Representatives of the a(4) = 2 and a(5) = 13 simple graphs:
{12}{13}{14}{23}{24} {12}{13}{14}{15}{23}{24}
{12}{13}{14}{23}{24}{34} {12}{13}{14}{15}{23}{45}
{12}{13}{14}{23}{24}{35}
{12}{13}{14}{23}{25}{45}
{12}{13}{14}{25}{35}{45}
{12}{13}{14}{15}{23}{24}{25}
{12}{13}{14}{15}{23}{24}{34}
{12}{13}{14}{15}{23}{24}{35}
{12}{13}{14}{23}{24}{35}{45}
{12}{13}{14}{15}{23}{24}{25}{34}
{12}{13}{14}{15}{23}{24}{35}{45}
{12}{13}{14}{15}{23}{24}{25}{34}{35}
{12}{13}{14}{15}{23}{24}{25}{34}{35}{45}
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], {2}]], Union@@#==Range[n] && Length[Select[Tuples[#], UnsameQ@@#&]]==0&]]], {n, 0, 5}]
CROSSREFS
Without the choice condition we have A002494, labeled A006129.
The connected case is A140636.
This is the covering case of A140637, complement A134964.
The labeled version is A367868, complement A367869.
The complement is counted by A368834.
The version with loops is A369147, complement A369200.
A005703 counts unlabeled connected choosable simple graphs, labeled A129271.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A283877 counts unlabeled set-systems, connected A300913.
Sequence in context: A369413 A282724 A104255 * A118352 A372891 A320360
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jan 23 2024
STATUS
approved