OFFSET
1,4
COMMENTS
The Strahler number of a vertex of a rooted tree is defined recursively in the following way: (i) the Strahler number of a leaf is 1; (ii) if the vertex has one child with Strahler number i and all other children have Strahler number less than i, then the Strahler number of the vertex is again i; (iii) if the vertex has two or more children with Strahler number i and no child with Strahler number greater than i, then the Strahler number of the vertex is i+1. See the Wikipedia reference. The Strahler number of a rooted tree T is defined as the Strahler number of the root of T.
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.
LINKS
E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
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.
Wikipedia, Strahler number
FORMULA
Define the Strahler polynomial of a rooted tree T as the generating polynomial of the vertices of T with respect to their Strahler numbers. For example, it follows at once that the Strahler polynomial of the rooted tree V is 2x + x^2. Denote by G(n)=G(n;x) the Strahler polynomial of the rooted tree with Matula-Goebel number n. Clearly, A214573(n,k) is the coefficient of x^k in G(n). We have (i) G(1)= x; (ii) if n=p(t) (the t-th prime), then G(n) = x^{degree(G(t)} + G(t); (iii) if n=rs (r,s>=2), then G(n) = G(r) - degree (G(r)) + G(s) - degree(G(s) + x^m, where m = 1+degree(G(r)) if degree(G(r))=degree(G(s)) and m = max(degree(G(r), G(s)) otherwise. The Strahler number a(n) = degree(G(n)).
EXAMPLE
a(4)=2 because the rooted tree with Matula-Goebel number 4 is V; the two leaves have Strahler numbers 1,1, and the root has Strahler number 2; this is - by definition - the Strahler number of the tree.
MAPLE
with(numtheory): G := 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 x elif bigomega(n) = 1 then sort(expand(x^degree(G(pi(n)))+G(pi(n)))) elif 1 < bigomega(n) and degree(G(r(n))) <> degree(G(s(n))) then sort(G(r(n))-x^degree(G(r(n)))+G(s(n))-x^degree(G(s(n)))+x^max(degree(G(r(n))), degree(G(s(n))))) else sort(G(r(n))-x^degree(G(r(n)))+G(s(n))-x^degree(G(s(n)))+x^(1+degree(G(r(n))))) end if end proc: seq(degree(G(n)), n = 1 .. 200);
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Aug 14 2012
STATUS
approved