A350798 -id:A350798 - cp's OEIS frontend

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

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

A350797 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k arcs and a global source (or sink), n >= 1, k = 0..(n-1)^2.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 2, 1, 0, 0, 0, 4, 11, 19, 15, 8, 2, 1, 0, 0, 0, 0, 9, 45, 157, 319, 453, 455, 352, 199, 93, 32, 9, 2, 1, 0, 0, 0, 0, 0, 20, 167, 928, 3395, 9015, 18172, 29089, 37688, 40446, 36267, 27476, 17560, 9543, 4354, 1688, 547, 157, 36, 9, 2, 1

Offset: 1

Andrew Howroyd, Jan 21 2022

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 2, 2,  1;
  [4] 0, 0, 0, 4, 11, 19, 15, 8, 2, 1;
  ...

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

Row sums are A350360.
Column sums are A350798.
The leading diagonal is A000081.
The labeled version is A350793.
Cf. A057277, A057278, A350795.

\\ See PARI link in A350794 for program code.
{ my(A=A350797triang(5)); for(n=1, #A, print(A[n])) }

A350796 Number of unlabeled digraphs with n arcs and a global source and sink.

Original entry on oeis.org

1, 1, 1, 2, 7, 25, 108, 513, 2690, 15230, 92361, 594669, 4040283, 28817783, 214898429, 1669663193, 13476692136, 112722792293, 974931812942, 8702563358405, 80039193725904, 757342429877879, 7362651015248190, 73451961108974776, 751144076656119144, 7866092802569673370

Offset: 0

Andrew Howroyd, Jan 21 2022

nonn

Column sums of A350795.

Cf. A350752, A350794, A350798, A350906, A350907.

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

A350906 Number of unlabeled initially-finally connected digraphs with n arcs.

Original entry on oeis.org

1, 1, 2, 5, 16, 56, 241, 1111, 5748, 31912, 190328, 1204317, 8050341, 56516303, 415128256, 3179020729, 25308005049, 208918893640, 1784451646305, 15739926014382, 143130061546156, 1339761466105929, 12891329514544223, 127351374611721837, 1290198076415425548, 13390893744153374776

Offset: 0

Andrew Howroyd, Jan 21 2022

nonn

Column sums of A057278.

Cf. A049531 (by vertices), A350752, A350796, A350798, A350907.

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

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

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

A350797 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k arcs and a global source (or sink), n >= 1, k = 0..(n-1)^2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A350796 Number of unlabeled digraphs with n arcs and a global source and sink.

Views

Author

Keywords

Crossrefs

Programs

PARI

A350906 Number of unlabeled initially-finally connected digraphs with n arcs.

Views

Author

Keywords

Crossrefs

Programs

PARI

A350907 Number of unlabeled initially connected digraphs with n arcs.

Views

Author

Keywords

Crossrefs

Programs

PARI