A369146 -id:A369146 - cp's OEIS frontend

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).

0, 0, 0, 0, 2, 13, 95, 826, 11137, 261899, 11729360, 1006989636, 164072166301, 50336940172142, 29003653625802754, 31397431814146891910, 63969589218557753075156, 245871863137828405124380563, 1787331789281458167615190373076, 24636021675399858912682459601585276

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

These are simple graphs covering n vertices such that some connected component has at least two cycles.

			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}

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

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.
Cf. A000088, A000612, A006649, A001434, A055621, A137916, A137917, A140638, A368596, A369141, A369146.

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}]

First differences of A140637.

a(n) = A002494(n) - A368834(n).

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

Original entry on oeis.org

1, 0, 1, 2, 5, 10, 27, 62, 165, 423, 1140, 3060, 8427, 23218, 64782, 181370, 511004, 1444285, 4097996, 11656644, 33243265, 94992847, 271953126, 779790166, 2239187466, 6438039076, 18532004323, 53400606823, 154024168401, 444646510812, 1284682242777

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

			Representatives of the a(2) = 1 through a(5) = 10 simple graphs:
  {12}  {12}{13}      {12}{34}          {12}{13}{45}
        {12}{13}{23}  {12}{13}{14}      {12}{13}{14}{15}
                      {12}{13}{24}      {12}{13}{14}{25}
                      {12}{13}{14}{23}  {12}{13}{23}{45}
                      {12}{13}{24}{34}  {12}{13}{24}{35}
                                        {12}{13}{14}{15}{23}
                                        {12}{13}{14}{23}{25}
                                        {12}{13}{14}{23}{45}
                                        {12}{13}{14}{25}{35}
                                        {12}{13}{24}{35}{45}

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

Without the choice condition we have A002494, labeled A006129.
The connected case is A005703, labeled A129271.
This is the covering case of A134964, complement A140637.
The labeled version is A367869, complement A367868.
The version with loops is A369200, complement A369147.
The complement is counted by A369202.
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.
Cf. A000088, A006649, A001434, A055621, A116508, A133686, A137916, A137917, A368984, A369146.

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}]

Euler transform of A005703 with A005703(1) = 0.
First differences of A134964.
a(n) = A002494(n) - A369202(n).

cp's OEIS Frontend

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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula