

A198339


Irregular triangle read by rows: row n is the sequence of Matula numbers of the subtrees of the rooted tree with MatulaGoebel number n.


6



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


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.
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 n1 and its last entry is the first occurrence of n.


REFERENCES

I. Gutman and YeongNan 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.


LINKS



FORMULA

We consider separately the subtrees that contain the root (root subtrees) and those that do not contain the root (nonroot 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 MatulaGoebel number n are described in A198338. The nonroot subtrees are the following: if n=1, then there is no nonroot subtree; if n = p(t) (= the tth prime), then the nonroot subtrees corresoponding to n are all the subtrees corresponding to t; if n=rs (r,s >=2), then the nonroot subtrees consist of the nonroot 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 MatulaGoebel 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



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



