A049524 Number of digraphs with a source and a sink on n labeled nodes.

1, 3, 48, 3424, 962020, 1037312116, 4344821892264, 71771421308713624, 4716467927380427847264, 1237465168798883061207535456, 1297923989772809185944542332007104, 5444330658513426322624322033259452670016, 91342931436147421630261703458729460990513248512

Offset

1,2

Comments

Here a source is defined to be a node which has a directed path to all other nodes and a sink to be a node to which all other nodes have a directed path. A digraph with a source and a sink can also be described as initially-finally connected. - Andrew Howroyd, Jan 16 2022

References

V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), p. 244.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..50

Sean A. Irvine, Java program (github)

V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

Prog

(PARI) InitFinally(15) \\ See A057271. - Andrew Howroyd, Jan 16 2022

Crossrefs

The unlabeled version is A049531.

Row sums of A057271.

Cf. A003027, A003028, A003029, A003030, A049414, A350790.

Sequence in context: A295813 A326217 A003029 * A270748 A322363 A359965

Adjacent sequences: A049521 A049522 A049523 * A049525 A049526 A049527

Keyword

nonn

Author

Vladeta Jovovic, Goran Kilibarda

Extensions

Terms a(12) and beyond from Andrew Howroyd, Jan 16 2022

Status

approved