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

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

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)

Examples

			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)
		

References

• 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).

Links

• 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.

Crossrefs

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.

Programs

Mathematica

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

PARI

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

PARI

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

Formula

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

Extensions

More terms from Vladeta Jovovic, Apr 10 2001