A003087 -id:A003087 - cp's OEIS frontend

A350448 Triangle read by rows: T(n,k) is the number of acyclic graphs on n unlabeled nodes whose longest directed path has k arcs.

1, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 8, 14, 8, 0, 1, 20, 89, 128, 64, 0, 1, 55, 634, 1934, 2336, 1024, 0, 1, 163, 5668, 36428, 83648, 84992, 32768, 0, 1, 556, 67926, 959718, 3919584, 7097088, 6144000, 2097152, 0, 1, 2222, 1137641, 37205922, 268989920, 793138688, 1175224320, 880803840, 268435456, 0

Offset: 0

Andrew Howroyd, Dec 31 2021

			Triangle begins:
  1;
  1,   0;
  1,   1,    0;
  1,   3,    2,     0;
  1,   8,   14,     8,     0;
  1,  20,   89,   128,    64,     0;
  1,  55,  634,  1934,  2336,  1024,     0;
  1, 163, 5668, 36428, 83648, 84992, 32768, 0;
  ...

Row sums are A003087.
Diagonals include A000007, A006125.
Cf. A122078.

\\ See PARI link in A122078 for program code.
{ my(T=AcyclicDigraphsByLongestPath(8)); for(n=1, #T, print(T[n])) }

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

A361589 Number of acyclic digraphs on n unlabeled nodes without isolated nodes.

Original entry on oeis.org

1, 0, 1, 4, 25, 271, 5682, 237684, 20042357, 3404651985, 1162523674892, 796395726736678, 1093229314594543016, 3004753338859186373234, 16527845763725396055765240, 181891586856152393087373330332, 4004313490358484085907684748704180, 176328671349936542115174881107633828418

Offset: 0

Andrew Howroyd, Mar 16 2023

nonn

Row sums of A361588.

Cf. A003087, A350794.

A361589seq(16) \\ See PARI link in A350794 for program code.

a(n) = A003087(n) - A003087(n-1) for n >= 1.

cp's OEIS Frontend

A350448 Triangle read by rows: T(n,k) is the number of acyclic graphs on n unlabeled nodes whose longest directed path has k arcs.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

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

A361589 Number of acyclic digraphs on n unlabeled nodes without isolated nodes.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula