A049524 -id:A049524 - cp's OEIS frontend

A003028 Number of digraphs on n labeled nodes with a source.

1, 3, 51, 3614, 991930, 1051469032, 4366988803688, 71895397383029040, 4719082081411731363408, 1237678715644664931691596416, 1297992266840866792981316221144960, 5444416466164313011147841248189209354496, 91343356480627224177654291875698256656613808896

Offset: 1

N. J. A. Sloane

Here a source is a node that is connected by a directed path to every other node in the digraph (but does not necessarily have indegree zero). - Geoffrey Critzer, Apr 14 2023

V. Jovovic and G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996) 237-247.
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

The unlabeled version is A051421.
Row sums of A057274.
Column k=1 of A361579.
Cf. A003027, A003029, A003030, A049524, A049414, A350792.

Initially(12) \\ See A057274. - Andrew Howroyd, Jan 11 2022

Corrected and extended by Vladeta Jovovic, Goran Kilibarda

Terms a(12) and beyond from Andrew Howroyd, Jan 11 2022

A049531 Number of digraphs with a source and a sink on n unlabeled nodes.

Original entry on oeis.org

1, 2, 11, 173, 8675, 1483821, 870901739, 1786098545810, 13011539185371716, 341128981258340797839, 32519138088689298538132027, 11366354205366488038532562993809, 14668937734550708660348161757913398001, 70315451107713339843384354196009678853303102

Offset: 1

Vladeta Jovovic, Goran Kilibarda

Here a source is defined to be a node which has a directed path to all other nodes and a sink to be a node to which all other nodes have a directed path. A digraph with a source and a sink can also be described as initially-finally connected. - Andrew Howroyd, Jan 01 2022

V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), p. 246.

Andrew Howroyd, Table of n, a(n) for n = 1..50

Row sums of A057278.
The labeled version is A049524.
Cf. A003085, A035512, A003088, A051421, A345258, A350794.

\\ See PARI link in A350794 for program code.
A049531seq(15) \\ Andrew Howroyd, Jan 21 2022

a(6)-a(7) from Andrew Howroyd, Jan 01 2022

Terms a(8) and beyond from Andrew Howroyd, Jan 20 2022

A057271 Triangle T(n,k) of number of digraphs with a source and a sink on n labeled nodes and k arcs, k=0,1,..,n*(n-1).

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 6, 20, 15, 6, 1, 0, 0, 0, 24, 234, 672, 908, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 120, 2544, 16880, 55000, 111225, 161660, 183006, 167660, 125945, 77520, 38760, 15504, 4845, 1140, 190, 20, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle starts:
[1] 1;
[2] 0,2,1;
[3] 0,0,6,20,15,6,1;
[4] 0,0,0,24,234,672,908,792,495,220,66,12,1;
  ...
The number of digraphs with a source and a sink on 3 labeled nodes is 48 = 6+20+15+6+1.

V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), p. 245.

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

Row sums give A049524.
The unlabeled version is A057278.
Cf. A057272, A057273, A057274, A057275, A062735, A350791.

\\ Following Eqn 20 in the Robinson reference.
Z(p,f)={my(n=serprec(p,x)); serconvol(p, sum(k=0, n-1, x^k*f(k), O(x^n)))}
G(e,p)={Z(p, k->1/e^(k*(k-1)/2))}
U(e,p)={Z(p, k->e^(k*(k-1)/2))}
DigraphEgf(n,e)={sum(k=0, n, e^(k*(k-1))*x^k/k!, O(x*x^n) )}
StrongD(n,e=2)={-log(U(e, 1/G(e, DigraphEgf(n, e))))}
InitFinally(n, e=2)={my(S=StrongD(n, e)); Vec(serlaplace( S - S^2 + exp(S) * U(e, G(e, S*exp(-S))^2*G(e, DigraphEgf(n,e))) ))}
row(n)={Vecrev(InitFinally(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 16 2022

A003029 Number of unilaterally connected digraphs with n labeled nodes.

Original entry on oeis.org

1, 3, 48, 3400, 955860, 1034141596, 4340689156440, 71756043154026904, 4716284688998245793376, 1237457313794197125403483936, 1297922676419612772784598299454784, 5444329780242560941321703550018388707904, 91342929096228825123968637168641318872709897472

Offset: 1

N. J. A. Sloane

V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), 237-247.
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

The unlabeled version is A003088.
Row sums of A057275.
Cf. A003027, A003028, A003030, A049524, A049414.

Unilaterally(12) \\ See A057275. - Andrew Howroyd, Jan 19 2022

Corrected and extended by Vladeta Jovovic, Goran Kilibarda

Terms a(12) and beyond from Andrew Howroyd, Jan 11 2022

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

Original entry on oeis.org

1, 2, 12, 432, 64240, 33904800, 61721081184, 394586260943616, 9146766152111641344, 792073976107698469670400, 261895415169919230764987845120, 335402460348866803020064114666616832, 1678893205649791601327398844631544110815232

Offset: 1

Andrew Howroyd, Jan 16 2022

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 1..50
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

The unlabeled version is A350794.
Row sums of A350791.
Cf. A049524, A165950, A350792, A003030.

nn = 15; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[z_] := Total[strong Table[z^i/i!, {i, 1, 58}]];
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[
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 *)

InitFinallyV(12) \\ See A350791 for program code.

For n >= 3, a(n) = 2*n*(n-1)*A003030(n-1) (Robinson equation 22). - Geoffrey Critzer, Apr 17 2023

A165950 Number of acyclic digraphs on n labeled nodes with one source and one sink.

Original entry on oeis.org

1, 2, 12, 216, 10600, 1306620, 384471444, 261548825328, 402632012394000, 1381332938730123060, 10440873023366019273820, 172308823347127690038311496, 6163501139185639837183141411320, 474942255590583211554917995123517868, 78430816994991932467786587093292327531620

Offset: 1

Vladeta Jovovic, Oct 01 2009

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Antoine Genitrini, Martin Pépin, and Alfredo Viola, Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling, hal-03029381 [math.CO], [cs.DM], [cs.DS], 2020.
Ira Gessel, Counting Acyclic Digraphs by Sources and Sinks
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

The unlabeled version is A345258.

Cf. A003024, A003025, A049524, A361210.

nn = 10; B[n_] := n! 2^Binomial[n, 2];e[z_] := Sum[z^n/B[n], {n, 0, nn}];
egf[ggf_] := Normal[Series[ggf, {z, 0, nn}]] /. Table[z^i -> z^i*2^Binomial[i, 2], {i, 1, nn + 1}]; Map[ Coefficient[#, u v] &,Table[n!, {n, 0, nn}] CoefficientList[ Series[Exp[(u - 1) (v - 1) z] egf[e[(u - 1) z]*1/e[-z]*e[(v - 1) z]], {z, 0, nn}], z]] (* Geoffrey Critzer, Apr 15 2023 *)

\\ see Marcel et al. link. B(n) is A003025 as vector.
B(n)={my(a=vector(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1)*binomial(n,k)*(2^(n-k)-1)^k*a[n-k])); a}
seq(n)={my(a=vector(n), b=B(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1) * binomial(n,k) * k * (2^(n-k)-1)^k * b[n-k])); a} \\ Andrew Howroyd, Jan 01 2022

a(1)=1 inserted and terms a(13) and beyond from Andrew Howroyd, Jan 01 2022

cp's OEIS Frontend

A003028 Number of digraphs on n labeled nodes with a source.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A049531 Number of digraphs with a source and a sink on n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A057271 Triangle T(n,k) of number of digraphs with a source and a sink on n labeled nodes and k arcs, k=0,1,..,n*(n-1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

A003029 Number of unilaterally connected digraphs with n labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A165950 Number of acyclic digraphs on n labeled nodes with one source and one sink.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions