A057271 -id:A057271 - cp's OEIS frontend

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

1, 0, 0, 1, 0, 0, 0, 2, 9, 6, 1, 0, 0, 0, 0, 6, 84, 316, 492, 417, 212, 66, 12, 1, 0, 0, 0, 0, 0, 24, 720, 6440, 26875, 65280, 105566, 122580, 106825, 71700, 37540, 15344, 4835, 1140, 190, 20, 1, 0, 0, 0, 0, 0, 0, 120, 6480, 107850, 868830, 4188696, 13715940

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1] 1;
  [2] 0,0,1;
  [3] 0,0,0,2,9,6,1;
  [4] 0,0,0,0,6,84,316,492,417,212,66,12,1;
  ...
Number of strongly connected digraphs on 3 labeled nodes is 18 = 2+9+6+1.

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041. See Table 2.

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)
Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020. See Table 2.

Row sums give A003030.
The unlabeled version is A057276.
Cf. A057271, A057272, A057274, A057275, A062735.
Cf. A123554, A339590, A339807.

B(nn, e=2)={my(v=vector(nn)); for(n=1, nn, v[n] = e^(n*(n-1)) - sum(k=1, n-1, binomial(n,k)*e^((n-1)*(n-k))*v[k])); v}
Strong(n, e=2)={my(u=B(n, e), v=vector(n)); v[1]=1; for(n=2, #v, v[n] = u[n] + sum(j=1, n-1, binomial(n-1, j-1)*u[n-j]*v[j])); v}
row(n)={ Vecrev(Strong(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 10 2022

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

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

A057270 Triangle T(n,k) of number of unilaterally connected digraphs on n unlabeled nodes with 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, 10, 30, 45, 38, 27, 13, 5, 1, 1, 0, 0, 0, 0, 1, 20, 136, 462, 972, 1412, 1639, 1485, 1152, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 0, 1, 35, 437, 2833, 11325, 31615, 67207, 115344, 165762, 204723, 219866, 206986, 170920, 124088, 78809, 43860, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Aug 23 2000

			[1],[0,1,1],[0,0,1,4,4,1,1],[0,0,0,1,10,30,45,38,27,13,5,1,1],...; Number of unilaterally connected digraphs on 4 unlabeled nodes is 171=1+10+30+45+38+27+13+5+1+1.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

R. W. Robinson, Counting strong digraphs (research announcement), J. Graph Theory 1, 1977, pp. 189-190.

Row sums give A003088. Cf. A057271-A057279.

More terms from Sean A. Irvine, May 27 2022

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

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 9, 20, 15, 6, 1, 0, 0, 0, 64, 330, 720, 914, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 625, 5804, 24560, 63940, 117310, 164260, 183716, 167780, 125955, 77520, 38760, 15504, 4845, 1140, 190, 20, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  1;
  0, 2, 1;
  0, 0, 9, 20,  15,   6,   1;
  0, 0, 0, 64, 330, 720, 914, 792, 495, 220, 66, 12, 1;
  ...
The number of digraphs with a source on 3 labeled nodes is the sum of the terms in row 3, i.e., 0+0+9+20+15+6+1 = 51 = A003028(3).

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.

Row sums give A003028.
The unlabeled version is A057277.
Cf. A057271, A057272, A057273, A057275, A062735.

\\ See A057273 for Strong.
Lambda(t, nn, e=2)={my(v=vector(1+nn)); for(n=0, nn, v[1+n] = e^(n*(n+t-1)) - sum(k=0, n-1, binomial(n,k)*e^((n-1)*(n-k))*v[1+k])); v}
Initially(n, e=2)={my(s=Strong(n, e), v=vector(n)); for(k=1, n, my(u=Lambda(k, n-k, e)); for(i=k, n, v[i] += binomial(i,k)*u[1+i-k]*s[k])); v }
row(n)={ Vecrev(Initially(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 11 2022

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

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 12, 20, 15, 6, 1, 0, 0, 0, 104, 426, 768, 920, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 1160, 9184, 32420, 73000, 123425, 166860, 184426, 167900, 125965, 77520, 38760, 15504, 4845, 1140, 190, 20, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle starts:
1;
0,2,1;
0,0,12,20,15,6,1;
0,0,0,104,426,768,920,792,495,220,66,12,1;
...
Number of digraphs with a quasi-source on 3 labeled nodes is 54=12+20+15+6+1.

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

Row sums give A049414. Cf. A057270, A057271, A057273-A057279.

A057275 Triangle T(n,k) of number of unilaterally connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 6, 20, 15, 6, 1, 0, 0, 0, 24, 222, 660, 908, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 120, 2304, 15540, 52700, 109545, 161120, 182946, 167660, 125945, 77520, 38760, 15504, 4845, 1140, 190, 20, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1],
  [0,2,1],
  [0,0,6,20,15,6,1],
  [0,0,0,0,24,222,660,908,792,495,220,66,12,1],
  ...
The number of unilaterally connected digraphs on 3 labeled nodes is 48 = 6+20+15+6+1.

Andrew Howroyd, Table of n, a(n) for n = 1..2680
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

Row sums give A003029.
The unlabeled version is A057270.
Cf. A057271, A057272, A057273, A057274, A062735.

\\ See A057273 for Strong.
Unilaterally(n, e=2)={my(u=vector(n), s=Strong(n,e)); for(n=1, #u, u[n]=vector(n, k, binomial(n,k)*s[k]*if(k==n, 1, sum(j=1, n-k, e^(k*(n-k-j))*(e^(k*j)-1)*u[n-k][j])))); vector(#u, n, vecsum(u[n]))}
row(n)={Vecrev(Unilaterally(n, 1+'y)[n])}
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 19 2022

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

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

Views

Author

Keywords

Examples

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

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Examples

Links

Crossrefs

A057275 Triangle T(n,k) of number of unilaterally connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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