|
| |
|
|
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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
