

A214578


Irregular triangle read by rows: if the rooted tree with MatulaGoebel number n is a generalized Bethe tree, then row n is the sequence of the associated partition numbers; otherwise, row n consists of a single 0.


1



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



OFFSET

1,5


COMMENTS

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.
A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree; they are called uniform trees in the Goldberg & Livshits reference.
There is a simple bijection between generalized Bethe trees with n edges (n>=1) and partitions of n in which each part is divisible by the next (the parts are given by the number of edges at the successive levels). We have the correspondences: number of edges  sum of parts; root degree  last part; number of leaves  first part; height  number of parts.


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.
O. Rojo, Spectra of weighted generalized Bethe trees joined at the root, Linear Algebra and its Appl., 428, 2008, 29612979.
M. K. Goldberg and E. M. Livshits, On minimal universal trees, Mathematical Notes of the Acad. of Sciences of the USSR, 4, 1968, 713717 (translation from the Russian Mat. Zametki 4 1968 371379).


LINKS

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


FORMULA

If n>=1 and the rooted tree with MatulaGoebel number n is not a generalized Bethe tree then we define Q(n)=0; otherwise let Q(n) be the polynomial (in x) whose coefficients are the parts of the partition associated to the generalized Bethe tree. We have Q(1)=0; Q(2)=1; if n = p(t) (=the tth prime) and Q(t)=0, then Q(n)=0; if n=p(t) and Q(t) =/ 0, then Q(n)=1+xQ(t); if n=rs , r, s >=2, Q(r)=/0, Q(s)=/0, and Q(r)/Q(s) = const, then Q(n) = Q(r)+Q(s); otherwise, Q(n) = 0.
With the given Maple program we obtain, for example, Q(529) = 4x^2 + 4x + 2, showing that the corresponding rooted tree is a generalized Bethe tree; also Q(987654321)=0, showing that the corresponding rooted tree is not a generalized Bethe tree.


EXAMPLE

Row 7 is 2,1 because the rooted tree with MatulaGoebel number 7 is Y; it is a generalized Bethe tree with corresponding partition 2,1 (number of edges at the various levels).
Triangle starts:
0;
1;
1,1;
2;
1,1,1;
0;
2,1;


MAPLE

with(numtheory): Q := 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 n = 2 then 1 elif bigomega(n) = 1 and Q(pi(n)) = 0 then 0 elif bigomega(n) = 1 then sort(expand(1+x*Q(pi(n)))) elif Q(r(n)) <> 0 and Q(s(n)) <> 0 and type(simplify(Q(r(n))/Q(s(n))), constant) = true then sort(Q(r(n))+Q(s(n))) else 0 end if end proc: for n to 20 do if Q(n) = 0 then print(0) else print(seq(coeff(Q(n), x, degree(Q(n))j), j = 0 .. degree(Q(n)))) end if end do; # yields sequence in triangular form


CROSSREFS

Sequence in context: A146061 A135936 A109707 * A064272 A117479 A200650
Adjacent sequences: A214575 A214576 A214577 * A214579 A214580 A214581


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Aug 18 2012


STATUS

approved



