login
A350360
Number of unlabeled digraphs with n nodes containing a global sink (or source).
8
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
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.
Sequence in context: A214380 A218801 A303066 * A293454 A162129 A326726
KEYWORD
nonn
AUTHOR
Jim Snyder-Grant, Dec 26 2021
EXTENSIONS
Terms a(8) and beyond from Andrew Howroyd, Jan 21 2022
STATUS
approved