A006129 -id:A006129 - cp's OEIS frontend

A121251 Number of labeled graphs without isolated vertices and with n edges.

1, 1, 6, 62, 900, 16824, 384668, 10398480, 324420840, 11472953760, 453518054216, 19815916826160, 948348447031440, 49334804947402800, 2771902062752597520, 167281797371598801136, 10791777047497882651296, 741135302021991803931360, 53983717302568691555767360

Offset: 0

Vladeta Jovovic, Aug 22 2006, Sep 19 2006

a(n) ~ C0*(C1*n)^n, where C0 = 1/2^(1+log(2)/4)/log(2) = 0.63970540489176946794... and C1 = 2/(log(2))^2/exp(1) = 1.5313857152078346894..., [Bender et al.]

E. A. Bender, E. R. Canfield and B. D. McKay, The asymptotic number of labeled

E. A. Bender and E. R. Canfield and B. D. McKay, The asymptotic number of labeled graphs with n vertices, q edges and no isolated vertices, preprint, 1996.
E. A. Bender, E. R. Canfield and B. D. McKay, The asymptotic number of labeled graphs with n vertices, q edges and no isolated vertices, J Combinatorial Theory, Series A, 80 (1997) 124-150.
Kassahun H. Betre, Yan X. Zhang, and Carter Edmond, Pure Simplicial and Clique Complexes with a Fixed Number of Facets, arXiv:2411.12945 [math.CO], 2024. See p. 23.
A. N. Bhavale, B. N. Waphare, Basic retracts and counting of lattices, Australasian J. of Combinatorics (2020) Vol. 78, No. 1, 73-99.

Cf. A006129.

a(n) = Sum_{m>=0} binomial(binomial(m,2),n)/2^(m+1). Column sums of A054548.

More terms from Max Alekseyev, Aug 23 2006

A322353 Number of factorizations of n into distinct semiprimes; a(1) = 1 by convention.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 2, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 2, 1, 1, 1, 1, 0, 2, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0

Offset: 1

Antti Karttunen, Dec 06 2018

nonn

A semiprime (A001358) is a product of any two prime numbers. In the even case, these factorizations have A001222(n)/2 factors. - Gus Wiseman, Dec 31 2020

Records 1, 2, 3, 4, 5, 9, 13, 15, 17, ... occur at 1, 60, 210, 840, 1260, 4620, 27720, 30030, 69300, ...

			a(4) = 1, as there is just one way to factor 4 into distinct semiprimes, namely as {4}.
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(n) factorizations for n = 60, 210, 840, 1260, 4620, 12600, 18480:
  4*15   6*35    4*6*35    4*9*35    4*15*77    4*6*15*35    4*6*10*77
  6*10   10*21   4*10*21   4*15*21   4*21*55    4*6*21*25    4*6*14*55
         14*15   4*14*15   6*10*21   4*33*35    4*9*10*35    4*6*22*35
                 6*10*14   6*14*15   6*10*77    4*9*14*25    4*10*14*33
                           9*10*14   6*14*55    4*10*15*21   4*10*21*22
                                     6*22*35    6*10*14*15   4*14*15*22
                                     10*14*33                6*10*14*22
                                     10*21*22
                                     14*15*22
(End)

Unlabeled multiset partitions of this type are counted by A007717.
The version for partitions is A112020, or A101048 without distinctness.
The non-strict version is A320655.
Positions of zeros include A320892.
Positions of nonzero terms are A320912.
The case of squarefree factors is A339661, or A320656 without distinctness.
Allowing prime factors gives A339839, or A320732 without distinctness.
A322661 counts loop-graphs, ranked by A320461.
A001055 counts factorizations, with strict case A045778.
A001358 lists semiprimes, with squarefree case A006881.
A027187 counts partitions of even length, ranked by A028260.
A037143 lists primes and semiprimes.
A338898/A338912/A338913 give the prime indices of semiprimes.
A339846 counts even-length factorizations, with ordered version A174725.
Cf. A001221, A006125, A006129, A028260, A320893, A338915, A339841.

Table[Count[Subsets[Select[Divisors[n], PrimeOmega[#] == 2 &]], ?(Times @@ # == n &)], {n, 105}] (* _Michael De Vlieger, Dec 11 2020 *)

A322353(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((2==bigomega(d)&&(d<=m)), s += A322353(n/d, d-1))); (s)); \\ Antti Karttunen, Dec 10 2020

a(n) = Sum_{d|n} (-1)^A001222(d) * A339839(n/d). - Gus Wiseman, Dec 31 2020

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

A369191 Number of labeled simple graphs covering n vertices with at most n edges.

Original entry on oeis.org

1, 0, 1, 4, 34, 387, 5686, 102084, 2162168, 52693975, 1450876804, 44509105965, 1504709144203, 55563209785167, 2224667253972242, 95984473918245388, 4439157388017620554, 219067678811211857307, 11489425098298623161164, 638159082104453330569185

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

Row-sums of left portion of A054548.

			The a(0) = 1 through a(3) = 4 graphs:
  {}  .  {{1,2}}  {{1,2},{1,3}}
                  {{1,2},{2,3}}
                  {{1,3},{2,3}}
                  {{1,2},{1,3},{2,3}}

The minimal case is A053530.
The connected case is A129271, unlabeled version A005703.
The case of equality is A367863, covering case of A367862.
This is the covering case of A369192, or A369193 for covered vertices.
The version for loop-graphs is A369194.
The unlabeled version is A370316.
A001187 counts connected graphs, unlabeled A001349.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A057500 counts connected graphs with n vertices and n edges.
A133686 counts choosable graphs, covering A367869.
A367867 counts non-choosable graphs, covering A367868.
Cf. A000169, A000272, A000666, A001429, A003465, A006649, A143543, A116508, A140638, A322661.

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

Inverse binomial transform of A369193.

A372167 Irregular triangle read by rows where T(n,k) is the number of simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

Original entry on oeis.org

1, 0, 1, 3, 1, 22, 12, 6, 0, 1, 237, 220, 165, 70, 35, 30, 0, 10, 0, 0, 1, 3961, 5460, 5830, 4140, 2805, 2112, 1230, 720, 600, 180, 230, 60, 45, 60, 0, 0, 15, 0, 0, 0, 1, 99900, 191975, 269220, 272055, 240485, 207095, 166005, 121530, 98770, 65905, 48503, 37065, 20055, 17570, 11445, 6552, 4410, 3570, 1680, 1785, 147, 735, 455, 140, 0, 105, 105, 0, 0, 0, 21, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 23 2024

			Triangle begins:
    1
    0
    1
    3    1
   22   12    6    0    1
  237  220  165   70   35   30    0   10    0    0    1
  ...
Row k = 4 counts the following graphs:
  12-34      12-13-14-23  12-13-14-23-24  .  12-13-14-23-24-34
  13-24      12-13-14-24  12-13-14-23-34
  14-23      12-13-14-34  12-13-14-24-34
  12-13-14   12-13-23-24  12-13-23-24-34
  12-13-24   12-13-23-34  12-14-23-24-34
  12-13-34   12-14-23-24  13-14-23-24-34
  12-14-23   12-14-24-34
  12-14-34   12-23-24-34
  12-23-24   13-14-23-34
  12-23-34   13-14-24-34
  12-24-34   13-23-24-34
  13-14-23   14-23-24-34
  13-14-24
  13-23-24
  13-23-34
  13-24-34
  14-23-24
  14-23-34
  14-24-34
  12-13-24-34
  12-14-23-34
  13-14-23-24

Andrew Howroyd, Table of n, a(n) for n = 0..340 (rows 0..10)
Gus Wiseman, All simple graphs covering {1,2,3,4} grouped by number of triangles.

Row sums are A006129, unlabeled A002494.
Row lengths are A050407.
Counting edges instead of triangles gives A054548, unlabeled A370167.
Column k = 0 is A372168 (non-covering A213434), unlabeled A372169.
Covering case of A372170, unlabeled A263340.
Column k = 1 is A372171 (non-covering A372172), unlabeled A372174.
The unlabeled version is A372173.
For all cycles (not just triangles) we have A372175, non-covering A372176.
A001858 counts acyclic graphs, unlabeled A005195.
A006125 counts simple graphs, unlabeled A000088.
A105784 counts acyclic covering graphs, unlabeled A144958.
Cf. A000272, A053530, A121251, A137916, A367868, A369199, A372191.

cys[y_]:=Select[Subsets[Union@@y,{3}], MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Length[cys[#]]==k&]], {n,0,5},{k,0,Binomial[n,3]}]

Inverse binomial transform of columns of A372170.

a(42) onwards from Andrew Howroyd, Dec 29 2024

A372171 Number of labeled simple graphs covering n vertices with a unique triangle.

Original entry on oeis.org

0, 0, 0, 1, 12, 220, 5460, 191975, 9596160, 683389812, 69270116040

Offset: 0

Gus Wiseman, Apr 24 2024

The unlabeled version is A372174.

			The a(4) = 12 graphs:
  12,13,14,23
  12,13,14,24
  12,13,14,34
  12,13,23,24
  12,13,23,34
  12,14,23,24
  12,14,24,34
  12,23,24,34
  13,14,23,34
  13,14,24,34
  13,23,24,34
  14,23,24,34

Column k = 1 of A372167, unlabeled A372173.
For no triangles we have A372168 (non-covering A213434), unlabeled A372169.
The non-covering case is A372172, unlabeled A372194.
The unlabeled version is A372174.
For all cycles (not just triangles) we have A372195, non-covering A372193.
A001858 counts acyclic graphs, unlabeled A005195.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494
A054548 counts labeled covering graphs by edges, unlabeled A370167.
A105784 counts acyclic covering graphs, unlabeled A144958.
A372170 counts graphs by triangles, unlabeled A263340.
A372175 counts covering graphs by cycles, non-covering A372176.
Cf. A000272, A053530, A121251, A137916, A367868, A369199, A372191.

cys[y_]:=Select[Subsets[Union@@y,{3}],MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Union@@#==Range[n]&&Length[cys[#]]==1&]],{n,0,5}]

Inverse binomial transform of A372172.

a(7)-a(10) from Andrew Howroyd, Aug 01 2024

A372173 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

Original entry on oeis.org

1, 0, 1, 1, 1, 4, 1, 1, 0, 1, 7, 5, 4, 2, 2, 1, 0, 1, 0, 0, 1, 24, 16, 23, 12, 15, 8, 7, 4, 4, 1, 3, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 69, 79, 113, 103, 105, 83, 73, 58, 45, 34, 31, 22, 14, 16, 10, 4, 8, 5, 2, 3, 2, 2, 2, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1

Offset: 0

Gus Wiseman, Apr 23 2024

			Triangle begins:
  1
  0
  1
  1 1
  4 1 1 0 1
  7 5 4 2 2 1 0 1 0 0 1

Andrew Howroyd, Table of n, a(n) for n = 0..340 (rows 0..10)
Gus Wiseman, All unlabeled simple graphs covering 5 vertices, grouped by number of triangles.

Row sums are A002494, labeled A006129.
Row lengths are A050407.
The non-covering version is A263340, labeled A372170.
Counting edges instead of triangles gives A370167, labeled A054548.
The labeled version is A372167.
Column k = 0 is A372169, labeled A372168 (non-covering A213434).
Column k = 1 is A372174, labeled A372171.
Column k = 1 is also the covering case of A372194, labeled A372172.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A053530, A137917, A137918, A140637, A144958, A322700, A370169.

a(21) onwards from Andrew Howroyd, Dec 29 2024

A095268 Number of distinct degree sequences among all n-vertex graphs with no isolated vertices.

Original entry on oeis.org

1, 0, 1, 2, 7, 20, 71, 240, 871, 3148, 11655, 43332, 162769, 614198, 2330537, 8875768, 33924859, 130038230, 499753855, 1924912894, 7429160296, 28723877732, 111236423288, 431403470222, 1675316535350, 6513837679610, 25354842100894, 98794053269694, 385312558571890, 1504105116253904, 5876236938019298, 22974847399695092

Offset: 0

Eric W. Weisstein, May 31 2004

nonn

A002494 is the number of graphs on n nodes with no isolated points and A095268 is the number of these graphs having distinct degree sequences.
Now that more terms have been computed, we can see that this is not the self-convolution of any integer sequence. - Paul D. Hanna, Aug 18 2006
Is it true that a(n+1)/a(n) tends to 4? Is there a heuristic argument why this might be true? - Gordon F. Royle, Aug 29 2006
Previous values a(30) = 5876236938019300 from Lorand Lucz, Jul 07 2013 and a(31) = 22974847474172100 from Lorand Lucz, Sep 03 2013 are wrong. New values a(30) and a(31) independently computed Kai Wang and Axel Kohnert. - Vaclav Kotesovec, Apr 15 2016
In the article by A. Iványi, G. Gombos, L. Lucz, T. Matuszka: "Parallel enumeration of degree sequences of simple graphs II" is in the tables on pages 258 and 261 a wrong value a(31) = 22974847474172100, but in the abstract another wrong value a(31) = 22974847474172374. - Vaclav Kotesovec, Apr 15 2016
The asymptotic formula given below confirms that a(n+1)/a(n) tends to 4. - Tom Johnston, Jan 18 2023

			a(4) = 7 because a 4-vertex graph with no isolated vertices can have degree sequence 1111, 2211, 2222, 3111, 3221, 3322 or 3333.
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(3) = 7 sorted degree sequences (empty column indicated by dot):
  ()  .  (1,1)  (2,1,1)  (1,1,1,1)
                (2,2,2)  (2,2,1,1)
                         (2,2,2,2)
                         (3,1,1,1)
                         (3,2,2,1)
                         (3,3,2,2)
                         (3,3,3,3)
For example, the complete graph K_4 has degrees y = (3,3,3,3), so y is counted under a(4). On the other hand, the only half-loop-graphs (up to isomorphism) with degrees y = (4,2,2,1) are: {(1),(1,2),(1,3),(1,4),(2,3)} and {(1),(2),(3),(1,2),(1,3),(1,4)}; and since neither of these is a graph (due to having half-loops), y is not counted under a(4).
(End)

Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Table of n, a(n) for n = 0..1651 (terms 0 through 79 from Kai Wang)
Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Counting graphic sequences via integrated random walks, arXiv:2301.07022 [math.CO], 2023.
A. Iványi, L. Lucz, T. Matuszka and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapiantiae, Inform.4 (2) (2012) 260-288.
A. Iványi, G. Gombos, L. Lucz, and T. Matuszka, Parallel enumeration of degree sequences of simple graphs II, Acta Universitatis Sapientiae, Informatica, Volume 5, Issue 2 (Dec 2013).
A. Iványi, L. Lucz, T. F. Móri and P. Sótér, On Erdős-Gallai and Havel-Hakimi algorithms, Acta Univ. Sapiantiae, Inform. 3 (2) (2011) 230-268.
A. Kohnert, Number of different degree sequences of a graph with no isolated vertices, 2016.
Frank Ruskey, Alley CATs in Search of Good Homes
Kai Wang, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms. But a(30) and a(31) are different.
Eric Weisstein's World of Mathematics, Degree sequence
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

Cf. A002494, A004250, A007721 (analog for connected graphs), A271831.
Counting the same partitions by sum gives A000569.
Allowing isolated nodes gives A004251.
The version with half-loops is A029889, with covering case A339843.
Covering simple graphs are ranked by A309356 and A320458.
Graphical partitions are ranked by A320922.
The version with loops is A339844, with covering case A339845.
A006125 counts simple graphs, with covering case A006129.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A339659 is a triangle counting graphical partitions.
Cf. A007717, A096373, A181819, A320921, A322661, A339559, A339560.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&]]],{n,0,5}] (* Gus Wiseman, Dec 31 2020 *)

a(n) ~ c * 4^n / n^(3/4) for some c > 0. Computational estimates suggest c ≈ 0.074321. - Tom Johnston, Jan 18 2023

Edited by N. J. A. Sloane, Aug 26 2006
More terms from Gordon F. Royle, Aug 21 2006
a(21) and a(22) from Frank Ruskey, Aug 29 2006
a(23) from Frank Ruskey, Aug 31 2006
a(24)-a(29) from Matuszka Tamás, Jan 10 2013
a(30)-a(31) from articles by Kai Wang and Axel Kohnert, Apr 15 2016
a(0) = 1 and a(1) = 0 prepended by Gus Wiseman, Dec 31 2020

A100743 Number of labeled n-vertex graphs without vertices of degree <=1.

Original entry on oeis.org

1, 0, 0, 1, 10, 253, 12068, 1052793, 169505868, 51046350021, 29184353055900, 32122563615242615, 68867440268165982320, 290155715157676330952559, 2417761590648159731258579164, 40013923822242935823157820555477, 1318910080336893719646370269435043184

Offset: 0

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 03 2005

nonn

			From _Gus Wiseman_, Aug 18 2019: (Start)
The a(4) = 10 edge-sets:
  {12,13,24,34}
  {12,14,23,34}
  {13,14,23,24}
  {12,13,14,23,24}
  {12,13,14,23,34}
  {12,13,14,24,34}
  {12,13,23,24,34}
  {12,14,23,24,34}
  {13,14,23,24,34}
  {12,13,14,23,24,34}
(End)

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

Graphs without isolated nodes are A006129.
The connected case is A059166.
Graphs without endpoints are A059167.
Labeled graphs with endpoints are A245797.
The unlabeled version is A261919.
Cf. A095983, A136284, A322395, A327079, A327107, A327227, A327229, A327230.
Cf. A095983, A322395.

m = 13;
egf = Exp[-x + x^2/2]*Sum[2^(n (n-1)/2)*(x/Exp[x])^n/n!, {n, 0, m+1}];
s = egf + O[x]^(m+1);
a[n_] := n!*SeriesCoefficient[s, n];
Table[a[n], {n, 0, m}] (* Jean-François Alcover, Feb 23 2019 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]>1&]],{n,0,4}] (* Gus Wiseman, Aug 18 2019 *)

seq(n)={Vec(serlaplace(exp(-x + x^2/2 + O(x*x^n))*sum(k=0, n, 2^(k*(k-1)/2)*(x/exp(x + O(x^n)))^k/k!)))} \\ Andrew Howroyd, Sep 04 2019

E.g.f.: exp(-x+x^2/2)*(Sum_{n>=0} 2^(n*(n-1)/2)*(x/exp(x))^n/n!). - Vladeta Jovovic, Jan 26 2006
Exponential transform of A059166. - Gus Wiseman, Aug 18 2019
Inverse binomial transform of A059167. - Gus Wiseman, Sep 02 2019

Terms a(14) and beyond from Andrew Howroyd, Sep 04 2019

cp's OEIS Frontend

A121251 Number of labeled graphs without isolated vertices and with n edges.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A322353 Number of factorizations of n into distinct semiprimes; a(1) = 1 by convention.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A369191 Number of labeled simple graphs covering n vertices with at most n edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A372167 Irregular triangle read by rows where T(n,k) is the number of simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A372171 Number of labeled simple graphs covering n vertices with a unique triangle.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A372173 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).