cp's OEIS Frontend

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

%I A327235 #12 Jul 03 2024 01:13:15
%S A327235 1,1,1,1,2,4,14,49,234,1476,15405,307536,12651788,1044977929,
%T A327235 167207997404,50838593828724,29156171171238607,31484900549777534887,
%U A327235 64064043979274771429379,246064055301339083624989655,1788069981480210465772374023323,24641385885409824180500407923934750
%N A327235 Number of unlabeled simple graphs with n vertices whose edge-set is not connected.
%F A327235 a(n) = 1 + A000088(n) - Sum_{i = 1..n} A001349(i).
%e A327235 The a(4) = 2 through a(6) = 14 edge-sets:
%e A327235   {}       {}             {}
%e A327235   {12,34}  {12,34}        {12,34}
%e A327235            {12,35,45}     {12,34,56}
%e A327235            {12,34,35,45}  {12,35,45}
%e A327235                           {12,34,35,45}
%e A327235                           {12,35,46,56}
%e A327235                           {12,36,46,56}
%e A327235                           {13,23,46,56}
%e A327235                           {12,34,35,46,56}
%e A327235                           {12,36,45,46,56}
%e A327235                           {13,23,45,46,56}
%e A327235                           {12,13,23,45,46,56}
%e A327235                           {12,35,36,45,46,56}
%e A327235                           {12,34,35,36,45,46,56}
%o A327235 (Python)
%o A327235 from functools import lru_cache
%o A327235 from itertools import combinations
%o A327235 from fractions import Fraction
%o A327235 from math import prod, gcd, factorial
%o A327235 from sympy import mobius, divisors
%o A327235 from sympy.utilities.iterables import partitions
%o A327235 def A327235(n):
%o A327235     if n == 0: return 1
%o A327235     @lru_cache(maxsize=None)
%o A327235     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 A327235     @lru_cache(maxsize=None)
%o A327235     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A327235     def a(n): return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n if n else 1
%o A327235     return 1+b(n)-sum(a(i) for i in range(1,n+1)) # _Chai Wah Wu_, Jul 03 2024
%Y A327235 Unlabeled non-connected graphs are A000719.
%Y A327235 Partial sums of A327075.
%Y A327235 The labeled version is A327199.
%Y A327235 Cf. A000088, A001349, A002494, A052446, A054592, A327070, A327071.
%K A327235 nonn
%O A327235 0,5
%A A327235 _Gus Wiseman_, Sep 01 2019
%E A327235 a(20)-a(21) from _Chai Wah Wu_, Jul 03 2024