Property of upper bounds on the number of rich words
share
A finite word w is called rich if it contains | w|+1 distinct palindromic factors including the empty word. Let q≥ 2 be the size of the alphabet. Let R(n) be the number of rich words of length n. Let d>1 be a real constant and let ϕ, ψ be real functions such that * there is n_0 such that 2ψ(2^-1ϕ(n))≥ dψ(n) for all n>n_0, * n/ϕ(n) is an upper bound on the palindromic length of rich words of length n, and * x/ψ(x)+xln(ϕ(x))/ϕ(x) is a strictly increasing concave function. We show that if c_1,c_2 are real constants and R(n)≤ q^c_1n/ψ(n)+c_2nln(ϕ(n))/ϕ(n) then for every real constant c_3>0 there is a positive integer n_0 such that for all n>n_0 we have that R(n)≤ q^(c_1+c_3)n/dψ(n)+c_2nln(ϕ(n))/ϕ(n)(1+1/c_2lnq+c_3)
READ FULL TEXT