A003025 - OEIS

%I M2083 #33 Jan 04 2024 18:11:22

%S 1,2,15,316,16885,2174586,654313415,450179768312,696979588034313,

%T 2398044825254021110,18151895792052235541515,

%U 299782788128536523836784628,10727139906233315197412684689421

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

%C From _Gus Wiseman_, Jan 02 2024: (Start)

%C 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:

%C   .  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,3}}

%C             {{2},{1,2}}  {{1},{1,2},{2,3}}

%C                          {{1},{1,3},{2,3}}

%C                          {{2},{1,2},{1,3}}

%C                          {{2},{1,2},{2,3}}

%C                          {{2},{1,3},{2,3}}

%C                          {{3},{1,2},{1,3}}

%C                          {{3},{1,2},{2,3}}

%C                          {{3},{1,3},{2,3}}

%C                          {{1},{1,2},{1,2,3}}

%C                          {{1},{1,3},{1,2,3}}

%C                          {{2},{1,2},{1,2,3}}

%C                          {{2},{2,3},{1,2,3}}

%C                          {{3},{1,3},{1,2,3}}

%C                          {{3},{2,3},{1,2,3}}

%C These set-systems are all connected.

%C The case of labeled graphs is A000169.

%C (End)

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Andrew Howroyd, <a href="/A003025/b003025.txt">Table of n, a(n) for n = 1..50</a>

%H Marcel et al., <a href="https://mathoverflow.net/q/395095">Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?</a>, MathOverflow, 2021.

%F a(n) = (-1)^(n-1) * n * A134531(n). - _Gus Wiseman_, Jan 02 2024

%e a(2) = 2: o-->--o (2 ways)

%e a(3) = 15: o-->--o-->--o (6 ways) and

%e o ... o o-->--o

%e .\ . / . \ . /

%e . v v ... v v

%e .. o ..... o

%e (3 ways) (6 ways)

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

%o (PARI) \\ requires A058876.

%o my(T=A058876(20)); vector(#T, n, T[n][1]) \\ _Andrew Howroyd_, Dec 27 2021

%o (PARI) \\ see Marcel et al. link (formula for a').

%o 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

%Y A diagonal of A058876.

%Y Row sums of A350487.

%Y The unlabeled version is A350415.

%Y Column k=1 of A361718.

%Y Cf. A003026, A003028, A345258.

%Y For any number of sinks we have A003024, unlabeled A003087.

%Y For n-1 sinks we have A058877.

%Y For a fixed sink we have A134531 (up to sign), column k=1 of A368602.

%Y Cf. A000169, A058891, A059201, A082402, A088957, A323818, A334282, A367904, A368600, A368601.

%K nonn

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Vladeta Jovovic_, Apr 10 2001