pith. sign in

arxiv: 1301.6568 · v2 · pith:6B4SSEGNnew · submitted 2013-01-28 · 🧮 math.CO · cs.DM

The total run length of a word

classification 🧮 math.CO cs.DM
keywords lengthwordtotalbeenfactormaximumnumberperiod
0
0 comments X
read the original abstract

A run in a word is a periodic factor whose length is at least twice its period and which cannot be extended to the left or right (by a letter) to a factor with greater period. In recent years a great deal of work has been done on estimating the maximum number of runs that can occur in a word of length $n$. A number of associated problems have also been investigated. In this paper we consider a new variation on the theme. We say that the total run length (TRL) of a word is the sum of the lengths of the runs in the word and that $\tau(n)$ is the maximum TRL over all words of length $n$. We show that $n^2/8 < \tau(n) < 47n^2/72 + 2n$ for all $n$. We also give a formula for the average total run length of words of length $n$ over an alphabet of size $\alpha$, and some other results.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.