cp's OEIS Frontend

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

%I A292300 #14 Jul 04 2024 02:24:00
%S A292300 1,3,9,30,142,995,12112,273192,11989763,1018690328,165078520804,
%T A292300 50500986390023,29053988449238084,31426435131210480044,
%U A292300 64000986548356386656321,245935832668632382906184889,1787577661081567721273106761469,24637809007060949223043923866443113
%N A292300 Number of connected graphs with at least 2 and at most n nodes.
%C A292300 Partial sums of A001349 starting at n=2.
%C A292300 See Table 1 of Lauritzen et al.
%H A292300 Steffen Lauritzen, Alessandro Rinaldo, and Kayvan Sadeghi, <a href="https://arxiv.org/abs/1701.08420">Random Networks, Graphical Models, and Exchangeability</a>, arXiv:1701.08420 [math.ST], 2017.
%o A292300 (Python)
%o A292300 from functools import lru_cache
%o A292300 from itertools import combinations
%o A292300 from fractions import Fraction
%o A292300 from math import prod, gcd, factorial
%o A292300 from sympy import mobius, divisors
%o A292300 from sympy.utilities.iterables import partitions
%o A292300 def A292300(n):
%o A292300     @lru_cache(maxsize=None)
%o A292300     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)))
%o A292300     @lru_cache(maxsize=None)
%o A292300     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A292300     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
%Y A292300 Cf. A001349.
%K A292300 nonn
%O A292300 2,2
%A A292300 _Eric M. Schmidt_, Sep 14 2017