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