A003085 Number of weakly connected digraphs with n unlabeled nodes.

1, 2, 13, 199, 9364, 1530843, 880471142, 1792473955306, 13026161682466252, 341247400399400765678, 32522568098548115377595264, 11366712907233351006127136886487, 14669074325902449468573755897547924182

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

References

• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 124 and 241.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Keith Briggs, Table of n, a(n) for n = 1..64
• P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
• Alexander G. Ginsberg, Firing-Rate Models in Computational Neuroscience: New Applications and Methodologies, Ph. D. Dissertation, Univ. Michigan, 2023. See p. 7.
• Martin Golubitsky and Yangyang Wang, Infinitesimal homeostasis in three-node input-output networks, Journal of Mathematical Biology (2020) Vol. 80, 1163-1185.
• A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
• X. Li, D. S. Stones, H. Wang, H. Deng, X. Liu and G. Wang, NetMODE: Network Motif Detection without Nauty, PLoS ONE 7(12): e50093. doi:10.1371/journal.pone.0050093. - From _N. J. A. Sloane_, Feb 02 2013
• Eric Weisstein's World of Mathematics, Weakly Connected Digraph

Crossrefs

Row sums of A054733.

Column sums of A350789.

The labeled case is A003027.

Cf. A000273, A003084, A035512 (strongly connected).

Programs

Maple

# The function EulerInvTransform is defined in A358451.
a := EulerInvTransform(A000273):
seq(a(n), n = 1..13); # Peter Luschny, Nov 21 2022

Mathematica

Needs["Combinatorica`"]; d[n_] := GraphPolynomial[n, x, Directed] /. x -> 1; max = 13; se = Series[ Sum[a[n]*x^n/n, {n, 1, max}] - Log[1 + Sum[ d[n]*x^n, {n, 1, max}]], {x, 0, max}]; sol = SolveAlways[ se == 0, x]; Do[ A003084[n] = a[n] /. sol[[1]], {n, 1, max}]; ClearAll[a, d]; a[n_] := (1/n)*Sum[ MoebiusMu[ n/d ] * A003084[d], {d, Divisors[n]} ]; Table[ a[n], {n, 1, max}] (* Jean-François Alcover, Feb 01 2012, after formula *)
terms = 13;
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v - 1];
d[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);
A003084 = CoefficientList[Log[Sum[d[n] x^n, {n, 0, terms+1}]] + O[x]^(terms + 1), x] Range[0, terms] // Rest;
a[n_] := (1/n)*Sum[MoebiusMu[n/d] * A003084[[d]], {d, Divisors[n]}];
Table[a[n], {n, 1, terms}] (* Jean-François Alcover, Aug 30 2019, after Andrew Howroyd in A003084 *)

Python

from functools import lru_cache
from itertools import product, combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A003085(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<Chai Wah Wu, Jul 05 2024

Formula

a(n) = (1/n)*Sum_{d|n} mu(n/d)*A003084(d), where mu is Moebius function.

Inverse Euler transform of A000273. - Andrew Howroyd, Dec 27 2021

Extensions

More terms from Vladeta Jovovic, Jan 09 2000