A292300 Number of connected graphs with at least 2 and at most n nodes.

1, 3, 9, 30, 142, 995, 12112, 273192, 11989763, 1018690328, 165078520804, 50500986390023, 29053988449238084, 31426435131210480044, 64000986548356386656321, 245935832668632382906184889, 1787577661081567721273106761469, 24637809007060949223043923866443113

Offset

2,2

Comments

Partial sums of A001349 starting at n=2.

See Table 1 of Lauritzen et al.

Links

Table of n, a(n) for n=2..19.

Steffen Lauritzen, Alessandro Rinaldo, and Kayvan Sadeghi, Random Networks, Graphical Models, and Exchangeability, arXiv:1701.08420 [math.ST], 2017.

Prog

(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 A292300(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r, s) for r, s in combinations(p.keys(), 2))+sum((q>>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 sum(sum(mobius(m//d)*c(d) for d in divisors(m, generator=True))//m for m in range(2, n+1)) # Chai Wah Wu, Jul 03 2024

Crossrefs

Cf. A001349.

Sequence in context: A370439 A003604 A357615 * A058148 A031031 A371831

Adjacent sequences: A292297 A292298 A292299 * A292301 A292302 A292303

Keyword

nonn

Author

Eric M. Schmidt, Sep 14 2017

Status

approved