Two-pattern strings II—frequency of occurrence and substring complexity

The previous paper in this series introduced a class of infinite binary strings, called two-pattern strings, that constitute a significant generalization of, and include, the much-studied Sturmian strings. The class of two-pattern strings is a union of a sequence of increasing (with respect to inclusion) subclasses Tλ of two-pattern strings of scope λ, λ=1,2,…. Prefixes of two-pattern strings are interesting from the algorithmic point of view (their recognition, generation, and computation of repetitions and near-repetitions) and since they include prefixes of the Fibonacci and the Sturmian strings, they merit investigation of how many finite two-pattern strings of a given size there are among all binary strings of the same length. In this paper we first consider the frequency fλ(n) of occurrence of two-pattern strings of length n and scope λ among all strings of length n on {a,b}: we show that limn→∞fλ(n)=0, but that for strings of lengths n⩽2λ, two-pattern strings of scope λ constitute more than one-quarter of all strings. Since the class of Sturmian strings is a subset of two-pattern strings of scope 1, it was natural to focus the study of the substring complexity of two-pattern strings to those of scope 1. Though preserving the aperiodicity of the Sturmian strings, the generalization to two-pattern strings greatly relaxes the constrained substring complexity (the number of distinct substrings of the same length) of the Sturmian strings. We derive upper and lower bounds on C1(k) (the number of distinct substring of length k) of two-pattern strings of scope 1, and we show that it can be considerably greater than that of a Sturmian string. In fact, we describe circumstances in which limk→∞(C1(k)−k)=∞.