A011266 -id:A011266 - cp's OEIS frontend

A361527 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] having exactly k strongly connected components all of which are simple cycles, n >= 0, 0 <= k <= n.

1, 0, 1, 0, 1, 3, 0, 2, 21, 25, 0, 6, 213, 774, 543, 0, 24, 3470, 30275, 59830, 29281, 0, 120, 95982, 1847265, 7757355, 10110735, 3781503, 0, 720, 4578588, 190855000, 1522899105, 3944546095, 3767987307, 1138779265

Offset: 0

Geoffrey Critzer, Mar 14 2023

Here, a strongly connected component containing exactly 1 vertex is considered a cycle.

			  1;
  0,  1;
  0,  1,   3;
  0,  2,  21,    25;
  0,  6, 213,   774,   543;
  0, 24,3470, 30275, 59830, 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.
Eric Weisstein's World of Mathematics, Simple Directed Graph
Wikipedia, Strongly connected component

Cf. A011266 (row sums), A003024 (main diagonal), A000142 (column k=1).

 nn = 7;
a[x_] := Log[1/(1 - x)];
begfa =Total[CoefficientList[ Series[1/(Total[ CoefficientList[Series[ Exp[-u *a[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}]];
Table[Take[(Range[0, nn]! CoefficientList[begfa, {z, u}])[[i]],i], {i, 1, nn + 1}] // Grid

A370385 Triangular array read by rows. T(n,k) is the number of binary relations R on [n] such that the unique idempotent relation in {R^i:i>=1} is a quasi-order containing exactly k strongly connected components.

Original entry on oeis.org

1, 1, 3, 4, 139, 66, 48, 25575, 9280, 3072, 1536, 18077431, 4498530, 1174800, 322560, 122880

Offset: 1

Geoffrey Critzer, Feb 18 2024

			Triangle begins:
        1;
        1;
        3,       4;
      139,      66,      48;
    25575,    9280,    3072,   1536;
 18077431, 4498530, 1174800, 322560, 122880;
 ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

Cf. A366866 (row sums), A070322 (column k=1), A011266 (main diagonal), A367948, A247231, A370464.

nn = 5; B[n_] := n! 2^Binomial[n, 2]; s[x_, y_] := y x + (3 y + y^2) x^2/2! + (139 y + 3 y^2 + 2 y^3) x^3/3! + (25575 y + 103 y^2 + 12 y^3 + 6 y^4) x^4/
    4! + (18077431 y + 4815 y^2 + 230 y^3 + 60 y^4 + 24 y^5) x^5/5! ;
ggf[egf_] :=Normal[Series[egf, {x, 0, nn}]] /.Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}]; Map[Select[#, # > 0 &] &,Table[B[n], {n, 0, nn}] CoefficientList[
   Series[1/ggf[Exp[-s[x, y]]], {x, 0, nn}], {x, y}]]

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

A370464 Triangular array read by rows. T(n,k) is the number of binary relations R on [n] such that the unique idempotent in {R^i:i>=1} contains exactly k non-arcless strongly connected components, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 3, 9, 4, 25, 277, 162, 48, 543, 38409, 18136, 6912, 1536, 29281, 23169481, 7195590, 2346000, 691200, 122880

Offset: 0

Geoffrey Critzer, Feb 19 2024

			Triangle begins ...
     1;
     1,        1;
     3,        9,       4;
    25,      277,     162,      48;
   543,    38409,   18136,    6912,   1536;
 29281, 23169481, 7195590, 2346000, 691200, 122880;
 ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

Cf. A002416 (row sums), A003024 (column k=0), A011266 (main diagonal), A370385.

nn = 5; B[n_] := n! 2^Binomial[n, 2];s[x_, y_] := y x + (3 y + y^2) x^2/2! + (139 y + 3 y^2 + 2 y^3) x^3/3! + (25575 y + 103 y^2 + 12 y^3 + 6 y^4) x^4/
    4! + (18077431 y + 4815 y^2 + 230 y^3 + 60 y^4 + 24 y^5) x^5/5! ;
ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /.Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}]; Map[Select[#, # > 0 &] &,Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[-(x + s[x, y])]], {x, 0, nn}], {x, y}]]

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

A371633 Number of ways to choose a simple labeled graph on [n], then partition the vertex set into independent sets, then choose a vertex from each independent set.

Original entry on oeis.org

1, 1, 4, 35, 740, 34629, 3581894, 802937479, 386655984648, 396751196145673, 862046936883049482, 3946154005780155709451, 37896676657907955726032908, 760791471852690599411320471565, 31830237745009483676211065390546958, 2768049771339996987073597682850993569807

Offset: 0

Geoffrey Critzer, Jun 06 2024

nonn

An independent set is a set of vertices in a graph, no two of which are adjacent.

R. P. Stanley, Exponential structures

Cf. A000248, A240936, A058843, A011266.

nn = 14; B[n_] := n! 2^Binomial[n, 2];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[Exp[ggf[x Exp[x]]], {x, 0, nn}], x]

Sum_{n>=0} a(n)*x^n/A011266(n) = exp(f(x)) where f(x) = Sum_{n>=1} n*x^n/A011266(n).

A380374 Number of ways to topologically sort the strong components of a labeled digraph on [n].

Original entry on oeis.org

1, 1, 5, 90, 5542, 1252120, 1152382456, 4491243320144, 72454914124818352, 4729326805677997351296, 1238455260161143286333919616, 1298230864749797963009864293455616, 5444709289384095954326434486307506566400, 91344784292457849099764110418297773249212062720

Offset: 0

Geoffrey Critzer, Jan 23 2025

nonn

a(n) is the number of ways to choose a labeled digraph D with n vertices (as in A053763) and then topologically sort the condensation of D, i.e., the directed acyclic graph (A003024) obtained by contracting each strongly connected component of D to a single vertex.

The cases in which D is acyclic are counted by A011266.

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
Wikipedia, Strongly connected component
Wikipedia, Topological sorting

Cf. A053763, A003024, A011266, A003030.

nn = 13; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]];s[z_] := Total[strong Table[z^i/B[i], {i, 1, 58}]];
B[n_] := n! 2^Binomial[n, 2];Table[B[n], {n, 0, nn}] CoefficientList[ Series[1/(1 - s[z]), {z, 0, nn}], z]

Sum_{n>=0} a(n)*x^n/B(n) = 1/(1-s(x)) where B(n) = A011266(n) and s(x) = Sum_{n>=1} A003030(n)*x^n/B(n).

cp's OEIS Frontend

A361527 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] having exactly k strongly connected components all of which are simple cycles, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A370385 Triangular array read by rows. T(n,k) is the number of binary relations R on [n] such that the unique idempotent relation in {R^i:i>=1} is a quasi-order containing exactly k strongly connected components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A370464 Triangular array read by rows. T(n,k) is the number of binary relations R on [n] such that the unique idempotent in {R^i:i>=1} contains exactly k non-arcless strongly connected components, n>=0, 0<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A371633 Number of ways to choose a simple labeled graph on [n], then partition the vertex set into independent sets, then choose a vertex from each independent set.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A380374 Number of ways to topologically sort the strong components of a labeled digraph on [n].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula