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).
From Kevin Ryde, Feb 25 2020: (Start)
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
Andrew Howroyd, Table of n, a(n) for n = 0..500
R. Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO], 2011.
FORMULA
a(n) = Sum_{k=1..floor(n/2)} A318601(n+1-k, k). - Andrew Howroyd, Aug 29 2018
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}}
From Kevin Ryde, Feb 25 2020: (Start)
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]&];
seq[40] (* Jean-François Alcover, Feb 08 2020, after Andrew Howroyd *)
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
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 20 2018
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Aug 29 2018
STATUS
approved