A347018 - OEIS

%I #54 Aug 11 2022 07:23:26

%S 1,1,1,2,3,5,8,14,24,43,74,134,238,433,778,1416,2564,4676,8498,15507,

%T 28246,51568,94049,171734,313417,572377,1044986,1908527,3485092,

%U 6365294,11624741,21232255,38778177,70828006,129363233,236282260,431563697,788254745,1439742242

%N 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 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      (i)  at most two branches at v have more than one vertex, and

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

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

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

%C (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 (ii) Any degree sequence (...,a,b,...) for a=3, b>=3, cannot be found in the degree sequence of the central path.

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

%H 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 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 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 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 By degree sequence of the central path:

%e a(1): (0)

%e a(2): (1,1)

%e a(3): (1,2,1)

%e a(4): (1,2,2,1),(1,3,1)

%e a(5): (1,2,2,2,1),(1,2,3,1),(1,4,1)

%e 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 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       (1,2,5,1),(1,3,2,3,1),(1,6,1)

%e 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       (1,4,2,2,2,1),(1,2,4,2,2,1),(1,5,2,2,1),(1,2,5,2,1),

%e       (1,6,2,1),(1,3,2,3,2,1),(1,3,2,2,3,1),(1,7,1),

%e       (1,4,2,3,1), (1,4,4,1)

%t A[z_,u_,r_]:=r z^4 (1+u z+(u^2 z^4)/(1-u z^4));

%t 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 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 beta[z_,u_,r_]:=-1/(r z) (1+A[z,u,r]/z);

%t 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 Nskasym[z_,u_,r_]:=Nsk[z,u,r]-Nsksym[z,u,r];

%t Nsksymodu[z_,u_,r_]:=(Nsksym[z,u,r]-Nsksym[z,-u,r])/2;

%t Nsksymodr[z_,u_,r_]:=(Nsksym[z,u,r]-Nsksym[z,u,-r])/2;

%t Nsksymevuevr[z_,u_,r_]:=(Nsksym[z,u,r]+Nsksym[z,-u,r]+Nsksym[z,u,-r]+Nsksym[z,-u,-r])/4;

%t 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 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 TableForm[Table[{i,Coefficient[Series[Nim[z]/.{u -> 1, r -> 1}, {z, 0, 50}], z^i]}, {i,1, 50}]]

%K nonn

%O 1,4

%A _Greyson C. Wesley_, Aug 10 2021