A217580 -id:A217580 - cp's OEIS frontend

A217652 Number of isolated nodes over all labeled directed graphs on n nodes.

0, 1, 2, 12, 256, 20480, 6291456, 7516192768, 35184372088832, 648518346341351424, 47223664828696452136960, 13617340432139183023890366464, 15576890575604482885591488987660288, 70778732319555200400381918345807787982848

Offset: 0

Geoffrey Critzer, Oct 09 2012

nonn

a(n) = Sum_{k=1..n} A217580(n,k) * k.

a(n) is also the number of labeled directed graphs on n nodes with an "Emperor". - Rémy-Robert Joseph, Nov 12 2012

Alois P. Heinz, Table of n, a(n) for n = 0..40

See also A123903 (case of tournaments) and A219116 (case of semicomplete digraphs) Rémy-Robert Joseph, Nov 12 2012

a:= n-> 2^(n^2-3*n+2)*n:
seq (a(n), n=0..15);  # Alois P. Heinz, Oct 09 2012

nn=15; s=Sum[2^(n^2-n)x^n/n!,{n,0,nn}]; Range[0,nn]! CoefficientList[Series[x s, {x,0,nn}], x]

A217652(n):=2^(n^2-3*n+2)*n$ makelist(A217652(n),n,0,10); /* Martin Ettl, Nov 13 2012 */

E.g.f.: x * A(x) where A(x) is the e.g.f. for A053763.

a(n) = 2^(n^2-3*n+2)*n. - Alois P. Heinz, Oct 09 2012

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.

cp's OEIS Frontend

A217652 Number of isolated nodes over all labeled directed graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula