cp's OEIS Frontend

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

%I A350360 #36 Jan 31 2022 03:14:11
%S A350360 1,1,5,60,2126,236560,86140208,105190967552,442114599155408,
%T A350360 6536225731179398016,345635717436525206325760,
%U A350360 66213119317905480992415271936,46409685828045501628276172471067136,119963222885004355352870426935849790038016
%N A350360 Number of unlabeled digraphs with n nodes containing a global sink (or source).
%C A350360 A global sink is a node that has out-degree zero and to which all other nodes have a directed path.
%C A350360 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.
%H A350360 Andrew Howroyd, <a href="/A350360/b350360.txt">Table of n, a(n) for n = 1..50</a>
%H A350360 Jim Snyder-Grant, <a href="https://github.com/jim-snyder-grant/counting-global-sinks">C code to generate and count digraphs with global sinks</a>
%H A350360 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DigraphSink.html">Digraph Sink</a>
%e A350360 For n=3, 5 digraph edge-sets: (vertex 0 is the single global sink)
%e A350360   {10,21,20}
%e A350360   {21,10}
%e A350360   {21,12,10}
%e A350360   {21,12,10,20}
%e A350360   {20,10}
%o A350360 (Sage)
%o A350360 # A simple but slow way is to start from all digraphs and filter
%o A350360 # This code can get to n=5
%o A350360 # The linked C code was used to get to n=7
%o A350360 def one_global_sink(g):
%o A350360     if (g.out_degree().count(0) != 1): return False;
%o A350360     s = g.out_degree().index(0)
%o A350360     return [g.distance(v,s) for v in g.vertices()].count(Infinity) == 0
%o A350360 [len([g for g in digraphs(n) if one_global_sink(g)]) for n in (0..5)]
%o A350360 (PARI) \\ See PARI link in A350794 for program code.
%o A350360 A350360seq(15) \\ _Andrew Howroyd_, Jan 21 2022
%Y A350360 The labeled version is A350792.
%Y A350360 Row sums of A350797.
%Y A350360 Cf. A051421, A049531.
%Y A350360 Cf. A049512, A350415, A350794, A350798.
%K A350360 nonn
%O A350360 1,3
%A A350360 _Jim Snyder-Grant_, Dec 26 2021
%E A350360 Terms a(8) and beyond from _Andrew Howroyd_, Jan 21 2022