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

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, 45, 50, 54, 55, 60, 63, 65, 70, 72, 77, 78, 80, 84, 88, 91, 96, 98, 104, 112, 119, 128, 133, 152, 75, 81, 90, 99, 100, 105, 108, 110, 117, 120, 121, 126, 130, 132

Offset

1,2

Comments

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.

Number of entries in row n is A000055(n) (= number of trees with n vertices).

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

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

Links

Emeric Deutsch, Rows n = 1..12, flattened

E. Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 2011.

E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.

F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.

I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.

I. Gutman, W. Linert, I. Lukovits, and Z. Tomovic, The multiplicative version of the Wiener index, J. Chem. Inf. Comput. Sci., 40, 2000, 113-116.

I. Gutman, W. Linert, I. Lukovits, and Z. Tomovic, On the multiplicative Wiener index and its possible chemical applications, Monatshefte f. Chemie, 131, 2000, 421-427.

I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.

D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.

Example

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.
Triangle begins:
1;
2;
3;
5,7;
9,12,16;
15,18,20,24,28,32;

Maple

# The following program (due mainly to W. Edwin Clark), yields row n for the specified n (<=15).
n := 9;
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;
# MIN is sequence A005517, MAX is sequence A005518.

Mathematica

nmax = 9 (* nmax > 3 *);
MIN = Join[{1, 2}, LinearRecurrence[{0, 0, 5}, {3, 5, 9}, nmax - 2]];
MAX = Join[{1, 2, 4}, NestList[Prime, 8, nmax - 4]];
row[n_] := (
f[m_] := Table[Prime[m/p]*PrimePi[p], {p, FactorInteger[m][[All, 1]]}];
M[m_] := Module[{A, B}, A = {m}; While[True, B = A; A = Union[Map[f, A] // Flatten, A]; If[B == A, Return[A]]]];
u [m_] := FactorInteger[m][[All, 1]][[1]];
v [m_] := m/u[m];
V [m_] := If [m==1, 1, If[PrimeQ[m], 1+V[PrimePi[m]], V[u[m]]+V[v[m]]-1]];
Q = {}; For[j = MIN[[n]], j <= MAX[[n]], j++, If[V[j] == n,  Q = Union[Q, {Min[M[j]]}]]];
Q);
row[1] = {1};
Table[row[n], {n, 1, nmax}] // Flatten (* Jean-François Alcover, Jan 19 2018, adapted from Maple *)

Crossrefs

Cf. A000055, A005517, A005518, A235112.

Sequence in context: A309881 A293230 A133231 * A228896 A281783 A224854

Adjacent sequences: A235108 A235109 A235110 * A235112 A235113 A235114

Keyword

nonn,tabf

Author

Emeric Deutsch, Jan 03 2014

Status

approved