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

1, 0, 1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 2, 3, 3, 0, 1, 2, 6, 7, 6, 0, 1, 3, 9, 17, 18, 11, 0, 1, 3, 13, 30, 51, 44, 23, 0, 1, 4, 17, 53, 109, 148, 117, 47, 0, 1, 4, 23, 79, 213, 372, 443, 299, 106, 0, 1, 5, 28, 119, 370, 827, 1276, 1306, 793, 235

Offset

1,10

Comments

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

Let R(x,y) be the g.f. of A318602 and S(x,y) be the g.f. of A318607. Then the number of hypertrees rooted at a vertex is R(x,y), the number rooted at an edge is y*(S(x,y) - R(x,y)) and the number rooted at a directed edge is y*S(x,y)*R(x,y). The dissymmetry theorem for trees gives that the number of unlabeled objects (this sequence) is the number rooted at a vertex plus the number rooted at an edge minus the number rooted at a directed edge.

Links

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

Formula

G.f.: R(x,y) + y*(S(x,y) - R(x,y)) - y*S(x,y)*R(x,y) where R(x,y) is the g.f. of A318602 and S(x,y) is the g.f. of A318607.

Example

Triangle begins:
  1;
  0, 1;
  0, 1, 1;
  0, 1, 1,  2;
  0, 1, 2,  3,  3;
  0, 1, 2,  6,  7,   6;
  0, 1, 3,  9, 17,  18,  11;
  0, 1, 3, 13, 30,  51,  44,  23;
  0, 1, 4, 17, 53, 109, 148, 117,  47;
  0, 1, 4, 23, 79, 213, 372, 443, 299, 106;
  ...
Case n=4: There are 4 possible graphs which are the complete graph on 4 nodes which has 1 block, a triangle joined to a single vertex which has 2 blocks and two trees which have 3 blocks. Row 4 is then 0, 1, 1, 2.
    o---o       o---o    o---o     o--o--o
    | X |      / \       |            |
    o---o     o---o      o---o        o
.
Case n=5, k=3: The following illustrates how the dissymmetry thereom for each unlabeled hypertree gives 1 = vertex rooted + edge (block) rooted - directed edge (vertex of block) rooted.
      o---o
     / \          1 = 3 + 2 - 4
    o---o---o
.
      o   o
     / \ /        1 = 3 + 2 - 4
    o---o---o
.
      o   o
     / \ / \      1 = 4 + 3 - 6
    o---o   o
.

Prog

(PARI) \\ here b(n) is A318602 as vector of polynomials.
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)}
b(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerMT(y*EulerMT(v)))); v}
G(n)={my(u=b(n)); apply(p->Vecrev(p), Vec(y*Ser(EulerMT(u))*(1-x*Ser(u)) + (1 - y)*Ser(u)))}
{ my(T=G(10)); for(n=1, #T, print(T[n])) }

Crossrefs

Rightmost diagonal is A000055 (unlabeled trees).

Row sums are A035053.

Cf. A304867, A318602, A318607.

Sequence in context: A107017 A201076 A201079 * A306814 A241382 A049260

Adjacent sequences: A318598 A318599 A318600 * A318602 A318603 A318604

Keyword

nonn,tabl

Author

Andrew Howroyd, Aug 29 2018

Status

approved