A347018 The number of unlabeled trees T on n vertices for which maximum multiplicity attained by any matrix whose graph is T implies the simplicity of its other eigenvalues.

1, 1, 1, 2, 3, 5, 8, 14, 24, 43, 74, 134, 238, 433, 778, 1416, 2564, 4676, 8498, 15507, 28246, 51568, 94049, 171734, 313417, 572377, 1044986, 1908527, 3485092, 6365294, 11624741, 21232255, 38778177, 70828006, 129363233, 236282260, 431563697, 788254745, 1439742242

Offset: 1

Author

Greyson C. Wesley, Aug 10 2021

Keywords

• nonn

Comments

The trees counted by a(n) are called NIM trees on n vertices (No Intermediate Multiplicities). Equivalently, a(n) counts the trees on n vertices such that every vertex v of degree >= 3 satisfies two conditions:

(i) at most two branches at v have more than one vertex, and

(ii) at v has at least three adjacent vertices with degrees <= 3.

This is from the monograph "Eigenvalues, multiplicities and graphs" (see references).

Notice that they are restricted caterpillars: NIM trees are caterpillars on n vertices such that the following two conditions hold:

(i) Any degree sequence (...,a,b,c,...) for a>=4, b=4, c>=4 cannot be found in the degree sequence of the central path.

(ii) Any degree sequence (...,a,b,...) for a=3, b>=3, cannot be found in the degree sequence of the central path.

Examples

			By degree sequence of the central path:
a(1): (0)
a(2): (1,1)
a(3): (1,2,1)
a(4): (1,2,2,1),(1,3,1)
a(5): (1,2,2,2,1),(1,2,3,1),(1,4,1)
a(6): (1,2,2,2,2,1),(1,2,3,2,1),(1,2,2,3,1),(1,2,4,1),(1,5,1)
a(7): (1,2,2,2,2,2,1),(1,2,4,2,1),(1,2,2,4,1),(1,2,2,3,2,1),(1,2,2,2,3,1),
      (1,2,5,1),(1,3,2,3,1),(1,6,1)
a(8): (1,2,2,2,2,2,2,1),(1,3,2,2,2,2,1),(1,2,3,2,2,2,1),(1,2,2,3,2,2,1),
      (1,4,2,2,2,1),(1,2,4,2,2,1),(1,5,2,2,1),(1,2,5,2,1),
      (1,6,2,1),(1,3,2,3,2,1),(1,3,2,2,3,1),(1,7,1),
      (1,4,2,3,1), (1,4,4,1)
		

References

• Charles R. Johnson and Carlos M. Saiago, Eigenvalues, multiplicities and graphs, Cambridge University Press, 2018.

Links

• Charles R. Johnson, George Tsoukalas, Greyson C. Wesley, and Zachary Zhao, k-NIM trees: Characterization and Enumeration, arXiv:2208.05450 [math.CO], 2022.

Programs

Mathematica

A[z_,u_,r_]:=r z^4 (1+u z+(u^2 z^4)/(1-u z^4));
Nsk[z_,u_,r_]:=r z(1/2 (1/(1-1/z A[z,u,r])+(1+1/z A[z,u,r])/(1-1/z^2 A[z^2,u^2,r^2]))-1)
alpha[z_,u_,r_]:=r A[z,u,r]+(2Nsk[z^2,u^2,r^2])/(z r) (1+A[z,u,r]/z);
beta[z_,u_,r_]:=-1/(r z) (1+A[z,u,r]/z);
Nsksym[z_,u_,r_]:=Sum[Product[beta[z^2^i,u^2^i,r^2^i],{i,0,k-1}] alpha[z^2^k,u^2^k,r^2^k],{k,0,6}];
Nskasym[z_,u_,r_]:=Nsk[z,u,r]-Nsksym[z,u,r];
Nsksymodu[z_,u_,r_]:=(Nsksym[z,u,r]-Nsksym[z,-u,r])/2;
Nsksymodr[z_,u_,r_]:=(Nsksym[z,u,r]-Nsksym[z,u,-r])/2;
Nsksymevuevr[z_,u_,r_]:=(Nsksym[z,u,r]+Nsksym[z,-u,r]+Nsksym[z,u,-r]+Nsksym[z,-u,-r])/4;
Nsym[z_]:=Nsksymevuevr[z,1/Sqrt[1-z^2],1/Sqrt[1-z^2]]+(Sqrt[1-z^2]/(1-z))(Nsksymodr[z,1/Sqrt[1-z^2],1/Sqrt[1-z^2]])+(Sqrt[1-z^2]/(1-z))(Nsksymodu[z,1/Sqrt[1-z^2],1/Sqrt[1-z^2]]);
Nim[z_]:=(z/(1-z)+Nsym[z])+(Nskasym[z,1/(1-z),1/(1-z)]+1/2(Nsksymevuevr[z,1/(1-z),1/(1-z)]-Nsksymevuevr[z,1/Sqrt[1-z^2],1/Sqrt[1-z^2]])+1/2 (Nsksymodr[z,1/(1-z),1/(1-z)]-Sqrt[1-z^2]/(1-z) Nsksymodr[z,1/Sqrt[1-z^2],1/Sqrt[1-z^2]])+1/2 (Nsksymodu[z,1/(1-z),1/(1-z)]-Sqrt[1-z^2]/(1-z) Nsksymodu[z,1/Sqrt[1-z^2],1/Sqrt[1-z^2]]));
TableForm[Table[{i,Coefficient[Series[Nim[z]/.{u -> 1, r -> 1}, {z, 0, 50}], z^i]}, {i,1, 50}]]

Formula

Conjecture: For n>15, a(n) = 2*a(n-1) + a(n-2) - 3*a(n-3) + 2*a(n-4) - a(n-5) - 2*a(n-6) + a(n-7) + 3*a(n-8) - 4*a(n-9) - a(n-10) + 2*a(n-11) - 2*a(n-12) + 2*a(n-13) + a(n-14) - a(n-15), with initial terms a(1) through a(15) as given.

If the above conjecture holds, then a(n) has o.g.f. (x - x^2 - 2*x^3 + 2*x^4 - x^5 - x^6 + 2*x^7 - 3*x^9 + 2*x^10 + x^11 - x^12 + 2*x^13 - x^15)/(1 - 2*x - x^2 + 3*x^3 - 2*x^4 + x^5 + 2*x^6 - x^7 - 3*x^8 + 4*x^9 + x^10 - 2*x^11 + 2*x^12 - 2*x^13 - x^14 + x^15).

If the above conjecture holds, then a(n) has an explicit Binet-like formula that can be obtained in terms of the roots of a fifth-degree polynomial.