cp's OEIS Frontend

A238416 Triangle read by rows: T(n,k) is the number of trees with n vertices having k vertices of degree 2 (n>=2, 0 <= k <= n - 2).

%I A238416 #19 Dec 20 2020 22:23:24
%S A238416 1,0,1,1,0,1,1,1,0,1,2,1,2,0,1,2,3,2,3,0,1,4,4,7,3,4,0,1,5,9,10,12,5,
%T A238416 5,0,1,10,15,25,20,22,6,7,0,1,14,31,46,54,38,34,9,8,0,1,26,57,103,111,
%U A238416 114,65,53,11,10,0,1,42,114,204,267,250,212,108,76,15,12,0,1,78,219,440,583,644,502,383,167,110,18,14,0,1
%N A238416 Triangle read by rows: T(n,k) is the number of trees with n vertices having k vertices of degree 2 (n>=2, 0 <= k <= n - 2).
%C A238416 Sum of entries in row n is A000055(n) (number of trees with n vertices).
%C A238416 T(n,0) = A000014(n) (= number of series-reduced trees with n vertices).
%C A238416 The author knows of no formula for T(n,k). The entries have been obtained in the following manner, explained for row n = 7. In A235111 we find that the 11 (=A000055(7)) trees with 7 vertices have M-indices 25, 27, 30, 35, 36, 40, 42, 48, 49, 56, and 64 (the M-index of a tree t is the smallest of the Matula numbers of the rooted trees isomorphic, as a tree, to t). Making use of the formula in A182907 for the degree sequence polynomial, from these Matula numbers one obtains that these trees have 5, 3, 3, 3, 2, 2, 1, 1, 1, 0, and 0 degree-2 vertices, respectively; the frequencies of 0, 1, 2, 3, 4, and 5 are 2, 3, 2, 3, 0, and 1, respectively. See the Maple program.
%H A238416 Andrew Howroyd, <a href="/A238416/b238416.txt">Table of n, a(n) for n = 2..1226</a> (rows 2..50)
%F A238416 G.f.: -x + R(x,y)*(1 + x*(1-y)) + (R(x^2,y^2)*(1 - x*(1-y)) - R(x,y)^2*(1 + x*(1-y)))/2 where R(x,y) satisfies R(x,y) = x*(R(x,y)*(y-1) + exp(Sum_{k>0} R(x^k,y^k)/k)). - _Andrew Howroyd_, Dec 20 2020
%e A238416 Row n=4 is T(4,0)=1,T(4,1)=0; T(4,2)=1; indeed, the star S[4] has no degree-2 vertex and the path P[4] has 2 degree-2 vertices.
%e A238416 Triangle starts:
%e A238416 1;
%e A238416 0, 1;
%e A238416 1, 0, 1;
%e A238416 1, 1, 0, 1;
%e A238416 2, 1, 2, 0, 1;
%e A238416 2, 3, 2, 3, 0, 1;
%e A238416 4, 4, 7, 3, 4, 0, 1;
%e A238416 5, 9, 10, 12, 5, 5, 0, 1.
%p A238416 MI := [25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64]: with(numtheory): g := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 1 elif bigomega(n) = 1 then sort(expand(g(pi(n))+x^bigomega(pi(n))*(x-1)+x)) else sort(expand(g(r(n))+g(s(n))-x^bigomega(r(n))-x^bigomega(s(n))+x^bigomega(n))) end if end proc: a := proc (n) options operator, arrow: coeff(g(n), x, 2) end proc: G := add(x^a(MI[q]), q = 1 .. 11): seq(coeff(G, x, j), j = 0 .. 5);
%o A238416 (PARI)
%o A238416 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 A238416 T(n)={my(u=[1]); for(n=2, n, u=concat([1], EulerMT(u) + (y-1)*u)); my(r=x*Ser(u), v=Vec(-x + r*(1 + x*(1-y)) + (substvec(r,[x,y],[x^2,y^2])*(1 - x*(1-y)) - r^2*(1 + x*(1-y)))/2)); [Vecrev(p) | p<-v]}
%o A238416 { my(A=T(10)); for(n=1, #A, print(A[n])) } \\ _Andrew Howroyd_, Dec 20 2020
%Y A238416 Cf. A000055, A000014, A182907.
%K A238416 nonn,tabl
%O A238416 2,11
%A A238416 _Emeric Deutsch_, Mar 05 2014