|
%I #38 Jul 07 2020 04:14:53
%S 1,1,1,1,2,2,5,6,13,20,41,70,144,266,545,1072,2210,4491,9388,19529,
%T 41286,87361,186657,399927,862584,1866461,4058367,8852686,19384258,
%U 42570435,93783472,207157172,458805044,1018564642,2266475432,5053991582,11292781891,25280844844
%N Number of non-isomorphic hypertrees of weight n.
%C 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).
%C From _Kevin Ryde_, Feb 25 2020: (Start)
%C 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).
%C 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.
%C (End)
%H Andrew Howroyd, <a href="/A304867/b304867.txt">Table of n, a(n) for n = 0..500</a>
%H R. Bacher, <a href="https://arxiv.org/abs/1102.2708">On the enumeration of labelled hypertrees and of labelled bipartite trees</a>, arXiv:1102.2708 [math.CO], 2011.
%F a(n) = Sum_{k=1..floor(n/2)} A318601(n+1-k, k). - _Andrew Howroyd_, Aug 29 2018
%e Non-isomorphic representatives of the a(6) = 5 hypertrees are the following:
%e {{1,2,3,4,5,6}}
%e {{1,2},{1,3,4,5}}
%e {{1,2,3},{1,4,5}}
%e {{1,2},{1,3},{1,4}}
%e {{1,2},{1,3},{2,4}}
%e Non-isomorphic representatives of the a(7) = 6 hypertrees are the following:
%e {{1,2,3,4,5,6,7}}
%e {{1,2},{1,3,4,5,6}}
%e {{1,2,3},{1,4,5,6}}
%e {{1,2},{1,3},{1,4,5}}
%e {{1,2},{1,3},{2,4,5}}
%e {{1,3},{2,4},{1,2,5}}
%e From _Kevin Ryde_, Feb 25 2020: (Start)
%e 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.
%e {1,2,3,4,5,6} 3 2
%e \ /
%e 4-*-1 (star 7)
%e / \
%e 5 6
%e .
%e {1,2},{1,3,4,5} /-3
%e 2--*--1--*--4
%e \-5
%e .
%e {1,2,3},{1,4,5} 2-\ /-4
%e *--1--*
%e 3-/ \-5
%e .
%e {1,2},{1,3},{1,4} /-*--2
%e 1--*--3
%e \-*--4
%e .
%e {1,2},{2,4},{1,3} 3--*--1--*--2--*--4 (path 7)
%e (End)
%t 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];
%t EulerT[v_List] := With[{q = etr[v[[#]]&]}, q /@ Range[Length[v]]];
%t ser[v_] := Sum[v[[i]] x^(i-1), {i, 1, Length[v]}] + O[x]^Length[v];
%t c[n_] := Module[{v = {1}}, For[i = 1, i <= Ceiling[n/2], i++, v = Join[{1}, EulerT[Join[{0}, EulerT[v]]]]]; v];
%t seq[n_] := Module[{u = c[n]}, x*ser[EulerT[u]]*(1 - x*ser[u]) + (1 - x)* ser[u] + x + O[x]^n // CoefficientList[#, x]&];
%t seq[40] (* _Jean-François Alcover_, Feb 08 2020, after _Andrew Howroyd_ *)
%o (PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
%o c(n)={my(v=[1]); for(i=1, ceil(n/2), v=concat([1], EulerT(concat([0], EulerT(v))))); v}
%o 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
%Y Cf. A007716, A030019, A035053, A048143, A054921, A134955, A134957, A144959, A304911, A304912, A318601.
%K nonn
%O 0,5
%A _Gus Wiseman_, May 20 2018
%E Terms a(10) and beyond from _Andrew Howroyd_, Aug 29 2018
|
