|
%I M2067 #64 Oct 06 2023 03:26:13
%S 1,2,13,199,9364,1530843,880471142,1792473955306,13026161682466252,
%T 341247400399400765678,32522568098548115377595264,
%U 11366712907233351006127136886487,14669074325902449468573755897547924182
%N Number of weakly connected digraphs with n unlabeled nodes.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 124 and 241.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Keith Briggs, <a href="/A003085/b003085.txt">Table of n, a(n) for n = 1..64</a>
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H Alexander G. Ginsberg, <a href="https://deepblue.lib.umich.edu/handle/2027.42/177859">Firing-Rate Models in Computational Neuroscience: New Applications and Methodologies</a>, Ph. D. Dissertation, Univ. Michigan, 2023. See p. 7.
%H Martin Golubitsky and Yangyang Wang, <a href="https://doi.org/10.1007/s00285-019-01457-x">Infinitesimal homeostasis in three-node input-output networks</a>, Journal of Mathematical Biology (2020) Vol. 80, 1163-1185.
%H A. Iványi, <a href="http://www.emis.de/journals/AUSM/C5-1/math51-5.pdf">Leader election in synchronous networks</a>, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
%H X. Li, D. S. Stones, H. Wang, H. Deng, X. Liu and G. Wang, <a href="http://dx.doi.org/10.1371/journal.pone.0050093">NetMODE: Network Motif Detection without Nauty</a>, PLoS ONE 7(12): e50093. doi:10.1371/journal.pone.0050093. - From _N. J. A. Sloane_, Feb 02 2013
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WeaklyConnectedDigraph.html">Weakly Connected Digraph</a>
%F a(n) = (1/n)*Sum_{d|n} mu(n/d)*A003084(d), where mu is Moebius function.
%F Inverse Euler transform of A000273. - _Andrew Howroyd_, Dec 27 2021
%p # The function EulerInvTransform is defined in A358451.
%p a := EulerInvTransform(A000273):
%p seq(a(n), n = 1..13); # _Peter Luschny_, Nov 21 2022
%t 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 *)
%t terms = 13;
%t 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];
%t edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v - 1];
%t d[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);
%t A003084 = CoefficientList[Log[Sum[d[n] x^n, {n, 0, terms+1}]] + O[x]^(terms + 1), x] Range[0, terms] // Rest;
%t a[n_] := (1/n)*Sum[MoebiusMu[n/d] * A003084[[d]], {d, Divisors[n]}];
%t Table[a[n], {n, 1, terms}] (* _Jean-François Alcover_, Aug 30 2019, after _Andrew Howroyd_ in A003084 *)
%Y Row sums of A054733.
%Y Column sums of A350789.
%Y The labeled case is A003027.
%Y Cf. A000273, A003084, A035512 (strongly connected).
%K nonn,nice
%O 1,2
%A _N. J. A. Sloane_
%E More terms from _Vladeta Jovovic_, Jan 09 2000
|
