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
A052444
Number of simple unlabeled n-node graphs of connectivity 3.
Original entry on oeis.org
0, 0, 0, 1, 2, 13, 111, 2004, 66410, 3902344, 388624106, 65142804740
Offset: 1
A054590
Number of disconnected digraphs with n unlabeled nodes.
Original entry on oeis.org
0, 1, 3, 19, 244, 10101, 1562298, 885237542, 1795141933300, 13031553571814674, 341286507770733602176, 32523592049568306757117737, 11366810480400463340177768296746, 14669108426561606778443288692015619955, 70315685953531425166863071956073529852161120
Offset: 1
-
from functools import lru_cache
from itertools import product
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A054590(n):
@lru_cache(maxsize=None)
def b(n): return int(sum(Fraction(1<Chai Wah Wu, Jul 05 2024
A139415
Number of preferential arrangements (or hierarchical orderings) on the disconnected graphs on n unlabeled nodes.
Original entry on oeis.org
0, 0, 2, 8, 40, 208, 1408, 12224, 157312, 3478528, 147761664, 12592434176, 2112188653568, 680441850810368, 415073848421801984, 476853486273606582272, 1030736815796444156755968, 4196432048875514376435007488, 32243698461915435195120257335296
Offset: 0
For n=3 we have A139415(3) = 8 because:
There A000719 (3)=2 disconnected graphs for n=3 unlabeled elements:
Three disconnected points
o o o
and
one point plus a two-point chain
o o-o.
The three disconnected points give us 011782(3) = 4 arrangements:
o o o,
-----
o
o o,
-----
o o
o,
-----
o
o
o.
The point plus the two-point chain provides us with 4 arrangements:
o o-o,
-----
o-o
o,
-----
o
o-o,
-----
o
|
o o.
This gives us 8 hierarchical orderings.
(See A136722 for the two connected graphs for n=3, these are the three-point chain and the triangle.)
-
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 A139415(n):
if n == 0: return 0
@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))
return b(n)-sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n<Chai Wah Wu, Jul 03 2024