A361579 -id:A361579 - cp's OEIS frontend

A003028 Number of digraphs on n labeled nodes with a source.

1, 3, 51, 3614, 991930, 1051469032, 4366988803688, 71895397383029040, 4719082081411731363408, 1237678715644664931691596416, 1297992266840866792981316221144960, 5444416466164313011147841248189209354496, 91343356480627224177654291875698256656613808896

Offset: 1

N. J. A. Sloane

Here a source is a node that is connected by a directed path to every other node in the digraph (but does not necessarily have indegree zero). - Geoffrey Critzer, Apr 14 2023

V. Jovovic and G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996) 237-247.
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

The unlabeled version is A051421.
Row sums of A057274.
Column k=1 of A361579.
Cf. A003027, A003029, A003030, A049524, A049414, A350792.

Initially(12) \\ See A057274. - Andrew Howroyd, Jan 11 2022

Corrected and extended by Vladeta Jovovic, Goran Kilibarda

Terms a(12) and beyond from Andrew Howroyd, Jan 11 2022

A361718 Triangular array read by rows. T(n,k) is the number of labeled directed acyclic graphs on [n] with exactly k nodes of indegree 0.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 15, 9, 1, 0, 316, 198, 28, 1, 0, 16885, 10710, 1610, 75, 1, 0, 2174586, 1384335, 211820, 10575, 186, 1, 0, 654313415, 416990763, 64144675, 3268125, 61845, 441, 1, 0, 450179768312, 286992935964, 44218682312, 2266772550, 43832264, 336924, 1016, 1

Offset: 0

Geoffrey Critzer, Apr 02 2023

Also the number of sets of n nonempty subsets of {1..n}, k of which are singletons, such that there is only one way to choose a different element from each. For example, row n = 3 counts the following set-systems:
  {{1},{1,2},{1,3}}    {{1},{2},{1,3}}    {{1},{2},{3}}
  {{1},{1,2},{2,3}}    {{1},{2},{2,3}}
  {{1},{1,3},{2,3}}    {{1},{3},{1,2}}
  {{2},{1,2},{1,3}}    {{1},{3},{2,3}}
  {{2},{1,2},{2,3}}    {{2},{3},{1,2}}
  {{2},{1,3},{2,3}}    {{2},{3},{1,3}}
  {{3},{1,2},{1,3}}    {{1},{2},{1,2,3}}
  {{3},{1,2},{2,3}}    {{1},{3},{1,2,3}}
  {{3},{1,3},{2,3}}    {{2},{3},{1,2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{1,3},{1,2,3}}
  {{2},{1,2},{1,2,3}}
  {{2},{2,3},{1,2,3}}
  {{3},{1,3},{1,2,3}}
  {{3},{2,3},{1,2,3}}

			Triangle begins:
  1;
  0,     1;
  0,     2,     1;
  0,    15,     9,    1;
  0,   316,   198,   28,  1;
  0, 16885, 10710, 1610, 75, 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. A058876 (mirror), A361579, A224069.
Row-sums are A003024, unlabeled A003087.
Column k = 1 is A003025(n) = |n*A134531(n)|.
Column k = n-1 is A058877.
For fixed sinks we get A368602.
A058891 counts set-systems, unlabeled A000612.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A000169, A059201, A082402, A088957, A133686, A334282, A350415, A367904, A367908, A368600, A368601.

nn = 8; B[n_] := n! 2^Binomial[n, 2] ;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[-z]], {z, 0, nn}], {z, u}])[[i]], i], {i, 1, nn + 1}] // Grid
nv=4;Table[Length[Select[Subsets[Subsets[Range[n]],{n}], Count[#,{_}]==k&&Length[Select[Tuples[#], UnsameQ@@#&]]==1&]],{n,0,nv},{k,0,n}]

T(n,k) = A368602(n,k) * binomial(n,k). - Gus Wiseman, Jan 03 2024

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

A003028 Number of digraphs on n labeled nodes with a source.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A361718 Triangular array read by rows. T(n,k) is the number of labeled directed acyclic graphs on [n] with exactly k nodes of indegree 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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