Subword histories and associated matrices

The basic numerical quantity investigated in this paper is |w|u, the number of occurrences of a word u as a scattered subword of a word w. Arithmetical combinations of such quantities yield a so-called subword history. We investigate the information content of subword histories. Reducing subword histories to linear ones, as well as the recently introduced Parikh matrices, will be important tools. Simple polynomial formulas for computing the value of a subword history for arbitrary powers of a word are obtained.