login
Number of uniform hypertrees spanning n vertices.
7

%I #20 Aug 21 2019 19:04:38

%S 1,1,1,4,17,141,1297,17683,262145,4861405,100112001,2371816701,

%T 61917364225,1796326510993,56693912375297,1947734359001551,

%U 72059082110369793,2863257607266475419,121439531096594251777,5480987217944109919765,262144000000000000000001

%N Number of uniform hypertrees spanning n vertices.

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

%H Robert Israel, <a href="/A320444/b320444.txt">Table of n, a(n) for n = 0..387</a>

%F a(n + 1) = Sum_{d|n} n!/(d! * (n/d)!) * ((n + 1)/d)^(n/d - 1).

%F a(p prime) = 1 + (p + 1)^(p - 1).

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

%e 5 X {{1,5},{2,5},{3,5},{4,5}}

%e 60 X {{1,4},{2,5},{3,5},{4,5}}

%e 60 X {{1,3},{2,4},{3,5},{4,5}}

%e 15 X {{1,2,5},{3,4,5}}

%e 1 X {{1,2,3,4,5}}

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

%p f(0):= 1: f(1):= 1:

%p map(f, [$0..25]); # _Robert Israel_, Jan 10 2019

%t Table[Sum[n!/(d!*(n/d)!)*((n+1)/d)^(n/d-1),{d,Divisors[n]}],{n,10}]

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

%Y Row sums of A326374.

%Y Cf. A000272, A030019, A035053, A038041, A052888, A057625, A061095, A121860, A134954, A236696, A262843.

%K nonn

%O 0,4

%A _Gus Wiseman_, Jan 09 2019