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,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

Cf. A000055, A000014, A182907.

Sequence in context: A137289 A211359 A211357 * A370852 A063574 A372095

Adjacent sequences: A238413 A238414 A238415 * A238417 A238418 A238419

Keyword

nonn,tabl

Author

Emeric Deutsch, Mar 05 2014

Status

approved