A137916 -id:A137916 - cp's OEIS frontend

A133686 Number of labeled n-node graphs with at most one cycle in each connected component.

1, 1, 2, 8, 57, 608, 8524, 145800, 2918123, 66617234, 1704913434, 48300128696, 1499864341015, 50648006463048, 1847622972848648, 72406232075624192, 3033607843748296089, 135313823447621913500, 6402077421524339766058, 320237988317922139148736

Offset: 0

Washington Bomfim, May 12 2008

The total number of those graphs of order 5 is 608. The number of forests of trees on n labeled nodes of order 5 is 291, so the majority of the graphs of that kind have one or more unicycles.

Also the number of labeled graphs with n vertices satisfying a strict version of the axiom of choice. The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once. The connected case is A129271, complement A140638. The unlabeled version is A134964. - Gus Wiseman, Dec 22 2023

			Below we see the 7 partitions of n=5 in the form c_1 + 2c_2 + ... + nc_n followed by the corresponding number of graphs. We consider the values of A129271(j) given by the table
   j|1|2|3| 4|  5|
----+-+-+-+--+---+
a(j)|1|1|4|31|347|
1*5 -> 5!1^5 / (1!^5 * 5!) = 1
2*1 + 1*3 -> 5!1^1 * 1^3 / (2!^1 * 1! * 1!^3 * 3!) = 10
2*2 + 1*1 -> 5!1^2 * 1^1 / (2!^2 * 2! * 1!^1 * 1!) = 15
3*1 + 1*2 -> 5!4^1 * 1^2 / (3!^1 * 1! * 1!^2 * 2!) = 40
3*1 + 2*1 -> 5!4^1 * 1^1 / (3!^1 * 1! * 2!^1 * 1!) = 40
4*1 + 1*1 -> 5!31^1 * 1^1 / (4!^1 * 1! * 1!^1 * 1!) = 155
5*1 -> 5!347^1 / (5!^1 * 1!) = 347
Total 608

Alois P. Heinz, Table of n, a(n) for n = 0..386
Wikipedia, Pseudoforest

Cf. A129137, A005703, A000272, A057500, A137916, A001858.
Row sums of triangle A144228. - Alois P. Heinz, Sep 15 2008
Cf. A137352. - Vladeta Jovovic, Sep 16 2008
The unlabeled version is A134964.
The complement is counted by A367867, covering A367868, connected A140638.
The covering case is A367869, connected A129271.
For set-systems we have A367902, ranks A367906.
The complement for set-systems is A367903, ranks A367907.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A143543 counts graphs by number of connected components.
Cf. A001187, A058891, A116508, A355740, A367769, A367770, A367863, A367901.

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 then 1
    elif k<0 or n add(T(n,k), k=0..n):
seq(a(n), n=0..20); # Alois P. Heinz, Sep 15 2008

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[ Exp[t/2-3t^2/4]/(1-t)^(1/2),{x,0,nn}],x] (* Geoffrey Critzer, Sep 05 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Select[Tuples[#], UnsameQ@@#&]!={}&]],{n,0,5}] (* Gus Wiseman, Dec 22 2023 *)

x='x+O('x^50); Vec(serlaplace(sqrt(-lambertw(-x)/(x*(1+ lambertw(-x))))*exp(-(3/4)*lambertw(-x)^2))) \\ G. C. Greubel, Nov 16 2017

a(0) = 1; for n >=1, a(n) = Sum of n!prod_{j=1}^n\{ frac{ A129271(j)^{c_j} } { j!^{c_j}c_j! } } over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0.
a(n) = Sum_{k=0..n} A144228(n,k). - Alois P. Heinz, Sep 15 2008
E.g.f.: sqrt(-LambertW(-x)/(x*(1+LambertW(-x))))*exp(-3/4 * LambertW(-x)^2). - Vladeta Jovovic, Sep 16 2008
E.g.f.: A(x)*B(x) where A(x) is the e.g.f. for A137916 and B(x) is the e.g.f. for A001858. - Geoffrey Critzer, Mar 23 2013
a(n) ~ 2^(-1/4) * Gamma(3/4) * exp(-1/4) * n^(n-1/4) / sqrt(Pi) * (1-7*Pi/(12*Gamma(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Oct 08 2013
E.g.f.: exp(B(x) - 1) where B(x) is the e.g.f. of A129271. - Andrew Howroyd, Dec 30 2023

Corrected and extended by Alois P. Heinz and Vladeta Jovovic, Sep 15 2008

A001858 Number of forests of trees on n labeled nodes.

Original entry on oeis.org

1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616

Offset: 0

N. J. A. Sloane and Simon Plouffe

The number of integer lattice points in the permutation polytope of {1,2,...,n}. - Max Alekseyev, Jan 26 2010
Equals the number of score sequences for a tournament on n vertices. See Prop. 7 of the article by Bartels et al., or Example 3.1 in the article by Stanley. - David Radcliffe, Aug 02 2022
Number of labeled acyclic graphs on n vertices. The unlabeled version is A005195. The covering case is A105784, connected A000272. - Gus Wiseman, Apr 29 2024

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of the a(4) = 38 forests:
  {}  {12}  {12,13}  {12,13,14}
      {13}  {12,14}  {12,13,24}
      {14}  {12,23}  {12,13,34}
      {23}  {12,24}  {12,14,23}
      {24}  {12,34}  {12,14,34}
      {34}  {13,14}  {12,23,24}
            {13,23}  {12,23,34}
            {13,24}  {12,24,34}
            {13,34}  {13,14,23}
            {14,23}  {13,14,24}
            {14,24}  {13,23,24}
            {14,34}  {13,23,34}
            {23,24}  {13,24,34}
            {23,34}  {14,23,24}
            {24,34}  {14,23,34}
                     {14,24,34}
(End)

B. Bollobas, Modern Graph Theory, Springer, 1998, p. 290.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..388 (first 101 terms from T. D. Noe)
J. E. Bartels, J. Mount, and D. J. A. Welsh, The polytope of win vectors. Annals of Combinatorics 1, 1-15 (1997). https://doi.org/10.1007/BF02558460
David Callan, A Combinatorial Derivation of the Number of Labeled Forests, J. Integer Seqs., Vol. 6, 2003.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.o
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 132.
Samuele Giraudo, Combalgebraic structures on decorated cliques, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 7, arXiv:1709.08416 [math.CO], 2017.
Anton Izosimov, Matrix polynomials, generalized Jacobians, and graphical zonotopes, arXiv:1506.05179 [math.AG], 2015.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See pp. 32-33.
Arun P. Mani and Rebecca J. Stones, Congruences for weighted number of labeled forests, INTEGERS 16 (2016). #A17.
J. Pitman, Coalescent Random Forests, J. Combin. Theory, A85 (1999), 165-193.
J. Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.
J. Riordan, Letter to N. J. A. Sloane, Oct 19 1970
J. Riordan, Letter to N. J. A. Sloane, Nov 10 1975
John Riordan and N. J. A. Sloane, Correspondence, 1974
N. J. A. Sloane, Letter to J. Riordan, Nov. 1970
R. Stanley, Decompositions of rational convex polytopes, Ann. Discrete Math 6.6 (1980): 333-342.
L. Takacs, On the number of distinct forests, SIAM J. Discrete Math., 3 (1990), 574-581.
E. M. Wright, A relationship between two sequences, Proc. London Math. Soc. (3) 17 (1967) 296-304.
Index entries for sequences related to forests

The connected case is A000272, rooted A000169.
The unlabeled version is A005195, connected A000055.
The covering case is A105784, unlabeled A144958.
Row sums of A138464.
For triangles instead of cycles we have A213434, covering A372168.
For a unique cycle we have A372193, covering A372195.
A002807 counts cycles in a complete graph.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A006572, A006573, A088956.
Cf. A053530, A054548, A137916, A263340, A322661, A367863, A372176.

exp(x+x^2+add(n^(n-2)*x^n/n!, n=3..50));
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      binomial(n-1, j-1)*j^(j-2)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Sep 15 2008
# third Maple program:
F:= exp(-LambertW(-x)*(1+LambertW(-x)/2)):
S:= series(F,x,51):
seq(coeff(S,x,j)*j!, j=0..50); # Robert Israel, May 21 2015

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[Exp[t-t^2/2],{x,0,nn}],x] (* Geoffrey Critzer, Sep 05 2012 *)
nmax = 20; CoefficientList[Series[-LambertW[-x]/(x*E^(LambertW[-x]^2/2)), {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jul 19 2019 *)

a(n)=if(n<0,0,sum(m=0,n,sum(j=0,m,binomial(m,j)*binomial(n-1,n-m-j)*n^(n-m-j)*(m+j)!/(-2)^j)/m!)) /* Michael Somos, Aug 22 2002 */

E.g.f.: exp( Sum_{n>=1} n^(n-2)*x^n/n! ). This implies (by a theorem of Wright) that a(n) ~ exp(1/2)*n^(n-2). - N. J. A. Sloane, May 12 2008 [Corrected by Philippe Flajolet, Aug 17 2008]
E.g.f.: exp(T - T^2/2), where T = T(x) = Sum_{n>=1} n^(n-1)*x^n/n! is Euler's tree function (see A000169). - Len Smiley, Dec 12 2001
Shifts 1 place left under the hyperbinomial transform (cf. A088956). - Paul D. Hanna, Nov 03 2003
a(0) = 1, a(n) = Sum_{j=0..n-1} C(n-1,j) (j+1)^(j-1) a(n-1-j) if n>0. - Alois P. Heinz, Sep 15 2008

More terms from Michael Somos, Aug 22 2002

A001429 Number of n-node connected unicyclic graphs.

Original entry on oeis.org

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

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

A088957 Hyperbinomial transform of the sequence of 1's.

Original entry on oeis.org

1, 2, 6, 29, 212, 2117, 26830, 412015, 7433032, 154076201, 3608522954, 94238893883, 2715385121740, 85574061070045, 2928110179818478, 108110945014584623, 4284188833355367440, 181370804507130015569, 8169524599872649117330, 390114757072969964280163

Offset: 0

Paul D. Hanna, Oct 26 2003

nonn

See A088956 for the definition of the hyperbinomial transform.
a(n) is the number of partial functions on {1,2,...,n} that are endofunctions with no cycles of length > 1.  The triangle A088956 classifies these functions according to the number of undefined elements in the domain.  The triangle A144289 classifies these functions according to the number of edges in their digraph representation (considering the empty function to have 1 edge).  The triangle A203092 classifies these functions according to the number of connected components. - Geoffrey Critzer, Dec 29 2011
a(n) is the number of rooted subtrees (for a fixed root) in the complete graph on n+1 vertices: a(3) = 29 is the number of rooted subtrees in K_4: 1 of size 1, 3 of size 2, 9 of size 3, and 16 spanning subtrees. - Alex Chin, Jul 25 2013 [corrected by Marko Riedel, Mar 31 2019]
From Gus Wiseman, Jan 28 2024: (Start)
Also the number of labeled loop-graphs on n vertices such that it is possible to choose a different vertex from each edge in exactly one way. For example, the a(3) = 29 uniquely choosable loop-graphs (loops shown as singletons) are:
  {}  {1}  {1,2}  {1,12}   {1,2,13}  {1,12,13}
      {2}  {1,3}  {1,13}   {1,2,23}  {1,12,23}
      {3}  {2,3}  {2,12}   {1,3,12}  {1,13,23}
                  {2,23}   {1,3,23}  {2,12,13}
                  {3,13}   {2,3,12}  {2,12,23}
                  {3,23}   {2,3,13}  {2,13,23}
                  {1,2,3}            {3,12,13}
                                     {3,12,23}
                                     {3,13,23}
(End)

			a(5) = 2117 = 1296 + 625 + 160 + 30 + 5 + 1 = sum of row 5 of triangle A088956.

Alois P. Heinz, Table of n, a(n) for n = 0..387
Marko Riedel et al., Proof of e.g.f. of sequence.

Cf. A088956 (triangle).
Row sums of A144289. - Alois P. Heinz, Jun 01 2009
Cf. A086331, A000169.
Column k=1 of A144303. - Alois P. Heinz, Oct 30 2012
The covering case is A000272, also the case of exactly n edges.
Without the choice condition we have A006125 (shifted left).
The unlabeled version is A087803.
The choosable version is A368927, covering A369140, loopless A133686.
The non-choosable version is A369141, covering A369142, loopless A367867.
Cf. A000081, A000085, A057500, A062740, A137916, A277473, A322661, A367904, A368596, A368597, A368924.

a088957 = sum . a088956_row  -- Reinhard Zumkeller, Jul 07 2013

a:= n-> add((n-j+1)^(n-j-1)*binomial(n,j), j=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Oct 30 2012

nn = 16; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}];
Range[0, nn]! CoefficientList[Series[Exp[x] Exp[t], {x, 0, nn}], x]  (* Geoffrey Critzer, Dec 29 2011 *)
With[{nmax = 50}, CoefficientList[Series[-LambertW[-x]*Exp[x]/x, {x, 0, nmax}], x]*Range[0, nmax]!] (* G. C. Greubel, Nov 14 2017 *)

x='x+O('x^10); Vec(serlaplace(-lambertw(-x)*exp(x)/x)) \\ G. C. Greubel, Nov 14 2017

a(n) = Sum_{k=0..n} (n-k+1)^(n-k-1)*C(n, k).
E.g.f.: A(x) = exp(x+sum(n>=1, n^(n-1)*x^n/n!)).
E.g.f.: -LambertW(-x)*exp(x)/x. - Vladeta Jovovic, Oct 27 2003
a(n) ~ exp(1+exp(-1))*n^(n-1). - Vaclav Kotesovec, Jul 08 2013
Binomial transform of A000272. - Gus Wiseman, Jan 25 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

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

A001434 Number of graphs with n nodes and n edges.

Original entry on oeis.org

1, 0, 0, 1, 2, 6, 21, 65, 221, 771, 2769, 10250, 39243, 154658, 628635, 2632420, 11353457, 50411413, 230341716, 1082481189, 5228952960, 25945377057, 132140242356, 690238318754, 3694876952577, 20252697246580, 113578669178222, 651178533855913, 3813856010041981

Offset: 0

N. J. A. Sloane

The labeled version is A116508. - Gus Wiseman, Feb 22 2024

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

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
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 = 0..50 (terms 1..40 from Sean A. Irvine)
CombOS - Combinatorial Object Server, Generate graphs
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.

The connected case is A001429, labeled A057500.
The covering case is A006649, labeled A367863.
Diagonal n = k of A008406.
The labeled version is A116508.
The version with loops is A368598, connected A368983.
Allowing up to n edges gives A370315, labeled A369192.
A000088 counts unlabeled graphs, labeled A006125.
A001349 counts unlabeled connected graphs, labeled A001187.
A002494 counts unlabeled covering graphs, labeled A006129.
Cf. A000055, A005703, A014068, A054924, A137916, A137917, A236570, A369201.

(* first do *) Needs["Combinatorica`"] (* then *) Table[ NumberOfGraphs[n, n], {n, 24}] (* Robert G. Wilson v, Mar 22 2011 *)
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 /@ Subsets[Subsets[Range[n],{2}],{n}]]],{n,0,5}] (* Gus Wiseman, Feb 22 2024 *)

a(n) = polcoef(G(n, O(x*x^n)), n) \\ G defined in A008406. - Andrew Howroyd, Feb 02 2024

More terms from Vladeta Jovovic, Jan 07 2000

a(0)=1 prepended by Andrew Howroyd, Feb 02 2024

cp's OEIS Frontend

A218696 Number of components over all graphs on n labeled nodes with unicyclic components (graphs counted by A137916).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A133686 Number of labeled n-node graphs with at most one cycle in each connected component.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A001858 Number of forests of trees on n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A001429 Number of n-node connected unicyclic graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

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

A088957 Hyperbinomial transform of the sequence of 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

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.