A350790 -id:A350790 - cp's OEIS frontend

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

1, 1, 2, 20, 574, 48854, 12444800, 9849180230, 25265372689314, 218451490123178684, 6562780921564838071734, 700270642102506752862044142, 269621199012416753533007480951824, 378982029174285293421133982496722212766, 1962119228020498122395242424575089505014761082

Offset: 1

Andrew Howroyd, Jan 19 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Andrew Howroyd, PARI Program, Jan 2022, updated Mar 2023.

The labeled version is A350790.
Row sums of A350795.
Cf. A049531, A051421, A345258, A350360, A350796.

A350794seq(15) \\ See link for program code.

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

Original entry on oeis.org

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

Offset: 1

Vladeta Jovovic, Goran Kilibarda

nonn

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

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

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.

The unlabeled version is A049531.
Row sums of A057271.
Cf. A003027, A003028, A003029, A003030, A049414, A350790.

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

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

A350792 Number of digraphs on n labeled nodes with a global source (or sink).

Original entry on oeis.org

1, 2, 24, 1216, 232960, 164069376, 428074336256, 4220285062479872, 160166476125189439488, 23705806454651474422005760, 13794322751716126282614505996288, 31714534285699906476309208596247216128, 288989543377657933541050197425959169851129856

Offset: 1

Andrew Howroyd, Jan 16 2022

nonn

A global sink is a node that has out-degree zero and to which all other nodes have a directed path.

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

The unlabeled version is A350360.
Row sums of A350793.
Cf. A003025, A003028, A350790.

InitiallyV(15) \\ See A350793 for program code.

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = n*2^((n-1)^2) - sum(k=1, n-1, binomial(n,k)*2^((n-2)*(n-k))*v[k])); v}

a(n) = n*2^((n-1)^2) - Sum_{k=1..n-1} binomial(n,k)*2^((n-2)*(n-k))*a(k).

A350791 Triangle read by rows: T(n,k) is the number of digraphs on n labeled 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, 2, 0, 0, 6, 6, 0, 0, 0, 24, 132, 180, 84, 12, 0, 0, 0, 0, 120, 1800, 8000, 16160, 18180, 12580, 5560, 1560, 260, 20, 0, 0, 0, 0, 0, 720, 22320, 214800, 999450, 2764650, 5125380, 6844380, 6882150, 5355750, 3277200, 1586520, 605370, 179250, 39900, 6300, 630, 30

Offset: 1

Andrew Howroyd, Jan 16 2022

			Triangle begins:
  [1] 1;
  [2] 0, 2;
  [3] 0, 0, 6, 6;
  [4] 0, 0, 0, 24, 132, 180, 84, 12;
  ...

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

Row sums are A350790.
The unlabeled version is A350795.
Cf. A057271, A350793.

\\ Following Eqn 21 in the Robinson reference.
Z(p,f)={my(n=serprec(p,x)); serconvol(p, sum(k=0, n-1, x^k*f(k), O(x^n)))}
G(e,p)={Z(p, k->1/e^(k*(k-1)/2))}
U(e,p)={Z(p, k->e^(k*(k-1)/2))}
DigraphEgf(n,e)={sum(k=0, n, e^(k*(k-1))*x^k/k!, O(x*x^n) )}
StrongD(n,e=2)={-log(U(e, 1/G(e, DigraphEgf(n, e))))}
InitFinallyV(n, e=2)={my(S=StrongD(n, e)); Vec(serlaplace( x - x^2 + exp(S) * U(e, G(e, x*exp(-S))^2*G(e, DigraphEgf(n,e))) ))}
row(n)={Vecrev(InitFinallyV(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) }

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A350792 Number of digraphs on n labeled nodes with a global source (or sink).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

A350791 Triangle read by rows: T(n,k) is the number of digraphs on n labeled 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