Journal of Automata, Languages and Combinatorics u (v) w, x–y \begin{matrix}c \\ ◯ \end{matrix} Otto-von-Guericke-Universität Magdeburg

Counting the occurrences of generalized patterns in words generated by a morphism

Sergey Kitaev and Toufik Mansour ^{1}

Matematik, Chalmers tekniska högskola och Göteborgs universitet, 412 96 Göteborg, Sweden

            e-mail: kitaev@math.chalmers.se, toufik@math.chalmers.se

ABSTRACT We count the number of occurrences of certain patterns in given words. We choose these words to be the set of all finite approximations of a sequence generated by a morphism with certain restrictions. The patterns in our considerations are either classical patterns 1-2, 2-1, 1-1- ⋯ -1, or arbitrary generalized patterns without internal dashes, in which repetitions of letters are allowed. In particular, we find the number of occurrences of the patterns 1-2, 2-1, 12, 21, 123 and 1-1- ⋯ -1 in the words obtained by iterations of the morphism 1 → 123, 2 → 13, 3 → 2, which is a classical example of a morphism generating a nonrepetitive sequence. Keywords: Combinatorics on words, iterated morphism, generalized pattern

1. Introduction and Background

We write permutations as words π = a_{1}a_{2} ⋯ a_{n}, whose letters are distinct and usually consist of the integers 1, 2, …, n.

An occurrence of a pattern p in a permutation π is “classically” defined as a subsequence in π (of the same length as the length of p) whose letters are in the same relative order as those in p. Formally speaking, for r ≤ n, we say that a permutation σ in the symmetric group S_{n} has an occurrence of the pattern p ∈ S_{r} if there exist 1 ≤ i_{1} < i_{2} < ⋯ < i_{r} ≤ n such that p = σ(i_{1})σ(i_{2}) … σ(i_{r}) in reduced form. The reduced form of a permutation σ on a set {j_{1}, j_{2}, …, j_{r}}, where j_{1} < j_{2} < ⋯ < j_{r}, is a permutation σ_{1} obtained by renaming the letters of the permutation σ so that j_{i} is renamed i for all i ∈ {1, …, r}. For example, the reduced form of the permutation 3651 is 2431. The first case of classical patterns studied was that of permutations avoiding a pattern of length 3 in S_{3}. Knuth [Knuth] found that, for any τ ∈ S_{3}, the number |S_{n}(τ)| of n-permutations avoiding τ is C_{n}, the nth Catalan number. Later, Simion and Schmidt [SimSch] determined the number |S_{n}(P)| of permutations in S_{n} simultaneously avoiding any given set of patterns P ⊆ S_{3}.

1Research financed by EC’s IHRP Programme, within the Research Training Network ”Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272

In [BabStein] Babson and Steingrímsson introduced generalised permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. In order to avoid confusion we write a ”classical” pattern, say 231, as 2-3-1, and if we write, say 2-31, then we mean that if this pattern occurs in the permutation, then the letters in the permutation that correspond to 3 and 1 are adjacent. For example, the permutation π = 516423 has only one occurrence of the pattern 2-31, namely the subword 564, whereas the pattern 2-3-1 occurs, in addition, in the subwords 562 and 563. A motivation for introducing these patterns in [BabStein] was the study of Mahonian statistics. A number of interesting results on generalised patterns were obtained in [Claes]. Relations to several well studied combinatorial structures, such as set partitions, Dyck paths, Motzkin paths and involutions, were shown there.

Burstein [Burstein] considered words instead of permutations. In particular, he found the number |[k]^{n}(P)| of words of length n in k-letter alphabet that avoid each pattern from a set P ⊆ S_{3} simultaneously. Burstein and Mansour [BurMans1] (resp. [BurMans2, BurMans3]) considered forbidden patterns (resp. generalized patterns) with repeated letters.

The most attention, in the papers on classical or generalized patterns, is paid to counting exact formulas and/or generating functions for the number of words or permutations avoiding, or having k occurrences of, certain pattern. In this paper we suggest another problem, namely counting the number of occurrences of a particular pattern τ in given words. We choose these words to be a set of all finite approximations (to be defined below) of a sequence generated by a morphism with certain restrictions. A motivation for such a choice is big interest in studying classes of sequences and words that are defined by iterative schemes [Lothaire, Salomaa]. The pattern τ in our considerations is either a classical pattern from the set {1-2, 2-1, 1-1- ⋯ -1}, or an arbitrary generalized pattern without internal dashes, in which repetitions of letters are allowed. In particular, we find that there are (3 · 4^{n−1} + 2^{n}) occurrences of the pattern 1-2 in the n-th finite approximation of the sequence w defined below, which is a classical example of a nonrepetitive sequence.

Let Σ be an alphabet and Σ^{⋆} be the set of all words of Σ. A map φ : Σ^{⋆} → Σ^{⋆} is called a morphism, if we have φ(uv) = φ(u)φ(v) for any u, v ∈ Σ^{⋆}. It is easy to see that a morphism φ can be defined by defining φ(i) for each i ∈ Σ. The set of all rules i → φ(i) is called a substitution system. We create words by starting with a letter from the alphabet Σ and iterating the substitution system. Such a substitution system is called a D0L (Deterministic, with no context Lindenmayer) system [LindRoz]. D0L systems are classical objects of formal language theory. They are interesting from mathematical point of view [Frid], but also have applications in theoretical biology [Lind]. Let |X| denote the length of a word X, that is the number of letters in X.

Suppose a word φ(a) begins with a for some a ∈ Σ, and that the length of φ^{k}(a) increases without bound. The symbolic sequence lim_{k→∞} φ^{k}(a) is said to be generated

by the morphism φ. In particular, lim_{k→∞} φ^{k}(a) is a fixed point of φ. However, in this

paper we are only interesting in the finite approximations of lim_{k→∞} φ^{k}(a), that is in the words φ^{k}(a) for k = 1, 2, . . ..

An example of a sequence generated by a morphism can be the following sequence w. We create words by starting with the letter 1 and iterating the substitution system ϕ_{w}: 1 → 123, 2 → 13, 3 → 2. Thus, the initial letters of w are 123132123213.... This sequence was constructed in connection with the problem of constructing a nonrepetitive sequence on a 3-letter alphabet, that is, a sequence that does not contain any subwords of the type XX = X^{2}, where X is any non-empty word over a 3letter alphabet. The sequence w has that property. The question of the existence of such a sequence, as well as the questions of the existence of sequences avoiding other kinds of repetitions, were studied in algebra [Adian, Justin, Kol], discrete analysis [Carpi, Dekk, Evdok, Ker, Pleas] and in dynamical systems [MorseHedl]. In Examples 1, 4 and 5 we give the number of occurrences of the patterns 1-2, 2-1, 1-1- ⋯ -1, 12, 123 and 21 in the finite approximations of w.

To proceed further, we need the following definitions. Let N_{ϕ}^{τ}(n) denote the number of occurrences of the pattern τ in a word generated by some morphism ϕ after n iterations. We say that an occurrence of τ is external for a pair of words (X, Y), if this occurrence starts in X and ends in Y. Also, an occurrence of τ for a word X is internal, if this occurrence starts and ends in this X.

2. Patterns 1-2, 2-1 and 1-1-...-1

Theorem 1 Let A = {1, 2, …, k} be an alphabet, where k ≥ 2 and a pattern τ ∈ {1-2, 2-1}. Let X_{1} begins with the letter 1 and consists of ℓ copies of each letter i ∈ A (ℓ ≥ 1). Let a morphism ϕ be such that

1 → X_{1}, 2 → X_{2}, 3 → X_{3}, …, k → X_{k},

where we allow X_{i} to be the empty word ϵ for i = 2, 3, …, k (that is, ϕ may be an

erasing morphism), ∑_{i=2}^{k} |X_{i}| = k · d, and each letter from A appears in the word

X_{2}X_{3} … X_{k} exactly d times. Besides, let e_{i,j} (resp. e_{i}) be the number of external occurrences of τ for (X_{i}, X_{j}) (resp. (X_{i}, X_{i})), where i ≠ j. We assume that e_{i,j} = e_{j,i} for all i and j. Let s_{i} be the number of internal occurrences of τ in X_{i}. In particular, s_{i} = e_{i} = e_{i,j} = e_{j,i} = 0, whenever X_{i} = ϵ; also, e_{i} = |X_{i}| · (|X_{i}| − 1)/2, whenever there are no repetitive letters in X_{i}. Then N_{ϕ}^{τ}(1) = s_{1} and for n ≥ 2, N_{ϕ}^{τ}(n) is given by

ℓ · (d + ℓ)^{n−2} ∑_{i=1}^{k} s_{i} + \binom{ℓ · (d + ℓ)^{n−2}}{2} ∑_{i=1}^{k} e_{i} + ℓ^{2} · (d + ℓ)^{2n−4} ∑_{1≤i<j≤k} e_{i,j}.

Proof. We assume that τ = 1-2. All the considerations for this τ remain the same for the case τ = 2-1.

If n = 1 then the statement is trivial.

Suppose n ≥ 2. Using the fact that X_{1}X_{2}X_{3} … X_{k}, has exactly d + ℓ occurrences of each letter i, i = 1, 2, …, k, one can prove by induction on n, that the word ϕ^{n}(1) is a permutation of ℓ · (d + ℓ)^{n−2} copies of each word X_{i}, where i = 1, 2, …, k. This implies, in particular, that |ϕ^{n}(1)| = k · ℓ · (d + ℓ)^{n−1}.

An occurrence of τ in ϕ^{n}(1) can be either internal, that is when τ occurs inside a word X_{i}, or external, which means that τ begins in a word X_{i} and ends in another word X_{j}. In the first of these cases, since there are ℓ · (d + ℓ)^{n−2} copies of each X_{i}, we have ℓ · (d + ℓ)^{n−2} ∑_{i=1}^{k} s_{i} possibilities. In the second case, either i = j, which gives \binom{ℓ·(d+ℓ)^{n−2}}{2} ∑_{i=1}^{k} e_{i} possibilities, or i ≠ j, in which case there are ℓ · (d + ℓ)^{n−2} possibilities to choose X_{i} (resp. X_{j}) among ℓ · (d + ℓ)^{n−2} copies of X_{i} (resp. X_{j}), and using the fact that e_{i,j} = e_{j,i} (the order in which the words X_{i} and X_{j} occur in ϕ^{n}(1) is unimportant), we have ℓ^{2} · (d + ℓ)^{2n−4} ∑_{1≤i<j≤k} e_{i,j} possibilities. Summing all the possibilities, we finish the proof. □

Let s (resp. e) denote the vector (s_{1}, s_{2}, …, s_{k}) (resp. (e_{1}, e_{2}, …, e_{k})), where s_{i} and e_{j} are defined in Theorem 1. All of the following examples are corollaries to Theorem 1.

Example 1 If we consider the morphism ϕ_{w} defined in Section 1 and the pattern τ = 1-2 then d = ℓ = 1, s = (3, 1, 0), e = (3, 1, 0) and e_{1,2} = e_{2,1} = 2, e_{1,3} = e_{3,1} = 1, e_{2,3} = e_{3,2} = 1. Hence, the number of occurrences of τ is given by N_{ϕ_{w}}^{1-2}(1) = 3 and, for n ≥ 2, N_{ϕ_{w}}^{1-2}(n) = (3 · 4^{n−1} + 2^{n})/2. If τ = 2-1 then s = (0, 0, 0), e = (3, 1, 0) and e_{1,2} = e_{2,1} = 2, e_{1,3} = e_{3,1} = 1, e_{2,3} = e_{3,2} = 1. Hence, N_{ϕ_{w}}^{2-1}(1) = 0 and, for n ≥ 2, N_{ϕ_{w}}^{2-1}(n) = (3 · 4^{n−1} − 2^{n})/2.

Example 2 If we consider the morphism ϕ: 1 → 1324, 2 → ϵ, 3 → 14, and 4 → 23 then for the pattern τ = 1-2, we have d = ℓ = 1, s = (5, 0, 1, 1), e = (6, 0, 1, 1), and e_{i,j}, for i ≠ j, are elements of the matrix

( \begin{matrix}− & 0 & 3 & 3 \\ 0 & − & 0 & 0 \\ 3 & 0 & − & 2 \\ 3 & 0 & 2 & − \end{matrix} ) .

Hence, N_{ϕ}^{1-2}(1) = 5 and, for n ≥ 2, N_{ϕ}^{1-2}(n) = 3 · 4^{n−1} + 11 · 2^{n−2}.

Example 3 If we consider the morphism ϕ: 1 → 13542, 2 → 423, 3 → ϵ, 4 → 5115, and 5 → 234 then for the pattern τ = 1-2, we have ℓ = 1, d = 2, s = (6, 1, 0, 2, 3), e = (10, 3, 0, 4, 3), and e_{i,j}, for i ≠ j, are elements of the matrix

( \begin{matrix}− & 6 & 0 & 8 & 6 \\ 6 & − & 0 & 6 & 3 \\ 0 & 0 & − & 0 & 0 \\ 8 & 6 & 0 & − & 6 \\ 6 & 3 & 0 & 6 & − \end{matrix} ) .

Hence, N_{ϕ}^{1-2}(1) = 6 and, for n ≥ 2, N_{ϕ}^{1-2}(n) = 5 · 9^{n−1} + 2 · 3^{n−2}.

Using the proof of Theorem 1, we have the following.

Theorem 2 Let a morphism ϕ satisfy all the conditions in the statement of Theorem 1 and the pattern τ = \underbrace{1-1- ⋯ -1}_{r times}. Then, for n ≥ 2, the number of occurrences of

τ in ϕ^{n}(1) is given by k · \binom{ℓ·(d+ℓ)^{n−1}}{r}, whereas for n = 1, by k · \binom{ℓ}{r}.

Proof. From the proof of Theorem 1, we have that if n ≥ 2 (resp. n = 1) then ϕ^{n}(1) has exactly ℓ · (d + ℓ)^{n−1} (resp. ℓ) copies of each letter from A. We can choose r of them in \binom{ℓ·(d+ℓ)^{n−1}}{r} (resp. \binom{ℓ}{r}) ways to form the pattern τ. The rest is clear. □

The following example is a corollary to Theorem 2.

Example 4 If we consider the morphism ϕ_{w} defined in Section 1 and the pattern τ = 1-1-1-1 then d = ℓ = 1, r = 4, hence the number of occurrences of τ in ϕ^{n}(1) is 0, whenever n = 1 or n = 2, and 3 · \binom{2^{n−1}}{4} otherwise.

3. Patterns without internal dashes

In what follows we need to extend the notion of an external occurrence of a pattern. Suppose W = AXBY C, where A, X, B, Y and C are some subwords. We say that an occurrence of τ in W is external for a pair of words (X, Y), if this occurrence starts in X, ends in Y and is allowed to have some of its letters in B. For instance, if W = 12324245, where A = 1, X = 23, B = 2 and Y = 424 then an occurrence of the generalized pattern 213, namely the subword 324 is an external occurrence for (X, Y).

Theorem 3 Let A = {1, 2, …, k} be an alphabet and a generalized pattern τ has no internal dashes. Let X_{1} begins with the letter 1 and consists of ℓ copies of each letter i ∈ A (ℓ ≥ 1). Let a morphism ϕ be such that

1 → X_{1}, 2 → X_{2}, 3 → X_{3}, …, k → X_{k},

where we allow X_{i} to be the empty word ϵ for i = 2, 3, …, k (that is, ϕ may be an

erasing morphism), ∑_{i=2}^{k} |X_{i}| = k · d, and each letter from A appears in the word

X_{2}X_{3} … X_{k} exactly d times. Besides, we assume that there are no external occurrences of τ in ϕ^{n}(1) for the pair (X_{i}, X_{j}) for each i and j. Let s_{i} be the number of internal occurrences of τ in X_{i}. In particular, s_{i} = 0, whenever X_{i} = ϵ. Then N_{ϕ}^{τ}(1) = s_{1} and for n ≥ 2,

N_{ϕ}^{τ}(n) = ℓ · (d + ℓ)^{n−2} ∑_{i=1}^{k} s_{i}.

Proof. The theorem is straightforward to prove by observing that for n ≥ 2, ϕ^{n}(1) has ℓ · (d + ℓ)^{n−2} occurrences of each word X_{i} (see the proof of Theorem 1). □

Remark 1 In order to use Theorem 3, we need to control the absence of external occurrences of a pattern τ for given τ (without internal dashes) and a morphism ϕ. To do this, we need, for any pair (X_{i}, X_{j}), to consider all the words X_{i}W X_{j}, where |W | < |τ| − 1, and W is a permutation of a number of words from the set {X_{1}, X_{2}, …, X_{k}}.

The following examples are corollaries to Theorem 3.

Example 5 If we consider the morphism ϕ_{w} defined in Section 1 and the pattern τ = 12 then all the conditions of Theorems 3 hold. In this case d = ℓ = 1 and s = (2, 1, 0). Hence, the number of occurrences of the patterns 12, that is the number of rises, is given by N_{ϕ_{w}}^{12}(1) = 2 and, for n ≥ 2, N_{ϕ_{w}}^{12}(n) = 3 · 2^{n−2}. If τ = 123 then we can apply the theorem to get that for n ≥ 2, N_{ϕ_{w}}^{123}(n) = 2^{n−2}.

If we want to count the number of occurrences of the pattern τ = 21, that is the number of descents, then we cannot apply Theorem 1, since for instance, the pair (X_{1}, X_{2}) = (123, 13) has an external occurrence of τ. However, it is obvious that the number of descents in ϕ^{n}(1) is equal to |ϕ^{n}(1)| − N_{ϕ_{w}}^{12}(1) − 1 = 3 · 2^{n−2} − 1.

Example 6 If we consider the morphism ϕ: 1 → 1243, 2 → 3, 3 → ϵ, and 4 → 124 then for the pattern τ = 123, all the conditions of Theorems 3 hold. In this case d = ℓ = 1, s = (1, 0, 0, 1). Hence, for n ≥ 1, N_{ϕ}^{123}(n) = 2^{n−1}. For τ = 321 we cannot apply Theorem 3, since the pair (X_{4}, X_{1}) has an external occurrence of τ (look at X_{4}X_{2}X_{1} = 12431243). Consideration of the words X_{4}X_{2} and X_{4}X_{1} implies that the theorem cannot be apply for the patterns 132 and 231 respectively. However, we can apply the theorem to the pattern 213 to prove that it does not occur in ϕ^{n}(1) for any n.

Acknowledgement: The final version of this paper was written during the second author’s (T.M.) stay at Haifa University, Haifa 31905, Israel. T.M. wants to express his gratitude to Haifa University for the support.

References

[Adian] Adian S. I.: The Burnside problem and identities in groups. Translated from the Russian by John Lennox and James Wiegold. Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], 95. Springer-Verlag, Berlin-New York, (1979). xi+311 pp.

[BabStein] Babson E., Steingrímsson E.: Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Art. B44b, 18 pp.

[Burstein] Burstein A., Enumeration of words with forbidden patterns, Ph.D. thesis, University of Pennsylvania, 1998.

[BurMans1] Burstein A. and Mansour T., Words restricted by patterns with at most 2 distinct letters, Electronic J. of Combinatorics, to appear (2002).

[BurMans2] Burstein A. and Mansour T., Words restricted by 3-letter generalized multipermutation patterns, preprint CO/0112281.

[BurMans3] Burstein A. and Mansour T., Counting occurrences of some subword patterns, preprint CO/0204320.

[Carpi] Carpi A.: On the number of abelian square-free words on four letters, Discrete Appl. Mathematics, Elsevier, 81 (1998), 155–167.

[Claes] A. Claesson: Generalised Pattern Avoidance, European J. Combin. 22 (2001), no. 7, 961–971.

[Dekk] Dekking F. M.: Strongly non-repetitive sequences and progression-free sets, Journal Com. Theory, Vol. 27-A, No. 2 (1979), 181–185.

[Evdok] Evdokimov A. A.: Strongly asymmetric sequences generated by a finite number of symbols, Dokl. Akad. Nauk SSSR, 179 (1968), 1268–1271. (Russian) English translation in: Soviet Math. Dokl., 9 (1968), 536–539.

[Frid] Frid A. E.: On the frequency of factors in a DOL word, J. Automata, Languages and Combinatorics, Otto-von-Guericke-Univ., Magdeburg 3(1) (1998), 29–41.

[Justin] Justin J.: Characterization of the repetitive commutative semigroups, Journal of Algebra (1972), no. 21, 87–90.

[Ker] Keränen V.: Abelian squares are avoidable on 4 letters, In W. Kuich, editor, Proc. ICALP’92, Lecture Notes in Comp. Sci., 623, Springer-Verlag, Berlin (1992), 41–52.

[Knuth] Knuth D. E.: The Art of Computer Programming, 2nd ed. Addison Wesley, Reading, MA, (1973).

[Kol] Kolotov A. T.: Aperiodic sequences and functions of the growth of algebras, Algebra i Logika 20 (1981), no. 2, 138–154. (Russian)

[Lind] Lindenmayer A.: Mathematical models for cellular interaction in development, Parts I and II, Journal of Theoretical Biology, 18 (1968), 280–315.

[LindRoz] Lindenmayer A., Rozenberg G.: Automata, languages, development, North-Holland Publishing Co., Amsterdam-New York-Oxford (1976), viii+529 pp.

[Lothaire] Lothaire M.: Combinatorics on Words, Encyclopedia of Mathematics, Vol. 17, Addison-Wesley (1986). Reprinted in the Cambridge Mathematical Library, Cambridge University Press, Cambridge UK, (1997).

[MorseHedl] Morse M., Hedlung G.: Unending chess, symbolic dynamics and a problem in semigroups, Duke Math. Journal, Vol. 11, No. 1 (1944), 1–7.

[Pleas] Pleasants P.: Non-repetitive sequences, Proc. Camb. Phil. Soc., Vol. 68 (1970), 267–274.

[Salomaa] Salomaa A.: Jewels of Formal Language Theory, Computer Science Press, [SimSch] R. Simion, F. Schmidt: Restricted permutations, European J. Combin. 6,

no. 4 (1985), 383–406.