cp's OEIS Frontend

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

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