THE SIGMA-SEQUENCE AND COUNTING OCCURRENCES OF SOME PATTERNS, SUBSEQUENCES AND SUBWORDS

SERGEY KITAEV

Abstract. We consider sigma-words, which are words used by Evdokimov in the construction of the sigma-sequence [7]. We then find the number of occurrences of certain patterns, subsequences and subwords in these words.

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 [13] 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 [16] determined the number |S_{n}(P)| of permutations in S_{n} simultaneously avoiding any given set of patterns P ⊆ S_{3}.

In [1] Babson and Steingrímsson introduced generalized 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 [1] was the study of Mahonian statistics. A number of interesting results on generalized patterns were obtained in [6]. Relations to several well studied combinatorial structures, such as set partitions, Dyck paths, Motzkin paths and involutions, were shown there.

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

The most attention, in the papers on classical or generalized patterns, is paid to finding exact formulas and/or generating functions for the number of words or permutations avoiding, or having k occurrences of, certain patterns. In [11] the authors suggested another problem, namely counting the number of occurrences of certain patterns in certain words. These words were chosen to be the set of all finite approximations of a sequence generated by a morphism with certain restrictions. A motivation for this choice was the interest in studying classes of sequences and words that are defined by iterative schemes [14, 15]. In [12] the authors also studied the number of occurrences of certain patterns in certain words. But there they choose these words to be the subdivision stages from which the Peano curve is obtained. The authors called these words the Peano words. The Peano curve was studied by the Italian mathematician Giuseppe Peano in 1890 as an example of a continuous space filling curve.

In the present paper we consider the sigma-words, which are words used by Evdokimov in construction of the sigma-sequence [7]. Evdokimov used this sequence to construct chains of maximal length in the n-dimensional unit cube. Independent interest to the sigma-sequence appears in connection with the well-known Dragon curve, discovered by physicist John E. Heighway and defined as follows: we fold a sheet of paper in half, then fold in half again, and again, etc. and then unfold in such way that each crease created by the folding process is opened out into a 90-degree angle. The “curve” refers to the shape of the partially unfolded paper as seen edge on. If one travels along the curve, some of the creases will represent turns to the left and others turns to the right. Now if 1 indicates a turn to the right, and 2 to the left, and we start travelling along the curve indicating the turns, we get the sigma-sequence [8]. In [10] the sigma-sequence was studied from another point of view. It was proved there that this sequence cannot be defined by iterated morphism.

Since the sigma-sequence w_{σ} is a sequence in a 2-letter alphabet, we consider patterns in 2letter alphabets. Moreover, the patterns in a 1-letter alphabet (for example 1-1-1) correspond to two subsequences (for this example, these subsequences are 1-1-1 and 2-2-2), whereas the patterns in a 2-letter alphabet (with at least one letter 2) uniquely determine the subsequences in w_{σ} that correspond to them, and conversely. For example, an occurrence of the pattern 1-2-1 is an occurrence of the subsequence 1-2-1, whereas an occurrence of the subsequence (subword) 211 is an occurrence of the pattern 211. Thus, any of our results for a pattern, can be interpreted in term of subsequences or subwords, depending on the context, and conversely.

In our paper we give either an explicit formula or recurrence relation for the number of occurrences for some classes of patterns, subwords and subsequences in the sigma-words. In particular, Theorem 4, allows to find the number of occurrences of an arbitrary generalized pattern without internal dashes of length ℓ, provided we know four certain numbers that can be easily calculated for the sigma-words C_{k}, D_{k}, C_{k+1} and D_{k+1} (to be defined below), where k = ⌈log_{2} ℓ⌉. Theorem 9 gives a recurrence relation for counting occurrences of patterns of the form τ_{1}-τ_{2}. In Section 6 we discuss occurrences of patterns of the form τ_{1}-τ_{2}- ⋯ -τ_{k}, where the pattern τ_{i} does not overlap with the patterns τ_{i−1} and τ_{i+1} for i = 1, 2, …, k − 1. Finally, Section 7 deals with patterns of the form [τ_{1}-τ_{2}- ⋯ -τ_{k}], [τ_{1}-τ_{2}- ⋯ -τ_{k}) and (τ_{1}-τ_{2}- ⋯ -τ_{k}] in Babson and Steingrímsson notation, which means that we use ”[x” in a pattern p to indicate that in an occurrence of p, the letter corresponding to the x must be the first letter of a word under consideration, whereas if we use “y]”, we mean that the letter corresponding to y must be the last (rightmost) letter in the word.

2. Preliminaries

In [7], Evdokimov constructed chains of maximal length in the n-dimensional unit cube using the sigma-sequence. The sigma-sequence w_{σ} was defined there by the following inductive scheme:

C_{1} = 1, D_{1} = 2

C_{k+1} = C_{k}1D_{k}, D_{k+1} = C_{k}2D_{k}
k = 1, 2, …

and w_{σ} = lim_{k→∞} C_{k}. Thus, the initial letters of w_{σ} are 11211221112212 . . .. We call the words C_{k}

the sigma words. The first four values of the sequence {C_{k}}_{k≥1} are 1, 112, 1121122, 112112211122122.

In [10] an equivalent definition of w_{σ} was given: any natural number n ≠ 0 can be presented unambiguously as n = 2^{t}(4s + σ), where σ < 4, and t is the greatest natural number such that 2^{t} divides n. If n runs through the natural numbers then σ runs through some sequence consisting of 1 and 3. If we substitute 3 by 2 in this sequence, we get w_{σ}.

In this paper we count occurrences of patterns in the sigma-words, which are particular initial subwords of w_{σ}. However, the challenging question is to find the number of occurrences of patterns or subwords in an arbitrary initial subword of w_{σ}, or more generally, in a subword of w_{σ} starting in the position i and ending in the position j.

It turns out that for counting occurrences of certain patterns or subwords in C_{n}, one needs to know the number of occurrences of certain patterns in D_{n}. So, in the most cases, we give results for both C_{n} and D_{n}. However, our main purpose is the words C_{n} for n ≥ 1, and in some propositions and examples we do not consider D_{n}.

In what follows, we give initial values for the words C_{i} and D_{i}:

THE SIGMA-SEQUENCE AND OCCURRENCES OF SOME PATTERNS, SUBSEQUENCES AND SUBWORDS 3

\begin{matrix}C_{1} = 1 & D_{1} = 2 \\ C_{2} = 112 & D_{2} = 122 \\ C_{3} = 1121122 & D_{3} = 1122122 \\ C_{4} = 112112211122122 & D_{4} = 112112221122122 \\ C_{5} = 1121122111221221112112221122122 & D_{5} = 1121122111221222112112221122122 \end{matrix}

We now give some other definitions.

A descent (resp. rise) in a word w = a_{1}a_{2} … a_{n} is an i such that a_{i} > a_{i+1} (resp. a_{i} < a_{i+1}). It follows from the definitions that an occurrence of a descent (resp. rise) is an occurrence of the pattern 21 (resp. 12).

Let c_{n}^{τ} (resp. d_{n}^{τ}) denote the number of occurrences of the pattern τ in C_{n} (resp. D_{n}).

Suppose a word W = AaB, where A and B are some words of the same length, and a is a letter. We define the kernel of order k for the word W to be the subword consisting of the k − 1 rightmost letters of A, the letter a, and the k − 1 leftmost letters of B. We denote it by K_{k}(W). For example, K_{3}(111211221) = 12112. If |A| < k − 1 then we assume K_{k}(W) = ϵ, that is, the kernel in this case is the empty word. Also, m_{k}(τ, W) denotes the number of occurrences of the pattern (or the word, or the subsequence depending on the context) τ in K_{k}(W).

We denote x-x- ⋯ -x (ℓ times) by x^{ℓ}. Also, ⌈a⌉ denotes the least natural number b such that a ≤ b.

3. Patterns 1-1- ⋯ -1, 1-2 and 2-1

It is easy to see that |C_{n}| = |D_{n}| = 2^{n} − 1. The following lemma gives the number of the letters 1 and 2 in C_{n} and D_{n}. Lemma 1. The number of 1s (resp. 2s) in C_{n} is 2^{n−1} (resp. 2^{n−1} − 1). The number of 1s (resp. 2s) in D_{n} is 2^{n−1} − 1 (resp. 2^{n−1}).

Proof. It is enough to find the number of 1s c_{n} and d_{n} in C_{n} and D_{n} respectively, since the number of 2s in C_{n} and D_{n} are obviously equal to |C_{n}| − c_{n} and |D_{n}| − d_{n} respectively.

It is easy to see from the structure of C_{n} and D_{n} that

\{ \begin{matrix}c_{n} = c_{n−1} + d_{n−1} + 1, \\ d_{n} = c_{n−1} + d_{n−1}, \end{matrix}

together with c_{1} = 1 and d_{1} = 0. The solution to this recurrence is c_{n} = 2^{n−1} and d_{n} = 2^{n−1}−1. □

Proposition 2. The number occurrences of the subsequence 1^{k} (resp. 2^{k}) in C_{n} is \binom{2^{n−1}}{k} (resp. \binom{2^{n−1}−1}{k}). Thus, the number of occurrences of the pattern 1^{k} in C_{n} is equal to

c_{n}^{1^{k}} = \binom{2^{n−1}}{k} + \binom{2^{n−1} − 1}{k} = \frac{2^{n} − k}{2^{n−1} − k} \binom{2^{n−1} − 1}{k}.

Proof. From Lemma 1, there are 2^{n−1} (resp. 2^{n−1} − 1) occurrences of the letter 1 (resp. 2) in C_{n}, and thus there are \binom{2^{n−1}}{k} (resp. \binom{2^{n−1}−1}{k}) occurrences of the subsequence 1^{k} (resp. 2^{k}) there. □

Proposition 3. We have that for all n ≥ 2, c_{n}^{1-2} = d_{n}^{1-2} = 2 · 4^{n−2} + (n − 2) · 2^{n−2}, and c_{n}^{2-1} = d_{n}^{2-1} = 2 · 4^{n−2} − n · 2^{n−2}.

Proof. Let us first consider the pattern 1-2. An occurrence of this pattern in C_{n} = C_{n−1}1D_{n−1} is either inside C_{n−1}, or inside D_{n−1}, or the letter 1 is from the word C_{n−1}1, whereas the letter 2 is from the word D_{n−1}. Thus

c_{n}^{1-2} = c_{n−1}^{1-2} + d_{n−1}^{1-2} + { (the number of 1s in C_{n−1}) + 1} · { the number of 2s in D_{n−1}}.

Using the same considerations for D_{n} = C_{n−1}2D_{n−1}, one can get

d_{n}^{1-2} = c_{n−1}^{1-2} + d_{n−1}^{1-2} + { the number of 1s in C_{n−1}} · { (the number of 2s in D_{n−1}) + 1}.

The number of 1s and 2s in C_{n−1} and D_{n−1} is given in Lemma 1. So,

\{ \begin{matrix}c_{n}^{1-2} = c_{n−1}^{1-2} + d_{n−1}^{1-2} + 2^{n−2} · (2^{n−2} + 1) \\ d_{n}^{1-2} = c_{n−1}^{1-2} + d_{n−1}^{1-2} + 2^{n−2} · (2^{n−2} + 1) \end{matrix} ⇔

(1)  ( \begin{matrix}c_{n}^{1-2} \\ d_{n}^{1-2} \end{matrix} ) = ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) ( \begin{matrix}c_{n−1}^{1-2} \\ d_{n−1}^{1-2} \end{matrix} ) + ( \begin{matrix}2^{n−2} · (2^{n−2} + 1) \\ 2^{n−2} · (2^{n−2} + 1) \end{matrix} )

together with c_{2}^{1-2} = 2 and d_{2}^{1-2} = 2. Here, and several times in what follows, we need to solve recurrence relations of the form

x_{n} = Ax_{n−1} + b,

where A is a matrix, and x_{n}, x_{n−1} and b are some vectors, where b sometimes depends on n. We recall from linear algebra that such relations can be solved by diagonalization of the matrix A, that is, by writing A = V DV^{−1}, where D is a diagonal matrix consisting of eigenvalues of A, and the columns of V are eigenvectors of A. For example, if A is a 2 × 2 matrix that consists of 1s, then we use

( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) = ( \begin{matrix}1 & 1 \\ −1 & 1 \end{matrix} ) ( \begin{matrix}0 & 0 \\ 0 & 2 \end{matrix} ) ( \begin{matrix}1/2 & −1/2 \\ 1/2 & 1/2 \end{matrix} )

for computing powers of A, and thus for solving the recurrence relations. For the recurrence 1, we get that for all n ≥ 2, c_{n}^{1-2} = d_{n}^{1-2} = 2 · 4^{n−2} + (n − 2) · 2^{n−2}.

In the same manner, we can get that for the pattern 2-1,

\{ \begin{matrix}c_{n}^{2-1} = c_{n−1}^{2-1} + d_{n−1}^{2-1} + 2^{n−2} · (2^{n−2} − 1), \\ d_{n}^{2-1} = c_{n−1}^{2-1} + d_{n−1}^{2-1} + 2^{n−2} · (2^{n−2} − 1), \end{matrix}

together with c_{3}^{2-1} = 2 and d_{3}^{2-1} = 2. This gives, that for all n ≥ 2, c_{n}^{2-1} = d_{n}^{2-1} = 2·4^{n−2}−n·2^{n−2}. □

Proposition 3 shows that asymptotically, the numbers of occurrences of the patterns, or the subsequences, 1-2 and 2-1 in C_{n} or D_{n} are equal.

4. Patterns without internal dashes

Recall the definitions in Section 2. Theorem 4. Let τ = τ_{1}τ_{2} … τ_{ℓ} be an arbitrary generalized pattern without internal dashes that consists of 1s and 2s. Suppose k = ⌈log_{2} ℓ⌉, a = m_{ℓ}(τ, D_{k}1C_{k}), and b = m_{ℓ}(τ, D_{k}2C_{k}). Then for n > k + 1, we have

c_{n}^{τ} = (a + b + c_{k+1}^{τ} + d_{k+1}^{τ}) · 2^{n−k−2} − b,
d_{n}^{τ} = (a + b + c_{k+1}^{τ} + d_{k+1}^{τ}) · 2^{n−k−2} − a.

Proof. Suppose n > k + 1. In this case, C_{n} = C_{n−1}1D_{n−1} = W_{1}K_{ℓ}(D_{k}1C_{k})W_{2}, for some words W_{1} and W_{2} such that |W_{1}| = |W_{2}|. Because of the definition of the kernel K_{ℓ}(D_{k}1C_{k}), an occurrence of the pattern τ in C_{n} is in either C_{n−1}, or D_{n−1}, or K_{k}(D_{k}1C_{k}) (from the definitions |C_{n−1} ∩ K_{k}(D_{k}1C_{k})| = |D_{n−1} ∩ K_{k}(D_{k}1C_{k})| = ℓ − 1 and thus these intersections cannot be an occurrence of τ). So,

c_{n}^{τ} = c_{n−1}^{τ} + d_{n−1}^{τ} + a,

whereas in the same way, we can obtain that

d_{n}^{τ} = c_{n−1}^{τ} + d_{n−1}^{τ} + b.

By solving these recurrence relations, we get the desirable result. □

In particular, Theorem 4 is valid for ℓ = 1, in which case the number of occurrences of τ in C_{n} (or D_{n}) is the number of letters in C_{n} (or D_{n}). Indeed, in this case, k = 0, a = b = c_{1}^{1} = d_{1}^{1} = 1, hence c_{n}^{1} = d_{n}^{1} = 2^{n} − 1 = |C_{n}| = |D_{n}|. Also, as a corollary to Theorem 4 we have, that if a = b = c_{k+1}^{τ} = d_{k+1}^{τ} = 0 for some pattern τ, then this pattern never appears in sigma-sequence.

All of the following examples are corollaries to Theorem 4.

Example 5. Suppose τ = 12. We have that k = 1, a = m_{2}(12, D_{1}1C_{1}) = 0 and b = m_{2}(12, D_{1}2C_{1}) = 0. Besides, c_{2}^{12} = 1 and d_{2}^{12} = 1. Thus using Theorem 4, for all n > 2, c_{n}^{12} = 2^{n−2}. So, the number of rises in C_{n} is equal to 2^{n−2}, for n ≥ 2.

If τ = 21, again k = 1, but now a = m_{2}(21, D_{1}1C_{1}) = 1 and b = m_{2}(21, D_{1}2C_{1}) = 1. Besides, c_{3}^{21} = 1 and d_{3}^{21} = 1. From Theorem 4, for all n > 3, c_{n}^{21} = 2^{n−2} − 1, which shows that the number of descents in C_{n} is one less than the number of rises.

Since in both cases a = b, using the recurrences in Theorem 4, we have that c_{n}^{12} = d_{n}^{12} = 2^{n−2}, whereas c_{n}^{21} = d_{n}^{21} = 2^{n−2} − 1. Example 6. Suppose τ = 112. We have that k = 2, a = m_{3}(112, D_{2}1C_{2}) = 0, and b = m_{3}(112, D_{2}2C_{2}) = 0. Besides, c_{3}^{112} = 2 and d_{3}^{112} = 1. Now, from Theorem 4, we have that for all n > 3, c_{n}^{112} = d_{n}^{112} = 3 · 2^{n−4}. Example 7. Suppose τ = 221. We have that k = 2, a = m_{3}(221, D_{2}1C_{2}) = 1, and b = m_{3}(221, D_{2}2C_{2}) = 1. Besides, c_{3}^{221} = 0 and d_{3}^{221} = 1. Now, from Theorem 4, we have that for all n > 3, c_{n}^{221} = d_{n}^{221} = 3 · 2^{n−4} − 1. Example 8. If τ = 2212221 then k = 3, a = m_{7}(221, D_{3}1C_{3}) = 0, b = m_{7}(221, D_{3}2C_{3}) = 1, c_{4}^{2212221} = 0, and d_{4}^{2212221} = 0. Thus for n ≥ 4, c_{n}^{2212221} = 2^{n−4} − 1.

5. Patterns of the form τ_{1}-τ_{2}

Theorem 9. Let p = τ_{1}-τ_{2} be a generalized pattern such that |τ_{1}| = k_{1} and |τ_{2}| = k_{2}. Suppose k = ⌈log_{2}(k_{1} + k_{2} − 1)⌉. The following denote the number of occurrences of the subwords τ_{1} and τ_{2} in the certain kernels: a_{τ_{1}} = m_{k_{1}}(τ_{1}, D_{k}1C_{k}), a_{τ_{2}} = m_{k_{2}}(τ_{2}, D_{k}1C_{k}), b_{τ_{1}} = m_{k_{1}}(τ_{1}, D_{k}2C_{k}), and b_{τ_{2}} = m_{k_{2}}(τ_{2}, D_{k}2C_{k}). Also, let r_{1}^{a} (resp. r_{2}^{a}, r_{1}^{b}, r_{2}^{b}) denote the number of occurrences of overlapping subwords τ_{1} and τ_{2} in the word D_{k}1C_{k} (resp. D_{k}1C_{k}, D_{k}2C_{k}, D_{k}2C_{k}), where τ_{1} ∈ K_{k_{1}}(D_{k}1C_{k}) and τ_{2} ∈ C_{k} (resp. τ_{1} ∈ D_{k} and τ_{2} ∈ K_{k_{2}}(D_{k}1C_{k}), τ_{1} ∈ K_{k_{1}}(D_{k}2C_{k}) and τ_{2} ∈ C_{k}, τ_{1} ∈ D_{k} and τ_{2} ∈ K_{k_{2}}(D_{k}2C_{k})). Besides, we assume that we know c_{n}^{τ_{i}} and d_{n}^{τ_{i}} for n > n_{i}, i = 1, 2. Then for n > max(k + 1, n_{1} + 1, n_{2} + 1), c_{n}^{τ} and d_{n}^{τ} are given by the following recurrence:

( \begin{matrix}c_{n}^{τ} \\ d_{n}^{τ} \end{matrix} ) = ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) ( \begin{matrix}c_{n−1}^{τ} \\ d_{n−1}^{τ} \end{matrix} ) + ( \begin{matrix}α_{n} \\ β_{n} \end{matrix} ) ,

where

α_{n} = (c_{n−1}^{τ_{1}} + a_{τ_{1}} − r_{1}^{a})d_{n−1}^{τ_{2}} + (a_{τ_{2}} − r_{2}^{a})c_{n−1}^{τ_{1}}

and

β_{n} = (c_{n−1}^{τ_{1}} + b_{τ_{1}} − r_{1}^{b})d_{n−1}^{τ_{2}} + (b_{τ_{2}} − r_{2}^{b})c_{n−1}^{τ_{1}}.

Proof. Suppose n > max(k + 1, n_{1} + 1, n_{2} + 1). Let us find a recurrence for the number c_{n}^{τ} (one can use the same considerations for d_{n}^{τ}).

An occurrence of the pattern τ in C_{n} = C_{n−1}1D_{n−1} is either inside C_{n−1}, or inside D_{n−1}, or begins in C_{n−1} or the letter 1 between C_{n−1} and D_{n−1} and ends in D_{n−1} or the letter 1. The first two cases obviously give c_{n−1} and d_{n−1} occurrences of τ. To count the contribution of the last to cases, we work with words instead of patterns. We do it to take in account the situations when τ_{1} or τ_{2} consists of copies of only one letter. In this case, we cannot count occurrence of these patterns separately, and then use this information, since, for instance, occurrences of the pattern τ_{1} = 111 are subwords 111 and 222 (the last one of these subwords we do not need), whereas occurrences of the pattern τ_{1} = 222 are not defined at all (222 is not a pattern).

If an occurrence of τ_{1}-τ_{2} does not entirely belong to C_{n−1} or D_{n−1} then we only have one of the following possibilities:

(a) the subword τ_{1} entirely belongs to C_{n−1} and the subword τ_{2} entirely belongs to D_{n−1};

(b) the subword τ_{1} belongs entirely to C_{n−1} and the subword τ_{2} belongs to the kernel K_{k_{2}}(D_{k}1C_{k}), where k = ⌈log_{2}(k_{1}+k_{2}−1)⌉ is the least number that allow to control, in C_{n} (n > k), overlapping occurrences of subwords τ_{1} and τ_{2} where τ_{1} is entirely from C_{n−1} and τ_{2} ∈ K_{k_{2}}(D_{k}1C_{k});

(c) the subword τ_{2} belongs entirely to D_{n−1} and the subword τ_{1} belongs to the kernel K_{k_{1}}(D_{k}1C_{k}).

In (a) we obviously have c_{n−1}^{τ_{1}} · d_{n−1}^{τ_{2}} possibilities.

In (b) we have c_{n−1}^{τ_{1}} · a_{τ_{2}} − c_{n−1}^{τ_{1}} · r_{2}^{a} possibilities, since we need to subtract those occurrences of τ_{1} and τ_{2} that overlap.

Similarly to (b), in (c) we have d_{n−1}^{τ_{2}} · a_{τ_{1}} − d_{n−1}^{τ_{2}} · r_{1}^{a} possibilities, which completes the proof. □

Remark 10. For using Theorem 9, one needs to know c_{n}^{τ} and d_{n}^{τ} for patterns τ without internal dashes. These numbers could be obtained by using Theorem 4.

The following corollary to Theorem 9 is straitforward to prove, using the fact that for nonoverlapping patterns τ_{1} and τ_{2}, r_{1}^{a} = r_{2}^{a} = r_{1}^{b} = r_{2}^{b} = 0.

Corollary 11. We make the same assumptions as those in Theorem 9. Suppose additionally that the words τ_{1} and τ_{2} are not overlapping in the following sense: no one suffix of τ_{1} is a prefix of τ_{2}. Then for n > max(k + 1, n_{1} + 1, n_{2} + 1), c_{n}^{τ} and d_{n}^{τ} are given by the same recurrence as that in Theorem 9 with

α_{n} = (c_{n−1}^{τ_{1}} + a_{τ_{1}})d_{n−1}^{τ_{2}} + a_{τ_{2}}c_{n−1}^{τ_{1}}

and

β_{n} = (c_{n−1}^{τ_{1}} + b_{τ_{1}})d_{n−1}^{τ_{2}} + b_{τ_{2}}c_{n−1}^{τ_{1}}.

Remark 12. Corollary 11 is valid under weaker assumptions, namely we only need the property of non-overlapping of the patterns τ_{1} and τ_{2} when one of them is in its kernel and the other one is not in its kernel. Example 15 deals with the pattern τ that has overlapping blocks τ_{1} and τ_{2}, but Corollary 11 can be applied. However, from practical point of view, checking the fact if two subwords are non-overlapping is more easy than considering the kernels and checking the non-overlapping of the subwords there.

Example 13. Suppose τ = 12-21. We have that |τ_{1}| = |τ_{2}| = 2. Now, in the statement of Theorem 9 we have that k = 2, a_{τ_{1}} = 0, a_{τ_{2}} = 1, b_{τ_{1}} = 0 and b_{τ_{2}} = 1. Also, since there are no overlapping occurrences of the subwords 12 and 21 in K_{3}(1221112) and K_{3}(1222112), we have r_{1}^{a} = 0, r_{2}^{a} = 0, r_{1}^{b} = 0 and r_{2}^{b} = 0. Besides, from example 5, c_{n}^{12} = d_{n}^{12} = 2^{n−2} and c_{n}^{21} = d_{n}^{21} = 2^{n−2} − 1. Thus, α_{n} = β_{n} = 4^{n−3}. Using the fact that c_{3}^{12-21} = 0 and d_{3}^{12-21} = 1, this allows us to get an explicit formula for c_{n}^{12-21} and d_{n}^{12-21} for n > 3:

c_{n}^{12-21} = d_{n}^{12-21} = \frac{1}{2}4^{n−2} − 3 · 2^{n−4}.

In particular c_{4}^{12-21} = 5.

Example 14. Suppose τ = 1-221. We have that |τ_{1}| = 1 and |τ_{2}| = 3. Moreover, the words τ_{1} and τ_{2} are not overlapping, hence we can use Corollary 11. We have that k = 2, a_{τ_{1}} = 1, a_{τ_{2}} = 1, b_{τ_{1}} = 0 and b_{τ_{2}} = 1. From example 7, d_{n}^{221} = 3 · 2^{n−4} − 1. Also, the number of occurrences of the letter 1 (the subword τ_{1} = 1) is given by Lemma 1: c_{n}^{1} = 2^{n−1}. So, α_{n} = 6 · 4^{n−4} + 3 · 2^{n−5} − 1 and β_{n} = 6 · 4^{n−4}. One can get now an explicit formula for c_{n}^{1-221} and d_{n}^{1-221} for n > 4:

\begin{matrix}c_{n}^{1-221} = \frac{1}{2}4^{n−2} + 27 · 2^{n−5} − n − 7, \\ d_{n}^{1-221} = \frac{1}{2}4^{n−2} + 21 · 2^{n−5} − 8. \end{matrix}

In particular, c_{5}^{1-221} = 47.

Example 15. Suppose τ = 112-21. We have that |τ_{1}| = k_{1} = 3 and |τ_{2}| = k_{2} = 2. The other parameters in Theorem 9 are k = 3, a_{τ_{1}} = 0, a_{τ_{2}} = 1, b_{τ_{1}} = 0, b_{τ_{2}} = 1, r_{1}^{a} = r_{2}^{a} = r_{1}^{b} = r_{2}^{b} = 0. From Example 6, for n ≥ 4, c_{n}^{112} = 3 · 2^{n−4}, and from Example 5, d_{n}^{21} = 2^{n−2} − 1. Thus, in Theorem 9, α_{n} = β_{n} = c_{n−1}^{112}(d_{n−1}^{21} + 1) = 3 · 4^{n−4}. Now, we solve the recurrence relation from the theorem to get, that for n > 3

c_{n}^{112-21} = d_{n}^{112-21} = \frac{3}{2} · 4^{n−3} − 2^{n−4}.

6. Counting occurrences of τ_{1}-τ_{2}- ⋯ -τ_{k}

In this section we study the number of occurrences of a pattern τ = τ_{1}-τ_{2}- ⋯ -τ_{k}, where τ_{i} are patterns without internal dashes. We say that τ consists of k blocks. We assume that for i = 1, 2, …, k − 1, the pattern τ_{i} does not overlap with the patterns τ_{i−1} and τ_{i+1}. In this case we give a recurrence relation for the number of occurrences of τ, provided we know the number of occurrences of certain patterns consisting of less than, or equal to, k − 1 blocks, as well as 2k certain numbers which can be calculated by considering the words D_{ℓ}1C_{ℓ} and C_{ℓ}2D_{ℓ}, where ℓ is the maximum number such that ℓ ≤ max_{i}⌈log_{2} |τ_{i}|⌉. The cases of k = 1 and k = 2 are studied in the previous sections; they give the bases for our calculations. However, the case of overlapping patterns τ_{i} is not solved, and it remains as a challenging problem, since an answer to this problem gives the way to count occurrences of an arbitrary generalized pattern, or an arbitrary subsequence, in σ-words.

Theorem 16. Let τ = τ_{1}-τ_{2}- ⋯ -τ_{k} be a generalized pattern such that |τ_{i}| = k_{i} for i = 1, 2, …, k. We assume that for i = 1, 2, …, k − 1, the subword τ_{i} does not overlap with the subwords τ_{i−1} and τ_{i+1} in the following sense: no one suffix of τ_{i−1} is a prefix of τ_{i} and no one suffix of τ_{i} is a prefix of τ_{i+1}. Suppose ℓ_{i} = ⌈log_{2} k_{i}⌉, ℓ = max_{i} ℓ_{i}, and for the subwords τ_{i} we have a_{i} = m_{k_{i}}(τ_{i}, D_{ℓ_{i}}1C_{ℓ_{i}}) and b_{i} = m_{k_{i}}(τ_{i}, D_{ℓ_{i}}2C_{ℓ_{i}}), for i = 1, 2, …, k. We assume that we know c_{n−1}^{τ_{1}-···-τ_{i}} and d_{n−1}^{τ_{i+1}-···-τ_{k}} for each 1 ≤ i ≤ k − 1 and for all n > n^{⋆}. Then for all n > max(ℓ + 1, n^{⋆} + 1), c_{n}^{τ} and d_{n}^{τ} are given by the following recurrence:

( \begin{matrix}c_{n}^{τ} \\ d_{n}^{τ} \end{matrix} ) = ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) ( \begin{matrix}c_{n−1}^{τ} \\ d_{n−1}^{τ} \end{matrix} )+∑_{i=1}^{k−1} ( \begin{matrix}c_{n−1}^{τ_{1}-···-τ_{i}} · d_{n−1}^{τ_{i+1}-···-τ_{k}} \\ c_{n−1}^{τ_{1}-···-τ_{i}} · d_{n−1}^{τ_{i+1}-···-τ_{k}} \end{matrix} )+∑_{i=1}^{k} ( \begin{matrix}a_{i} · c_{n−1}^{τ_{1}-···-τ_{i−1}} · d_{n−1}^{τ_{i+1}-···-τ_{k}} \\ b_{i} · c_{n−1}^{τ_{1}-···-τ_{i−1}} · d_{n−1}^{τ_{i+1}-···-τ_{k}} \end{matrix} ) .

Proof. We consider only c_{n}^{τ}, since the same arguments can be applied to d_{n}^{τ}. We use the considerations similar to those in Theorem 9.

An occurrence of the pattern τ in C_{n} = C_{n−1}1D_{n−1} can be entirely in C_{n} or D_{n}. The first term counts such occurrences. Otherwise, we have two possibilities: either the letter 1 between the words C_{n−1} and D_{n−1} does not belong to an occurrence of τ, or it does do it, in which case there exist i (exactly one) such that the subword τ_{i} occurs in its kernel. The first sum in the statement is obviously responsible for the first of this cases, whereas the second sum is responsible for the second case (in the last case we use the fact that subwords τ_{i} are not overlapping). □

As a corollary to Theorem 16, we have Corollary 11.

The following example is another corollary to Theorem 16.

Example 17. Suppose τ = 2 − 1 − 221, that is, τ_{1} = 2, τ_{2} = 1 and τ_{3} = 221. So, parameters in Theorem 16 are the following: k_{1} = k_{2} = 1, k_{3} = 3, ℓ_{1} = ℓ_{2} = 1, ℓ_{3} = 2, ℓ = 2. From D_{1}1C_{1} = 211 we obtain a_{1} = 0, a_{2} = 1. From D_{2}1C_{2} = 1221112 we obtain a_{3} = 1. From D_{1}2C_{1} = 221 we get b_{1} = 1, b_{2} = 0. From D_{2}2C_{2} = 1222112 we get b_{3} = 1. Besides, from Proposition 3, Examples 7 and 14, we have

c_{n}^{τ_{1}-τ_{2}} = c_{n}^{2−1} = 2 · 4^{n−2} − n · 2^{n−2}, for n > 1;
d_{n}^{τ_{3}} = d_{n}^{221} = 3 · 2^{n−4} − 1, for n > 3;
d_{n}^{τ_{2}-τ_{3}} = d_{n}^{1-221} = \frac{1}{2} · 4^{n−2} + 21 · 2^{n−5} − 8, for n > 4.

Also, the number of occurrences of the subword τ_{1} = 2 in C_{n} is given by Proposition 2: c_{n}^{τ_{1}} = c_{n}^{2} = 2^{n−1} − 1. So, the number of occurrences of the pattern τ in C_{n} and D_{n}, for n > 5, satisfies the following recurrence relation:

( \begin{matrix}c_{n}^{τ} \\ d_{n}^{τ} \end{matrix} ) = ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) ( \begin{matrix}c_{n−1}^{τ} \\ d_{n−1}^{τ} \end{matrix} ) + ( \begin{matrix}\frac{5}{1024}8^{n} + \frac{25−3n}{256}4^{n} − \frac{171}{64}2^{n} + 9 \\ \frac{5}{1024}8^{n} + \frac{21−3n}{256}4^{n} − 2^{n+1} \end{matrix} ) ,

with initial conditions c_{5}^{τ} = 70 and d_{5}^{τ} = 74.

7. Patterns of the form [τ_{1}-τ_{2}- ⋯ -τ_{k}], [τ_{1}-τ_{2}- ⋯ -τ_{k}) and (τ_{1}-τ_{2}- ⋯ -τ_{k}]

We recall that according to Babson and Steingrímsson notation for generalized patterns, if we use ”[” in a pattern, for example if we write p = [1-2), we indicate that in an occurrence of p, the letter corresponding to the 1 must be the first letter of a word under consideration, whereas if we write, say, p = (1-2], then the letter corresponding to 2 must be the last (rightmost) letter of the word.

In the theorems of this section, we assume that we can find the numbers c_{n}^{τ_{1}-τ_{2}-···-τ_{k}} and d_{n}^{τ_{1}-τ_{2}-···-τ_{k}} for any patterns τ_{i}, i = 1, 2, …, k, without internal dashes. For certain special cases, these numbers can be obtained using the theorems of Sections 5 and 6. Theorem 18. Suppose τ_{1} and τ_{2} are two patterns without internal dashes such that |τ_{1}| = k_{1} and |τ_{2}| = k_{2}. Also, suppose ℓ_{1} = log_{2}(k_{1} + 1), ℓ_{2} = log_{2}(k_{2} + 1) and ℓ = log_{2}(k_{1} + k_{2} + 1). Let a(τ_{1}, τ_{2}) be the number of overlapping subwords τ_{1} and τ_{2} in C_{ℓ} such that τ_{1} occurs as k_{1} leftmost letters of C_{ℓ}; b(τ_{1}, τ_{2}) is the number of overlapping subwords τ_{1} and τ_{2} in C_{ℓ} such that τ_{2} occurs as k_{2} rightmost letters of C_{ℓ}. We assume that we know c_{n}^{τ_{i}} and d_{n}^{τ_{i}} for i = 1, 2 and for all n > n^{⋆}.

i. For n ≥ max(ℓ_{1}, n^{⋆}),

c_{n}^{[τ_{1}-τ_{2})} = \{ \begin{matrix}0, & if C_{ℓ_{1}} does not begin with τ_{1}, \\ c_{n}^{τ_{2}} − a(τ_{1}, τ_{2}), & otherwise. \end{matrix}

ii. For n ≥ max(ℓ_{2}, n^{⋆}),

c_{n}^{(τ_{1}-τ_{2}]} = \{ \begin{matrix}0, & if C_{ℓ_{2}} does not end with τ_{2}, \\ c_{n}^{τ_{1}} − b(τ_{1}, τ_{2}), & otherwise. \end{matrix}

iii. For n ≥ ℓ,

c_{n}^{[τ_{1}-τ_{2}]} = \{ \begin{matrix}0, & if C_{ℓ} does not begin with τ_{1} or end with τ_{2}, \\ 1, & otherwise. \end{matrix}

iv. For n ≥ max(ℓ_{1}, n^{⋆}),

d_{n}^{[τ_{1}-τ_{2})} = \{ \begin{matrix}0, & if D_{ℓ_{1}} does not begin with τ_{1}, \\ d_{n}^{τ_{2}} − a(τ_{1}, τ_{2}), & otherwise. \end{matrix}

v. For n ≥ max(ℓ_{2}, n^{⋆}),

d_{n}^{(τ_{1}-τ_{2}]} = \{ \begin{matrix}0, & if D_{ℓ_{2}} does not end with τ_{2}, \\ d_{n}^{τ_{1}} − b(τ_{1}, τ_{2}), & otherwise. \end{matrix}

vi. For n ≥ ℓ,

d_{n}^{[τ_{1}-τ_{2}]} = \{ \begin{matrix}0, & if D_{ℓ} does not begin with τ_{1} or end with τ_{2}, \\ 1, & otherwise. \end{matrix}

Proof. We prove case i, all the other cases are then easy to see.

Clearly, if C_{ℓ_{1}} does not begin with τ_{1} then C_{n} does not begin with τ_{1} for all n ≥ ℓ_{1}, which means that c_{n}^{[τ_{1}-τ_{2})} = 0 in this case. Otherwise, to count occurrences of the pattern [τ_{1}-τ_{2}) is the same as to find the number of occurrences of the pattern τ_{2} in C_{n} and then subtract the number of such occurrences of τ_{2} that begin from the i-th letter of C_{n}, where 1 ≤ i ≤ k_{1}. □

The following two examples are corollaries to Theorem 18. Example 19. Suppose we have the patterns σ_{1} = [1122 − 21211) and σ_{2} = (21221 − 12]. From Theorem 18, c_{n}^{σ_{1}} = d_{n}^{σ_{1}} = 0, since C_{3} does not begin with 1122 (ℓ_{1} = 3). Also, c_{n}^{σ_{2}} = d_{n}^{σ_{2}} = 0, since C_{3} does not end with 12 (ℓ_{2} = 3). Example 20. Suppose τ = [112-21). We have that k_{1} = 3, ℓ_{1} = 2 and C_{2} begins with the subword 112. Besides, a(112, 21) = 1 and, from Example 5, c_{n}^{21} = d_{n}^{21} = 2^{n−2} − 1. Theorem 18 now yields, that for n > 3, we have c_{n}^{[112-21)} = c_{n}^{τ_{2}} − a(τ_{1}, τ_{2}) = 2^{n−2} − 2.

The following theorem is straightforward to prove under the assumption that certain subwords do not overlap. Theorem 21. Let {τ_{1}, τ_{2}, …, τ_{k}} be a set of generalized patterns without internal dashes. Suppose |τ_{1}| = s_{1}, |τ_{k}| = s_{k}, ℓ_{1} = log_{2}(s_{1} + 1) and ℓ_{k} = log_{2}(s_{k} + 1). Also, ℓ = max(ℓ_{1}, ℓ_{k}).

i. With the assumption that the subword τ_{1} does not overlap with the subword τ_{2}, that is, no one suffix of τ_{1} is a prefix of τ_{2}, we have (a)

c_{n}^{[τ_{1}-τ_{2}-···-τ_{k})} = \{ \begin{matrix}0, & if C_{ℓ_{1}} does not begin with τ_{1}, \\ c_{n}^{τ_{2}-τ_{3}-···-τ_{k}}, & otherwise. \end{matrix}

(b)

d_{n}^{[τ_{1}-τ_{2}-···-τ_{k})} = \{ \begin{matrix}0, & if D_{ℓ_{1}} does not begin with τ_{1}, \\ d_{n}^{τ_{2}-τ_{3}-···-τ_{k}}, & otherwise. \end{matrix}

ii. With assumption that the subword τ_{k−1} does not overlap with the subword τ_{k}, that is, no one suffix of τ_{k−1} is a prefix of τ_{k}, we have (a)

c_{n}^{(τ_{1}-τ_{2}-···-τ_{k}]} = \{ \begin{matrix}0, & if C_{ℓ_{k}} does not end with τ_{k}, \\ c_{n}^{τ_{1}-τ_{2}-···-τ_{k−1}}, & otherwise. \end{matrix}

(b)

d_{n}^{(τ_{1}-τ_{2}-···-τ_{k}]} = \{ \begin{matrix}0, & if D_{ℓ_{k}} does not end with τ_{k}, \\ d_{n}^{τ_{1}-τ_{2}-···-τ_{k−1}}, & otherwise. \end{matrix}

iii. With the assumption that the subword τ_{1} does not overlap with the subword τ_{2}, and the subword τ_{k−1} does not overlap with the subword τ_{k}, we have (a)

c_{n}^{[τ_{1}-τ_{2}-···-τ_{k}]} = \{ \begin{matrix}0, & if C_{ℓ} does not begin with τ_{1} or does not end with τ_{k}, \\ c_{n}^{τ_{2}-τ_{3}-···-τ_{k−1}}, & otherwise. \end{matrix}

(b)

d_{n}^{[τ_{1}-τ_{2}-···-τ_{k}]} = \{ \begin{matrix}0, & if D_{ℓ} does not begin with τ_{1} or does not end with τ_{k}, \\ d_{n}^{τ_{2}-τ_{3}-···-τ_{k−1}}, & otherwise. \end{matrix}

The following example is a corollary to Theorem 21. Example 22. Suppose τ = [112-1-221-22]. The parameters of Theorem 21 are k_{1} = 3, k_{2} = 2, ℓ_{1} = 2, ℓ_{2} = 2, ℓ = 2. C_{3} begins with the subword 112 and ends with the subword 22. Thus by Theorem 21 and Example 14, c_{n}^{[112-1-221-22]} = c_{n}^{1-221} = \frac{1}{2}4^{n−2} + 27 · 2^{n−5} − n − 7.

References

[1] 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.

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

[3] Burstein A., Mansour T.: Words restricted by patterns with at most 2 distinct letters, Electronic J. of Combinatorics, 9(2) (2002), #R3.

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

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

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

[7] Evdokimov A. A.: On the Maximal Chain Length of an Unit n-dimensional Cube, Maths Notes 6, No. 3 (1969), 309–319. (Russian)

[8] Private communication (2001).

[9] Gelbaum B., Olmsted J.: Counterexamples in Analysis, Holden-day, San Francisco, London, Amsterdam, (1964).

[10] Kitaev S., There are no iterated morphisms that define the Arshon sequence and the sigma-sequence, to appear J. Automata, Languages and Combinatorics (2002).

[11] Kitaev S., Mansour T.: Counting the occurrences of generalized patterns in words generated by a morphism, preprint CO/0210170.

[12] Kitaev S., Mansour T.: The Peano curve and counting occurrences of some patterns, preprint CO/0210268.

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

[14] 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).

[15] Salomaa A.: Jewels of Formal Language Theory, Computer Science Press (1981).

[16] Simion R., Schmidt F.: Restricted permutations, European J. Combin. 6, no. 4 (1985), 383–406.

[17] Yablonsky S. V.: Discrete mathematics and mathematical problems of cybernetics, Nauka, Vol. 1, Moscow (1974), 112–116. (Russian)

   E-mail address: kitaev@math.chalmers.se

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