A327235
Number of unlabeled simple graphs with n vertices whose edge-set is not connected.
Original entry on oeis.org
1, 1, 1, 1, 2, 4, 14, 49, 234, 1476, 15405, 307536, 12651788, 1044977929, 167207997404, 50838593828724, 29156171171238607, 31484900549777534887, 64064043979274771429379, 246064055301339083624989655, 1788069981480210465772374023323, 24641385885409824180500407923934750
Offset: 0
The a(4) = 2 through a(6) = 14 edge-sets:
{} {} {}
{12,34} {12,34} {12,34}
{12,35,45} {12,34,56}
{12,34,35,45} {12,35,45}
{12,34,35,45}
{12,35,46,56}
{12,36,46,56}
{13,23,46,56}
{12,34,35,46,56}
{12,36,45,46,56}
{13,23,45,46,56}
{12,13,23,45,46,56}
{12,35,36,45,46,56}
{12,34,35,36,45,46,56}
Unlabeled non-connected graphs are
A000719.
-
from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A327235(n):
if n == 0: return 1
@lru_cache(maxsize=None)
def b(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
@lru_cache(maxsize=None)
def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
def a(n): return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n if n else 1
return 1+b(n)-sum(a(i) for i in range(1,n+1)) # Chai Wah Wu, Jul 03 2024
A327237
Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices that, if the isolated vertices are removed, have cut-connectivity k.
Original entry on oeis.org
1, 1, 0, 1, 0, 1, 1, 3, 3, 1, 4, 40, 15, 4, 1, 56, 660, 267, 35, 5, 1, 1031, 18756, 11022, 1862, 90, 6, 1
Offset: 0
Triangle begins:
1
1 0
1 0 1
1 3 3 1
4 40 15 4 1
56 660 267 35 5 1
Row sums without the first column are
A287689.
Cf.
A006125,
A001187,
A013922,
A259862,
A322389,
A326786,
A327070,
A327114,
A327125,
A327127,
A327198.
-
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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],cutConnSys[Union@@#,#]==k&]],{n,0,4},{k,0,n}]
A182100
The number of connected simple labeled graphs with <= n nodes.
Original entry on oeis.org
1, 2, 4, 11, 65, 974, 31744, 2069971, 267270041, 68629753650, 35171000942708, 36024807353574291, 73784587576805254665, 302228602363365451957806, 2475873310144021668263093216, 40564787336902311168400640561099
Offset: 0
From _Gus Wiseman_, Sep 03 2019: (Start)
The a(0) = 1 through a(3) = 11 edge-sets (singletons represent uncovered vertices):
{} {} {} {}
{{1}} {{1}} {{1}}
{{2}} {{2}}
{{1,2}} {{3}}
{{1,2}}
{{1,3}}
{{2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}
(End)
The unlabeled version is
A292300(n) + 1.
-
nn = 15; g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[Exp[x] (Log[g] + 1), {x, 0, nn}], x]
Comments