A323819 -id:A323819 - cp's OEIS frontend

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

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

A309667 Number of non-isomorphic connected set-systems on up to n vertices.

Original entry on oeis.org

1, 2, 5, 35, 1947, 18664537, 12813206150464222, 33758171486592987151274638818642016, 1435913805026242504952006868879460423801146743462225386062178112354069599

Offset: 0

Gus Wiseman, Aug 11 2019

nonn

A set-system is a finite set of finite nonempty sets.

			Non-isomorphic representatives of the a(0) = 1 through a(2) = 5 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{1,2}}
             {{2},{1,2}}
             {{1},{2},{1,2}}

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

The covering case is A323819 (first differences).
The BII-numbers of connected set-systems are A326749.
The labeled version is A326964.
Cf. A000371, A000612, A001187, A007718, A058891, A092918, A261006, A300913, A323818.

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

Original entry on oeis.org

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

Gus Wiseman, Jan 02 2024

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.

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

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.

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

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

More terms from Alois P. Heinz, Jan 04 2024

A323820 Number of non-isomorphic connected set-systems covering n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 6, 171, 611846, 200253853704319, 263735716028826427334553304608242, 5609038300883759793482640992086670066496449147691597380632107520565546

Offset: 0

Gus Wiseman, Jan 30 2019

nonn

The labeled case is A323817.

			Non-isomorphic representatives of the a(3) = 6 set-systems:
  {{1,2,3}}
  {{1,3},{2,3}}
  {{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Cf. A000295, A003465, A016031, A048143, A055621, A293510, A305001, A317795 (not necessarily connected), A323817 (unlabeled case), A323819 (with singletons).

Inverse Euler transform of A317795.

cp's OEIS Frontend

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

A309667 Number of non-isomorphic connected set-systems on up to n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A323820 Number of non-isomorphic connected set-systems covering n vertices with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula