A235111 - OEIS

%I #33 Jan 19 2018 03:10:50

%S 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 45,50,54,55,60,63,65,70,72,77,78,80,84,88,91,96,98,104,112,119,128,

%U 133,152,75,81,90,99,100,105,108,110,117,120,121,126,130,132

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

%C 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 Number of entries in row n is A000055(n) (= number of trees with n vertices).

%C First entry in row n is A005517(n) (= smallest among the Matula numbers of the rooted trees with n vertices).

%C Last entry (= largest entry) in row n is A235112(n).

%H Emeric Deutsch, <a href="/A235111/b235111.txt">Rows n = 1..12, flattened</a>

%H 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 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 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="http://dx.doi.org/10.1016/0012-365X(95)00182-V">On Matula numbers</a>, Discrete Math., 150, 1996, 131-142.

%H 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 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 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 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 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 Triangle begins:

%e 1;

%e 2;

%e 3;

%e 5,7;

%e 9,12,16;

%e 15,18,20,24,28,32;

%p # The following program (due mainly to _W. Edwin Clark_), yields row n for the specified n (<=15).

%p n := 9;

%p 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 # MIN is sequence A005517, MAX is sequence A005518.

%t nmax = 9 (* nmax > 3 *);

%t MIN = Join[{1, 2}, LinearRecurrence[{0, 0, 5}, {3, 5, 9}, nmax - 2]];

%t MAX = Join[{1, 2, 4}, NestList[Prime, 8, nmax - 4]];

%t row[n_] := (

%t f[m_] := Table[Prime[m/p]*PrimePi[p], {p, FactorInteger[m][[All, 1]]}];

%t M[m_] := Module[{A, B}, A = {m}; While[True, B = A; A = Union[Map[f, A] // Flatten, A]; If[B == A, Return[A]]]];

%t u [m_] := FactorInteger[m][[All, 1]][[1]];

%t v [m_] := m/u[m];

%t V [m_] := If [m==1, 1, If[PrimeQ[m], 1+V[PrimePi[m]], V[u[m]]+V[v[m]]-1]];

%t Q = {}; For[j = MIN[[n]], j <= MAX[[n]], j++, If[V[j] == n,  Q = Union[Q, {Min[M[j]]}]]];

%t Q);

%t row[1] = {1};

%t Table[row[n], {n, 1, nmax}] // Flatten (* _Jean-François Alcover_, Jan 19 2018, adapted from Maple *)

%Y Cf. A000055, A005517, A005518, A235112.

%K nonn,tabf

%O 1,2

%A _Emeric Deutsch_, Jan 03 2014