

A214574


The Strahler number of the rooted tree with MatulaGoebel 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 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.


LINKS

Table of n, a(n) for n=1..119.
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, 23142322.
F. Goebel, On a 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
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 Rev. 10 (1968) 273.
Wikipedia, Strahler number
Index entries for sequences related to MatulaGoebel numbers


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 MatulaGoebel 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 tth 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 MatulaGoebel 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 * A298071 A246920 A244964
Adjacent sequences: A214571 A214572 A214573 * A214575 A214576 A214577


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Aug 14 2012


STATUS

approved



