

A193401


Triangle read by rows: row n contains the coefficients (of the increasing powers of the variable) of the characteristic polynomial of the Laplacian matrix of the rooted tree having MatulaGöbel number n.


2



0, 1, 0, 2, 1, 0, 3, 4, 1, 0, 3, 4, 1, 0, 4, 10, 6, 1, 0, 4, 10, 6, 1, 0, 4, 9, 6, 1, 0, 4, 9, 6, 1, 0, 5, 20, 21, 8, 1, 0, 5, 20, 21, 8, 1, 0, 5, 20, 21, 8, 1, 0, 5, 18, 20, 8, 1, 0, 5, 18, 20, 8, 1, 0, 5, 18, 20, 8, 1, 0, 6, 35, 56, 36, 10, 1, 0, 5, 16, 18, 8, 1, 0, 5, 18, 20, 8, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Row n contains 1+A061775(n) entries (= 1+ number of vertices of the rooted tree).
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



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), then switches (easily) to the Laplacian matrices and finds the coefficients of their characteristic polynomials.


EXAMPLE

Row 4 is 0, 3, 4, 1 because the rooted tree having MatulaGoebel number 4 is V; the Laplacian matrix is [2,1,1; 1,1,0; 1,0,1], having characteristic polynomial x^3  4x^2 +3x
Triangle starts:
0, 1;
0, 2, 1;
0, 3, 4, 1;
0, 3, 4, 1;
0, 4, 10, 6, 1;
0, 4, 10, 6, 1;
0, 4, 9, 6, 1;
0, 4, 9, 6, 1;


MAPLE

with(numtheory): with(linalg): with(LinearAlgebra): DA := proc (d) local aa: aa := proc (i, j) if d[i, j] = 1 then 1 else 0 end if end proc: Matrix(RowDimension(d), RowDimension(d), aa) end proc: AL := proc (a) local ll: ll := proc (i, j) if i = j then add(a[i, k], k = 1 .. RowDimension(a)) else a[i, j] end if end proc: Matrix(RowDimension(a), RowDimension(a), ll) end proc: 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 from 1 to 18 do seq(coeff(CharacteristicPolynomial(AL(DA(d(n))), x), x, k), k = 0 .. V(n)) end do; # yields triangle in triangular form


CROSSREFS



KEYWORD

sign,tabf


AUTHOR



STATUS

approved



