A238415 Triangle read by rows: T(n,k) is the number of trees with n vertices having k branching vertices (n>=2, 0<=k<=floor(n/2) - 1).

1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 3, 1, 11, 10, 1, 1, 17, 24, 5, 1, 25, 56, 22, 2, 1, 36, 114, 74, 10, 1, 50, 224, 219, 55, 2, 1, 70, 411, 576, 224, 19, 1, 94, 733, 1394, 807, 126, 4, 1, 127, 1252, 3150, 2536, 637, 38, 1, 168, 2091, 6733, 7305, 2711, 305, 6

Offset

2,6

Comments

A branching node of a tree is a vertex of degree at least 3.

Sum of entries in row n is A000055(n) (number of trees with n vertices).

Row n has floor(n/2) entries.

T(n,1) = A004250(n-1).

Links

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

Formula

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 A196049, from these Matula numbers one obtains that these trees have 0, 1, 1, 1, 1, 1, 2, 1, 2, 2, and 1 branching vertices, respectively; the frequencies of 0, 1, and 2 are 1, 7, and 3, respectively. See the Maple program.

Example

Row n=4 is T(4,0)=1,T(4,1)=1; indeed, the path P[4] has no branching vertex and the star S[4] has 1 branching vertex.
Triangle starts:
1;
1;
1, 1;
1, 2;
1, 4, 1;
1, 7, 3;
1, 11, 10, 1;
1, 17, 24, 5;

Maple

MI := [25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64]: with(numtheory): a := 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 0 elif bigomega(n) = 1 and bigomega(pi(n)) <> 2 then a(pi(n)) elif bigomega(n) = 1 then a(pi(n))+1 elif bigomega(s(n)) <> 2 then a(r(n))+a(s(n)) else a(r(n))+a(s(n))+1 end if end proc: g := add(x^a(MI[j]), j = 1 .. nops(MI)): seq(coeff(g, x, q), q = 0 .. 2);

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)}
R(n)={my(v=[1]); for(i=2, n, v=concat([1], y*EulerMT(v) + (1-y)*v)); v}
seq(n)={my(p=x*Ser(R(n))); Vec(p + (((1-y)*x-1)*p^2 + ((1-y)*x+1)*substvec(p, [x, y], [x^2, y^2]))/2)}
{ my(A=Vec(seq(20))); for(n=2, #A, print(Vecrev(A[n]))) } \\ Andrew Howroyd, May 21 2018

Crossrefs

Cf. A000055, A235111, A196049, A004250.

Sequence in context: A191306 A191525 A066633 * A283826 A088443 A117352

Adjacent sequences: A238412 A238413 A238414 * A238416 A238417 A238418

Keyword

nonn,tabf

Author

Emeric Deutsch, Mar 05 2014

Extensions

Terms a(51) and beyond from Andrew Howroyd, May 21 2018

Status

approved