cp's OEIS Frontend

A054918 Number of connected unlabeled digraphs with n nodes such that complement is also connected.

%I A054918 #28 Jul 06 2024 01:34:17
%S A054918 1,1,10,180,9120,1520742,878908844,1791588717764,13024366540532952,
%T A054918 341234368845828951004,32522226812040344643993088,
%U A054918 11366680383641301437820379768750,14669062959091969068110415719779627436
%N A054918 Number of connected unlabeled digraphs with n nodes such that complement is also connected.
%H A054918 Andrew Howroyd, <a href="/A054918/b054918.txt">Table of n, a(n) for n = 1..50</a>
%H A054918 V. A. Liskovets, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/LISK/Derseq.html">Some easily derivable sequences</a>, J. Integer Sequences, 3 (2000), #00.2.2.
%F A054918 a(n) = 2*A003085(n) - A000273(n).
%t A054918 A000273 = Cases[Import["https://oeis.org/A000273/b000273.txt", "Table"], {_, _}][[All, 2]];
%t A054918 A003085 = Cases[Import["https://oeis.org/A003085/b003085.txt", "Table"], {_, _}][[All, 2]];
%t A054918 a[n_] := 2*A003085[[n]] - A000273[[n + 1]];
%t A054918 Array[a, 50] (* _Jean-François Alcover_, Aug 31 2019 *)
%o A054918 (Python)
%o A054918 from functools import lru_cache
%o A054918 from itertools import product, combinations
%o A054918 from fractions import Fraction
%o A054918 from math import prod, gcd, factorial
%o A054918 from sympy import mobius, divisors
%o A054918 from sympy.utilities.iterables import partitions
%o A054918 def A054918(n):
%o A054918     @lru_cache(maxsize=None)
%o A054918     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 A054918     @lru_cache(maxsize=None)
%o A054918     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A054918     return (sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n<<1)-b(n) # _Chai Wah Wu_, Jul 05 2024
%Y A054918 Cf. A000273, A003085.
%K A054918 nonn,easy
%O A054918 1,3
%A A054918 _N. J. A. Sloane_, May 24 2000
%E A054918 More terms from _Vladeta Jovovic_, Jul 19 2000