A369200 -id:A369200 - cp's OEIS frontend

A368927 Number of labeled loop-graphs covering a subset of {1..n} such that it is possible to choose a different vertex from each edge.

1, 2, 7, 39, 314, 3374, 45630, 744917, 14245978, 312182262, 7708544246, 211688132465, 6397720048692, 210975024924386, 7537162523676076, 289952739051570639, 11949100971787370300, 525142845422124145682, 24515591201199758681892, 1211486045654016217202663

Offset: 0

Gus Wiseman, Jan 15 2024

nonn

These are loop-graphs where every connected component has a number of edges less than or equal to the number of vertices. Also loop-graphs with at most one cycle (unicyclic) in each connected component.

			The a(0) = 1 through a(2) = 7 loop-graphs (loops shown as singletons):
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}

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

Without the choice condition we have A006125.
The case of a unique choice is A088957, unlabeled A087803.
The case without loops is A133686, complement A367867, covering A367869.
For exactly n edges and no loops we have A137916, unlabeled A137917.
For exactly n edges we have A333331 (maybe), complement A368596.
For edges of any positive size we have A367902, complement A367903.
The covering case is A369140, complement A369142.
The complement is counted by A369141.
The complement for n edges and no loops is A369143, covering A369144.
The unlabeled version is A369145, complement A369146.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts labeled covering loop-graphs, connected A062740.
Cf. A000169, A000272, A000666, A014068, A057500, A116508, A367863, A368601, A368924, A368984, A369200.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}]

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(exp(3*t/2 - 3*t^2/4)/sqrt(1-t) ))} \\ Andrew Howroyd, Feb 02 2024

Binomial transform of A369140.
Exponential transform of A369197 with A369197(1) = 2.
E.g.f.: exp(3*T(x)/2 - 3*T(x)^2/4)/sqrt(1-T(x)), where T(x) is the e.g.f. of A000169. - Andrew Howroyd, Feb 02 2024

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

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

Original entry on oeis.org

0, 0, 1, 8, 60, 471, 4911, 78797, 2207405, 113740613, 10926218807, 1956363413115, 652335084532025, 405402273420833338, 470568642161119515627, 1023063423471189429817807, 4178849203082023236054797465, 32168008290073542372004072630072, 468053896898117580623237189882068990

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

			The a(0) = 0 through a(3) = 8 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{1,2}}
                         {{1},{2},{3},{1,2}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

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

Without the choice condition we have A000666, labeled A006125 (shifted).
For a unique choice we have A087803, labeled A088957.
The case without loops is A140637, labeled A367867 (covering A367868).
For exactly n edges we have A368835, labeled A368596.
The labeled complement is A368927, covering A369140.
The labeled version is A369141, covering A369142.
The complement is counted by A369145, covering A369200.
The covering case is A369147.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A129271 counts connected choosable simple graphs, unlabeled A005703.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
Cf. A000088, A000612, A006649, A062740, A134964, A137917, A140638, A368600, A368984, A369199.

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}]], Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,4}]

Partial sums of A369147.

a(n) = A000666(n) - A369145(n). - Andrew Howroyd, Feb 02 2024

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

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

Original entry on oeis.org

1, 2, 5, 12, 30, 73, 185, 467, 1207, 3147, 8329, 22245, 60071, 163462, 448277, 1236913, 3432327, 9569352, 26792706, 75288346, 212249873, 600069431, 1700826842, 4831722294, 13754016792, 39224295915, 112048279650, 320563736148, 918388655873, 2634460759783, 7566000947867

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

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

			The a(0) = 1 through a(3) = 12 loop-graphs (loops shown as singletons):
  {}  {}     {}           {}
      {{1}}  {{1}}        {{1}}
             {{1,2}}      {{1,2}}
             {{1},{2}}    {{1},{2}}
             {{1},{1,2}}  {{1},{1,2}}
                          {{1},{2,3}}
                          {{1,2},{1,3}}
                          {{1},{2},{3}}
                          {{1},{2},{1,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{1,2},{1,3},{2,3}}

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

Without the choice condition we get A000666, labeled A006125 (shifted left).
The case of a unique choice is A087803, labeled A088957.
Without loops we have A134964, labeled A133686 (covering A367869).
For exactly n edges and no loops we have A137917, labeled A137916.
The labeled version is A368927, covering A369140.
The labeled complement is A369141, covering A369142.
For exactly n edges we have A368984, labeled A333331 (maybe).
The complement for exactly n edges is A368835, labeled A368596.
The complement is counted by A369146, labeled A369141 (covering A369142).
The covering case is A369200.
The complement for exactly n edges and no loops is A369201, labeled A369143.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable simple graphs, unlabeled A005703.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
A367867 counts non-choosable labeled graphs, covering A367868.
A368927 counts choosable labeled loop-graphs, covering A369140.
Cf. A000088, A006649, A062740, A140638, A368924, A369194.

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}]], Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]]],{n,0,4}]

Partial sums of A369200.

Euler transform of A369289. - Andrew Howroyd, Feb 02 2024

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

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

Original entry on oeis.org

0, 0, 1, 7, 52, 411, 4440, 73886, 2128608, 111533208, 10812478194, 1945437194308, 650378721118910, 404749938336301313, 470163239887698682289, 1022592854829028310302180, 4177826139658552046624979658, 32163829440870460348768017832607, 468021728889827507080865185809438918

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

			The a(0) = 0 through a(3) = 7 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{3},{1,2}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(3) = 7 unlabeled non-choosable loop-graphs.

Without the choice condition we have A322700, labeled A322661.
The complement for exactly n edges is A368984, labeled A333331 (maybe).
The labeled complement is A369140, covering case of A368927.
The labeled version is A369142, covering case of A369141.
This is the covering case of A369146.
The complement is counted by A369200, covering case of A369145.
Without loops we have A369202, covering case of A140637.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, labeled A006125 (shifted left).
A002494 counts unlabeled covering graphs, labeled A006129.
A007716 counts non-isomorphic multiset partitions, connected A007718.
Cf. A000088, A000612, A005703, A055621, A062740, A134964, A137917, A140638, A367868, A368835, A369199.

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

First differences of A369146.

a(n) = A322700(n) - A369200(n). - Andrew Howroyd, Feb 02 2024

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

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

Original entry on oeis.org

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

A368927 Number of labeled loop-graphs covering a subset of {1..n} such that it is possible to choose a different vertex from each edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula