A214578 Irregular triangle read by rows: if the rooted tree with Matula-Goebel 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.

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

Offset: 1

Author

Emeric Deutsch, Aug 18 2012

Keywords

• nonn
• tabf

Comments

The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel 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 Matula-Goebel 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.

Examples

			Row 7 is 2,1 because the rooted tree with Matula-Goebel 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;
  ...
		

References

• O. Rojo, Spectra of weighted generalized Bethe trees joined at the root, Linear Algebra and its Appl., 428, 2008, 2961-2979.
• M. K. Goldberg and E. M. Livshits, On minimal universal trees, Mathematical Notes of the Acad. of Sciences of the USSR, 4, 1968, 713-717 (translation from the Russian Mat. Zametki 4 1968 371-379).

Links

• Emeric Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322; arXiv preprint.
• F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
• I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
• I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
• D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.

Programs

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

Mathematica

r[n_Integer] := r[n] = FactorInteger[n][[1, 1]];
s[n_Integer] := n/r[n];
Q[n_Integer] := Cancel@ Together@ Simplify@ Which[n == 1, 0, n == 2, 1, PrimeOmega[n] == 1 && Q[PrimePi[n]] === 0, 0, PrimeOmega[n] == 1, 1 + x * Q[PrimePi[n]], Q[r[n]] =!= 0 && Q[s[n]] =!= 0 && FreeQ[Q[r[n]]/Q[s[n]], x], Q[r[n]] + Q[s[n]], True, 0];
Table[If[Q[n] =!= 0, Reverse@ CoefficientList[Q[n], x], {0}], {n, 1, 100}] // Flatten (* Jean-François Alcover, Aug 03 2024, after Emeric Deutsch *)

Formula

If n>=1 and the rooted tree with Matula-Goebel 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 t-th 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.