A057278 -id:A057278 - cp's OEIS frontend

A057276 Triangle T(n,k) of number of strongly connected digraphs on n unlabeled nodes and with k arcs, k=0..n*(n-1).

1, 0, 0, 1, 0, 0, 0, 1, 2, 1, 1, 0, 0, 0, 0, 1, 4, 16, 22, 22, 11, 5, 1, 1, 0, 0, 0, 0, 0, 1, 7, 58, 240, 565, 928, 1065, 953, 640, 359, 150, 59, 16, 5, 1, 1, 0, 0, 0, 0, 0, 0, 1, 10, 165, 1281, 6063, 19591, 47049, 87690, 131927, 163632, 170720, 151238, 115122, 75357, 42745, 20891, 8877, 3224, 1039, 286, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1] 1;
  [2] 0,0,1;
  [3] 0,0,0,1,2,1,1;
  [4] 0,0,0,0,1,4,16,22,22,11,5,1,1;
  ...
The number of strongly connected digraphs on 3 unlabeled nodes is 5 = 1+2+1+1.

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

Row sums give A035512.
Column sums give A350752.
The labeled version is A057273.
Cf. A054733, A057270, A057277, A057278, A057279, A350489.

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

Terms a(46) and beyond from Andrew Howroyd, Jan 13 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

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).

Original entry on oeis.org

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

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

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

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

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 3, 4, 4, 1, 1, 0, 0, 0, 7, 21, 37, 47, 38, 27, 13, 5, 1, 1, 0, 0, 0, 0, 18, 90, 309, 661, 1125, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 0, 44, 374, 1981, 7107, 19166, 41867, 77194, 122918, 170308, 206980, 220768, 207301, 171008, 124110, 78813, 43862, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Table starts:
[1],
[0,1,1],
[0,0,3,4,4,1,1],
[0,0,0,7,21,37,47,38,27,13,5,1,1],
...
Number of digraphs with a quasi-source on 3 unlabeled nodes is 13=3+4+4+1+1.

Sean A. Irvine, Java program (github)
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

Row sums give A049512. Cf. A057270-A057278.

More terms from Sean A. Irvine, May 30 2022

A350906 Number of unlabeled initially-finally connected digraphs with n arcs.

Original entry on oeis.org

1, 1, 2, 5, 16, 56, 241, 1111, 5748, 31912, 190328, 1204317, 8050341, 56516303, 415128256, 3179020729, 25308005049, 208918893640, 1784451646305, 15739926014382, 143130061546156, 1339761466105929, 12891329514544223, 127351374611721837, 1290198076415425548, 13390893744153374776

Offset: 0

Andrew Howroyd, Jan 21 2022

nonn

Column sums of A057278.

Cf. A049531 (by vertices), A350752, A350796, A350798, A350907.

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

cp's OEIS Frontend

A057276 Triangle T(n,k) of number of strongly connected digraphs on n unlabeled nodes and with k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

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

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

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

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A350906 Number of unlabeled initially-finally connected digraphs with n arcs.

Views

Author

Keywords

Crossrefs

Programs

PARI