A318601 -id:A318601 - cp's OEIS frontend

A304867 Number of non-isomorphic hypertrees of weight n.

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

Offset: 0

Gus Wiseman, May 20 2018

nonn

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)

			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)

Andrew Howroyd, Table of n, a(n) for n = 0..500
Roland Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO], 2011.

Cf. A007716, A030019, A035053, A048143, A054921, A134955, A134957, A144959, A304911, A304912, A318601.

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 *)

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

a(n) = Sum_{k=1..floor(n/2)} A318601(n+1-k, k). - Andrew Howroyd, Aug 29 2018

Terms a(10) and beyond from Andrew Howroyd, Aug 29 2018

A318602 Triangle read by rows: T(n,k) is the number of rooted hypertrees on n unlabeled nodes with k edges, (0 <= k < n).

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 3, 4, 0, 1, 5, 10, 9, 0, 1, 6, 20, 30, 20, 0, 1, 8, 33, 77, 91, 48, 0, 1, 9, 49, 152, 277, 268, 115, 0, 1, 11, 68, 269, 655, 969, 790, 286, 0, 1, 12, 91, 428, 1330, 2651, 3294, 2308, 719, 0, 1, 14, 116, 647, 2420, 6137, 10300, 10993, 6737, 1842

Offset: 1

Andrew Howroyd, Aug 29 2018

Equivalently, the number of rooted connected graphs on n unlabeled nodes with k blocks where every block is a complete graph.

			Triangle begins:
  1;
  0, 1;
  0, 1,  2;
  0, 1,  3,  4;
  0, 1,  5, 10,   9;
  0, 1,  6, 20,  30,  20;
  0, 1,  8, 33,  77,  91,  48;
  0, 1,  9, 49, 152, 277, 268, 115;
  0, 1, 11, 68, 269, 655, 969, 790, 286;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Rightmost diagonal is A000081 (rooted trees).
Row sums are A007563.
Cf. A318601.

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
R(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerMT(y*EulerMT(v)))); [Vecrev(p) | p <- v]}
{ my(T=R(10));for(n=1, #T, print(T[n])) }

A318607 Triangle read by rows: T(n,k) is the number of sets of rooted hypertrees on a total of n unlabeled nodes with a total of k edges, (0 <= k < n).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 6, 4, 1, 4, 12, 16, 9, 1, 5, 20, 42, 46, 20, 1, 6, 30, 86, 145, 128, 48, 1, 7, 42, 153, 353, 483, 364, 115, 1, 8, 56, 248, 729, 1369, 1592, 1029, 286, 1, 9, 72, 376, 1345, 3236, 5150, 5151, 2930, 719, 1, 10, 90, 541, 2287, 6728, 13708, 18792, 16513, 8344, 1842

Offset: 1

Andrew Howroyd, Aug 30 2018

Equivalently, the number of sets of rooted connected graphs on a total of n unlabeled nodes with a total of k blocks where every block is a complete graph.

Bivariate Euler transform of triangle A318602.

			Triangle begins:
  1;
  1, 1;
  1, 2, 2;
  1, 3, 6, 4;
  1, 4, 12, 16, 9;
  1, 5, 20, 42, 46, 20;
  1, 6, 30, 86, 145, 128, 48;
  1, 7, 42, 153, 353, 483, 364, 115;
  1, 8, 56, 248, 729, 1369, 1592, 1029, 286;
  ...
Case n=3: There are 5 sets of rooted graph which are illustrated below (an x marks a root node). These have 0, 1, 1, 2, 2 blocks so row 3 is 1, 2, 2.
      x        o        o        o        o
              /        / \        \      /
    x   x    x   x    x---o    x---o    x---o

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Rightmost diagonal is A000081 (rooted trees).
Row sums are A035052.
Cf. A318601, A318602.

\\ here EulerMT is Euler transform (bivariate version).
EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
A(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerMT(y*EulerMT(v)))); [Vecrev(p) | p <- EulerMT(v)]}
{ my(T=A(10)); for(n=1, #T, print(T[n])) }

cp's OEIS Frontend

A304867 Number of non-isomorphic hypertrees of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A318602 Triangle read by rows: T(n,k) is the number of rooted hypertrees on n unlabeled nodes with k edges, (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A318607 Triangle read by rows: T(n,k) is the number of sets of rooted hypertrees on a total of n unlabeled nodes with a total of k edges, (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI