cp's OEIS Frontend

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

%I A003025 M2083 #33 Jan 04 2024 18:11:22
%S A003025 1,2,15,316,16885,2174586,654313415,450179768312,696979588034313,
%T A003025 2398044825254021110,18151895792052235541515,
%U A003025 299782788128536523836784628,10727139906233315197412684689421
%N A003025 Number of n-node labeled acyclic digraphs with 1 out-point.
%C A003025 From _Gus Wiseman_, Jan 02 2024: (Start)
%C A003025 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 A003025   .  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,3}}
%C A003025             {{2},{1,2}}  {{1},{1,2},{2,3}}
%C A003025                          {{1},{1,3},{2,3}}
%C A003025                          {{2},{1,2},{1,3}}
%C A003025                          {{2},{1,2},{2,3}}
%C A003025                          {{2},{1,3},{2,3}}
%C A003025                          {{3},{1,2},{1,3}}
%C A003025                          {{3},{1,2},{2,3}}
%C A003025                          {{3},{1,3},{2,3}}
%C A003025                          {{1},{1,2},{1,2,3}}
%C A003025                          {{1},{1,3},{1,2,3}}
%C A003025                          {{2},{1,2},{1,2,3}}
%C A003025                          {{2},{2,3},{1,2,3}}
%C A003025                          {{3},{1,3},{1,2,3}}
%C A003025                          {{3},{2,3},{1,2,3}}
%C A003025 These set-systems are all connected.
%C A003025 The case of labeled graphs is A000169.
%C A003025 (End)
%D A003025 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 A003025 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003025 Andrew Howroyd, <a href="/A003025/b003025.txt">Table of n, a(n) for n = 1..50</a>
%H A003025 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 A003025 a(n) = (-1)^(n-1) * n * A134531(n). - _Gus Wiseman_, Jan 02 2024
%e A003025 a(2) = 2: o-->--o (2 ways)
%e A003025 a(3) = 15: o-->--o-->--o (6 ways) and
%e A003025 o ... o o-->--o
%e A003025 .\ . / . \ . /
%e A003025 . v v ... v v
%e A003025 .. o ..... o
%e A003025 (3 ways) (6 ways)
%t A003025 Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Count[#,{_}]==1&&Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,4}] (* _Gus Wiseman_, Jan 02 2024 *)
%o A003025 (PARI) \\ requires A058876.
%o A003025 my(T=A058876(20)); vector(#T, n, T[n][1]) \\ _Andrew Howroyd_, Dec 27 2021
%o A003025 (PARI) \\ see Marcel et al. link (formula for a').
%o A003025 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 A003025 A diagonal of A058876.
%Y A003025 Row sums of A350487.
%Y A003025 The unlabeled version is A350415.
%Y A003025 Column k=1 of A361718.
%Y A003025 Cf. A003026, A003028, A345258.
%Y A003025 For any number of sinks we have A003024, unlabeled A003087.
%Y A003025 For n-1 sinks we have A058877.
%Y A003025 For a fixed sink we have A134531 (up to sign), column k=1 of A368602.
%Y A003025 Cf. A000169, A058891, A059201, A082402, A088957, A323818, A334282, A367904, A368600, A368601.
%K A003025 nonn
%O A003025 1,2
%A A003025 _N. J. A. Sloane_
%E A003025 More terms from _Vladeta Jovovic_, Apr 10 2001