|
|
A320444
|
|
Number of uniform hypertrees spanning n vertices.
|
|
7
|
|
|
1, 1, 1, 4, 17, 141, 1297, 17683, 262145, 4861405, 100112001, 2371816701, 61917364225, 1796326510993, 56693912375297, 1947734359001551, 72059082110369793, 2863257607266475419, 121439531096594251777, 5480987217944109919765, 262144000000000000000001
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
The density of a hypergraph is the sum of sizes of its edges minus the number of edges minus the number of vertices. A hypertree is a connected hypergraph of density -1. A hypergraph is uniform if its edges all have the same size. The span of a hypergraph is the union of its edges.
|
|
LINKS
|
|
|
FORMULA
|
a(n + 1) = Sum_{d|n} n!/(d! * (n/d)!) * ((n + 1)/d)^(n/d - 1).
a(p prime) = 1 + (p + 1)^(p - 1).
|
|
EXAMPLE
|
Non-isomorphic representatives of the 5 unlabeled uniform hypertrees on 5 vertices and their multiplicities in the labeled case, which add up to a(5) = 141:
5 X {{1,5},{2,5},{3,5},{4,5}}
60 X {{1,4},{2,5},{3,5},{4,5}}
60 X {{1,3},{2,4},{3,5},{4,5}}
15 X {{1,2,5},{3,4,5}}
1 X {{1,2,3,4,5}}
|
|
MAPLE
|
f:= proc(n) local d; add((n-1)!/(d! * ((n-1)/d)!) * (n/d)^((n-1)/d - 1), d = numtheory:-divisors(n-1)); end proc:
f(0):= 1: f(1):= 1:
|
|
MATHEMATICA
|
Table[Sum[n!/(d!*(n/d)!)*((n+1)/d)^(n/d-1), {d, Divisors[n]}], {n, 10}]
|
|
PROG
|
(PARI) a(n) = if (n<2, 1, n--; sumdiv(n, d, n!/(d! * (n/d)!) * ((n + 1)/d)^(n/d - 1))); \\ Michel Marcus, Jan 10 2019
|
|
CROSSREFS
|
Cf. A000272, A030019, A035053, A038041, A052888, A057625, A061095, A121860, A134954, A236696, A262843.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|