

A238421


Row n contains the numbers obtained from the rooted tree with Matula number n in the following manner: partition the edges of the tree into subsets so that in each subset each edge has the same pair of endpoint degrees; row n contains the sizes of these subsets, listed in an arbitrary order.


0



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



OFFSET

2,2


COMMENTS

Very often the terms of the sequence are denoted by m_{i,j}; see, for example, the Vukicevic reference.
The Maple program yields a more precise information, For example, for n=5 it gives the polynomial P(5) = 2xy^2 + x^2 y^2. A term bx^i y^j in such a polynomial means that the tree has b edges with endpoint degrees i,j.
The Matula 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.


REFERENCES

F. Goebel, On a 11 correspondence 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 YN. 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.
E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Applied Math., 160, 2012, 23142322.
D. Vukicevic, On the edge degrees of trees, Glasnik Matem., 44(64), 2009, 259266.


LINKS

Table of n, a(n) for n=2..48.
E. Deutsch, Rooted tree statistics from Matula numbers, arXiv1111.4288.


EXAMPLE

Row 5 is 1,2. Indeed, the rooted tree with Matula number 5 is the path ABCD. The edge BC has endpoint degrees 2,2; both edges AB and CD have endpoint degrees 1,2.
Row 8 is 3. Indeed the rooted tree with Matula number 8 is the star with 4 vertices. Each of the 3 edges has endpoint degrees 1,3.
Row 987654321 is 4,7,3,1,4,5,2,2. Indeed, the Maple program yields P(987654321) = 4xy^2 + 7xy^3 + 3x^2y^3 + x^2y^2 + 4xy^5 + 5x^2y^5 + 2x^3y^5 + 2x^5y^5. The tree is shown in Fig. 2 of the Deutsch reference.


MAPLE

with(numtheory): P := proc (n) local DL, r, s: DL := proc (n) if n = 2 then [1] elif bigomega(n) = 1 then [1+bigomega(pi(n))] else [op(DL(op(1, factorset(n)))), op(DL(n/op(1, factorset(n))))] end if end proc: 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 = 2 then x*y elif bigomega(n) = 1 then P(pi(n))+x*y^(1+bigomega(pi(n)))(sum(x^min(bigomega(pi(n)), DL(pi(n))[j])*y^max(bigomega(pi(n)), DL(pi(n))[j]), j = 1 .. bigomega(pi(n))))+sum(x^min(1+bigomega(pi(n)), DL(pi(n))[j])*y^max(1+bigomega(pi(n)), DL(pi(n))[j]), j = 1 .. bigomega(pi(n))) else P(r(n))+P(s(n))(sum(x^min(bigomega(r(n)), DL(r(n))[j])*y^max(bigomega(r(n)), DL(r(n))[j]), j = 1 .. bigomega(r(n))))(sum(x^min(bigomega(s(n)), DL(s(n))[j])*y^max(bigomega(s(n)), DL(s(n))[j]), j = 1 .. bigomega(s(n))))+sum(x^min(bigomega(n), DL(r(n))[j])*y^max(bigomega(n), DL(r(n))[j]), j = 1 .. bigomega(r(n)))+sum(x^min(bigomega(n), DL(s(n))[j])*y^max(bigomega(n), DL(s(n))[j]), j = 1 .. bigomega(s(n))) end if end proc:


CROSSREFS

Sequence in context: A029413 A237523 A238568 * A105154 A076447 A136690
Adjacent sequences: A238418 A238419 A238420 * A238422 A238423 A238424


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Mar 26 2014


STATUS

approved



