A049414 -id:A049414 - 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

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

Original entry on oeis.org

1, 3, 48, 3424, 962020, 1037312116, 4344821892264, 71771421308713624, 4716467927380427847264, 1237465168798883061207535456, 1297923989772809185944542332007104, 5444330658513426322624322033259452670016, 91342931436147421630261703458729460990513248512

Offset: 1

Vladeta Jovovic, Goran Kilibarda

nonn

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 16 2022

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

Andrew Howroyd, Table of n, a(n) for n = 1..50
Sean A. Irvine, Java program (github)
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.

The unlabeled version is A049531.
Row sums of A057271.
Cf. A003027, A003028, A003029, A003030, A049414, A350790.

InitFinally(15) \\ See A057271. - Andrew Howroyd, Jan 16 2022

Terms a(12) and beyond from 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

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

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 12, 20, 15, 6, 1, 0, 0, 0, 104, 426, 768, 920, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 1160, 9184, 32420, 73000, 123425, 166860, 184426, 167900, 125965, 77520, 38760, 15504, 4845, 1140, 190, 20, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle starts:
1;
0,2,1;
0,0,12,20,15,6,1;
0,0,0,104,426,768,920,792,495,220,66,12,1;
...
Number of digraphs with a quasi-source on 3 labeled nodes is 54=12+20+15+6+1.

V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

Row sums give A049414. Cf. A057270, A057271, A057273-A057279.

A049512 Number of quasi-initially connected digraphs on n unlabeled nodes.

Original entry on oeis.org

1, 2, 13, 197, 9312, 1528634, 880277970

Offset: 1

Vladeta Jovovic, Goran Kilibarda

From Sean A. Irvine, Aug 01 2021: (Start)
A quasi-initially connected digraph is a digraph containing at least one vertex v such that every vertex u in the graph can either be reached from v or v can be reached from u (while obeying the directions on the edges).
There is no known formula. (End)

Sean A. Irvine, Java program (github)
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

Cf. A049414, A003085, A035512, A003088, A051421.

a(6)-a(7) from Sean A. Irvine, Aug 01 2021

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

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A003029 Number of unilaterally connected digraphs with n labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

A049512 Number of quasi-initially connected digraphs on n unlabeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions