A003025 -id:A003025 - cp's OEIS frontend

A350487 Triangle read by rows: T(n,k) is the number of acyclic digraphs on n labeled nodes with k arcs and a global source, n >= 1, k = 0..n*(n-1)/2.

1, 0, 2, 0, 0, 9, 6, 0, 0, 0, 64, 132, 96, 24, 0, 0, 0, 0, 625, 2640, 4850, 4900, 2850, 900, 120, 0, 0, 0, 0, 0, 7776, 55800, 186480, 379170, 516660, 491040, 328680, 152640, 46980, 8640, 720, 0, 0, 0, 0, 0, 0, 117649, 1286670, 6756120, 22466010

Offset: 1

Andrew Howroyd, Jan 01 2022

			Triangle begins:
  [1] 1;
  [2] 0, 2;
  [3] 0, 0, 9,  6;
  [4] 0, 0, 0, 64, 132,   96,   24;
  [5] 0, 0, 0,  0, 625, 2640, 4850, 4900, 2850, 900, 120;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

Row sums are A003025.
Leading diagonal is A000169.
The unlabeled version is A350488.
Cf. A081064.

T(n)={my(a=vector(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1)*binomial(n,k)*((1+'y)^(n-k)-1)^k*a[n-k])); [Vecrev(p) | p <- a]}
{ my(A=T(6)); for(n=1, #A, print(A[n])) }

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.

Original entry on oeis.org

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

A060335 Number of n-node labeled acyclic digraphs with 3 out-points.

Original entry on oeis.org

1, 28, 1610, 211820, 64144675, 44218682312, 68501035223124, 235728863806525320, 1784437537982029455525, 29470895991194487015464740, 1054563682428338672254476697886, 81276604641664521211218527866093204

Offset: 3

Vladeta Jovovic, Apr 10 2001

nonn

R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.

Andrew Howroyd, Table of n, a(n) for n = 3..50

A diagonal of A058876.

Cf. A003025, A003026.

\\ requires A058876.
my(T=A058876(20)); vector(#T-2, n, T[n+2][3]) \\ Andrew Howroyd, Dec 27 2021

A060337 Number of labeled acyclic digraphs with n nodes containing exactly n-2 points of in-degree zero.

Original entry on oeis.org

15, 198, 1610, 10575, 61845, 336924, 1751076, 8801325, 43141175, 207347778, 980828238, 4578689115, 21135851625, 96628899960, 438068838536, 1971349880985, 8813183238315, 39169902510270, 173172640973010

Offset: 3

Vladeta Jovovic, Apr 10 2001

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.

Andrew Howroyd, Table of n, a(n) for n = 3..500
Index entries for linear recurrences with constant coefficients, signature (21,-189,955,-2982,5964,-7640,6048,-2688,512).

Third column of A058876.

Cf. A003025, A003026.

LinearRecurrence[{21,-189,955,-2982,5964,-7640,6048,-2688,512},{15,198,1610,10575,61845,336924,1751076,8801325,43141175},20] (* Harvey P. Dale, Mar 23 2022 *)

\\ requires A058876.
my(T=A058876(25)); vector(#T-2, n, T[n+2][n]) \\ Andrew Howroyd, Dec 27 2021

G.f.: x^3*(15 - 117*x + 287*x^2 - 138*x^3 - 300*x^4 + 280*x^5)/((1 - x)*(1 - 2*x)*(1 - 4*x))^3. - Andrew Howroyd, Dec 27 2021

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

cp's OEIS Frontend

A350487 Triangle read by rows: T(n,k) is the number of acyclic digraphs on n labeled nodes with k arcs and a global source, n >= 1, k = 0..n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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

A060335 Number of n-node labeled acyclic digraphs with 3 out-points.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

A060337 Number of labeled acyclic digraphs with n nodes containing exactly n-2 points of in-degree zero.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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