A345258 -id:A345258 - cp's OEIS frontend

A350794 Number of digraphs on n unlabeled nodes with a global source and sink.

1, 1, 2, 20, 574, 48854, 12444800, 9849180230, 25265372689314, 218451490123178684, 6562780921564838071734, 700270642102506752862044142, 269621199012416753533007480951824, 378982029174285293421133982496722212766, 1962119228020498122395242424575089505014761082

Offset: 1

Andrew Howroyd, Jan 19 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Andrew Howroyd, PARI Program, Jan 2022, updated Mar 2023.

The labeled version is A350790.
Row sums of A350795.
Cf. A049531, A051421, A345258, A350360, A350796.

A350794seq(15) \\ See link for program code.

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Original entry on oeis.org

1, 2, 15, 316, 16885, 2174586, 654313415, 450179768312, 696979588034313, 2398044825254021110, 18151895792052235541515, 299782788128536523836784628, 10727139906233315197412684689421

Offset: 1

N. J. A. Sloane

nonn

From Gus Wiseman, Jan 02 2024: (Start)
Also the number of n-element sets of finite nonempty subsets of {1..n}, including a unique singleton, such that there is exactly one way to choose a different element from each. For example, the a(0) = 0 through a(3) = 15 set-systems are:
  .  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,3}}
            {{2},{1,2}}  {{1},{1,2},{2,3}}
                         {{1},{1,3},{2,3}}
                         {{2},{1,2},{1,3}}
                         {{2},{1,2},{2,3}}
                         {{2},{1,3},{2,3}}
                         {{3},{1,2},{1,3}}
                         {{3},{1,2},{2,3}}
                         {{3},{1,3},{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}}
These set-systems are all connected.
The case of labeled graphs is A000169.
(End)

			a(2) = 2: o-->--o (2 ways)
a(3) = 15: o-->--o-->--o (6 ways) and
o ... o o-->--o
.\ . / . \ . /
. v v ... v v
.. o ..... o
(3 ways) (6 ways)

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
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.

A diagonal of A058876.
Row sums of A350487.
The unlabeled version is A350415.
Column k=1 of A361718.
Cf. A003026, A003028, A345258.
For any number of sinks we have A003024, unlabeled A003087.
For n-1 sinks we have A058877.
For a fixed sink we have A134531 (up to sign), column k=1 of A368602.
Cf. A000169, A058891, A059201, A082402, A088957, A323818, A334282, A367904, A368600, A368601.

Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Count[#,{}]==1&&Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,4}] (* _Gus Wiseman, Jan 02 2024 *)

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

\\ see Marcel et al. link (formula for a').
seq(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) * (2^(n-k)-1)^k * a[n-k])); a} \\ Andrew Howroyd, Jan 01 2022

a(n) = (-1)^(n-1) * n * A134531(n). - Gus Wiseman, Jan 02 2024

More terms from Vladeta Jovovic, Apr 10 2001

A350415 Number of acyclic digraphs on n unlabeled nodes with a global source (or sink).

Original entry on oeis.org

1, 1, 3, 16, 164, 3341, 138101, 11578037, 1961162564, 668678055847, 457751797355605, 628137837068751147, 1726130748679532455689, 9493834992383031007906911, 104476428350838383854529661007, 2299979227717819421763629684068904

Offset: 1

Andrew Howroyd, Dec 29 2021

nonn

A local source (also called an out-node) is a node whose in-degree is zero. In the case of an acyclic digraph with only one local source, the source is also a global source.

Andrew Howroyd, Table of n, a(n) for n = 1..50
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.

The labeled case is A003025.
Row sums of A350488.
A diagonal of A122078.
Cf. A003087, A345258, A350360.

A350415seq(16) \\ See PARI link in A122078 for program code.

A049531 Number of digraphs with a source and a sink on n unlabeled nodes.

Original entry on oeis.org

1, 2, 11, 173, 8675, 1483821, 870901739, 1786098545810, 13011539185371716, 341128981258340797839, 32519138088689298538132027, 11366354205366488038532562993809, 14668937734550708660348161757913398001, 70315451107713339843384354196009678853303102

Offset: 1

Vladeta Jovovic, Goran Kilibarda

Here a source is defined to be a node which has a directed path to all other nodes and a sink to be a node to which all other nodes have a directed path. A digraph with a source and a sink can also be described as initially-finally connected. - Andrew Howroyd, Jan 01 2022

V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), p. 246.

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

Row sums of A057278.
The labeled version is A049524.
Cf. A003085, A035512, A003088, A051421, A345258, A350794.

\\ See PARI link in A350794 for program code.
A049531seq(15) \\ Andrew Howroyd, Jan 21 2022

a(6)-a(7) from Andrew Howroyd, Jan 01 2022

Terms a(8) and beyond from Andrew Howroyd, Jan 20 2022

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

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 4, 4, 1, 0, 0, 0, 0, 1, 9, 25, 32, 22, 8, 1, 0, 0, 0, 0, 0, 1, 17, 92, 259, 441, 496, 379, 195, 66, 13, 1, 0, 0, 0, 0, 0, 0, 1, 28, 259, 1286, 4026, 8754, 13930, 16686, 15289, 10785, 5842, 2397, 722, 151, 19, 1

Offset: 1

Andrew Howroyd, Jan 08 2022

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 1, 1;
  [4] 0, 0, 0, 1, 4, 4,  1;
  [5] 0, 0, 0, 0, 1, 9, 25, 32,  22,   8,   1;
  [6] 0, 0, 0, 0, 0, 1, 17, 92, 259, 441, 496, 379, 195, 66, 13, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)

Row sums are A345258.
Column sums are A350492.
Cf. A122078, A350447, A350449, A350488.

\\ See PARI link in A122078 for program code.
{ my(A=A350491rows(7)); for(i=1, #A, print(A[i])) }

A350492 Number of unlabeled acyclic digraphs with n arcs and a global source and sink.

Original entry on oeis.org

1, 1, 1, 2, 5, 14, 44, 153, 584, 2414, 10732, 50909, 256198, 1360645, 7593530, 44366458, 270517289, 1716555943, 11308051214, 77170484915, 544525867544, 3965944595335, 29769162604337, 229970873746105, 1826057472681595, 14886348784740516

Offset: 0

Andrew Howroyd, Jan 08 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..40

Column sums of A350491.

Cf. A122078, A345258, A350451, A350490.

A350492seq(20) \\ See PARI link in A122078 for program code.

A165950 Number of acyclic digraphs on n labeled nodes with one source and one sink.

Original entry on oeis.org

1, 2, 12, 216, 10600, 1306620, 384471444, 261548825328, 402632012394000, 1381332938730123060, 10440873023366019273820, 172308823347127690038311496, 6163501139185639837183141411320, 474942255590583211554917995123517868, 78430816994991932467786587093292327531620

Offset: 1

Vladeta Jovovic, Oct 01 2009

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Antoine Genitrini, Martin Pépin, and Alfredo Viola, Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling, hal-03029381 [math.CO], [cs.DM], [cs.DS], 2020.
Ira Gessel, Counting Acyclic Digraphs by Sources and Sinks
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.

The unlabeled version is A345258.

Cf. A003024, A003025, A049524, A361210.

nn = 10; B[n_] := n! 2^Binomial[n, 2];e[z_] := Sum[z^n/B[n], {n, 0, nn}];
egf[ggf_] := Normal[Series[ggf, {z, 0, nn}]] /. Table[z^i -> z^i*2^Binomial[i, 2], {i, 1, nn + 1}]; Map[ Coefficient[#, u v] &,Table[n!, {n, 0, nn}] CoefficientList[ Series[Exp[(u - 1) (v - 1) z] egf[e[(u - 1) z]*1/e[-z]*e[(v - 1) z]], {z, 0, nn}], z]] (* Geoffrey Critzer, Apr 15 2023 *)

\\ see Marcel et al. link. B(n) is A003025 as vector.
B(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)*(2^(n-k)-1)^k*a[n-k])); a}
seq(n)={my(a=vector(n), b=B(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1) * binomial(n,k) * k * (2^(n-k)-1)^k * b[n-k])); a} \\ Andrew Howroyd, Jan 01 2022

a(1)=1 inserted and terms a(13) and beyond from Andrew Howroyd, Jan 01 2022

cp's OEIS Frontend

A350794 Number of digraphs on n unlabeled nodes with a global source and sink.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A350415 Number of acyclic digraphs on n unlabeled nodes with a global source (or sink).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A049531 Number of digraphs with a source and a sink on n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A350492 Number of unlabeled acyclic digraphs with n arcs and a global source and sink.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A165950 Number of acyclic digraphs on n labeled nodes with one source and one sink.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions