cp's OEIS Frontend

A304867 Number of non-isomorphic hypertrees of weight n.

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