A198339 Irregular triangle read by rows: row n is the sequence of Matula numbers of the subtrees of the rooted tree with Matula-Goebel number n.
1, 1, 1, 2, 1, 1, 1, 2, 2, 3, 1, 1, 1, 2, 2, 4, 1, 1, 1, 1, 2, 2, 2, 3, 3, 5, 1, 1, 1, 1, 2, 2, 2, 3, 4, 6, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 7, 1, 1, 1, 1, 2, 2, 2, 4, 4, 4, 8, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 6, 6, 9, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 5, 6, 10
Offset: 1
Examples
Row 4 is [1,1,1,2,2,4] because the rooted tree with Matula-Goebel number 4 is V and its subtrees are *,*,*, |, |, and V. Triangle starts: 1; 1,1,2; 1,1,1,2,2,3; 1,1,1,2,2,4; 1,1,1,1,2,2,2,3,3,5; 1,1,1,1,2,2,2,3,4,6;
References
- 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 Review, 10, 1968, 273.
Links
- E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288
- 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.
- Index entries for sequences related to Matula-Goebel numbers
Programs
-
Maple
m2union := proc (x, y) sort([op(x), op(y)]) end proc: with(numtheory): MRST := 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 [1] elif bigomega(n) = 1 then [1, seq(ithprime(mrst[pi(n)][i]), i = 1 .. nops(mrst[pi(n)]))] else [seq(seq(mrst[r(n)][i]*mrst[s(n)][j], i = 1 .. nops(mrst[r(n)])), j = 1 .. nops(mrst[s(n)]))] end if end proc: MNRST := 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 [] elif bigomega(n) = 1 then m2union(mrst[pi(n)], mnrst[pi(n)]) else m2union(mnrst[r(n)], mnrst[s(n)]) end if end proc: MST := proc (n) m2union(mrst[n], mnrst[n]) end proc: for n to 2000 do mrst[n] := MRST(n): mnrst[n] := MNRST(n): mst[n] := MST(n) end do;
Formula
We consider separately the subtrees that contain the root (root subtrees) and those that do not contain the root (non-root subtrees). A root subtree of a rooted tree T is a subtree of T containing the root. The Matula numbers of the root subtrees of the rooted tree with Matula-Goebel number n are described in A198338. The non-root subtrees are the following: if n=1, then there is no non-root subtree; if n = p(t) (= the t-th prime), then the non-root subtrees corresoponding to n are all the subtrees corresponding to t; if n=rs (r,s >=2), then the non-root subtrees consist of the non-root subtrees corresponding to r and those corresponding to s. The Maple program, based on this recursive procedure, yields row n (<=2000; adjustable) with the command MST(n).
Comments