A369143 -id:A369143 - cp's OEIS frontend

A001429 Number of n-node connected unicyclic graphs.

1, 2, 5, 13, 33, 89, 240, 657, 1806, 5026, 13999, 39260, 110381, 311465, 880840, 2497405, 7093751, 20187313, 57537552, 164235501, 469406091, 1343268050, 3848223585, 11035981711, 31679671920, 91021354454, 261741776369, 753265624291, 2169441973139, 6252511838796

Offset: 3

N. J. A. Sloane

Also unlabeled connected simple graphs with n vertices and n edges. The labeled version is A057500. - Gus Wiseman, Feb 12 2024

			From _Gus Wiseman_, Feb 12 2024: (Start)
Representatives of the a(3) = 1 through a(6) = 13 simple graphs:
  {12,13,23}  {12,13,14,23}  {12,13,14,15,23}  {12,13,14,15,16,23}
              {12,13,24,34}  {12,13,14,23,25}  {12,13,14,15,23,26}
                             {12,13,14,23,45}  {12,13,14,15,23,46}
                             {12,13,14,25,35}  {12,13,14,15,26,36}
                             {12,13,24,35,45}  {12,13,14,23,25,36}
                                               {12,13,14,23,25,46}
                                               {12,13,14,23,45,46}
                                               {12,13,14,23,45,56}
                                               {12,13,14,25,26,35}
                                               {12,13,14,25,35,46}
                                               {12,13,14,25,35,56}
                                               {12,13,14,25,36,56}
                                               {12,13,24,35,46,56}
(End)

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 3..500
Washington G. Bomfim, A picture of the twenty one unicycles with 3,4,5 and 6 vertices
Audace A. V. Dossou-Olory, Graphs and unicyclic graphs with extremal connected subgraphs, arXiv:1812.02422 [math.CO], 2018.
R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy) Includes illustrations for n <= 6.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
S. Karim, J. Sawada, Z. Alamgirz and S. M. Husnine, Generating bracelets with fixed content, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 103-112.
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Marko Riedel et al., Non-isomorphic, connected, unicyclic graphs, Math Stackexchange, November 2018. (Derivation of algorithm and Maple implementation using PET.)
Marko Riedel, Maple implementation using PET.
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points, Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967. doi: 10.2172/4180737.
Eric Weisstein's World of Mathematics, Unicyclic Graph

For at most one cycle we have A005703, labeled A129271, complement A140637.
Next-to-main diagonal of A054924. Cf. A000055.
The labeled version is A057500, connected case of A137916.
This is the connected case of A137917 and A236570.
Row k = 1 of A137918.
The version with loops is A368983.
A001349 counts unlabeled connected graphs.
A001434 and A006649 count unlabeled graphs with # vertices = # edges.
A006129 counts covering graphs, unlabeled A002494.
Cf. A014068, A054548, A116508, A133686, A140638, A369143, A369201.

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];Apply[Plus,Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,3,nn}]]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
(* Second program: *)
TreeGf[nn_] := Module[{A}, A = Table[1, {nn}]; For[n = 1, n <= nn 1, n++, A[[n + 1]] = 1/n * Sum[Sum[ d*A[[d]], {d, Divisors[k]}]*A[[n - k + 1]], {k, 1, n}]]; x A.x^Range[0, nn-1]];
seq[n_] := Module[{t, g}, If[n < 3, {}, t = TreeGf[n - 2]; g[e_] := Normal[t + O[x]^(Quotient[n, e]+1)] /. x -> x^e  + O[x]^(n+1); Sum[Sum[ EulerPhi[d]*g[d]^(k/d), {d, Divisors[k]}]/k + If[OddQ[k], g[1]* g[2]^Quotient[k, 2], (g[1]^2 + g[2])*g[2]^(k/2-1)/2], {k, 3, n}]]/2 // Drop[CoefficientList[#, x], 3]&];
seq[32] (* Jean-François Alcover, Oct 05 2019, after Andrew Howroyd's PARI code *)

\\ TreeGf gives gf of A000081
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={if(n<3, [], my(t=TreeGf(n-2)); my(g(e)=subst(t + O(x*x^(n\e)),x,x^e) + O(x*x^n)); Vec(sum(k=3, n, sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/2))/2))} \\ Andrew Howroyd, May 05 2018

a(n) = A068051(n) - A027852(n) - A000081(n).

More terms from Ronald C. Read
a(27) corrected, more terms, formula from Christian G. Bower, Feb 12 2002
Edited by Charles R Greathouse IV, Oct 05 2009
Terms a(30) and beyond from Andrew Howroyd, May 05 2018

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

Original entry on oeis.org

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

A137917 a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.

Original entry on oeis.org

1, 0, 0, 1, 2, 5, 14, 35, 97, 264, 733, 2034, 5728, 16101, 45595, 129327, 368093, 1049520, 2999415, 8584857, 24612114, 70652441, 203075740, 584339171, 1683151508, 4852736072, 14003298194, 40441136815, 116880901512, 338040071375, 978314772989, 2833067885748, 8208952443400

Offset: 0

Washington Bomfim, Feb 24 2008

nonn

a(n) is the number of simple unlabeled graphs on n nodes whose components have exactly one cycle. - Geoffrey Critzer, Oct 12 2012

Also the number of unlabeled simple graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. - Gus Wiseman, Jan 25 2024

			From _Gus Wiseman_, Jan 25 2024: (Start)
Representatives of the a(0) = 1 through a(5) = 5 simple graphs:
  {}  .  .  {12,13,23}  {12,13,14,23}  {12,13,14,15,23}
                        {12,13,24,34}  {12,13,14,23,25}
                                       {12,13,14,23,45}
                                       {12,13,14,25,35}
                                       {12,13,24,35,45}
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..500
F. Ruskey, Combinatorial Generation, p. 79, Eq.(4.27), 2003
Eric Weisstein's World of Mathematics, Pseudoforest.
Wikipedia, Pseudoforest.

Cf. A008483, A137918.
The connected case is A001429.
Without the choice condition we have A001434, covering A006649.
For any number of edges we have A134964, complement A140637.
The labeled version is A137916.
The version with loops is A369145, complement A368835.
The complement is counted by A369201, labeled A369143, covering A369144.
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.
Cf. A000088, A000612, A007716, A014068, A053530, A116508, A133686, A140638, A368601, A369141, A369146.

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];c=Drop[Apply[Plus,Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,3,nn}]],1];CoefficientList[Series[Product[1/(1-x^i)^c[[i]],{i,1,nn-1}],{x,0,nn}],x]   (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
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}] (* Gus Wiseman, Jan 25 2024 *)

a(n) = Sum_{1*j_1 + 2*j_2 + ... = n} (Product_{i=3..n} binomial(A001429(i) + j_i -1, j_i)). [F. Ruskey p. 79, (4.27) with n replaced by n+1, and a_i replaced by A001429(i)].

Euler transform of A001429. - Geoffrey Critzer, Oct 12 2012

Edited by Washington Bomfim, Jun 27 2012
Terms a(30) and beyond from Andrew Howroyd, May 05 2018
Offset changed to 0 by Gus Wiseman, Jan 27 2024

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

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

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

A369144 Number of labeled simple graphs with n edges 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, 0, 0, 90, 4935, 200970, 7636860, 291089610, 11459170800, 471932476290, 20447369179380, 933942958593645, 44981469288560805, 2282792616992648670, 121924195590795244920, 6843305987751060036720, 403003907531795513467260, 24861219342100679072572470

Offset: 0

Gus Wiseman, Jan 21 2024

nonn

			The term a(6) = 90 counts all permutations of the (non-connected) graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}}.

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

The covering complement is counted by A137916.
Without the choice condition we have A367863, covering case of A116508.
Allowing any number of edges gives A367868, covering case of A367867.
With loops we have A368730, covering case of A368596, unlabeled A368835.
This is the covering case of A369143.
A003465 counts covering set-systems, unlabeled A055621.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A058891 counts set-systems, unlabeled A000612.
A322661 counts covering loop-graphs, connected A062740.
Cf. A000085, A057500, A129271, A133686, A333331, A367869, A367901, A367903, A367907, A368600.

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

a(n) = A367863(n) - A137916(n). - Andrew Howroyd, Feb 02 2024

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

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

Original entry on oeis.org

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

Gus Wiseman, Jan 22 2024

nonn

These are graphs with n vertices and n edges having at least two cycles in the same component.

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

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(6) = 7 unlabeled non-choosable graphs with 6 vertices and 6 edges.

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.
Cf. A000088, A000612, A014068, A053530, A133686, A140638, A368601, 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}],{n}],Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,5}]

a(n) = A001434(n) - A137917(n).

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

cp's OEIS Frontend

A001429 Number of n-node connected unicyclic graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A137917 a(n) is the number of unlabeled graphs on n nodes whose components are unicyclic graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

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