cp's OEIS Frontend

A327075 Number of non-connected unlabeled simple graphs covering n vertices.

%I A327075 #15 Jul 03 2024 01:13:20
%S A327075 1,0,0,0,1,2,10,35,185,1242,13929,292131,12344252,1032326141,
%T A327075 166163019475,50671385831320,29105332577409883,31455744378606296280,
%U A327075 64032559078724993894492,245999991257359808853560276,1787823917424909126688749033668,24639597815428343970034635549911427
%N A327075 Number of non-connected unlabeled simple graphs covering n vertices.
%C A327075 We consider the empty graph to be neither connected (one component) nor disconnected (more than one component).
%H A327075 Gus Wiseman, <a href="/A327075/a327075.png">The a(4) = 1 through a(6) = 10 non-connected covering graphs.</a>
%F A327075 a(n) = A002494(n) - A001349(n), if we assume A001349(0) = A001349(1) = 0.
%e A327075 Non-isomorphic representatives of the a(0) = 1 through a(6) = 10 graphs (empty columns not shown):
%e A327075   {}  {12,34}  {12,35,45}     {12,34,56}
%e A327075                {12,34,35,45}  {12,35,46,56}
%e A327075                               {12,36,46,56}
%e A327075                               {13,23,46,56}
%e A327075                               {12,34,35,46,56}
%e A327075                               {12,36,45,46,56}
%e A327075                               {13,23,45,46,56}
%e A327075                               {12,13,23,45,46,56}
%e A327075                               {12,35,36,45,46,56}
%e A327075                               {12,34,35,36,45,46,56}
%o A327075 (Python)
%o A327075 from functools import lru_cache
%o A327075 from itertools import combinations
%o A327075 from fractions import Fraction
%o A327075 from math import prod, gcd, factorial
%o A327075 from sympy import mobius, divisors
%o A327075 from sympy.utilities.iterables import partitions
%o A327075 def A327075(n):
%o A327075     if n <= 1: return 1-n
%o A327075     @lru_cache(maxsize=None)
%o A327075     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 A327075     @lru_cache(maxsize=None)
%o A327075     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A327075     return b(n)-b(n-1)-sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # _Chai Wah Wu_, Jul 03 2024
%Y A327075 Column k = 0 of A327201.
%Y A327075 The labeled version is A327070.
%Y A327075 Disconnected graphs are A000719.
%Y A327075 Cf. A000088, A001187, A001349, A002494, A006129, A054592.
%K A327075 nonn
%O A327075 0,6
%A A327075 _Gus Wiseman_, Aug 26 2019
%E A327075 a(20)-a(21) from _Chai Wah Wu_, Jul 03 2024