cp's OEIS Frontend

A054590 Number of disconnected digraphs with n unlabeled nodes.

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