%I M0706 #67 Mar 09 2022 09:05:57
%S 1,2,3,5,9,15,25,45,75,125,225,375,625,1125,1875,3125,5625,9375,15625,
%T 28125,46875,78125,140625,234375,390625,703125,1171875,1953125,
%U 3515625,5859375,9765625,17578125,29296875,48828125
%N Smallest label f(T) given to a rooted tree T with n nodes in Matula-Goebel labeling.
%C Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it.
%C For n >= 3, this is also the minimum number of Hamiltonian paths in a strong tournament with n vertices (Busch). - _Gordon Royle_, Jan 24 2022
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Arthur H. Busch, <a href="https://doi.org/10.37236/1141">A Note on the Number of Hamiltonian Paths in Strong Tournaments</a>, Electronic Journal of Combinatorics, N3 (2006).
%H F. Goebel, <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 I. Gutman and A. Ivic, <a href="https://www.jstor.org/stable/44095760">Graphs with maximal and minimal Matula numbers</a>, Bulletin CVII Acad. Serbe, Sciences Math., 107, No. 19, 1994, 65-74.
%H 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 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 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,5).
%F a(1)=1; a(2)=2; a(n) = 3*5^((n-3)/3) if n=0 (mod 3); a(n)=5^((n-1)/3) if n>=4 and n=1 (mod 3); a(n)=9*5^((n-5)/3) if n>=5 and n = 2 (mod 3) (see the Gutman and Ivic 1994 paper). - _Emeric Deutsch_, Apr 15 2012
%F G.f.: z*(1+2*z+3*z^2-z^4)/(1-5*z^3) (conjectured by _Simon Plouffe_).
%F a(n+3) = 5*a(n) for n >= 3 under plausible assumptions about growth of prime numbers. - _David W. Wilson_, Jul 05 2001
%F A091233(n) = (A005518(n)-a(n))+1. - _Antti Karttunen_, May 24 2004
%p a := proc (n) if n = 1 then 1 elif n = 2 then 2 elif `mod`(n, 3) = 0 then 3*5^((1/3)*n-1) elif `mod`(n, 3) = 1 then 5^((1/3)*n-1/3) else 9*5^((1/3)*n-5/3) end if end proc: seq(a(n), n = 1 .. 34); # _Emeric Deutsch_, Apr 15 2012
%p A005517:=(-1-2*z-3*z**2+z**4)/(-1+5*z**3); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%t Join[{1,2},LinearRecurrence[{0,0,5},{3,5,9},40]] (* _Harvey P. Dale_, Feb 25 2012 *)
%t a[n_] := Which[n == 1, 1, n == 2, 2, Mod[n, 3] == 0, 3*5^((1/3)*n-1), Mod[n, 3] == 1, 5^((1/3)*n-1/3), True, 9*5^((1/3)*n-5/3)]; Table[a[n], {n, 1, 34}] (* _Jean-François Alcover_, Mar 06 2014, after _Emeric Deutsch_ *)
%Y Cf. A061773. See A005518 for the largest value of f(T).
%K nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_