cp's OEIS Frontend

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.

%I A347018 #54 Aug 11 2022 07:23:26
%S A347018 1,1,1,2,3,5,8,14,24,43,74,134,238,433,778,1416,2564,4676,8498,15507,
%T A347018 28246,51568,94049,171734,313417,572377,1044986,1908527,3485092,
%U A347018 6365294,11624741,21232255,38778177,70828006,129363233,236282260,431563697,788254745,1439742242
%N 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.
%C A347018 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:
%C A347018      (i)  at most two branches at v have more than one vertex, and
%C A347018      (ii) at v has at least three adjacent vertices with degrees <= 3.
%C A347018   This is from the monograph "Eigenvalues, multiplicities and graphs" (see references).
%C A347018 Notice that they are restricted caterpillars: NIM trees are caterpillars on n vertices such that the following two conditions hold:
%C A347018 (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.
%C A347018 (ii) Any degree sequence (...,a,b,...) for a=3, b>=3, cannot be found in the degree sequence of the central path.
%D A347018 Charles R. Johnson and Carlos M. Saiago, Eigenvalues, multiplicities and graphs, Cambridge University Press, 2018.
%H A347018 Charles R. Johnson, George Tsoukalas, Greyson C. Wesley, and Zachary Zhao, <a href="https://arxiv.org/abs/2208.05450">k-NIM trees: Characterization and Enumeration</a>, arXiv:2208.05450 [math.CO], 2022.
%F A347018 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.
%F A347018 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).
%F A347018 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.
%e A347018 By degree sequence of the central path:
%e A347018 a(1): (0)
%e A347018 a(2): (1,1)
%e A347018 a(3): (1,2,1)
%e A347018 a(4): (1,2,2,1),(1,3,1)
%e A347018 a(5): (1,2,2,2,1),(1,2,3,1),(1,4,1)
%e A347018 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)
%e A347018 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),
%e A347018       (1,2,5,1),(1,3,2,3,1),(1,6,1)
%e A347018 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),
%e A347018       (1,4,2,2,2,1),(1,2,4,2,2,1),(1,5,2,2,1),(1,2,5,2,1),
%e A347018       (1,6,2,1),(1,3,2,3,2,1),(1,3,2,2,3,1),(1,7,1),
%e A347018       (1,4,2,3,1), (1,4,4,1)
%t A347018 A[z_,u_,r_]:=r z^4 (1+u z+(u^2 z^4)/(1-u z^4));
%t A347018 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)
%t A347018 alpha[z_,u_,r_]:=r A[z,u,r]+(2Nsk[z^2,u^2,r^2])/(z r) (1+A[z,u,r]/z);
%t A347018 beta[z_,u_,r_]:=-1/(r z) (1+A[z,u,r]/z);
%t A347018 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}];
%t A347018 Nskasym[z_,u_,r_]:=Nsk[z,u,r]-Nsksym[z,u,r];
%t A347018 Nsksymodu[z_,u_,r_]:=(Nsksym[z,u,r]-Nsksym[z,-u,r])/2;
%t A347018 Nsksymodr[z_,u_,r_]:=(Nsksym[z,u,r]-Nsksym[z,u,-r])/2;
%t A347018 Nsksymevuevr[z_,u_,r_]:=(Nsksym[z,u,r]+Nsksym[z,-u,r]+Nsksym[z,u,-r]+Nsksym[z,-u,-r])/4;
%t A347018 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]]);
%t A347018 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]]));
%t A347018 TableForm[Table[{i,Coefficient[Series[Nim[z]/.{u -> 1, r -> 1}, {z, 0, 50}], z^i]}, {i,1, 50}]]
%K A347018 nonn
%O A347018 1,4
%A A347018 _Greyson C. Wesley_, Aug 10 2021