

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 MatulaGö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 MatulaGöbel number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGö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 MatulaGö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 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
I. Gutman and YeongNan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 1722.
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 MatulaGö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 MatulaGöbel number 4 is V; the distance matrix is [0,1,1; 1,0,2; 1,2,0], having characteristic polynomial 46x+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)][i1, j1] elif i = 1 then 1+dd[pi(n)][1, j1] elif j = 1 then 1+dd[pi(n)][i1, 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



