

A191516


Irregular triangle read by rows: a(n,k) is the number of edges with degree k (k>=1) in the rooted tree with MatulaGoebel number n (n>=3).


1



2, 2, 2, 1, 2, 1, 0, 3, 0, 3, 2, 2, 2, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 3, 0, 0, 4, 1, 2, 1, 2, 1, 2, 0, 0, 4, 1, 3, 1, 1, 3, 1, 2, 3, 2, 1, 2, 1, 0, 3, 1, 2, 4, 2, 1, 2, 3, 0, 3, 0, 4, 0, 1, 1, 3, 1, 2, 2, 2, 2, 3, 0, 0, 0, 5, 2, 4, 1, 3, 1, 1, 4, 1, 2, 0, 2, 2, 1, 0, 3, 1, 1, 0, 3, 1, 2, 2, 2, 1, 1, 3, 1, 2, 1, 2, 1, 3, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

3,1


COMMENTS

The degree of an edge is the number of edges adjacent to it.
The MatulaGoebel number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGoebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the MatulaGoebel numbers of the m branches of T.
Sum of entries in row n = A196050(n) (= number of edges).
Sum(k*a(n,k), k>=1) = A198332(n) (=sum of edge degrees (the Platt index)).


REFERENCES

A. T. Balaban, Chemical graphs, Theoret. Chim. Acta (Berl.) 53, 355375, 1979.
F. Goebel, On a 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
I. Gutman and YeongNan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 1722.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.
R. Todeschini and V. Consonni, Handbook of Molecular Descriptors, WileyVCH, 2000.


LINKS

Table of n, a(n) for n=3..114.
E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288


FORMULA

Let f(n)=F(n,x) be the generating polynomial of the edges of the rooted tree with MatulaGoebel number n, with respect to edgedegree. Write f(n)=g(n)+h(n), where g(n) is over the edges emanating from the root and h(n) is over the remaining edges. We have g(1)=0, h(1)=0; if n = p(t) (=the tth prime), then g(n)=x^G(t), h(n)=xg(t)+h(t); if n=rs (r,s>=2), then g(n)=x^G(s)*g(r) + x^G(r)*g(s), h(n)=h(r)+h(s). G(m) denotes the number of prime divisors of m counted with multiplicities.


EXAMPLE

Row 5 is 2,1 because the rooted tree with MatulaGoebel number 5 is the path tree ABCD on 4 vertices; AB and CD have degree 1 and BC has degree 2.
Row 7 is 0,3 because the rooted tree with MatulaGoebel number 7 is Y, where no edge has degree 1 and all 3 edges have degree 2.
Triangle starts:
2;
2;
2,1;
2,1;
0,3;
0,3;
2,2;


MAPLE

with(numtheory): f := proc (n) local r, s, g, h: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: g:=proc(n) if n = 1 then 0 elif bigomega(n) = 1 then x^(bigomega(pi(n))) else x^(bigomega(s(n)))*g(r(n))+x^(bigomega(r(n)))*g(s(n)) fi end: h:=proc(n) if n=1 then 0 elif bigomega(n)=1 then x*g(pi(n))+h(pi(n)) else h(r(n))+h(s(n)) fi end: sort(expand(g(n)+h(n))) end: for n from 3 to 42 do seq(coeff(f(n), x, j), j=1..degree(f(n))) od; # yields sequence in triangular form


CROSSREFS

Cf. A196050, A198332.
Sequence in context: A320844 A212119 A096831 * A168141 A232654 A034095
Adjacent sequences: A191513 A191514 A191515 * A191517 A191518 A191519


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Dec 15 2011


STATUS

approved



