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,4

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.

Number of entries in row n is A184161(n). Row n>=2 can be easily identified: its first entry is the entry 1 following the first occurrence of n-1 and its last entry is the first occurrence of n.

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

Table of n, a(n) for n=1..88.

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

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).

Example

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;

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;

Crossrefs

Cf. A184161, A198338, A198341.

Sequence in context: A128494 A257696 A110730 * A262561 A264990 A277315

Adjacent sequences: A198336 A198337 A198338 * A198340 A198341 A198342

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 04 2011

Status

approved