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.

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

Offset: 0

Author

Geoffrey Critzer, Oct 07 2023

Keywords

• nonn

Comments

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.

Links

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

Crossrefs

Cf. A003030.

Programs

Mathematica

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]

Formula

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