|
%I #14 Aug 30 2018 15:07:08
%S 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,
%T 30,51,44,23,0,1,4,17,53,109,148,117,47,0,1,4,23,79,213,372,443,299,
%U 106,0,1,5,28,119,370,827,1276,1306,793,235
%N Triangle read by rows: T(n,k) is the number of hypertrees on n unlabeled nodes with k edges, (0 <= k < n).
%C Equivalently, the number of connected graphs on n unlabeled nodes with k blocks where every block is a complete graph.
%C 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.
%H Andrew Howroyd, <a href="/A318601/b318601.txt">Table of n, a(n) for n = 1..1275</a>
%F 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.
%e Triangle begins:
%e 1;
%e 0, 1;
%e 0, 1, 1;
%e 0, 1, 1, 2;
%e 0, 1, 2, 3, 3;
%e 0, 1, 2, 6, 7, 6;
%e 0, 1, 3, 9, 17, 18, 11;
%e 0, 1, 3, 13, 30, 51, 44, 23;
%e 0, 1, 4, 17, 53, 109, 148, 117, 47;
%e 0, 1, 4, 23, 79, 213, 372, 443, 299, 106;
%e ...
%e 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.
%e o---o o---o o---o o--o--o
%e | X | / \ | |
%e o---o o---o o---o o
%e .
%e 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.
%e o---o
%e / \ 1 = 3 + 2 - 4
%e o---o---o
%e .
%e o o
%e / \ / 1 = 3 + 2 - 4
%e o---o---o
%e .
%e o o
%e / \ / \ 1 = 4 + 3 - 6
%e o---o o
%e .
%o (PARI) \\ here b(n) is A318602 as vector of polynomials.
%o 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)}
%o b(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerMT(y*EulerMT(v)))); v}
%o G(n)={my(u=b(n)); apply(p->Vecrev(p), Vec(y*Ser(EulerMT(u))*(1-x*Ser(u)) + (1 - y)*Ser(u)))}
%o { my(T=G(10)); for(n=1, #T, print(T[n])) }
%Y Rightmost diagonal is A000055 (unlabeled trees).
%Y Row sums are A035053.
%Y Cf. A304867, A318602, A318607.
%K nonn,tabl
%O 1,10
%A _Andrew Howroyd_, Aug 29 2018
|
