A350793 -id:A350793 - cp's OEIS frontend

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

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

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

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

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

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