%I #18 Jul 05 2024 18:48:34
%S 0,1,3,19,244,10101,1562298,885237542,1795141933300,13031553571814674,
%T 341286507770733602176,32523592049568306757117737,
%U 11366810480400463340177768296746,14669108426561606778443288692015619955,70315685953531425166863071956073529852161120
%N Number of disconnected digraphs with n unlabeled nodes.
%H Andrew Howroyd, <a href="/A054590/b054590.txt">Table of n, a(n) for n = 1..50</a>
%F a(n) = A000273(n) - A003085(n).
%o (Python)
%o from functools import lru_cache
%o from itertools import product
%o from fractions import Fraction
%o from math import prod, gcd, factorial
%o from sympy import mobius, divisors
%o from sympy.utilities.iterables import partitions
%o def A054590(n):
%o @lru_cache(maxsize=None)
%o def b(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s)<<1 for r,s in combinations(p.keys(),2))+sum(r*(q*r-1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
%o @lru_cache(maxsize=None)
%o def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o return b(n)-sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # _Chai Wah Wu_, Jul 05 2024
%Y The labeled case is A054593.
%Y Cf. A000273, A000719, A003085.
%K nonn
%O 1,3
%A _Vladeta Jovovic_, Apr 14 2000
%E Terms a(14) and beyond from _Andrew Howroyd_, Apr 18 2021