A368984 -id:A368984 - cp's OEIS frontend

A137916 Number of n-node labeled graphs whose components are unicyclic graphs.

1, 0, 0, 1, 15, 222, 3670, 68820, 1456875, 34506640, 906073524, 26154657270, 823808845585, 28129686128940, 1035350305641990, 40871383866109888, 1722832666898627865, 77242791668604946560, 3670690919234354407000, 184312149879830557190940, 9751080154504005703189791

Offset: 0

Washington Bomfim, Feb 22 2008

Also the number of labeled simple graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. The version without the choice condition is A116508, covering A367863. - Gus Wiseman, Jan 25 2024

			a(6) = 3670 because A057500(6) = 3660 and two triangles can be labeled in 10 ways.
From _Gus Wiseman_, Jan 25 2024: (Start)
The a(0) = 1 through a(4) = 15 simple graphs:
  {}  .  .  {12,13,23}  {12,13,14,23}
                        {12,13,14,24}
                        {12,13,14,34}
                        {12,13,23,24}
                        {12,13,23,34}
                        {12,13,24,34}
                        {12,14,23,24}
                        {12,14,23,34}
                        {12,14,24,34}
                        {12,23,24,34}
                        {13,14,23,24}
                        {13,14,23,34}
                        {13,14,24,34}
                        {13,23,24,34}
                        {14,23,24,34}
(End)

V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999.

Alois P. Heinz, Table of n, a(n) for n = 0..386 (terms n = 151..200 from Andrew Howroyd)
Eric Weisstein's World of Mathematics, Pseudoforest.
Wikipedia, Pseudoforest.

The connected case is A057500.
Row sums of A106239.
The unlabeled version is A137917.
Diagonal of A144228.
The version with loops appears to be A333331, unlabeled A368984.
Column k = 0 of A368924.
The complement is counted by A369143, unlabeled A369201, covering A369144.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable simple graphs, covering A367869.
A140637 counts unlabeled non-choosable graphs, covering A369202.
A367867 counts non-choosable graphs, covering A367868.
Cf. A001434, A006649, A053530, A116508, A129271, A134964, A140638, A367862, A367863, A369191.

cy:= proc(n) option remember;
       binomial(n-1, 2)*add((n-3)!/(n-2-t)!*n^(n-2-t), t=1..n-2)
     end:
T:= proc(n,k) option remember; `if`(k=0, 1, `if`(k<0 or n T(n,n):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 15 2008

nn = 20; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; Drop[Range[0, nn]! CoefficientList[Series[Exp[Log[1/(1 - t)]/2 - t/2 - t^2/4], {x, 0, nn}], x], 1] (* Geoffrey Critzer, Jan 24 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}] (* Gus Wiseman, Jan 25 2024 *)

A057500(p) = (p-1)! * p^p /2 * sum(k = 3,p, 1/(p^k*(p-k)!)); /* Vladeta Jovovic, A057500. */
F(n,N) = { my(s = 0, K, D, Mc); forpart(P = n, D = Set(P); K = vector(#D);
for(i=1, #D, K[i] = #select(x->x == D[i], Vec(P)));
Mc = n!/prod(i=1,#D, K[i]!);
s += Mc * prod(i = 1, #D, A057500(D[i])^K[i] / ( D[i]!^K[i])) , [3, n], [N, N]); s };
a(n)= {my(N); sum(N = 1, n, F(n,N))};

seq(n)={my(w=lambertw(-x+O(x*x^n))); Vec(serlaplace(exp(-log(1+w)/2 + w/2 - w^2/4)))} \\ Andrew Howroyd, May 18 2021

a(n) = Sum_{N = 1..n} ((n!/N!) * Sum_{n_1 + n_2 + ... + n_N = n} Product_{i = 1..N} ( A057500(n_i) / n_i! ) ). [V. F. Kolchin p. 31, (1.4.2)] replacing numerator terms n_i^(n_i-2) by A057500(n_i).
a(n) = A144228(n,n). - Alois P. Heinz, Sep 15 2008
E.g.f.: exp(B(T(x))) where B(x) = (log(1/(1-x))-x-x^2/2)/2 and T(x) is the e.g.f. for A000169 (labeled rooted trees). - Geoffrey Critzer, Jan 24 2012
a(n) ~ 2^(-1/4)*exp(-3/4)*GAMMA(3/4)*n^(n-1/4)/sqrt(Pi) * (1-7*Pi/(12*GAMMA(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Aug 16 2013
E.g.f.: exp(B(x)) where B(x) is the e.g.f. of A057500. - Andrew Howroyd, May 18 2021

a(0)=1 prepended by Andrew Howroyd, May 18 2021

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.

Original entry on oeis.org

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

A369141 Number of labeled loop-graphs covering a subset of {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 25, 710, 29394, 2051522, 267690539, 68705230758, 35184059906570, 36028789310419722, 73786976083150073999, 302231454897259573627852, 2475880078570549574773324062, 40564819207303333310731978895956, 1329227995784915872613854321228773937

Offset: 0

Gus Wiseman, Jan 20 2024

nonn

Also labeled loop-graphs having at least one connected component containing more edges than vertices.

			The a(0) = 0 through a(3) = 25 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{1,2}}
                         {{1},{3},{1,3}}
                         {{2},{3},{2,3}}
                         {{1},{2},{3},{1,2}}
                         {{1},{2},{3},{1,3}}
                         {{1},{2},{3},{2,3}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,2},{2,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3}}
                         {{1},{3},{1,2},{2,3}}
                         {{1},{3},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3}}
                         {{2},{3},{1,2},{2,3}}
                         {{2},{3},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{2},{1,2},{1,3},{2,3}}
                         {{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{3},{1,2},{2,3}}
                         {{1},{2},{3},{1,3},{2,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3},{2,3}}
                         {{2},{3},{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 A006125, unlabeled A000088.
The case of a unique choice is A088957, unlabeled A087803.
The case without loops is A367867, covering A367868.
For edges of any positive size we have A367903, complement A367902.
For exactly n edges we have A368596, complement A333331 (maybe).
The complement is counted by A368927, covering A369140.
The covering case is A369142.
For n edges and no loops we have A369143, covering A369144.
The unlabeled version is A369146 (covering A369147), complement A369145.
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.
A133686 counts choosable graphs, covering A367869.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
Cf. A000272, A000666, A006649, A062740, A116508, A137916, A368924, A368984, A369194.

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

Binomial transform of A369142.

a(n) = A006125(n + 1) - A368927(n). - Andrew Howroyd, Feb 02 2024

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

A333331 Number of integer points in the convex hull in R^n of parking functions of length n.

Original entry on oeis.org

1, 3, 17, 144, 1623, 22804, 383415, 7501422

Offset: 1

Richard Stanley, Mar 15 2020

It is observed by Gus Wiseman in A368596 and A368730 that this sequence appears to be the complement of those sequences. If this is the case, then a(n) is the number of labeled graphs with loops allowed in which each connected component has an equal number of vertices and edges and the conjectured formula holds. Terms for n >= 9 are expected to be 167341283, 4191140394, 116425416531, ... - Andrew Howroyd, Jan 10 2024
From Gus Wiseman, Mar 22 2024: (Start)
An equivalent conjecture is that a(n) is the number of loop-graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. I call these graphs choosable. For example, the a(3) = 17 choosable loop-graphs are the following (loops shown as singletons):
  {{1},{2},{3}}  {{1},{2},{1,3}}  {{1},{1,2},{1,3}}  {{1,2},{1,3},{2,3}}
                 {{1},{2},{2,3}}  {{1},{1,2},{2,3}}
                 {{1},{3},{1,2}}  {{1},{1,3},{2,3}}
                 {{1},{3},{2,3}}  {{2},{1,2},{1,3}}
                 {{2},{3},{1,2}}  {{2},{1,2},{2,3}}
                 {{2},{3},{1,3}}  {{2},{1,3},{2,3}}
                                  {{3},{1,2},{1,3}}
                                  {{3},{1,2},{2,3}}
                                  {{3},{1,3},{2,3}}
(End)

			For n=2 the parking functions are (1,1), (1,2), (2,1). They are the only integer points in their convex hull. For n=3, in addition to the 16 parking functions, there is the additional point (2,2,2).

R. P. Stanley (Proposer), Problem 12191, Amer. Math. Monthly, 127:6 (2020), 563.

Thomas Selig, The stochastic sandpile model on complete graphs, arXiv:2209.07301 [math.PR], 2022.

All of the following relative references pertain to the conjecture:
The case of unique choice A000272.
The version without the choice condition is A014068, covering A368597.
The case of just pairs A137916.
For any number of edges of any positive size we have A367902.
The complement A368596, covering A368730.
Allowing edges of any positive size gives A368601, complement A368600.
Counting by singletons gives A368924.
For any number of edges we have A368927, complement A369141.
The connected case is A368951.
The unlabeled version is A368984, complement A368835.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
Cf. A000169, A000666, A057500, A062740, A129271, A133686, A367863, A367903, A369146, A369199.

Conjectured e.g.f.: exp(-log(1-T(x))/2 + T(x)/2 - T(x)^2/4) where T(x) = -LambertW(-x) is the e.g.f. of A000169. - Andrew Howroyd, Jan 10 2024

A369142 Number of labeled loop-graphs covering {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 22, 616, 26084, 1885323, 253923163, 66619551326, 34575180977552, 35680008747431929, 73392583275070667841, 301348381377662031986734, 2471956814761854578316988092, 40530184362443276558060719358471, 1328619783326799871747200601484790193

Offset: 0

Gus Wiseman, Jan 20 2024

nonn

Also labeled loop-graphs covering n vertices with at least one connected component containing more edges than vertices.

			The a(0) = 0 through a(3) = 22 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{3},{1,2}}
                         {{1},{2},{3},{1,3}}
                         {{1},{2},{3},{2,3}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,2},{2,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3}}
                         {{1},{3},{1,2},{2,3}}
                         {{1},{3},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3}}
                         {{2},{3},{1,2},{2,3}}
                         {{2},{3},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{2},{1,2},{1,3},{2,3}}
                         {{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{3},{1,2},{2,3}}
                         {{1},{2},{3},{1,3},{2,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3},{2,3}}
                         {{2},{3},{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

The version for a unique choice is A000272, unlabeled A000055.
Without the choice condition we have A006125, unlabeled A000088.
The case without loops is A367868, covering case of A367867.
For exactly n edges we have A368730, covering case of A368596.
The complement is counted by A369140, covering case of A368927.
This is the covering case of A369141.
For n edges and no loops we have A369144, covering A369143.
The unlabeled version is A369147, covering case of A369146.
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 graphs, unlabeled A005703.
A133686 counts choosable graphs, covering A367869.
A322661 counts covering loop-graphs, connected A062740, unlabeled A322700.
A367902 counts choosable set-systems, complement A367903.
Cf. A000666, A003465, A006649, A116508, A137916, A333331, A368600, A368924, A368984, A369145, A369194.

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

Inverse binomial transform of A369141.

a(n) = A322661(n) - A369140(n). - Andrew Howroyd, Feb 02 2024

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

A368835 Number of unlabeled n-edge loop-graphs with at most n vertices such that it is not possible to choose a different vertex from each edge.

Original entry on oeis.org

0, 0, 0, 1, 5, 23, 98, 394, 1560, 6181, 24655, 99701, 410513, 1725725, 7423757, 32729320, 148027044, 687188969, 3275077017, 16022239940, 80431483586, 414094461610, 2185052929580, 11808696690600, 65312048149993, 369408792148714, 2135111662435080, 12601466371445619

Offset: 0

Gus Wiseman, Jan 13 2024

nonn

			Non-isomorphic representatives of the a(4) = 5 loop-graphs:
  {{1,1},{2,2},{3,3},{1,2}}
  {{1,1},{2,2},{1,2},{1,3}}
  {{1,1},{2,2},{1,2},{3,4}}
  {{1,1},{2,2},{1,3},{2,3}}
  {{1,1},{1,2},{1,3},{2,3}}

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

The case of a unique choice is A000081, row sums of A106234.
The labeled version is A368596, covering A368730.
Without the choice condition we have A368598.
The complement is A368984, row sums of A368926.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A014068 counts loop-graphs, unlabeled A000666.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A322661 counts labeled covering half-loop-graphs, connected A062740.
Cf. A116508, A129271, A133686, A137916, A137917, A333331, A367863, A368836, A368924, A368927.

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

a(n) = A368598(n) - A368984(n). - Andrew Howroyd, Jan 14 2024

a(8) onwards from Andrew Howroyd, Jan 14 2024

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

Original entry on oeis.org

1, 1, 4, 23, 193, 2133, 29410, 486602, 9395315, 207341153, 5147194204, 141939786588, 4304047703755, 142317774817901, 5095781837539766, 196403997108015332, 8106948166404074281, 356781439557643998591, 16675999433772328981216, 824952192369049982670686

Offset: 0

Gus Wiseman, Jan 20 2024

nonn

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

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

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

For a unique choice we have A000272, covering case of A088957.
Without the choice condition we have A322661, unlabeled A322700.
For exactly n edges we have A333331 (maybe), complement A368596.
The case without loops is A367869, covering case of A133686.
This is the covering case of A368927.
The complement is counted by A369142, covering case of A369141.
The unlabeled version is the first differences of A369145.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts simple graphs; also loop-graphs if shifted left.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A367862 counts graphs with n vertices and n edges, covering A367863.
Cf. A000169, A000666, A003465, A006649, A062740, A116508, A137916, A368924, A368984, A369194.

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

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

Inverse binomial transform of A368927.
Exponential transform of A369197.
E.g.f.: exp(-x)*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(6) onwards from Andrew Howroyd, Feb 02 2024

A368951 Number of connected labeled graphs with n edges and n vertices and with loops allowed.

Original entry on oeis.org

1, 1, 2, 10, 79, 847, 11436, 185944, 3533720, 76826061, 1880107840, 51139278646, 1530376944768, 49965900317755, 1767387701671424, 67325805434672100, 2747849045156064256, 119626103584870552921, 5533218319763109888000, 270982462739224265922466

Offset: 0

Andrew Howroyd, Jan 10 2024

nonn

Exponential transform appears to be A333331. - Gus Wiseman, Feb 12 2024

			From _Gus Wiseman_, Feb 12 2024: (Start)
The a(0) = 1 through a(3) = 10 loop-graphs:
  {}  {11}  {11,12}  {11,12,13}
            {22,12}  {11,12,23}
                     {11,13,23}
                     {22,12,13}
                     {22,12,23}
                     {22,13,23}
                     {33,12,13}
                     {33,12,23}
                     {33,13,23}
                     {12,13,23}
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Graph Loop.

Cf. A000169, A333331, A063170, A053506.
This is the connected covering case of A014068.
The case without loops is A057500, covering case of A370317.
Allowing any number of edges gives A062740, connected case of A322661.
This is the connected case of A368597.
The unlabeled version is A368983, connected case of A368984.
For at most n edges we have A369197.
A000085 counts set partitions into singletons or pairs.
A006129 counts covering graphs, connected A001187.
Cf. A000272, A000666, A054780, A116508, A136556, A367863, A368600.

egf:= (L-> 1-L/2-log(1+L)/2-L^2/4)(LambertW(-x)):
a:= n-> n!*coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 10 2024

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(-log(1-t)/2 + t/2 - t^2/4 + 1))}

a(n) = A000169(n) + A057500(n) for n > 0.
E.g.f.: 1 - log(1-T(x))/2 + T(x)/2 - T(x)^2/4 where T(x) = -LambertW(-x) is the e.g.f. of A000169.
From Peter Luschny, Jan 10 2024: (Start)
a(n) = (exp(n)*Gamma(n + 1, n) - (n - 1)*n^(n - 1))/(2*n) for n > 0.
a(n) = (1/2)*(A063170(n)/n - A053506(n)) for n > 0.  (End)

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

cp's OEIS Frontend

A137916 Number of n-node labeled graphs whose components are unicyclic graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

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

A369141 Number of labeled loop-graphs covering a subset of {1..n} 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

Extensions

A333331 Number of integer points in the convex hull in R^n of parking functions of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A369142 Number of labeled loop-graphs covering {1..n} 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

Extensions

A368835 Number of unlabeled n-edge loop-graphs with at most n vertices such that it is not possible to choose a different vertex from each edge.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments