|
|
A304867
|
|
Number of non-isomorphic hypertrees of weight n.
|
|
37
|
|
|
1, 1, 1, 1, 2, 2, 5, 6, 13, 20, 41, 70, 144, 266, 545, 1072, 2210, 4491, 9388, 19529, 41286, 87361, 186657, 399927, 862584, 1866461, 4058367, 8852686, 19384258, 42570435, 93783472, 207157172, 458805044, 1018564642, 2266475432, 5053991582, 11292781891, 25280844844
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
A hypertree E is a connected antichain of finite sets satisfying Sum_{e in E} (|e| - 1) = |U(E)| - 1. The weight of a hypertree is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices (see A035053).
a(n), except at n=1, is the number of free trees of n edges (so n+1 vertices) where any two leaves are an even distance apart. All trees are bipartite graphs and this condition is equivalent to all leaves being in the same bipartite half. The diameter of a tree is always between two leaves so these trees have even diameter (A000676).
The correspondence between hypertrees and these free trees is described for instance by Bacher (start of section 1.2). In such a free tree, call a vertex "even" if it is an even distance from a leaf. The hypertree vertices are these even vertices. Each hyperedge is the set of vertices surrounding an odd vertex, so hypertree weight is the total number of edges in the free tree.
(End)
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Non-isomorphic representatives of the a(6) = 5 hypertrees are the following:
{{1,2,3,4,5,6}}
{{1,2},{1,3,4,5}}
{{1,2,3},{1,4,5}}
{{1,2},{1,3},{1,4}}
{{1,2},{1,3},{2,4}}
Non-isomorphic representatives of the a(7) = 6 hypertrees are the following:
{{1,2,3,4,5,6,7}}
{{1,2},{1,3,4,5,6}}
{{1,2,3},{1,4,5,6}}
{{1,2},{1,3},{1,4,5}}
{{1,2},{1,3},{2,4,5}}
{{1,3},{2,4},{1,2,5}}
a(6) = 5 hypertrees of weight 6 and their corresponding free trees of 6 edges (7 vertices). Each * is an "odd" vertex (odd distance to a leaf). Each hyperedge is the set of "even" vertices surrounding an odd.
{1,2,3,4,5,6} 3 2
\ /
4-*-1 (star 7)
/ \
5 6
.
{1,2},{1,3,4,5} /-3
2--*--1--*--4
\-5
.
{1,2,3},{1,4,5} 2-\ /-4
*--1--*
3-/ \-5
.
{1,2},{1,3},{1,4} /-*--2
1--*--3
\-*--4
.
{1,2},{2,4},{1,3} 3--*--1--*--2--*--4 (path 7)
(End)
|
|
MATHEMATICA
|
etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}]*b[n - j], {j, 1, n}]/n]; b];
EulerT[v_List] := With[{q = etr[v[[#]]&]}, q /@ Range[Length[v]]];
ser[v_] := Sum[v[[i]] x^(i-1), {i, 1, Length[v]}] + O[x]^Length[v];
c[n_] := Module[{v = {1}}, For[i = 1, i <= Ceiling[n/2], i++, v = Join[{1}, EulerT[Join[{0}, EulerT[v]]]]]; v];
seq[n_] := Module[{u = c[n]}, x*ser[EulerT[u]]*(1 - x*ser[u]) + (1 - x)* ser[u] + x + O[x]^n // CoefficientList[#, x]&];
|
|
PROG
|
(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
c(n)={my(v=[1]); for(i=1, ceil(n/2), v=concat([1], EulerT(concat([0], EulerT(v))))); v}
seq(n)={my(u=c(n)); Vec(x*Ser(EulerT(u))*(1-x*Ser(u)) + (1 - x)*Ser(u) + x + O(x*x^n))} \\ Andrew Howroyd, Aug 29 2018
|
|
CROSSREFS
|
Cf. A007716, A030019, A035053, A048143, A054921, A134955, A134957, A144959, A304911, A304912, A318601.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|