A003030 -id:A003030 - cp's OEIS frontend

A186081 Number of binary relations R on {1,2,...,n} such that the transitive closure of R is the trivial relation.

1, 1, 4, 144, 25696, 18082560, 47025585664, 450955726792704, 16260917603754029056, 2253010420928564535951360, 1219004114245442237742488879104, 2601909995433633381004133738019815424, 22040854392120341022554569447470527813779456

Offset: 0

Geoffrey Critzer, Feb 12 2011

For n >= 2, a(n) is the number of strongly connected binary relations on [n]. - Geoffrey Critzer, Dec 04 2023

			a(2)=4 because there are four relations on {1,2} whose transitive closure is {(1,1), (1,2), (2,1), (2,2)}. They are the three nontransitive relations,{(1,2), (2,1)}, {(1,2), (2,1), (2,2)}, {(1,1), (1,2), (2,1)} and the trivial relation itself.

Cf. A002416, A003030, A070322, A361269.

Needs["Combinatorica`"];
f[list_] := Apply[Plus, Table[MatrixPower[list,n], {n,1,Length[list]}]];
Join[{1}, Table[Length[Select[Map[Flatten, Map[f, Tuples[Strings[{0, 1}, n], n]]], FreeQ[#, 0] &]], {n, 1, 4}]]
(* Second program: *)
a[ n_] := If[ n < 1, Boole[n == 0], With[{triv = matnk[n, 2^n^2 - 1]}, Sum[ Boole[triv === transitiveClosure[ matnk[n, k]]], {k, 0, 2^n^2 - 1}]]]; matnk[n_, k_] := Partition[ IntegerDigits[ k, 2, n^2], n]; transitiveClosure[x_] := FixedPoint[ Sign@(# + Dot[#, x]) &, x, Length@x]; (* Michael Somos, Mar 08 2012 *)

From Geoffrey Critzer, Dec 04 2023: (Start)
For n >= 2, a(n) = A003030(n)*2^n = A361269(n,1).
E.g.f.: 1 + s(2*x) - x where s(x) is the e.g.f. for A003030. (End)

a(0)=1 prepended by Alois P. Heinz, Aug 31 2015
a(6) from Bert Dobbelaere, Feb 16 2019
a(7)-a(12) from Geoffrey Critzer, Dec 04 2023

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

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 18, 18, 18, 0, 1606, 1098, 684, 446, 0, 565080, 263580, 116370, 55620, 26430, 0, 734774776, 225806940, 68822910, 24578010, 9729090, 3596762, 0, 3523091615568, 680637057912, 136498491360, 34626926250, 10819771830, 3694824126, 1111506858

Offset: 0

Andrew Howroyd, May 04 2023

			Triangle begins:
  1;
  0,         1;
  0,         1,         2;
  0,        18,        18,       18;
  0,      1606,      1098,      684,      446;
  0,    565080,    263580,   116370,    55620,   26430;
  0, 734774776, 225806940, 68822910, 24578010, 9729090, 3596762;
  ...

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

Column k=1 is A003030.
Main diagonal is A082402.
Row sums are A003027.
The unlabeled version is A361587.
Cf. A189898, A361455.

\\ Uses functions defined in A361455.
T(n)={my(e=2); [Vecrev(p) | p<-Vec(serlaplace(1 + log(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])) }

A366350 Number of labeled directed graphs on [n] with self loops allowed such that the following implication holds for all x,y in [n]. If x and y are in distinct strongly connected components then there is a directed edge from x to y or from y to x.

Original entry on oeis.org

1, 2, 12, 240, 29056, 18656960, 47473519744, 452285200546816, 16275391021965395968, 2253596336074652670148608, 1219094258112479334941371285504, 2601963635581642923807860961645363200

Offset: 0

Geoffrey Critzer, Oct 07 2023

nonn

Equivalently, a(n) is the number of n x n binary relation matrices such that each of the blocks above the diagonal of its Frobenius normal form is a 1-block (a block containing all 1's). See Gregory, Kirkland and Pullman for definition of Frobenius normal form.

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.

Cf. A003030.

nn = 11; strong =Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[x_] := Total[Prepend[strong Table[x^i/i!, {i, 1, 58}], 1]];Table[n!, {n, 0, nn}] CoefficientList[Series[1/(1 - (s[x + x] - 1)), {x, 0, nn}], x]

E.g.f.: 1/(1-(s(2x)-1)) where s(x) is the e.g.f. for A003030.

A054944 Number of strongly connected labeled digraphs on n nodes with an even number of edges.

Original entry on oeis.org

1, 1, 10, 806, 282552, 367387448, 1761545808144, 31759604694834608, 2200205489188051324800, 595216852658907342647881088, 635231932478914399659212340198144, 2690533983413127566229805840755699623168, 45382894419701545228622064475653706686181248000, 3054532231410772852023213016232868881612380320979954688

Offset: 1

N. J. A. Sloane, May 24 2000

V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A054945.

b[n_] := b[n] = If[n == 1, 1, 2^(n*(n - 1)) - Sum[Binomial[n, j]*2^((n - 1)*(n - j))*b[j], {j, 1, n - 1}]];
c[1] = 1; c[n_] := c[n] = b[n] + Sum[Binomial[n - 1, j - 1]*b[n - j]*c[j], {j, 1, n - 1}];
a[n_] := (c[n] + (n - 1)!)/2;
Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Aug 30 2019, after Vaclav Kotesovec in A003030 *)

a(n) = (A003030(n)+(n-1)!)/2.

More terms from Vladeta Jovovic, Jul 15 2000

More terms from Jean-François Alcover, Aug 30 2019

A054945 Number of strongly connected labeled digraphs on n nodes with an odd number of edges.

Original entry on oeis.org

0, 0, 8, 800, 282528, 367387328, 1761545807424, 31759604694829568, 2200205489188051284480, 595216852658907342647518208, 635231932478914399659212336569344, 2690533983413127566229805840755659706368, 45382894419701545228622064475653706685702246400, 3054532231410772852023213016232868881612380314752933888

Offset: 1

N. J. A. Sloane, May 24 2000

V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A003030, A054944.

b[n_] := b[n] = If[n == 1, 1, 2^(n*(n - 1)) - Sum[Binomial[n, j]*2^((n - 1)*(n - j))*b[j], {j, 1, n - 1}]];
c[1] = 1; c[n_] := c[n] = b[n] + Sum[Binomial[n - 1, j - 1]*b[n - j]*c[j], {j, 1, n - 1}];
a[n_] := (c[n] - (n - 1)!)/2;
Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Aug 30 2019, after  Vaclav Kotesovec in A003030 *)

a(n) = (A003030(n)-(n-1)!)/2.

More terms from Vladeta Jovovic, Jul 15 2000

More terms from Jean-François Alcover, Aug 30 2019

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

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 27, 27, 9, 1, 2401, 1372, 294, 28, 1, 759375, 253125, 33750, 2250, 75, 1, 887503681, 171774906, 13852815, 595820, 14415, 186, 1, 3938980639167, 437664515463, 20841167403, 551353635, 8751645, 83349, 441, 1, 67675234241018881, 4263006881324024, 117484441611292, 1850148686792, 18210124870, 114709448, 451612, 1016, 1

Offset: 0

Geoffrey Critzer, Apr 03 2023

			Triangle T(n,k) begins:
       1;
       0,      1;
       1,      2,     1;
      27,     27,     9,    1;
    2401,   1372,   294,   28,  1;
  759375, 253125, 33750, 2250, 75, 1;
  ...

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

Cf. A086206 (column k=0), A053763 (row sums), A361592, A350792 (a subclass of the digraphs for the case k=1 of this sequence), A003028.

nn = 6; B[n_] := n! 2^Binomial[n, 2] ; 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, 0, nn}]; Table[ Take[(Table[B[n], {n, 0, nn}] CoefficientList[   Series[ggf[Exp[(u - 1) z]]/ggf[Exp[-s[z]]], {z, 0, nn}], {z, u}])[[i]], i], {i, 1, nn + 1}]

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

Original entry on oeis.org

1, 0, 1, 2, 1, 1, 36, 24, 3, 1, 2240, 1762, 87, 6, 1, 462720, 577000, 8630, 215, 10, 1, 332613632, 737645836, 3455820, 26085, 435, 15, 1, 867410804736, 3525456796232, 5166693532, 12154030, 61775, 777, 21, 1, 8503156728135680, 63526200994115056, 28215577119548, 20705805988, 32624585, 125776, 1274, 28, 1

Offset: 0

Geoffrey Critzer, Apr 11 2023

Here, a strongly connected component is isolated if it is both an in-component and an out-component. A component is an in-component (out-component) if it corresponds to a node with outdegree (indegree) zero in the condensation of the digraph.

			       1;
       0,      1;
       2,      1,    1;
      36,     24,    3,   1;
    2240,   1762,   87,   6,  1;
  462720, 577000, 8630, 215, 10, 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.

Cf. A217580, A361579, A003030, A053763.

nn = 8; 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}]];
d[z_] := Sum[2^(n (n - 1)) z^n/n!, {n, 0, nn}]; Table[Take[(Table[n!, {n, 0, nn}] CoefficientList[ Series[Exp[(u - 1) s[z]] d[z], {z, 0, nn}], {z, u}])[[i]],
   i], {i, 1, nn + 1}] // Grid

E.g.f.: exp((u-1)*S(z))*D(z) where S(z) is the e.g.f. for A003030 and D(z) is the e.g.f. for A053763.

A363834 Number of labeled digraphs (with self loops allowed) on [n] such that every strongly connected component of size at least 2 contains a vertex with a self loop.

Original entry on oeis.org

1, 2, 15, 452, 58023, 31083662, 66296957895, 554842541248592, 18340342731323665263, 2411916363098805776251322, 1266238008719333748929247025455, 2657054767893996575723268008873476172, 22295054304671836968688374028608806896204023

Offset: 0

Geoffrey Critzer, Oct 19 2023

nonn

The sequence gives a good lower bound for the number of convergent binary relations (A365534) which is only known for n <= 6.

			a(2) = 15 because there are 16 labeled digraphs with self loops on [2] and all of them are good except: [1->2,2->1].

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

Cf. A365534, A070322, A003030.

nn = 12; B[n_] := 2^Binomial[n, 2] n!; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"], Length@# == 2 &][[All, 2]]; sm[x_] :=  Total[Table[2^n - 1, {n, 1, Length[strong]}] 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[-(sm[x] + x)]], {x, 0, nn}], x]

Sum_{n>=0} a(n)*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-(sm(x)-1+x))) where E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)), sm(x) = Sum_{n>=0} (2^n-1)*A003030(n)*x^n/n! and @ is the exponential Hadamard product (see Panafieu and Dovgal).

A365325 Triangular array read by rows. T(n,k) is the number of labeled digraphs (with self loops allowed) on [n] containing exactly k primitive components, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 4, 9, 3, 51, 298, 138, 25, 1831, 40815, 17853, 4494, 543, 166930, 23752151, 7418420, 1861755, 325895, 29281, 36681301, 55427713806, 10701675348, 2105585760, 391017795, 53021223, 3781503

Offset: 0

Geoffrey Critzer, Oct 22 2023

A primitive component (A070322) is a strongly connected component (A003030) such that the gcd of the lengths of its cycles is 1.

			Triangle begins
   1;
   1,     1;
   4,     9,     3;
  51,   298,   138,   25;
1831, 40815, 17853, 4494, 543;
...

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

Cf. A002416 (row sums), A003024 (main diagonal), A070322, A003030, A361269.

nn = 6; 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}]]; primitive =
 Select[Import["https://oeis.org/A070322/b070322.txt", "Table"],
   Length@# == 2 &][[All, 2]]; pr[x_] := Total[primitive Table[x^i/i!, {i, 0, 6}]];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[- (y (pr[x] - 1) + s[2 x] - (pr[x] - 1))]], {x,
      0, nn}], {x, y}]] // Grid

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

A366396 Number of labeled directed graphs on [n] with self loops allowed such that the following implication holds for all x,y in [n]. If x and y are in distinct strongly connected components and y is reachable from x then there is a directed edge from x to y.

Original entry on oeis.org

1, 2, 16, 368, 34624, 19194752, 47730489856, 452968293106688, 16282682505688059904, 2253889950034687424110592, 1219139359408849690950674415616, 2601990460616856808147727573494857728, 22041041736721298233193355574294486210576384

Offset: 0

Geoffrey Critzer, Oct 08 2023

nonn

Cf. A366350, A001035, A003030.

nn = 12; posets = Select[Import["https://oeis.org/A001035/b001035.txt", "Table"],
   Length@# == 2 &][[All, 2]];p[x_] := Total[posets Table[x^i/i!, {i, 0, 18}]]; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[x_] := Total[Prepend[strong Table[x^i/i!, {i, 1, 58}], 1]];Table[n!, {n, 0, nn}] CoefficientList[Series[p[s[2 x] - 1], {x, 0, nn}], x]

E.g.f.: p(s(2x)-1) where p(x) is the e.g.f. for A001025 and s(x) is the e.g.f. for A003030.

cp's OEIS Frontend

A186081 Number of binary relations R on {1,2,...,n} such that the transitive closure of R is the trivial relation.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A366350 Number of labeled directed graphs on [n] with self loops allowed such that the following implication holds for all x,y in [n]. If x and y are in distinct strongly connected components then there is a directed edge from x to y or from y to x.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A054944 Number of strongly connected labeled digraphs on n nodes with an even number of edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A054945 Number of strongly connected labeled digraphs on n nodes with an odd number of edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A363834 Number of labeled digraphs (with self loops allowed) on [n] such that every strongly connected component of size at least 2 contains a vertex with a self loop.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs