The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A214574 The Strahler number of the rooted tree with Matula-Goebel number n. 1
1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3 (list; graph; refs; listen; history; text; internal format)
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
Cf. A214573.
Sequence in context: A043532 A043557 A055027 * A342510 A298071 A246920
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Aug 14 2012
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 28 19:24 EDT 2024. Contains 372919 sequences. (Running on oeis4.)