A327235 Number of unlabeled simple graphs with n vertices whose edge-set is not connected.

1, 1, 1, 1, 2, 4, 14, 49, 234, 1476, 15405, 307536, 12651788, 1044977929, 167207997404, 50838593828724, 29156171171238607, 31484900549777534887, 64064043979274771429379, 246064055301339083624989655, 1788069981480210465772374023323, 24641385885409824180500407923934750

Offset: 0

Author

Gus Wiseman, Sep 01 2019

Keywords

• nonn

Examples

			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}
		

Crossrefs

Unlabeled non-connected graphs are A000719.

Partial sums of A327075.

The labeled version is A327199.

Cf. A000088, A001349, A002494, A052446, A054592, A327070, A327071.

Programs

Python

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

Formula

a(n) = 1 + A000088(n) - Sum_{i = 1..n} A001349(i).

Extensions

a(20)-a(21) from Chai Wah Wu, Jul 03 2024