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,3

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.

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

Example

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}

Prog

(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)]
(PARI) \\ See PARI link in A350794 for program code.
A350360seq(15) \\ Andrew Howroyd, Jan 21 2022

Crossrefs

The labeled version is A350792.

Row sums of A350797.

Cf. A051421, A049531.

Cf. A049512, A350415, A350794, A350798.

Sequence in context: A214380 A218801 A303066 * A293454 A162129 A326726

Adjacent sequences: A350357 A350358 A350359 * A350361 A350362 A350363

Keyword

nonn

Author

Jim Snyder-Grant, Dec 26 2021

Extensions

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

Status

approved