A368602 Triangle read by rows where T(n,k) is the number of labeled acyclic digraphs on {1..n} with sinks {1..k}.

1, 0, 1, 0, 1, 1, 0, 5, 3, 1, 0, 79, 33, 7, 1, 0, 3377, 1071, 161, 15, 1, 0, 362431, 92289, 10591, 705, 31, 1, 0, 93473345, 19856703, 1832705, 93375, 2945, 63, 1, 0, 56272471039, 10249747713, 789619327, 32382465, 782719, 12033, 127, 1

Offset: 0

Author

Gus Wiseman, Jan 02 2024

Keywords

• nonn
• tabl

Comments

Also the number of set-systems with n vertices and n edges such that {i} is a singleton edge iff i <= k, and such that there is only one way to choose a different vertex from each edge.

Examples

			Triangle begins:
    1
    0    1
    0    1    1
    0    5    3    1
    0   79   33    7    1
    0 3377 1071  161   15    1
    ...
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},{2},{1,2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{1,3},{1,2,3}}
		

Crossrefs

Column k = n-1 is A000225 = A058877(n)/n.

Column k = 1 is A134531 (up to sign) or A003025(n)/n, non-fixed A350415.

For any choice of k sinks we get A361718.

A058891 counts set-systems, unlabeled A000612.

A059201 counts covering T_0 set-systems.

A323818 counts covering connected set-systems, unlabeled A323819.

Cf. A000169, A003024, A003087, A082402, A088957, A334282, A367862, A367904, A367908, A368600, A368601.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n]],{n}], Union@@Cases[#,{_}]==Range[k] && Length[Select[Tuples[#],UnsameQ@@#&]]==1&]], {n,0,3},{k,0,n}]

Formula

T(n,k) = A361718(n,k)/binomial(n,k).

Extensions

More terms from Alois P. Heinz, Jan 04 2024