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

Author

Jim Snyder-Grant, Dec 26 2021

Keywords

• nonn

Comments

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.

Examples

			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}
		

Links

• 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

Crossrefs

The labeled version is A350792.

Row sums of A350797.

Cf. A051421, A049531.

Cf. A049512, A350415, A350794, A350798.

Programs

PARI

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

Sage

# 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)]

Extensions

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