A054590 - OEIS

%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