A350794 -id:A350794 - cp's OEIS frontend

A051421 Number of digraphs on n unlabeled nodes with a sink (or, with a source).

1, 2, 12, 185, 8990, 1505939, 875542491, 1789247738400, 13018820342147705, 341188114831706152794, 32520852428719860881939391, 11366533535523591133597276823755, 14669006027884671703581740693080811331, 70315546525961698601351615055416574931833334

Offset: 1

Vladeta Jovovic

Here a sink is defined to be a node to which all other nodes have a directed path. - Andrew Howroyd, Dec 27 2021

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 218 (incorrect version).
Ronald C. Read, email to N. J. A. Sloane, 28 August, 2000.

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

The labeled case is A003028.
Row sums of A057277.
Cf. A003085, A035512, A003088, A049531, A350415, A350360, A350794.

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

a(6) corrected and a(7) from Sean A. Irvine, Sep 11 2021

a(0)=1 removed and terms a(8) and beyond from Andrew Howroyd, Jan 21 2022

A049531 Number of digraphs with a source and a sink on n unlabeled nodes.

Original entry on oeis.org

1, 2, 11, 173, 8675, 1483821, 870901739, 1786098545810, 13011539185371716, 341128981258340797839, 32519138088689298538132027, 11366354205366488038532562993809, 14668937734550708660348161757913398001, 70315451107713339843384354196009678853303102

Offset: 1

Vladeta Jovovic, Goran Kilibarda

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 01 2022

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

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

Row sums of A057278.
The labeled version is A049524.
Cf. A003085, A035512, A003088, A051421, A345258, A350794.

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

a(6)-a(7) from Andrew Howroyd, Jan 01 2022

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

A057278 Triangle T(n,k) of number of digraphs with a source and a sink on n unlabeled nodes and k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 1, 4, 4, 1, 1, 0, 0, 0, 1, 11, 31, 45, 38, 27, 13, 5, 1, 1, 0, 0, 0, 0, 1, 23, 152, 486, 992, 1419, 1641, 1485, 1152, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 0, 1, 42, 517, 3194, 12174, 32860, 68423, 116168, 166164, 204867, 219906, 206993, 170922, 124088, 78809, 43860, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1],
  [0,1,1],
  [0,0,1,4,4,1,1],
  [0,0,0,1,11,31,45,38,27,13,5,1,1],
  ...
The number of digraphs with a source and a sink on 3 unlabeled nodes is 11 = 1+4+4+1+1.

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

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)

Row sums give A049531.
Column sums give A350906.
The labeled version is A057271.
Cf. A057270, A057276, A057277, A057279, A350794, A350795.

\\ See PARI link in A350794 for program code.
{ my(A=A057278triang(5)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 21 2022

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

A057277 Triangle T(n,k) of number of digraphs with a source on n unlabeled nodes with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 2, 4, 4, 1, 1, 0, 0, 0, 4, 16, 34, 46, 38, 27, 13, 5, 1, 1, 0, 0, 0, 0, 9, 56, 229, 573, 1058, 1448, 1653, 1487, 1153, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 0, 20, 198, 1218, 5089, 15596, 37302, 72776, 119531, 168233, 205923, 220337, 207147, 170965, 124099, 78811, 43861, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1],
  [0, 1, 1],
  [0, 0, 2, 4, 4, 1, 1],
  [0, 0, 0, 4, 16, 34, 46, 38, 27, 13, 5, 1, 1],
  ....
The number of digraphs with a source on 3 unlabeled nodes is 12 = 2+4+4+1+1.

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)

Row sums give A051421.
Column sums give A350907.
The labeled version is A057274.
Cf. A057270, A057276, A057278, A057279, A350794, A350797.

\\ See PARI link in A350794 for program code.
{ my(A=A057277triang(5)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 21 2022

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

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

Original entry on oeis.org

1, 1, 5, 60, 2126, 236560, 86140208, 105190967552, 442114599155408, 6536225731179398016, 345635717436525206325760, 66213119317905480992415271936, 46409685828045501628276172471067136, 119963222885004355352870426935849790038016

Offset: 1

Jim Snyder-Grant, Dec 26 2021

nonn

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.

			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}

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

The labeled version is A350792.
Row sums of A350797.
Cf. A051421, A049531.
Cf. A049512, A350415, A350794, A350798.

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

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

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

A350795 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k arcs and a global source and sink, n >= 1, k = 0..max(1,n-1)*(n-2)+1.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 6, 8, 4, 1, 0, 0, 0, 0, 1, 16, 70, 140, 159, 113, 53, 17, 4, 1, 0, 0, 0, 0, 0, 1, 33, 313, 1439, 3941, 7297, 9750, 9840, 7717, 4788, 2377, 946, 309, 80, 18, 4, 1, 0, 0, 0, 0, 0, 0, 1, 58, 998, 8447, 43269, 152135, 396011

Offset: 1

Andrew Howroyd, Jan 21 2022

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 1, 1;
  [4] 0, 0, 0, 1, 6,  8,  4,   1;
  [5] 0, 0, 0, 0, 1, 16, 70, 140, 159, 113, 53, 17, 4, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..2319 (rows 1..20)

Row sums are A350794.
Column sums are A350796.
The labeled version is A350791.
Cf. A057277, A057278, A350797.

\\ See PARI link in A350794 for program code.
{ my(A=A350795triang(5)); for(n=1, #A, print(A[n])) }

A350797 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k arcs and a global source (or sink), n >= 1, k = 0..(n-1)^2.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 2, 1, 0, 0, 0, 4, 11, 19, 15, 8, 2, 1, 0, 0, 0, 0, 9, 45, 157, 319, 453, 455, 352, 199, 93, 32, 9, 2, 1, 0, 0, 0, 0, 0, 20, 167, 928, 3395, 9015, 18172, 29089, 37688, 40446, 36267, 27476, 17560, 9543, 4354, 1688, 547, 157, 36, 9, 2, 1

Offset: 1

Andrew Howroyd, Jan 21 2022

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 2, 2,  1;
  [4] 0, 0, 0, 4, 11, 19, 15, 8, 2, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..2490 (rows 1..20)

Row sums are A350360.
Column sums are A350798.
The leading diagonal is A000081.
The labeled version is A350793.
Cf. A057277, A057278, A350795.

\\ See PARI link in A350794 for program code.
{ my(A=A350797triang(5)); for(n=1, #A, print(A[n])) }

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

Original entry on oeis.org

1, 2, 12, 432, 64240, 33904800, 61721081184, 394586260943616, 9146766152111641344, 792073976107698469670400, 261895415169919230764987845120, 335402460348866803020064114666616832, 1678893205649791601327398844631544110815232

Offset: 1

Andrew Howroyd, Jan 16 2022

nonn

This sequence differs from A049524 in that the source and sink are restricted to being single nodes.

Andrew Howroyd, Table of n, a(n) for n = 1..50
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.

The unlabeled version is A350794.
Row sums of A350791.
Cf. A049524, A165950, A350792, A003030.

nn = 15; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[z_] := Total[strong Table[z^i/i!, {i, 1, 58}]];
ggf[egf_] := Normal[Series[egf, {z, 0, nn}]] /. Table[z^i -> z^i/2^Binomial[i, 2], {i, 1, nn + 1}];egf[ggf_] := Normal[Series[ggf, {z, 0, nn}]] /.Table[z^i -> z^i*2^Binomial[i, 2], {i, 1, nn + 1}];Table[n!, {n, 0, nn}] CoefficientList[
Series[z - z^2 + Exp[(u - 1) (v - 1) s[ z]] egf[ggf[z Exp[(u - 1) s[z]]]*1/ggf[Exp[-s[z]]]*ggf[z Exp[(v - 1) s[ z]]]] /. {u -> 0, v -> 0}, {z, 0, nn}], z] (* Geoffrey Critzer, Apr 17 2023 *)

InitFinallyV(12) \\ See A350791 for program code.

For n >= 3, a(n) = 2*n*(n-1)*A003030(n-1) (Robinson equation 22). - Geoffrey Critzer, Apr 17 2023

A350796 Number of unlabeled digraphs with n arcs and a global source and sink.

Original entry on oeis.org

1, 1, 1, 2, 7, 25, 108, 513, 2690, 15230, 92361, 594669, 4040283, 28817783, 214898429, 1669663193, 13476692136, 112722792293, 974931812942, 8702563358405, 80039193725904, 757342429877879, 7362651015248190, 73451961108974776, 751144076656119144, 7866092802569673370

Offset: 0

Andrew Howroyd, Jan 21 2022

nonn

Column sums of A350795.

Cf. A350752, A350794, A350798, A350906, A350907.

A350796seq(15) \\ See PARI link in A350794 for program code.

A350798 Number of unlabeled digraphs with n arcs and a global source (or sink).

Original entry on oeis.org

1, 1, 2, 6, 21, 84, 387, 1953, 10802, 64267, 408489, 2750686, 19518841, 145236878, 1128884559, 9135566309, 76758391212, 667993213393, 6008434514996, 55755719348210, 532896254763646, 5238211003916685, 52885470406233727, 547751388283907208, 5813693205313803535, 63170000832869927871

Offset: 0

Andrew Howroyd, Jan 21 2022

nonn

Column sums of A350797.

Cf. A350360, A350752, A350796, A350906, A350907.

A350798seq(15) \\ See PARI link in A350794 for program code.

cp's OEIS Frontend

A051421 Number of digraphs on n unlabeled nodes with a sink (or, with a source).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A049531 Number of digraphs with a source and a sink on n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A057278 Triangle T(n,k) of number of digraphs with a source and a sink on n unlabeled nodes and k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A057277 Triangle T(n,k) of number of digraphs with a source on n unlabeled nodes with k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Sage

Extensions

A350795 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k arcs and a global source and sink, n >= 1, k = 0..max(1,n-1)*(n-2)+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A350797 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k arcs and a global source (or sink), n >= 1, k = 0..(n-1)^2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Links