login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A184187 Triangle read by rows: row n contains the coefficients (of the increasing powers of the variable) of the characteristic polynomial of the distance matrix of the rooted tree having Matula-Göbel number n. 3
0, 1, -1, 0, 1, -4, -6, 0, 1, -4, -6, 0, 1, -12, -32, -20, 0, 1, -12, -32, -20, 0, 1, -12, -28, -15, 0, 1, -12, -28, -15, 0, 1, -32, -120, -140, -50, 0, 1, -32, -120, -140, -50, 0, 1, -32, -120, -140, -50, 0, 1, -32, -112, -116, -38, 0, 1, -32, -112, -116, -38, 0, 1, -32, -112, -116, -38, 0, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

COMMENTS

Row n contains 1+A061775(n) entries (= 1+ number of vertices of the rooted tree). The pairs 0,1 are ends of rows.

The Matula-Göbel 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-Göbel 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-Göbel numbers of the m branches of T.

LINKS

Table of n, a(n) for n=1..69.

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

F. Göbel, 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 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.

FORMULA

Let T be a rooted tree with root b. If b has degree 1, then let A be the rooted tree with root c, obtained from T by deleting the edge bc emanating from the root. If b has degree >=2, then A is obtained (not necessarily in a unique way) by joining at b two trees B and C, rooted at b. It is straightforward to express the distance matrix of T in terms of the entries of the distance matrix of A (resp. of B and C). Making use of this, the Maple program (improvable!) finds recursively the distance matrices of the rooted trees with Matula-Göbel numbers 1..1000 (upper limit can be altered) and then finds the coefficients of their characteristic polynomials.

EXAMPLE

Row 4 is -4,-6,0,1 because the rooted tree having Matula-Göbel number 4 is V; the distance matrix is [0,1,1; 1,0,2; 1,2,0], having characteristic polynomial -4-6x+x^3.

Triangle starts:

0,1;

-1,0,1;

-4,-6,0,1;

-4,-6,0,1;

-12,-32,-20,0,1;

-12,-32,-20,0,1;

-12,-28,-15,0,1;

MAPLE

with(numtheory): with(linalg): with(LinearAlgebra): V := 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 1 elif bigomega(n) = 1 then 1+V(pi(n)) else V(r(n))+V(s(n))-1 end if end proc: d := proc (n) local r, s, C, a: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: C := proc (A, B) local c: c := proc (i, j) options operator, arrow: A[1, i]+B[1, j+1] end proc: Matrix(RowDimension(A), RowDimension(B)-1, c) end proc: a := proc (i, j) if i = 1 and j = 1 then 0 elif 2 <= i and 2 <= j then dd[pi(n)][i-1, j-1] elif i = 1 then 1+dd[pi(n)][1, j-1] elif j = 1 then 1+dd[pi(n)][i-1, 1] else  end if end proc: if n = 1 then Matrix(1, 1, [0]) elif bigomega(n) = 1 then Matrix(V(n), V(n), a) else Matrix(blockmatrix(2, 2, [dd[r(n)], C(dd[r(n)], dd[s(n)]), Transpose(C(dd[r(n)], dd[s(n)])), SubMatrix(dd[s(n)], 2 .. RowDimension(dd[s(n)]), 2 .. RowDimension(dd[s(n)]))])) end if end proc: for n to 1000 do dd[n] := d(n) end do: for n to 14 do seq(coeff(CharacteristicPolynomial(d(n), x), x, k), k = 0 .. V(n)) end do;

CROSSREFS

Cf. A061775.

Sequence in context: A324472 A070683 A195785 * A106145 A198372 A203993

Adjacent sequences:  A184184 A184185 A184186 * A184188 A184189 A184190

KEYWORD

sign,tabf

AUTHOR

Emeric Deutsch, Feb 08 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 6 14:15 EST 2019. Contains 329806 sequences. (Running on oeis4.)