|
|
A003025
|
|
Number of n-node labeled acyclic digraphs with 1 out-point.
(Formerly M2083)
|
|
16
|
|
|
1, 2, 15, 316, 16885, 2174586, 654313415, 450179768312, 696979588034313, 2398044825254021110, 18151895792052235541515, 299782788128536523836784628, 10727139906233315197412684689421
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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)
|
|
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
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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)
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Subsets[Range[n]], {n}], Count[#, {_}]==1&&Length[Select[Tuples[#], UnsameQ@@#&]]==1&]], {n, 0, 4}] (* Gus Wiseman, Jan 02 2024 *)
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|