A051421 -id:A051421 - cp's OEIS frontend

A039748 Erroneous version of A051421.

1, 1, 2, 12, 184

Offset: 0

dead

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

1, 1, 2, 20, 574, 48854, 12444800, 9849180230, 25265372689314, 218451490123178684, 6562780921564838071734, 700270642102506752862044142, 269621199012416753533007480951824, 378982029174285293421133982496722212766, 1962119228020498122395242424575089505014761082

Offset: 1

Andrew Howroyd, Jan 19 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Andrew Howroyd, PARI Program, Jan 2022, updated Mar 2023.

The labeled version is A350790.
Row sums of A350795.
Cf. A049531, A051421, A345258, A350360, A350796.

A350794seq(15) \\ See link for program code.

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

Original entry on oeis.org

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

A057277 Triangle T(n,k) of number of digraphs with a source on n unlabeled nodes with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 2, 4, 4, 1, 1, 0, 0, 0, 4, 16, 34, 46, 38, 27, 13, 5, 1, 1, 0, 0, 0, 0, 9, 56, 229, 573, 1058, 1448, 1653, 1487, 1153, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 0, 20, 198, 1218, 5089, 15596, 37302, 72776, 119531, 168233, 205923, 220337, 207147, 170965, 124099, 78811, 43861, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1],
  [0, 1, 1],
  [0, 0, 2, 4, 4, 1, 1],
  [0, 0, 0, 4, 16, 34, 46, 38, 27, 13, 5, 1, 1],
  ....
The number of digraphs with a source on 3 unlabeled nodes is 12 = 2+4+4+1+1.

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)

Row sums give A051421.
Column sums give A350907.
The labeled version is A057274.
Cf. A057270, A057276, A057278, A057279, A350794, A350797.

\\ See PARI link in A350794 for program code.
{ my(A=A057277triang(5)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 21 2022

Terms a(46) and beyond from Andrew Howroyd, Jan 21 2022

A350360 Number of unlabeled digraphs with n nodes containing a global sink (or source).

Original entry on oeis.org

1, 1, 5, 60, 2126, 236560, 86140208, 105190967552, 442114599155408, 6536225731179398016, 345635717436525206325760, 66213119317905480992415271936, 46409685828045501628276172471067136, 119963222885004355352870426935849790038016

Offset: 1

Jim Snyder-Grant, Dec 26 2021

nonn

A global sink is a node that has out-degree zero and to which all other nodes have a directed path.

A global source is a node that has in-degree zero and has a directed path to all other nodes. A digraph with a global source, transposed, is a digraph with a global sink.

			For n=3, 5 digraph edge-sets: (vertex 0 is the single global sink)
  {10,21,20}
  {21,10}
  {21,12,10}
  {21,12,10,20}
  {20,10}

Andrew Howroyd, Table of n, a(n) for n = 1..50
Jim Snyder-Grant, C code to generate and count digraphs with global sinks
Eric Weisstein's World of Mathematics, Digraph Sink

The labeled version is A350792.
Row sums of A350797.
Cf. A051421, A049531.
Cf. A049512, A350415, A350794, A350798.

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

# A simple but slow way is to start from all digraphs and filter
# This code can get to n=5
# The linked C code was used to get to n=7
def one_global_sink(g):
    if (g.out_degree().count(0) != 1): return False;
    s = g.out_degree().index(0)
    return [g.distance(v,s) for v in g.vertices()].count(Infinity) == 0
[len([g for g in digraphs(n) if one_global_sink(g)]) for n in (0..5)]

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

A003088 Number of unilateral digraphs with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 11, 171, 8603, 1478644, 870014637

Offset: 0

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 218.
Ronald C. Read, email to N. J. A. Sloane, 28 August, 2000.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson, Counting strong digraphs (research announcement), J. Graph Theory 1, 1977, pp. 189-190.

Cf. A057270, A003029 (labeled case), A003085, A035512, A051421, A049531, A049512.

Note that Read and Wilson incorrectly give a(4) as 172 - thanks to Vladeta Jovovic, Goran Kilibarda for finding this error and for verifying a(5).

a(7) from Sean A. Irvine, Jan 26 2015

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

A350907 Number of unlabeled initially connected digraphs with n arcs.

Original entry on oeis.org

1, 1, 3, 8, 29, 111, 522, 2604, 14459, 85796, 544753, 3659313, 25902251, 192171887, 1489090036, 12011329453, 100583184087, 872346402439, 7819597099285, 72313198682817, 688784601395670, 6747614973580663, 67896777481378196, 700913648767703716, 7415270780191604414, 80316990564932960558

Offset: 0

Andrew Howroyd, Jan 21 2022

nonn

Column sums of A057277.

Cf. A051421 (by vertices), A350752, A350796, A350798, A350906.

A350907seq(15) \\ See PARI link in A350794 for program code.

cp's OEIS Frontend

A039748 Erroneous version of A051421.

Views

Author

Keywords

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

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

A057277 Triangle T(n,k) of number of digraphs with a source on n unlabeled nodes with k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A350360 Number of unlabeled digraphs with n nodes containing a global sink (or source).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Sage

Extensions

A003088 Number of unilateral digraphs with n unlabeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A350907 Number of unlabeled initially connected digraphs with n arcs.

Views

Author

Keywords

Crossrefs

Programs

PARI