login
A318601
Triangle read by rows: T(n,k) is the number of hypertrees on n unlabeled nodes with k edges, (0 <= k < n).
4
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
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.
Sequence in context: A107017 A201076 A201079 * A306814 A241382 A049260
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Aug 29 2018
STATUS
approved