cp's OEIS Frontend

A367142 Number of connected simple graphs on n unlabeled vertices without universal vertices.

%I A367142 #21 Jul 05 2024 09:34:34
%S A367142 1,0,0,0,2,10,78,697,10073,248734,11441903,994695397,163040832612,
%T A367142 50170816696627,28952985431480109,31368326987104006472,
%U A367142 63938133627255371867509,245807830666379498961633640,1787085789384745555957516856804,24634233851674722043622102881490796
%N A367142 Number of connected simple graphs on n unlabeled vertices without universal vertices.
%C A367142 A universal vertex is adjacent to every other vertex.
%H A367142 Chai Wah Wu, <a href="/A367142/b367142.txt">Table of n, a(n) for n = 0..87</a>
%H A367142 Wikipedia, <a href="https://en.wikipedia.org/wiki/Vertex_(graph_theory)">Vertex_(graph_theory)</a>.
%F A367142 a(n) = A001349(n) - A000088(n-1) for n > 0.
%F A367142 a(n) = Sum_{k=2..n-2} A332760(n,k) for n > 0.
%e A367142 The a(4) = 2 graphs are P_4 (path graph) and C_4 (cycle graph).
%o A367142 (Python)
%o A367142 from functools import lru_cache
%o A367142 from itertools import combinations
%o A367142 from fractions import Fraction
%o A367142 from math import prod, gcd, factorial
%o A367142 from sympy import mobius, divisors
%o A367142 from sympy.utilities.iterables import partitions
%o A367142 def A367142(n):
%o A367142     if n == 0: return 1
%o A367142     @lru_cache(maxsize=None)
%o A367142     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 A367142     @lru_cache(maxsize=None)
%o A367142     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A367142     return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n-b(n-1) # _Chai Wah Wu_, Jul 03 2024
%Y A367142 A002494 is the not necessarily connected case.
%Y A367142 Cf. A000088, A001349, A332760, A367143.
%K A367142 nonn
%O A367142 0,5
%A A367142 _Andrew Howroyd_, Nov 06 2023