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,5

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

Links

Table of n, a(n) for n=0..44.

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.

Formula

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

Example

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

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

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.

Sequence in context: A352399 A129467 A129065 * A355565 A202700 A024026

Adjacent sequences: A361715 A361716 A361717 * A361719 A361720 A361721

Keyword

nonn,tabl

Author

Geoffrey Critzer, Apr 02 2023

Status

approved