login
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).
2
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, 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, 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
OFFSET
2,11
COMMENTS
Sum of entries in row n is A000055(n) (number of trees with n vertices).
T(n,0) = A000014(n) (= number of series-reduced trees with n vertices).
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.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 2..1226 (rows 2..50)
FORMULA
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
EXAMPLE
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.
Triangle starts:
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, 5, 0, 1.
MAPLE
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);
PROG
(PARI)
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)}
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]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 20 2020
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Mar 05 2014
STATUS
approved