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.

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

Author

Geoffrey Critzer, Apr 02 2023

Keywords

• nonn
• tabl

Comments

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}}

Examples

			Triangle begins:
  1;
  0,     1;
  0,     2,     1;
  0,    15,     9,    1;
  0,   316,   198,   28,  1;
  0, 16885, 10710, 1610, 75, 1;
  ...
		

Links

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

Crossrefs

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.

Programs

Mathematica

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}]

Formula

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