login
A198322
The Matula-Goebel numbers of the rooted trees that have palindromic Wiener polynomials.
0
1, 2, 7, 8, 56, 76, 107, 147, 163, 292, 454, 839, 1433, 4221, 5833, 6137, 7987, 8626, 16216, 17059, 17128, 17764, 23438, 25672, 36812, 41203, 45952, 46428, 51768, 60635, 83009, 86716, 86908, 88321, 91951, 93534, 94542, 99141, 100142, 108848, 120357, 124783, 133741, 136768, 137941, 140079, 142424, 145404, 145654
OFFSET
1,2
COMMENTS
The Wiener polynomials are assumed to have zero constant terms.
The Matula-Goebel 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-Goebel 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-Goebel numbers of the m branches of T.
REFERENCES
G. Caporossi, A. A. Dobrynin, I. Gutman, and P. Hansen, Trees with palindromic Hosoya polynomials, Graph Theory Notes of New York, XXXVI, 1999, 10-16.
LINKS
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 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.
B. E. Sagan, Y-N. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959-969.
FORMULA
The Wiener polynomial W(n,x) of the rooted tree corresponding to the Matula-Goebel number n is given in A196059. It is palindromic if and only if x^{1+degree(W(n,x))}*W(n,1/x)=W(n,x).
EXAMPLE
7 is in the sequence because the rooted tree with Matula-Goebel number 7 is Y; 3 distances are equal to 1 and 3 distances are equal to 2; Wiener polynomial is 3x+3x^2.
MAPLE
with(numtheory): W := proc (n) local r, s, R: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: R := proc (n) if n = 1 then 0 elif bigomega(n) = 1 then sort(expand(x*R(pi(n))+x)) else sort(expand(R(r(n))+R(s(n)))) end if end proc: if n = 1 then 0 elif bigomega(n) = 1 then sort(expand(W(pi(n))+x*R(pi(n))+x)) else sort(expand(W(r(n))+W(s(n))+R(r(n))*R(s(n)))) end if end proc: A := {}: for n to 100000 do if expand(x^(1+degree(W(n)))*subs(x = 1/x, W(n))) = W(n) then A := `union`(A, {n}) else end if end do: A;
MATHEMATICA
r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
R[n_] := Which[n == 1, 0, PrimeOmega[n] == 1, Expand[x*R[PrimePi[n]] + x], True, Expand[R[r[n]] + R[s[n]]]];
W[n_] := Which[n == 1, 0, PrimeOmega[n] == 1, Expand[W[PrimePi[n]] + x*R[PrimePi[n]] + x], True, Expand[W[r[n]] + W[s[n]] + R[r[n]]*R[s[n]]]];
A = {};
Do[If[n == 1 || Expand[x^(1 + Exponent[W[n], x])*(W[n] /. x -> 1/x)] == W[n], Print[n]; A = Union[A, {n}]], {n, 1, 100000}] // Quiet;
A (* Jean-François Alcover, Jun 18 2024, after Maple code *)
CROSSREFS
Cf. A196059.
Sequence in context: A001493 A000637 A250715 * A372422 A371331 A222134
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Oct 24 2011
STATUS
approved