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).

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

Author

Emeric Deutsch, Mar 05 2014

Keywords

• nonn
• tabl

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.

Examples

			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.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 2..1226 (rows 2..50)

Crossrefs

Cf. A000055, A000014, A182907.

Programs

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);

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

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