cp's OEIS Frontend

A214573 Irregular triangle read by rows: the (n,k)-entry is the number of vertices with Strahler number k in the rooted tree with Matula-Goebel number n (n>=1, k>=1).

%I A214573 #24 Aug 12 2024 01:22:14
%S A214573 1,2,3,2,1,4,3,1,2,2,3,1,4,1,4,1,5,4,1,3,2,3,2,5,1,4,1,2,3,5,1,3,2,5,
%T A214573 1,4,2,5,1,4,2,5,1,6,1,4,2,6,1,4,2,4,2,6,1,6,5,1,6,1,3,3,5,2,6,1,4,2,
%U A214573 4,2,5,2,6,1,3,3,5,2,3,3,6,1,7,1,5,2,5,2,6,1,4,2,1,7,1,4,3,5,2,4,2,7,1,7,1,5,2,5,2,5,2,2,4,7,1,5,2,6,1,6,2,6,1,6,2,7,1,3,3,4,3,6,2,6,2,5,2,7,1,4,3,5,2
%N A214573 Irregular triangle read by rows: the (n,k)-entry is the number of vertices with Strahler number k in the rooted tree with Matula-Goebel number n (n>=1, k>=1).
%C A214573 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; 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.
%C A214573 The Strahler number of a rooted tree T is defined as the Strahler number of the root of T.
%C A214573 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.
%C A214573 Number of entries in row n = A214574(n) = the Strahler number of the rooted tree with Matula-Goebel number n.
%C A214573 Sum of entries in row n = A061775(n) = number of vertices in the rooted tree with Matula-Goebel number n.
%H A214573 Emeric Deutsch, <a href="http://arxiv.org/abs/1111.4288">Rooted tree statistics from Matula numbers</a>, arXiv:1111.4288 [math.CO], 2011.
%H A214573 Emeric Deutsch, <a href="http://dx.doi.org/10.1016/j.dam.2012.05.012">Rooted tree statistics from Matula numbers</a>, Discrete Appl. Math., 160, 2012, 2314-2322.
%H A214573 F. Göbel, <a href="http://dx.doi.org/10.1016/0095-8956(80)90049-0">On a 1-1-correspondence between rooted trees and natural numbers</a>, J. Combin. Theory, B 29 (1980), 141-143.
%H A214573 I. Gutman and A. Ivic, <a href="http://dx.doi.org/10.1016/0012-365X(95)00182-V">On Matula numbers</a>, Discrete Math., 150, 1996, 131-142.
%H A214573 I. Gutman and Yeong-Nan Yeh, <a href="http://www.emis.de/journals/PIMB/067/3.html">Deducing properties of trees from their Matula numbers</a>, Publ. Inst. Math., 53 (67), 1993, 17-22.
%H A214573 D. W. Matula, <a href="http://www.jstor.org/stable/2027327">A natural rooted tree enumeration by prime factorization</a>, SIAM Rev. 10 (1968) 273.
%H A214573 Wikipedia, <a href="http://en.wikipedia.org/wiki/Strahler_number">Strahler number</a>
%H A214573 <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>
%F A214573 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 Maple program is based on these recursion relations.
%e A214573 Row 4 is 2,1. Indeed, 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.
%e A214573 Triangle starts:
%e A214573   1;
%e A214573   2;
%e A214573   3;
%e A214573   2,1;
%e A214573   4;
%e A214573   3,1;
%e A214573   2,2;
%e A214573   ...
%p A214573 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: for n to 100 do g[n] := G(n) end do: for n to 100 do seq(coeff(g[n], x, j), j = 1 .. degree(g[n])) end do: seq(seq(coeff(g[n], x, j), j = 1 .. degree(g[n])), n = 1 .. 100);
%t A214573 r[n_] := FactorInteger[n][[1, 1]];
%t A214573 s[n_] := n/r[n];
%t A214573 degree = Exponent[#, x]&;
%t A214573 G[n_] := G[n] = Which[n == 1, x, PrimeOmega[n] == 1, Sort[ Expand[ x^degree[G[PrimePi[n]]] + G[PrimePi[n]]]], 1 < PrimeOmega[n] && degree[G[r[n]], x] != degree[G[s[n]]], 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]]]]], True, Sort[G[r[n]] - x^degree[G[r[n]]] + G[s[n]] - x^degree[G[s[n]]] + x^(1 + degree[G[r[n]]])]];
%t A214573 Table[Table[Coefficient[G[n], x, j], {j, 1, degree[G[n], x]}], {n, 1, 100}] // Flatten (* _Jean-François Alcover_, Aug 11 2024, after _Emeric Deutsch_ *)
%Y A214573 Cf. A214574, A061775.
%K A214573 nonn,tabf
%O A214573 1,2
%A A214573 _Emeric Deutsch_, Aug 14 2012