login
Number of digraphs on n labeled nodes with a global source and sink.
5

%I #28 Apr 18 2023 07:37:36

%S 1,2,12,432,64240,33904800,61721081184,394586260943616,

%T 9146766152111641344,792073976107698469670400,

%U 261895415169919230764987845120,335402460348866803020064114666616832,1678893205649791601327398844631544110815232

%N Number of digraphs on n labeled nodes with a global source and sink.

%C This sequence differs from A049524 in that the source and sink are restricted to being single nodes.

%H Andrew Howroyd, <a href="/A350790/b350790.txt">Table of n, a(n) for n = 1..50</a>

%H R. W. Robinson, <a href="http://cobweb.cs.uga.edu/~rwr/publications/components.pdf">Counting digraphs with restrictions on the strong components</a>, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

%F For n >= 3, a(n) = 2*n*(n-1)*A003030(n-1) (Robinson equation 22). - _Geoffrey Critzer_, Apr 17 2023

%t nn = 15; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],

%t Length@# == 2 &][[All, 2]]; s[z_] := Total[strong Table[z^i/i!, {i, 1, 58}]];

%t ggf[egf_] := Normal[Series[egf, {z, 0, nn}]] /. Table[z^i -> z^i/2^Binomial[i, 2], {i, 1, nn + 1}];egf[ggf_] := Normal[Series[ggf, {z, 0, nn}]] /.Table[z^i -> z^i*2^Binomial[i, 2], {i, 1, nn + 1}];Table[n!, {n, 0, nn}] CoefficientList[

%t Series[z - z^2 + Exp[(u - 1) (v - 1) s[ z]] egf[ggf[z Exp[(u - 1) s[z]]]*1/ggf[Exp[-s[z]]]*ggf[z Exp[(v - 1) s[ z]]]] /. {u -> 0, v -> 0}, {z, 0, nn}], z] (* _Geoffrey Critzer_, Apr 17 2023 *)

%o (PARI) InitFinallyV(12) \\ See A350791 for program code.

%Y The unlabeled version is A350794.

%Y Row sums of A350791.

%Y Cf. A049524, A165950, A350792, A003030.

%K nonn

%O 1,2

%A _Andrew Howroyd_, Jan 16 2022