A003030 -id:A003030 - cp's OEIS frontend

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

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

A339807 Irregular triangle read by rows: T(n,k) (n>=2, k>=1) is the number of strong digraphs on n nodes with k descents.

Original entry on oeis.org

1, 2, 11, 5, 10, 154, 540, 581, 272, 49, 122, 3418, 27304, 90277, 150948, 150519, 95088, 37797, 8714, 893, 3346, 142760, 1938178, 12186976, 42696630, 94605036, 145009210, 161845163, 134933733, 84656743, 39632149, 13481441, 3156845, 455917, 30649

Offset: 2

Hugo Pfoertner, Dec 28 2020

T(n,1) = A005321(n-1). Length of row n = binomial(n,2). It appears that T(n,binomial(n,2)) = A348901(n-1). - Geoffrey Critzer, Feb 12 2025

			Triangle begins:
 1;
 2, 11, 5;
 10, 154, 540, 581, 272, 49;
 122, 3418, 27304, 90277, 150948, 150519, 95088, 37797, 8714, 893;
 3346, 142760, 1938178, 12186976, 42696630, 94605036, 145009210, 161845163, 134933733, 84656743, 39632149, 13481441, 3156845, 455917, 30649;
 ...

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.

Cf. A003030 (row sums), A057273 (another version of the same triangle), A307049, A339590, A005321, A000217.

nn = 8; B[n_] := FunctionExpand[QFactorial[n, (1 + u y)/(1 + y)]] (1 + y)^Binomial[n, 2]; g[z_] := Sum[(1 + u y)^Binomial[n, 2] z^n/FunctionExpand[QFactorial[n, (1 + u y)/(1 + y)]], {n, 0, nn}]; egf[eggf_] := Normal[Series[eggf, {z, 0, nn}]] /.Table[z^i -> z^i*B[i]/i!, {i, 1, nn + 1}]; Map[Drop[#, 1] &, Drop[Map[CoefficientList[#, u] &, Table[n!, {n, 0, nn}]CoefficientList[Series[-Log[egf[1/g[z]]], {z, 0, nn}], z] /. y -> 1], 2]] // Grid (* Geoffrey Critzer, Feb 12 2025 *)

Row 2 added by N. J. A. Sloane, Dec 29 2020

A350730 Number of strongly connected oriented graphs on n labeled nodes.

Original entry on oeis.org

1, 0, 2, 66, 7998, 2895570, 3015624078, 8890966977354, 74079608267459142, 1754419666770364130730, 119163820122708911990211222, 23431180614718394105521543222866, 13448652672256961901980839022683943838, 22684139279519345808802725789494254587951810

Offset: 1

Andrew Howroyd, Jan 11 2022

nonn

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

The unlabeled version is A350489.
Row sums of A350731.
Cf. A003030, A054941.

StrongO(14) \\ See A350731 for program code.

A086366 Number of labeled n-node digraphs in which every node belongs to a directed cycle.

Original entry on oeis.org

1, 0, 1, 18, 1699, 587940, 750744901, 3556390155318, 63740128872703879, 4405426607409460017480, 1190852520892329350092354441, 1270598627613805616203391468226138, 5381238039128882594932248239301142751179, 90766634183072089515270648224715368261615375340

Offset: 0

Valery A. Liskovets and Vladeta Jovovic, Sep 04 2003

nonn

These are the directed graphs whose strong components exclude a single vertex. - Andrew Howroyd, Jan 15 2022

Andrew Howroyd, Table of n, a(n) for n = 0..50
Valery Liskovets, Labeled digraphs in which every node belongs to a directed cycle [Broken link]

Column k=0 of A361592.
The unlabeled version is A361586.
Cf. A003030, A086193.

G(p)={my(n=serprec(p,x)); serconvol(p, sum(k=0, n-1, x^k/2^(k*(k-1)/2), O(x^n)))}
U(p)={my(n=serprec(p,x)); serconvol(p, sum(k=0, n-1, x^k*2^(k*(k-1)/2), O(x^n)))}
DigraphEgf(n)={sum(k=0, n, 2^(k*(k-1))*x^k/k!, O(x*x^n) )}
seq(n)={Vec(serlaplace(U(1/G(exp(x+log(U(1/G(DigraphEgf(n)))))))))} \\ Andrew Howroyd, Jan 15 2022

a(0)=1 prepended and terms a(12) and beyond from Andrew Howroyd, Jan 15 2022

A355612 Number of labeled digraphs on [n] such that for any pair C_1,C_2 of distinct strongly connected components, if x in C_1 is directed to y in C_2 then every vertex in C_1 is directed to every vertex in C_2.

Original entry on oeis.org

1, 1, 4, 52, 2524, 629296, 750098464, 3540134362192, 63605185617860464, 4402130837352016607296, 1190565802204629673473661504, 1270503156085666608161173288964992, 5381113705726490960372769906727545572224, 90765998703828737395601069325546106634460887296, 6109068274998388232409260496587163340177606642565219584

Offset: 0

Geoffrey Critzer, Jul 09 2022

nonn

Here a digraph can have both a directed edge from x to y and y to x but no self loops are allowed.

Cf. A003024, A003030.

nn = 14; d[x_] := Total[Cases[Import["https://oeis.org/A003024/b003024.txt",
      "Table"], {, }][[All, 2]]*Table[x^(i - 1)/(i - 1)!, {i, 1, 41}]];
s[x_] := Total[ Prepend[Cases[Import["https://oeis.org/A003030/b003030.txt",
       "Table"], {, }][[All, 2]], 1]* Table[x^(i - 1)/(i - 1)!, {i, 1, 59}]];
Range[0, nn]! CoefficientList[Series[d[s[x] - 1], {x, 0, nn}], x]

E.g.f.: D(S(x)-1) where D(x),S(x) are the e.g.f.'s for A003024 and A003030 respectively.

A361269 Triangular array read by rows. T(n,k) is the number of binary relations on [n] containing exactly k strongly connected components, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 2, 0, 4, 12, 0, 144, 168, 200, 0, 25696, 18768, 12384, 8688, 0, 18082560, 8697280, 3923040, 1914560, 936992, 0, 47025585664, 14670384000, 4512045120, 1622358720, 647087040, 242016192, 0, 450955726792704, 87781550054912, 17679638000640, 4496696041600, 1408276410240, 482302375296, 145763745920

Offset: 0

Geoffrey Critzer, Mar 06 2023

			  1;
  0,     2;
  0,     4,    12;
  0,   144,   168,   200;
  0, 25696, 18768, 12384, 8688;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
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.
Wikipedia, Strongly connected component

Cf. A003030, A003024, A002416 (row sums).

nn =15; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[x_] := Total[strong Table[x^i/i!, {i, 1, 58}]]; begf = Total[CoefficientList[ Series[1/(Total[CoefficientList[Series[ Exp[-u *s[x]], {x, 0, nn}], x]* Table[z^n/(2^Binomial[n, 2]), {n, 0, nn}]]), {z, 0, nn}],z]*Table[z^n 2^Binomial[n, 2], {n, 0, nn}]] /. z -> 2 z;
Range[0, nn]! CoefficientList[begf, {z, u}] // Grid (* Geoffrey Critzer, Mar 14 2023 after Andrew Howroyd *)

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))}
RelEgf(n, e)={sum(k=0, n, e^(k^2)*x^k/k!, O(x*x^n) )}
T(n)={my(e=2); [Vecrev(p) | p<-Vec(serlaplace(U(e, 1/G(e, exp(y*log(U(e, 1/G(e, RelEgf(n, e)))))))))]}
{ my(A=T(6)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Mar 06 2023

E.g.f. for column 1: A(2*x) where A(x) is the e.g.f. for A003030.

E.g.f. for main diagonal: B(2*x) where B(x) is the e.g.f. for A003024.

Terms a(15) and beyond from Andrew Howroyd, Mar 06 2023

A361455 Triangle read by rows: T(n,k) is the number of simple digraphs on labeled n nodes with k strongly connected components.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 18, 21, 25, 0, 1606, 1173, 774, 543, 0, 565080, 271790, 122595, 59830, 29281, 0, 734774776, 229224750, 70500705, 25349355, 10110735, 3781503, 0, 3523091615568, 685793359804, 138122171880, 35130437825, 11002159455, 3767987307, 1138779265

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
  1;
  0,         1;
  0,         1,         3;
  0,        18,        21,       25;
  0,      1606,      1173,      774,      543;
  0,    565080,    271790,   122595,    59830,    29281;
  0, 734774776, 229224750, 70500705, 25349355, 10110735, 3781503;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50).

Column k=1 is A003030.
Main diagonal is A003024.
Row sums are A053763.
The unlabeled version is A361582.
Cf. A189898 (weak components), A361269 (loops allowed), A361591.

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) )}
T(n)={my(e=2); [Vecrev(p) | p<-Vec(serlaplace(U(e, 1/G(e, exp(y*log(U(e, 1/G(e, DigraphEgf(n, e)))))))))]}
{ my(A=T(6)); for(i=1, #A, print(A[i])) }

T(n,k) = A361269(n,k)/2^n.

A361579 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k source-like components, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 3, 1, 0, 51, 12, 1, 0, 3614, 447, 34, 1, 0, 991930, 53675, 2885, 85, 1, 0, 1051469032, 21514470, 741455, 16665, 201, 1, 0, 4366988803688, 30405612790, 642187105, 9816380, 90678, 462, 1, 0, 71895397383029040, 160152273169644, 2024633081100, 19625842425, 122330544, 474138, 1044, 1

Offset: 0

Geoffrey Critzer, Mar 16 2023

Here, a source-like component of a digraph D is a strongly connected component of D that corresponds to a node of in-degree 0 in the condensation of D.

			Triangle begins:
  1;
  0,      1;
  0,      3,     1;
  0,     51,    12,    1;
  0,   3614,   447,   34,  1;
  0, 991930, 53675, 2885, 85, 1;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
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.
Wikipedia, Strongly connected component

Cf. A003028 (column k=1), A053763 (row sums).

nn = 6; B[n_] := n! 2^Binomial[n, 2]; strong =Select[Import["https://oeis.org/A003030/b003030.txt", "Table"], Length@# == 2 &][[All, 2]]; s[x_] := Total[strong Table[x^i/i!, {i, 1, 58}]];
ggfz[egfx_] := Normal[Series[egfx, {x, 0, nn}]] /.Table[x^i -> z^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[Series[ggfz[Exp[(u - 1) s[x]]]/ggfz[Exp[- s[x]]], {z, 0, nn}], {z u}] // Grid

A361592 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k strongly connected components of size 1, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 1, 0, 3, 18, 21, 0, 25, 1699, 1080, 774, 0, 543, 587940, 267665, 103860, 59830, 0, 29281, 750744901, 225144360, 64169325, 19791000, 10110735, 0, 3781503, 3556390155318, 672637205149, 126726655860, 29445913175, 7939815030, 3767987307, 0, 1138779265

Offset: 0

Geoffrey Critzer, Mar 16 2023

			Triangle begins:
       1;
       0,      1;
       1,      0,      3;
      18,     21,      0,    25;
    1699,   1080,    774,     0, 543;
  587940, 267665, 103860, 59830,   0, 29281;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
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.
Wikipedia, Strongly connected component

Cf. A086366 (column k=0), A003024 (main diagonal), A053763 (row sums), A361590 (unlabeled version).

nn = 7; B[n_] := n! 2^Binomial[n, 2]; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"], Length@# == 2 &][[All, 2]];s[x_] := Total[strong Table[x^i/i!, {i, 1, 58}]]; ggfz[egfx_] := Normal[Series[egfx, {x, 0, nn}]] /.Table[x^i -> z^i/2^Binomial[i, 2], {i, 0, nn}];Table[Take[(Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggfz[Exp[-(s[x] - x + u x)]], {z, 0, nn}], {z,u}])[[i]], i], {i, 1, nn + 1}] // Grid

A366866 Number of binary relations R on [n] such that the transitive closure of R contains the identity relation.

Original entry on oeis.org

1, 1, 7, 253, 39463, 24196201, 56481554827, 502872837857293, 17309567681965278223, 2333553047265268677638161, 1243013506394568266481053180947, 2629978323181659930952963974617537173, 22170279317365870690118601982232935268994583

Offset: 0

Geoffrey Critzer, Oct 25 2023

nonn

Equivalently, a(n) is the number of n X n Boolean relation matrices whose Frobenius normal form contains no 0-blocks on the diagonal.  See Gregory, Kirkland, and Pullman.
Equivalently, a(n) is the number of labeled directed graphs on [n] (with self loops allowed) such that every strongly connected component contains at least one arc.
This sequence is a good upper-bound for the number of relations that converge to a quasi-order (A366252) which is only known for n <= 6.
If the transitive closure of a relation R contains the identity relation then there is exactly one transitive relation in {R,R^2,R^3...}.  See Schwarz link.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
S. Schwarz, On the semigroup of binary relations on a finite set , Czechoslovak Mathematical Journal, 1970.

Cf. A366252, A003030, A000798.

nn = 12; B[n_] := 2^Binomial[n, 2] n!; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],Length@# == 2 &][[All, 2]]; s[x_] := Total[strong Table[x^i/i!, {i,1,58}]];ggf[egf_]:=Normal[Series[egf, {x, 0, nn}]] /.Table[x^i ->x^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[
  Series[1/ggf[Exp[- (s[2 x] - x)]], {x, 0, nn}], x]

Sum_{n>=0} a_n*x^n/(2^n*binomial(n,2)) = 1/(E(x) @ exp(-(s(2x)-x))) where E(x) = Sum_{n>=0} x^n/(2^n*binomial(n,2)), s(x) is the e.g.f. for A003030, and @ is the exponential Hadamard product (see Panafieu and Dovgal).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A339807 Irregular triangle read by rows: T(n,k) (n>=2, k>=1) is the number of strong digraphs on n nodes with k descents.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A350730 Number of strongly connected oriented graphs on n labeled nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A086366 Number of labeled n-node digraphs in which every node belongs to a directed cycle.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A355612 Number of labeled digraphs on [n] such that for any pair C_1,C_2 of distinct strongly connected components, if x in C_1 is directed to y in C_2 then every vertex in C_1 is directed to every vertex in C_2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A361269 Triangular array read by rows. T(n,k) is the number of binary relations on [n] containing exactly k strongly connected components, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A361455 Triangle read by rows: T(n,k) is the number of simple digraphs on labeled n nodes with k strongly connected components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A361579 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k source-like components, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs