login
A369201
Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).
6
0, 0, 0, 0, 0, 1, 7, 30, 124, 507, 2036, 8216, 33515, 138557, 583040, 2503093, 10985364, 49361893, 227342301, 1073896332, 5204340846, 25874724616, 131937166616, 689653979583, 3693193801069, 20247844510508, 113564665880028, 651138092719098, 3813739129140469
OFFSET
0,7
COMMENTS
These are graphs with n vertices and n edges having at least two cycles in the same component.
FORMULA
a(n) = A001434(n) - A137917(n).
EXAMPLE
The a(0) = 0 through a(6) = 7 simple graphs:
. . . . . {{12}{13}{14}{23}{24}} {{12}{13}{14}{15}{23}{24}}
{{12}{13}{14}{15}{23}{45}}
{{12}{13}{14}{23}{24}{34}}
{{12}{13}{14}{23}{24}{35}}
{{12}{13}{14}{23}{24}{56}}
{{12}{13}{14}{23}{25}{45}}
{{12}{13}{14}{25}{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}], {n}], Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 5}]
CROSSREFS
Without the choice condition we have A001434, covering A006649.
The labeled version without choice is A116508, covering A367863, A367862.
The complement is counted by A137917, labeled A137916.
For any number of edges we have A140637, complement A134964.
For labeled set-systems we have A368600.
The case with loops is A368835, labeled A368596.
The labeled version is A369143, covering A369144.
A006129 counts covering graphs, unlabeled A002494.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable simple graphs, unlabeled A005703.
Sequence in context: A037709 A037611 A171472 * A220720 A024311 A210100
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jan 22 2024
EXTENSIONS
a(25) onwards from Andrew Howroyd, Feb 02 2024
STATUS
approved