OFFSET
1,2
COMMENTS
Number of acyclic-function digraphs on n vertices. An acyclic-function digraph is a labeled digraph which (i) has no cycles and no loops, (ii) has outdegree 0 or 1 for all vertices and (iii) has x > y when vertex x has outdegree 0 and vertex y has outdegree 1.
This sequence is the sum of antidiagonals of A058127.
Conjecture: For even n, a(n) is prime or a weak Fermat pseudoprime to base n. - Davide Rotondo, Nov 06 2024
LINKS
T. D. Noe, Table of n, a(n) for n=1..100
D. P. Walsh, Notes on acyclic functions and their directed graphs
FORMULA
a(n) = Sum_{k=1..n} k*n^(n-k-1). - Benoit Cloitre, Sep 28 2002
EXAMPLE
a(3) = 6 since the acyclic-function digraphs on 3 vertices are: {(1), (2), (3)} {(1,2), (3)} {(1,3), (2)} {(1,2), (2,3)} {(1,3), (2,3)} {(2,1), (1,3)} where (x) denotes a vertex of degree 0 and (x,y) denotes the subgraph consisting of vertices x and y and the arc from x to y.
MATHEMATICA
Join[{1}, Table[(n^n-n)/(n-1)^2, {n, 2, 20}]] (* Harvey P. Dale, Jul 17 2011 *)
CROSSREFS
KEYWORD
nice,nonn,changed
AUTHOR
Dennis P. Walsh, Nov 14 2000
STATUS
approved