cp's OEIS Frontend

A235111 Irregular triangle read by rows: row n (n>=1) contains in increasing order the M-indices of the trees with n vertices.

%I A235111 #33 Jan 19 2018 03:10:50
%S A235111 1,2,3,5,7,9,12,16,15,18,20,24,28,32,25,27,30,35,36,40,42,48,49,56,64,
%T A235111 45,50,54,55,60,63,65,70,72,77,78,80,84,88,91,96,98,104,112,119,128,
%U A235111 133,152,75,81,90,99,100,105,108,110,117,120,121,126,130,132
%N A235111 Irregular triangle read by rows: row n (n>=1) contains in increasing order the M-indices of the trees with n vertices.
%C A235111 We define the M-index of a tree T to be the smallest of the Matula numbers of the rooted trees isomorphic (as a tree) to T. Example. The path tree P[5] = ABCDE has M-index 9. Indeed, there are 3 rooted trees isomorphic to P[5]: rooted at A, B, and C, respectively. Their Matula numbers are 11, 10, and 9, respectively. Consequently, the M-index of P[5] is 9.
%C A235111 Number of entries in row n is A000055(n) (= number of trees with n vertices).
%C A235111 First entry in row n is A005517(n) (= smallest among the Matula numbers of the rooted trees with n vertices).
%C A235111 Last entry (= largest entry) in row n is A235112(n).
%H A235111 Emeric Deutsch, <a href="/A235111/b235111.txt">Rows n = 1..12, flattened</a>
%H A235111 E. Deutsch, <a href="http://arxiv.org/abs/1111.4288">Tree statistics from Matula numbers</a>, arXiv preprint arXiv:1111.4288 [math.CO], 2011.
%H A235111 E. 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 A235111 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 A235111 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 A235111 I. Gutman, W. Linert, I. Lukovits, and Z. Tomovic, <a href="http://dx.doi.org/10.1021/ci990060s">The multiplicative version of the Wiener index</a>, J. Chem. Inf. Comput. Sci., 40, 2000, 113-116.
%H A235111 I. Gutman, W. Linert, I. Lukovits, and Z. Tomovic, <a href="http://dx.doi.org/10.1007/PL00010312">On the multiplicative Wiener index and its possible chemical applications</a>, Monatshefte f. Chemie, 131, 2000, 421-427.
%H A235111 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 A235111 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.
%e A235111 Example. Row 4 is [5, 7]. Indeed, there are 2 trees with 4 vertices: the path P[4] and the star S[3] with 3 edges. There are two rooted trees isomorphic to P[4], having Matula numbers 5 and 6; smallest is 5. There are two rooted trees isomorphic to S[3], having Matula numbers 7 and 8; smallest is 7.
%e A235111 Triangle begins:
%e A235111 1;
%e A235111 2;
%e A235111 3;
%e A235111 5,7;
%e A235111 9,12,16;
%e A235111 15,18,20,24,28,32;
%p A235111 # The following program (due mainly to _W. Edwin Clark_), yields row n for the specified n (<=15).
%p A235111 n := 9;
%p A235111 with(numtheory): MIN := [1, 2, 3, 5, 9, 15, 25, 45, 75, 125, 225, 375, 625, 1125, 1875]: MAX := [1, 2, 4, 8, 19, 67, 331, 2221, 19577, 219613, 3042161, 50728129, 997525853, 22742734291, 592821132889]: f := proc (m) local x, p, S: S := NULL: x := factorset(m): for p in x do S := S, ithprime(m/p)*pi(p) end do: S end proc: M := proc (m) local A, B: A := {m}: do B := A: A := `union`(map(f, A), A): if B = A then return A end if end do end proc: V := proc (n) local u, v: u := proc (n) options operator, arrow: op(1, factorset(n)) end proc: v := proc (n) options operator, arrow: n/u(n) end proc: if n = 1 then 1 elif isprime(n) then 1+V(pi(n)) else V(u(n))+V(v(n))-1 end if end proc: Q := {}: for j from MIN[n] to MAX[n] do if V(j) = n then Q := `union`(Q, {min(M(j))}) else  end if end do: Q;
%p A235111 # MIN is sequence A005517, MAX is sequence A005518.
%t A235111 nmax = 9 (* nmax > 3 *);
%t A235111 MIN = Join[{1, 2}, LinearRecurrence[{0, 0, 5}, {3, 5, 9}, nmax - 2]];
%t A235111 MAX = Join[{1, 2, 4}, NestList[Prime, 8, nmax - 4]];
%t A235111 row[n_] := (
%t A235111 f[m_] := Table[Prime[m/p]*PrimePi[p], {p, FactorInteger[m][[All, 1]]}];
%t A235111 M[m_] := Module[{A, B}, A = {m}; While[True, B = A; A = Union[Map[f, A] // Flatten, A]; If[B == A, Return[A]]]];
%t A235111 u [m_] := FactorInteger[m][[All, 1]][[1]];
%t A235111 v [m_] := m/u[m];
%t A235111 V [m_] := If [m==1, 1, If[PrimeQ[m], 1+V[PrimePi[m]], V[u[m]]+V[v[m]]-1]];
%t A235111 Q = {}; For[j = MIN[[n]], j <= MAX[[n]], j++, If[V[j] == n,  Q = Union[Q, {Min[M[j]]}]]];
%t A235111 Q);
%t A235111 row[1] = {1};
%t A235111 Table[row[n], {n, 1, nmax}] // Flatten (* _Jean-François Alcover_, Jan 19 2018, adapted from Maple *)
%Y A235111 Cf. A000055, A005517, A005518, A235112.
%K A235111 nonn,tabf
%O A235111 1,2
%A A235111 _Emeric Deutsch_, Jan 03 2014