A143543 -id:A143543 - cp's OEIS frontend

A330345 Number of labeled simple graphs with n vertices whose covered portion has exactly two automorphisms.

0, 0, 1, 6, 42, 700, 16995

Offset: 0

Gus Wiseman, Dec 12 2019

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

The unlabeled version is A330344.
The covering case is A330297.
Covering simple graphs are A006129.
Graphs with exactly two automorphisms are A330297 (labeled covering), A330344 (unlabeled), A330345 (labeled), A330346 (unlabeled covering), A241454 (unlabeled connected).
Cf. A006125, A143543, A330098, A330228, A330230, A330282, A330343.

graprms[m_]:=Union[Table[Sort[Sort/@(m/.Rule@@@Table[{p[[i]],i},{i,Length[p]}])],{p,Permutations[Union@@m]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[graprms[#]]==Length[Union@@#]!/2&]],{n,0,4}]

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

Original entry on oeis.org

0, 0, 0, 1, 19, 307, 5237, 99137, 2098946, 49504458, 1291570014, 37002273654, 1156078150969, 39147186978685, 1428799530304243, 55933568895261791, 2338378885159906196, 103995520598384132516, 4903038902046860966220, 244294315694676224001852, 12827355456239840407125363

Offset: 0

Gus Wiseman, Feb 18 2024

nonn

The case of an empty edge set is excluded.

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

The covering case is A057500, which is also the covering case of A370317.
This is the connected case of A367862, covering A367863.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A062734 counts connected graphs by edge count.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A001429, A006649, A061540, A116508, A323818, A367916, A368951, A369197.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Length[#]==Length[Union@@#] && Length[csm[#]]==1&]],{n,0,5}]

\\ Compare A370317; use A057500 for efficiency.
a(n)=n!*polcoef(polcoef(exp(x*y + O(x*x^n))*(-x+log(sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2)*x^k/k!, O(x*x^n)))), n), n) \\ Andrew Howroyd, Feb 19 2024

Binomial transform of A057500 (if the null graph is not connected).

a(n) = n!*[x^n][y^n] exp(x*y)*(-x + log(Sum_{k>=0} (1 + y)^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Feb 19 2024

A323875 Number of labeled graphs on n nodes with two connected components.

Original entry on oeis.org

0, 1, 3, 19, 230, 5098, 207536, 15891372, 2343580752, 675458276144, 383306076989440, 430041136692146912, 956431386434331323776, 4224539434553753578497024, 37106501188130085159785113344, 648740172906485727983524271405824, 22591360806791558877526051411343415296, 1567817808096346724727108606144936617617408

Offset: 1

Marko Riedel, Feb 05 2019

nonn

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, section 1.2.

Marko Riedel et al., Proof of recurrence relation.
Marko Riedel, Maple implementation of memoized recurrence.

Cf. A143543, A323876, A323877.

a(n) = A143543(n, 2).

E.g.f.: log(Sum_{q>=0} 2^binomial(q, 2)*z^q/q!)^2/2!.

A323876 Number of labeled graphs on n nodes with three connected components.

Original entry on oeis.org

0, 0, 1, 6, 55, 825, 20818, 925036, 76321756, 12143833740, 3786364993664, 2323363153263768, 2810644049356050752, 6714880790313869814368, 31734660624638397560681792, 297106568651256947892439231872, 5516820501457062391874183605225216, 203371936690880564729559424288326233856, 14896201998273652941883043518617399703696384

Offset: 1

Marko Riedel, Feb 05 2019

nonn

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, section 1.2.

Marko Riedel et al., Proof of recurrence relation.
Marko Riedel, Maple implementation of memoized recurrence.

Cf. A143543, A323875, A323877.

a(n) = A143543(n+1, 3) for n >= 1 and a(0) = 0.

E.g.f.: log(Sum_{q>=0} 2^binomial(q, 2)*z^q/q!)^3/3!.

A323877 Number of labeled graphs on n nodes with four connected components.

Original entry on oeis.org

0, 0, 0, 1, 10, 125, 2275, 64673, 3102204, 272277040, 46202044900, 15442093276764, 10171924771814520, 13188852179018387144, 33674263441006260931040, 169522275849148918884400912, 1685048703908907788901122512512, 33116110237646373502366665503208064, 1288337109916947580133035603563656989952, 99320901948403913391024993536094346775110656

Offset: 1

Marko Riedel, Feb 05 2019

nonn

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, section 1.2.

Marko Riedel et al., Proof of recurrence relation.
Marko Riedel, Maple implementation of memoized recurrence.

Cf. A143543, A323875, A323876.

a(n) = A143543(n+1, 4) for n >= 1 and a(0) = 0.

E.g.f.: log(Sum_{q>=0} 2^binomial(q, 2)*z^q/q!)^4/4!.

A330343 Number of labeled fully chiral simple graphs (also called identity or asymmetric graphs) covering n vertices.

Original entry on oeis.org

1, 0, 0, 0, 0, 5760, 766080, 149022720, 48990251520, 28928242022400, 32147584690636800, 69035206021583155200

Offset: 1

Gus Wiseman, Dec 12 2019

In a fully chiral graph, every permutation of the vertices gives a different representative, so the only automorphism is the identity.

The unlabeled version is A003400.
Identity trees are A004111.
Covering simple graphs are A006129.
Full chiral integer partitions are A330228.
Fully chiral factorizations are A330235.
Fully chiral set-systems are A330229 (labeled covering), A330282 (labeled), A330294 (unlabeled), A330295 (unlabeled covering).
Graphs with exactly two automorphisms are A330297 (labeled covering), A330344 (unlabeled), A330345 (labeled), A330346 (unlabeled covering), A241454 (unlabeled connected).
Cf. A006125, A016031, A124059, A143543, A330098, A330224, A330226, A330227, A330230, A330231, A330236.

graprms[m_]:=Union[Table[Sort[Sort/@(m/.Rule@@@Table[{p[[i]],i},{i,Length[p]}])],{p,Permutations[Union@@m]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[graprms[#]]==n!&]],{n,5}] (* brute force, not for computation *)

a(n) = n! * A003400(n).

A226773 Number of ways to select a simple labeled graph on n nodes and then select a subset of its connected components.

Original entry on oeis.org

1, 2, 6, 28, 216, 3008, 82944, 4774912, 575299584, 142633336832, 71796623671296, 72847596766363648, 148448195686743146496, 606392780411924463484928, 4960249711027691772375465984, 81204042297885177526853243502592, 2659755256932431408054237587983826944

Offset: 0

Geoffrey Critzer, Jun 17 2013

nonn

Since almost all such graphs are connected a(n) is asymptotic to 2*A006125.

Alois P. Heinz, Table of n, a(n) for n = 0..81

b:= n-> 2^(n*(n-1)/2):
a:= n-> (t-> add(`if`(j=t, 1, 2)*b(j)*b(n-j)
             *binomial(n, j), j=0..t))(n/2):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 01 2016

nn=15; g=Sum[2^Binomial[n,2] x^n/n!, {n,0,nn}]; Range[0,nn]! CoefficientList[Series[g^2, {x,0,nn}], x]

E.g.f.: A(x)^2 = B(x,y) (evaluated at y = 2) where A(x) is the e.g.f. for A006125 and B(x,y) is the e.g.f. for A143543.

A369827 Number of labeled graphs on 2n nodes with n connected components.

Original entry on oeis.org

1, 1, 19, 825, 64673, 8692845, 2075942407, 947096199049, 871511924986417, 1641139351778666025, 6294238937330719034075, 48874098188760259868846393, 765415330468764867988682358017, 24118078877292963934598044030624645, 1526534496216469250983883702116378352415

Offset: 0

Alois P. Heinz, Feb 02 2024

nonn

All terms are odd.

Alois P. Heinz, Table of n, a(n) for n = 0..79

Cf. A143543.

a(n) = A143543(2n,n).

A360603 Triangle read by rows. T(n, k) = A360604(n, k) * A001187(k) for 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 4, 0, 8, 6, 12, 38, 0, 64, 32, 48, 152, 728, 0, 1024, 320, 320, 760, 3640, 26704, 0, 32768, 6144, 3840, 6080, 21840, 160224, 1866256, 0, 2097152, 229376, 86016, 85120, 203840, 1121568, 13063792, 251548592

Offset: 0

Peter Luschny, Feb 20 2023

			Triangle T(n, k) starts:
[0] 1;
[1] 0,       1;
[2] 0,       1,      1;
[3] 0,       2,      2,     4;
[4] 0,       8,      6,    12,    38;
[5] 0,      64,     32,    48,   152,    728;
[6] 0,    1024,    320,   320,   760,   3640,   26704;
[7] 0,   32768,   6144,  3840,  6080,  21840,  160224,  1866256;
[8] 0, 2097152, 229376, 86016, 85120, 203840, 1121568, 13063792, 251548592.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Algorithms for Competitive Programming, Counting labeled graphs, cp-algorithms.
Albert Nijenhuis and Herbert S Wilf, The enumeration of connected graphs and linked diagrams, Journal of Combinatorial Theory, Vol. 27(3), 1979, Pages 356-359.
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, Labeled Graph.

Cf. A006125 Graphs on n labeled nodes, T(n+1, 1) and Sum_{k=0..n} T(n, k).
Cf. A054592 Disconnected labeled graphs with n nodes, Sum_{k=0..n-1} T(n, k).
Cf. A001187 Connected labeled graphs with n nodes, T(n, n).
Cf. A123903 Isolated nodes in all simple labeled graphs on n nodes, T(n+2, 2).
Cf. A053549 Labeled rooted connected graphs, T(n+1, n).
Cf. A275462 Leaves in all simple labeled connected graphs on n nodes T(n+2, n).
Cf. A060818 gcd_{k=0..n} T(n, k) = gcd(n!, 2^n).
Cf. A143543 Labeled graphs on n nodes with k connected components.
Cf. A095340 Total number of nodes in all labeled graphs on n nodes.
Cf. A360604, A360860 (accumulation triangle).

T := (n, k) -> 2^binomial(n-k, 2)*binomial(n-1, k-1)*A001187(k):
for n from 0 to 9 do seq(T(n, k), k = 0..n) od;
# Based on the recursion:
Trow := proc(n) option remember; if n = 0 then return [1] fi;
seq(2^binomial(n-k, 2) * binomial(n-1, k-1) * Trow(k)[k+1], k = 1..n-1);
2^(n*(n-1)/2) - add(j, j = [%]); [0, %%, %] end:
seq(print(Trow(n)), n = 0..8);

A001187[n_] := A001187[n] = 2^((n - 1)*n/2) - Sum[Binomial[n - 1, k]*2^((k - n + 1)*(k - n + 2)/2)*A001187[k + 1], {k, 0, n - 2}];
T[n_, k_] := 2^Binomial[n - k, 2]*Binomial[n - 1, k - 1]*A001187[k];
Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 02 2023, after Peter Luschny in A001187 *)

from math import comb as binomial
from functools import cache
@cache
def A360603Row(n: int) -> list[int]:
    if n == 0: return [1]
    s = [2 ** (((k - n + 1) * (k - n)) // 2) * binomial(n - 1, k - 1) * A360603Row(k)[k] for k in range(1, n)]
    b = 2 ** (((n - 1) * n) // 2) - sum(s)
    return [0] + s + [b]

T(n, k) = 2^binomial(n-k, 2)*binomial(n-1, k-1) * A001187(k).
Recursion over the rows of the triangle: Set row(0) = [1] where [.] denotes a 0-based list. Assume now all rows(j) for j < n computed, next compute r = [2^binomial(n-k, 2) * binomial(n-1, k-1) * row(k)[k] for k = 1..n-1] and s = 2^(n*(n-1)/2) - Sum(r). Then row(n) = [0] & r & [s], where '&' denotes the concatenation of lists. (See the Python program for an implementation.)
T(n, n) = A001187(n) (connected labeled graphs).
T(n-1, n) = A053549(n-1) for n >= 1 (labeled rooted connected graphs).
T(n, 1) = Sum_{k>=0} T(n-1, k) = A006125(n-1) for n >= 1 (all labeled graphs).
Sum_{k=0..n-1} T(n, k) = A054592(n) for n >= 1 (disconnected labeled graphs).
See additional formulas in the cross-references.

A370319 Triangle read by rows where T(n,k) is the number of labeled graphs with n vertices and k non-isolated vertices.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 0, 3, 4, 1, 0, 6, 16, 41, 1, 0, 10, 40, 205, 768, 1, 0, 15, 80, 615, 4608, 27449, 1, 0, 21, 140, 1435, 16128, 192143, 1887284, 1, 0, 28, 224, 2870, 43008, 768572, 15098272, 252522481, 1, 0, 36, 336, 5166, 96768, 2305716, 67942224, 2272702329, 66376424160

Offset: 0

Gus Wiseman, Feb 18 2024

			Triangle begins:
     1
     1     0
     1     0     1
     1     0     3     4
     1     0     6    16    41
     1     0    10    40   205   768
     1     0    15    80   615  4608 27449
Row n = 3 counts the following edge sets:
  {}  .  {{1,2}}  {{1,2},{1,3}}
         {{1,3}}  {{1,2},{2,3}}
         {{2,3}}  {{1,3},{2,3}}
                  {{1,2},{1,3},{2,3}}

Row sums are A006125, unlabeled A000088.
Column k = n is A006129, unlabeled A002494.
Mirror of A198261, unlabeled A217653.
The unlabeled version is the partial subsequences of A002494.
Cf. A001187, A003465, A006126, A116508, A143543, A287689, A367862.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[Union@@#]==k&]],{n,0,5},{k,0,n}]
Flatten@Table[Binomial[n,k]*Sum[(-1)^(k-m) Binomial[k,m] 2^Binomial[m,2],{m,0,k}],{n,0,10},{k,0,n}] (* Giorgos Kalogeropoulos, Feb 25 2024 *)

T(n,k) = binomial(n,k) * A006129(k).
T(n,n-1) = (n-1) * A006129(n-1).
T(n,k) = A198261(n, n-k). - Andrew Howroyd, Feb 26 2024

More terms from Giorgos Kalogeropoulos, Feb 25 2024

cp's OEIS Frontend

A330345 Number of labeled simple graphs with n vertices whose covered portion has exactly two automorphisms.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A323875 Number of labeled graphs on n nodes with two connected components.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A323876 Number of labeled graphs on n nodes with three connected components.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A323877 Number of labeled graphs on n nodes with four connected components.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A330343 Number of labeled fully chiral simple graphs (also called identity or asymmetric graphs) covering n vertices.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A226773 Number of ways to select a simple labeled graph on n nodes and then select a subset of its connected components.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

Formula

A369827 Number of labeled graphs on 2n nodes with n connected components.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A360603 Triangle read by rows. T(n, k) = A360604(n, k) * A001187(k) for 0 <= k <= n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs