A350791 -id:A350791 - cp's OEIS frontend

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

1, 0, 2, 1, 0, 0, 6, 20, 15, 6, 1, 0, 0, 0, 24, 234, 672, 908, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 120, 2544, 16880, 55000, 111225, 161660, 183006, 167660, 125945, 77520, 38760, 15504, 4845, 1140, 190, 20, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle starts:
[1] 1;
[2] 0,2,1;
[3] 0,0,6,20,15,6,1;
[4] 0,0,0,24,234,672,908,792,495,220,66,12,1;
  ...
The number of digraphs with a source and a sink on 3 labeled nodes is 48 = 6+20+15+6+1.

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

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

Row sums give A049524.
The unlabeled version is A057278.
Cf. A057272, A057273, A057274, A057275, A062735, A350791.

\\ Following Eqn 20 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))))}
InitFinally(n, e=2)={my(S=StrongD(n, e)); Vec(serlaplace( S - S^2 + exp(S) * U(e, G(e, S*exp(-S))^2*G(e, DigraphEgf(n,e))) ))}
row(n)={Vecrev(InitFinally(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 16 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])) }

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

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

Original entry on oeis.org

1, 0, 2, 0, 0, 9, 12, 3, 0, 0, 0, 64, 252, 396, 320, 144, 36, 4, 0, 0, 0, 0, 625, 4860, 17060, 35900, 50775, 51300, 38340, 21540, 9075, 2800, 600, 80, 5, 0, 0, 0, 0, 0, 7776, 99720, 603720, 2300310, 6206730, 12654384, 20310840, 26385240, 28273620, 25302960

Offset: 1

Andrew Howroyd, Jan 17 2022

			Triangle begins:
  [1] 1;
  [2] 0, 2;
  [3] 0, 0, 9, 12, 3;
  [4] 0, 0, 0, 64, 252, 396, 320, 144, 36, 4;
  ...

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

Row sums are A350792.
The leading diagonal is A000169.
The unlabeled version is A350797.
Cf. A057274, A350791.

InitiallyV(n, e=2)={my(v=vector(n)); for(n=1, n, v[n] = n*e^((n-1)^2) - sum(k=1, n-1, binomial(n,k)*e^((n-2)*(n-k))*v[k])); v}
row(n)={Vecrev(InitiallyV(n, 1+'y)[n])}
{ for(n=1, 5, print(row(n))) }

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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