Permutations realized by shifts.

1 Introduction and definitions

This paper is motivated by an innovative application of pattern-avoiding permutations to dynamical systems (see (1; 2; 4)), which is based on the following idea. Given a piecewise monotone map on a one-dimensional interval, consider the finite sequences (orbits) that are obtained by iterating the map, starting from any point in the interval. It turns out that the relative order of the entries in these sequences cannot be arbitrary. This means that, for any given such map, there will be some order patterns that will never appear in any orbit. The set of such patterns, which we call forbidden patterns, is closed under consecutive pattern containment. These facts can be used to distinguish random from deterministic time series.

A natural question that arises is how to determine, for a given map, what its forbidden patterns are. While this problem is wide open in general, in the present paper we study it for a particular kind of maps, called (one-sided) shift systems. Shift systems are interesting for two reasons. One one hand, they exhibit all important features of low-dimensional chaos. On the other hand, they are natural maps from a combinatorial perspective, and the study of their forbidden patterns can be done in an elegant combinatorial way.

Forbidden patterns in shift systems were first considered in (1; 2). The authors prove that the smallest forbidden pattern of the shift on N symbols has length N + 2. They also conjecture that, for any N, there are exactly six forbidden patterns of minimal length. In the present paper we give a complete characterization of forbidden patterns of shift systems, and enumerate them with respect to their length.

We will start with some background on consecutive pattern containment, forbidden patterns in maps, and shift systems. In Section 2 we give a formula for the parameter that determines how many symbols are needed in order for a permutation to be realized by a shift. This characterizes allowed and forbidden patterns of shift maps. In Section 3 we give another equivalent characterization involving a transformation on permutations, and we prove that the shift on N symbols has six forbidden patterns of minimal length N + 2, as conjectured in (1). In Section 4 we give a formula for the number of patterns of a given length that are realized by the binary shift, and then we generalize it to the shift on N symbols, for arbitrary N. Many of the proofs are omitted in this extended abstract, but they can be found in the full version (5).

1.1 Permutations and consecutive patterns

We denote by [S.sub.n] the set of permutations of {1,2, ..., n}. If [pi] [member of] [S.sub.n], we will write its one-line notation as [pi] = [[pi](1), [pi](2), ..., [pi](n)] (or [pi] = [pi](1)[pi](2) ... [pi](n) if it creates no confusion). The use of square brackets is to distinguish it from the cycle notation, where [pi] is written as a product of cycles of the form (i, [pi](i), [[pi].sup.2](i), ..., [[pi].sup.k-1](i)), with [[pi].sup.k](i) = i. For example, [pi] = [2,5,1,7,3,6,4] = (1,2,5,3)(4,7)(6).

Given a permutation [pi] = [pi](1)[pi](2) ... [pi](n), let D([pi]) denote the descent set of [pi], that is, D([pi]) = {i : 1 [less than or equal to] i [less than or equal to] n - 1, [pi](i) > [pi](i + 1)}. Let des([pi]) = [absolute value of D([pi])] be the number of descents. The Eulerian polynomials are defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Its coefficients are called the Eulerian numbers. The descent set and the number of descents can be defined for any sequence of integers a = [a.sub.1][a.sub.2] ... [a.sub.n] by letting D(a) = {i : 1 [less than or equal to] i [less than or equal to] n - 1, [a.sub.i] > [a.sub.i+1]}.

Let X be a totally ordered set, and let [x.sub.1], ..., [x.sub.n] [member of] X with [x.sub.1] < [x.sub.2] < ... < [x.sub.n]. Any permutation of these values can be expressed as [[x.sub.[pi](1)], [x.sub.[pi](2)], ..., [x.sub.[pi](n)], where [pi] [member of] [S.sub.n]. We define its reduction to be [rho]([[x.sub.[pi](1)], [x.sub.[pi](2)], ..., [x.sub.[pi](n)]) = [absolute value of [pi](1), [[pi](2), ..., [pi](n)]] = [pi]. Note that the reduction is just a relabeling of the entries with the numbers from 1 to n, keeping the order relationships among them. For example [rho]([4,7,1,6.2, [square root of 2]]) = [3,5,1,4,2]. If the values [y.sub.1], ..., [y.sub.n] are not all different, then [rho]([[y.sub.1], ..., [y.sub.n]) is not defined.

Given two permutations [sigma] [member of] [S.sub.m], [pi] [member of] [S.sub.n], with m [greater than or equal to] n, we say that a contains n as a consecutive pattern is there is some i such that [rho]([summation](i), [summation](i + 1), ..., [summation](i + n - 1)]) = [pi]. Otherwise, we say that [sigma] avoids [pi] as a consecutive pattern. The set of permutations in [S.sub.n] that avoid [pi] as a consecutive pattern is denoted by A[v.sub.n]([pi]). We let Av([pi]) = [[universal].sub.n [greater than or equal to] 1] A[v.sub.n]([pi]). Consecutive pattern containment was first studied in (6), where the sets A[v.sub.n]([pi]) are enumerated for certain permutations [pi].

1.2 Allowed and forbidden patterns in maps

Let f be a map f : X [right arrow] X. Given x [member of] X and n [greater than or equal to] 1, we define

Pat(x, f, n) = [rho]([x, f (x), [f.sup.2](x), ..., [f.sup.n-1](x)]),

provided that there is no pair 1 [less than or equal to] i < j [less than or equal to] n such that [f.sup.i-1](x) = [f.sup.j-1](x). If there is such a pair, then Pat(x, f, n) is not defined. When it is defined, we have Pat(x, f, n) [member of] [S.sub.n]. If [pi] [member of] [S.sub.n] and there is some x [member of] X such that Pat(x, f, n) = [pi], we say that [pi] is realized by f (at x), or that [pi] is an allowed pattern of f. The set of all permutations realized by f is denoted by Allow(f) = [[universal].sub.n [greater than or equal to] 1] [Allow.sub.n](f), where

[Allow.sub.n](f) = {Pat(x, f, n) : x [member of] X} [bar.subset] [S.sub.n].

The remaining permutations are called forbidden patterns, and denoted by Forb(f) = [[universal].sub.n [greater than or equal to] 1] [Forb.sub.n](f), where [Forb.sub.n](f) = [S.sub.n] \ [Allow.sub.n](f).

We are introducing some variations to the notation and terminology used in (1; 2; 4). The main change is that our permutation n = Pat(x, f, n) is essentially the inverse of the permutation of {0,1, ..., n - 1} that the authors of (1) refer to as the order pattern defined by x. Our convention, aside from simplifying the notation, will be more convenient from a combinatorial point of view. The advantage is that now the set Allow(f) is closed under consecutive pattern containment, in the standard sense used in the combinatorics literature, and we no longer need to talk about outgrowth forbidden patterns like in (1). Indeed, if [sigma] [member of] Allow(f) and [sigma] contains [tau] as a consecutive pattern, then [tau] [member of] Allow(f). An equivalent statement is that if [pi] [member of] Forb(f), then Allow(f) [bar.subset] Av([pi]). The minimal elements of Forb(f), i.e., those permutations in Forb(f) that avoid all other patterns in Forb(f), will be called basic forbidden patterns of f. The set of these patterns will be denoted BF(f). Note that basic patterns are the inverses of root patterns as defined in(1).

Let us consider now the case in which X is a closed interval in R, with the usual total order on real numbers. An important incentive to study the set of forbidden patterns of a map comes from the following result, which is a consequence of (4).

Proposition 1.1 If I [subset] R is a closed interval and f : I [right arrow] I is piecewise monotone, then Forb(f) [not equal to] 0.

Recall that piecewise monotone means that there is a finite partition of I into intervals such that f is continuous and strictly monotone on each of those intervals. It fact, it is shown in (4) that for such a map, the number of allowed patterns of f grows at most exponentially, i.e., there is a constant C such that [absolute value of [Allow.sub.n](f)] < [C.sup.n] for n large enough. The value of C is related to the topological entropy of f (see (4) for details). Since the growth of the total number of permutations of length n is super-exponential, the above proposition follows.

Proposition 1.1, together with the above observation that Allow(f) is closed under consecutive pattern containment, provides an interesting connection between dynamical systems on one-dimensional interval maps and pattern avoiding permutations. An important application is that forbidden patterns can be used to distinguish random from deterministic time series. Indeed, in a sequence ([x.sub.1], [x.sub.2], [x.sub.3], ...) where each [x.sub.i] has been chosen independently at random from some continuous probability distribution, any pattern [pi] [member of] [S.sub.n] appears as [pi] = [rho]([[x.sub.i], [x.sub.i+1], ..., [x.sub.i+n-1]]) for some i with nonvanishing probability, and this probability approaches one as the length of the sequence increases. On the other hand, if the sequence has been generated by defining [x.sub.k+1] = f([x.sub.k]) for k [greater than or equal to] 1, where f : I [right arrow] I is a piecewise monotone map, then Proposition 1.1 guarantees that some patterns (in fact, most of them) will never appear in the sequence. The practical aspect of these applications has been considered in (3).

A structural property of the set of allowed patterns of a map is that it is closed under consecutive pattern containment. A new and interesting direction of research is to study more properties of the sets Allow(f). Some natural problems that arise are the following.

1. Understand how Allow(f) and BF(f) depend on the map f.

2. Describe and/or enumerate (exactly or asymptotically) Allow(f) and BF(f) for a particular f.

3. Among the sets of patterns [SIGMA] such that A[v.sub.n] ([SIGMA]) grows at most exponentially in n (this is a necessary condition), characterize those for which there exists a map f such that BF(f) = [SIGMA].

4. Given a map f, determine the length of its smallest forbidden pattern.

Most of this paper is devoted to solving problem 2 for a specific family of maps, that we describe next.

1.3 One-sided shifts

We will concentrate on the set of allowed patterns of certain maps called one-sided shift maps, or simply shifts for short. For a detailed definition of the associated dynamical system, called the one-sided shift space, we refer the reader to (1).

The totally ordered set X considered above will now be the set [W.sub.N] = [{0,1, ..., N - 1}.sup.N] of infinite words on N symbols, equipped with the lexicographic order. Define the (one-sided) shift transformation

[[summation].sub.N] : [W.sub.N] [right arrow] [W.sub.N] [w.sub.1][w.sub.2][w.sub.3] ... [??] [w.sub.2][w.sub.3][w.sub.4]....

We will use [SIGMA] instead of [[SIGMA].sub.N] when it creates no confusion.

Given w [member of] [W.sub.N], n [greater than or equal to] 1, and [pi] [member of] [S.sub.n], we have from the above definition that Pat(w,[SIGMA],n) = [pi] if, for all indices 1 [less than or equal to] i, j [less than or equal to] n, [[summation].sup.i-1](w) < [[summation].sup.j- 1](w) if and only if [pi](i) < [pi](j). For example,

Pat(2102212210 ..., [summation], 7) = [4, 2,1, 7, 5, 3, 6], (1)

because the relative order of the successive shifts is
```2102212210 ... 4
102212210 ... 2
02212210 ... 1
2212210 ... 7
212210 ... 5
12210 ... 3
2210 ... 6,
```

regardless of the entries in place of the dots. The case N = 1 is trivial, since the only allowed pattern of [[summation].sub.1] is the permutation of length 1. In the rest of the paper, we will assume that N [greater than or equal to] 2.

If x [member of] {0,1, ..., N - 1}, we will use the notation [x.sup.[infinity]] = xxx.... If w [member of] [W.sub.N], then [w.sub.n] denotes the n-th letter of w, and we write w = [w.sub.1][w.sub.2][w.sub.3].... We will also write [w.sub.[k,l]] = [w.sub.k][w.sub.k+1] ... [w.sub.l], and [w.sub.[k,[infinity])] = [w.sub.k][w.sub.k+1].... Note that [w.sub.[k,[infinity])] = [summation.sup.Ek-1](w).

It is shown in (1) that [[summation].sub.N] has the same set of forbidden patterns as the so-called sawtooth map defined by x [??] Nx mod 1 for x [member of] [0,1]. This map is piecewise linear, and therefore has forbidden patterns by Proposition 1.1. Forbidden patterns of shift systems were first studied in (1), where the main result is the following.

Proposition 1.2 ((1)) Let N [greater than or equal to] 2. We have that

(a) [Forb.sub.n]([[summation.sub.N]) = [??] for every n [less than or equal to] N + 1,

(b) [Forb.sub.n]([[summation].sub.N]) [not equal to] [??] for every n [greater than or equal to] N + 2.

Example 1. It can be checked that the smallest forbidden patterns of E4 are 615243, 324156, 342516, 162534,453621,435261.

Recall that a word w [member of] [{0,1, ..., N - 1}.sup.k] is primitive if it cannot be written as a power of any proper subword, i.e., it is not of the form w = [[universal].sup.m] for any m > 1, where the exponent indicates concatenation of u with itself m times. Let [[phhi].sub.N](k) denote the number of primitive words of length k over an N-letter alphabet. It is well known that [[psi].sub.N](k) = [[summation].sub.d|k] [mu](d)[N.sup.k/d], where [mu] denotes the Mobius function.

2 The number of symbols needed to realize a pattern

Given a permutation [pi] [member of] [S.sub.n], let N([pi]) be the smallest number N such that [pi] [member of] Allow([[summation].sub.N]). The value of N([pi]) indicates what is the minimum number of symbols needed in the alphabet in order for [pi] to be realized by a shift. For example, if [pi] = [4,2,1,7,5,3,6], then N([pi]) [less than or equal to] 3 because of equation (1), and it is not hard to see that N([pi]) = 3. The main result in this section is a formula for N([pi]).

Theorem 2.1 Let n [greater than or equal to] 2. For any [pi] [member of] [S.sub.n], N([pi]) is given by

N([pi]) = 1 + [absolute value of A([pi])] + [DELTA]([pi]), (2)

where

A([pi]) = (a : 1 [less than or equal to] a [less than or equal to] n-1 such that if i = [[pi].sup.-1](a), j = [[pi].sup.-1](a + 1), then i, j < n and [pi](j + 1)},

and [DELTA]([pi]) = 0 except in the following three cases, in which [DELTA]([pi]) = 1:

(I) [pi](n) [not member of] (1, n}, and if i = [[pi].sup.-1]([pi](n) - 1), j = [[pi].sup.-1]([pi](n) + 1), then [pi] (i + 1) > [pi](j + 1); (II) [pi](n) = 1 and [pi](n - 1) = 2; or (III) [pi](n) = n and [pi](n - 1) = n - 1.

Note that A([pi]) is the set of entries a in the one-line notation of [pi] such that the entry following a + 1 is smaller than the entry following a. For example, if [pi] = [4,3,6,1,5,2], then A([pi]) = (3,4,5}, so Theorem 2.1 says that N([pi]) = 1 + 3 + 0 = 4. The following lemma, whose proof is omitted here, will be useful in the proof.

Lemma 2.2 Suppose that Pat(w,[SIGMA],n) = [pi].

1. If 1 [less than or equal to] i, j < n, [pi](i) < [pi](j), and [pi](i + 1) > [pi](j + 1), then [w.sub.i] < [w.sub.j].

2. If 1 [less than or equal to] i < k [less than or equal to] n are such that [absolute value of [pi](i) - [pi](k)] = 1, then the word [w.sub.[i,k-1]] is primitive.

We will prove Theorem 2.1 in two parts. First we show that N([pi]) [greater than or equal to] 1 + [absolute value of A([pi])] + A([pi]) by proving that if w [member of] [W.sub.N] is such that Pat(w,[SIGMA],n) = [pi], then necessarily N [greater than or equal to] 1 + [absolute value of A([pi])] + [DELTA]([pi]). This fact is a consequence of the following lemma.

Lemma 2.3 Suppose that Pat(w,[SIGMA],n) = [pi], and let b = [pi](n). The entries of w satisfy

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3)

with strict inequalities [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for each a [member of] A([pi]). Additionally, if A([pi]) = 1, then in each of the three cases from Theorem 2.1 we have, respectively, that

(I) one of the inequalities [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is strict;

(II) ... [less than or equal to] [w.sub.n+2] [less than or equal to] [w.sub.n+1] [less than or equal to] [w.sub.n] [less than or equal to] [w.sub.n-1] and one of these inequalities is strict;

(III) [w.sub.n-1] [less than or equal to] [w.sub.n] [less than or equal to] [w.sub.n+1] [less than or equal to] [w.sub.n+2] [less than or equal to] ... and one of these inequalities is strict.

In all cases, the entries of w must satisfy [absolute value of A([pi])] + [DELTA]([pi]) strict inequalities.

Proof: The condition Pat(w,[SIGMA],n) = [pi] is equivalent to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (4)

which clearly implies equation (3). If we remove the term wn from it, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

For every a [member of] the inequality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in (5) has to be strict, by Lemma 2.2 with i = [[pi].sup.-1](a) and j = [[pi].sup.-1](a + 1). Let us now see that in the three cases when [DELTA]([pi]) = 1, an additional strict inequality must be satisfied.

Consider first case (I). Let i = [[pi].sup.-1](b - 1) and j = [[pi].sup.-1](b + 1). Since [pi](i + 1) > [pi](j + 1), Lemma 2.2 implies that [w.sub.i] < [w.sub.j], so the inequality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (equivalently, [w.sub.i] < [w.sub.j]) in (5a) has to be strict. In case (II), the leftmost inequality in (4) is [w.sub.[n -1, [infinity]]) < [w.sub.[n- [infinity]]). For this to hold, we need ... [less than or equal to] [w.sub.n+2] [less than or equal to] [w.sub.n+1] [less than or equal to] [w.sub.n] [less than or equal to] [w.sub.n-1] and at least one of these inequalities must be strict. Similarly, in case (III), the rightmost inequality in (4) is [w.sub.[n-1,[infinity]]) < [w.sub.[n,[infinity]]). This forces [w.sub.n-1] [less than or equal to] [w.sub.n] [less than or equal to] [w.sub.n+1] [less than or equal to] [w.sub.n+2] [less than or equal to] ... with at least one strict inequality.

We will refer to the [absolute value of A([pi])] + [DELTA]([pi]) strict inequalities in Lemma 2.3 as the required strict inequalities. Combined with the weak inequalities from the lemma, they force the number of symbols used in w to be at least 1 + [absolute value of A([pi])] + [DELTA]([pi]). Examples 2 and 3 illustrate how this lemma is used.

Now we show that N([pi]) [less than or equal to] 1 + [absolute value of A([pi])] + [DELTA]([pi]). We will show how for any given [pi] [member of] [S.sub.n] one can construct a word w [member of] [W.sub.N] with Pat(w,[SIGMA],n) = [pi], where N = 1 + [absolute value of A([pi])] + [DELTA]([pi]). We need w to satisfy condition (4). Again, let b = [pi](n).

The first important observation is that, if we can only use N different symbols, then the [absolute value of A([pi])|+[DELTA]([pi]) = N - 1 required strict inequalities from Lemma 2.3 determine the values of the entries [w.sub.1][w.sub.2] ... [w.sub.n-1]. This fact is restated as Corollary 2.9. Consequently, we are forced to assign values to these entries as follows:

(a) If b [member of] {1,n}, assign values to the variables in equation (5a) from left to right, starting with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and increasing the value by 1 at each required strict inequality.

(b) If b = 1, assign values to the variables in equation (5b) from left to right, starting with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], or with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (this is needed in order for condition (II) in Lemma 2.3 to hold), and increasing the value by 1 at each required strict inequality.

(c) If b = n, assign values to the variables in equation (5c) from left to right, starting with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and increasing the value by 1 at each required strict inequality. (Note that when [DELTA]([pi]) = 1, the last assigned value is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].)

It remains to assign the values to [w.sub.m] for m [greater than or equal to] n. Before we do this, let us prove some facts about the entries [w.sub.1] ... [w.sub.n-1]. In the following two lemmas, whose proof can be found in (5), n is any permutation in [S.sub.n] with N([pi]) = N and [w.sub.1] ... [w.sub.n-1] are the values in {0,1, ..., N - 1} assigned above in order to satisfy the required strict inequalities.

Lemma 2.4 Let i < n. If [pi](i) > [pi](i + 1), then [w.sub.i] [greater than or equal to] 1. If [pi](i) < [pi](i + 1), then [w.sub.i] < N - 2.

Lemma 2.5 If 1 [less than or equal to] i, j < n are such that [pi](i) < [pi](j) and [pi](i + 1) > [pi](j + 1), then [w.sub.i] < [w.sub.j].

Once the values [w.sub.1] ... [w.sub.n-1] have been determined, there are several ways to assign values to [w.sub.m] for m [greater than or equal to] n. Two possibilities are the following.

A. Assume that b [not equal to] n. Let k = [[pi].sup.-1](b + 1). Let u = [w.sub.1][w.sub.2] ... [w.sub.k-1] and p = [w.sub.k][w.sub.k+1] ... [w.sub.n-1]. Let m be any integer satisfying m [greater than or equal to] 1 + n-2/n-k (for definiteness, we can pick m = n - 1). Let [w.sub.A]([pi]) = [up.sup.m][0.sup.[infinity]].

B. Assume that b [not equal to] 1. Let k = [[pi].sup.-1](b - 1). Let u = [w.sub.1][w.sub.2] ... [w.sub.k-1 and p = [w.sub.k][w.sub.k+1] ... [w.sub.n-1]. Again, let m be such that m [greater than or equal to] 1 + n-2/n-k (for definiteness, we can pick m = n - 1). Let [w.sub.B]([pi]) = [up.sup.m][(N - 1).sup.[infinity]].

Clearly, [w.sub.A]([pi]) and [w.sub.B]([pi]) use N different symbols. It remains to prove that if w is any of these two words, Pat(w,[SIGMA],n) = [pi], which is equivalent to showing that w satisfies condition (4). Let us now prove that this is the case for w = [w.sub.A]([pi]), when b [not equal to] n.

In the following two lemmas (see the proof in (5)) and in Proposition 2.8, [pi] is any permutation in [S.sub.n] with [pi](n) [not equal to] n, and w = [w.sub.A]([not equal to]). Also, k, u, p and m are as defined in case A above.

Lemma 2.6 The word p = [w.sub.k][w.sub.k+1] ... [w.sub.n-1] is primitive and has some nonzero entry.

Lemma 2.7 We have that [w.sub.[n,[infinity])] < [w.sub.[k,[infinity])]. Moreover, there is no 1 [less than or equal to] s [less than or equal to] n such that [w.sub.[n,[infinity])] < [w.sub.[s,[infinity])] < [w.sub.[k,[infinity])].

Proposition 2.8 If 1 [less than or equal to] i, j [less than or equal to] n are such that [pi](i) < [pi](j), then [w.sub.[i,[infinity]) < [w.sub.[j,[infinity])].

The above proposition proves that Pat([w.sub.A]([pi]),[SIGMA],n) = [pi]. If b [not equal to] 1, proving that Pat([w.sub.B]([pi]),[SIGMA],n) = [pi] is analogous. We can complete the proof of the upper bound on N([pi]) as follows. Let [pi] [member of] [S.sub.n] be given, and let N = 1 + [absolute value of A([pi])] + [DELTA]([pi]). If [pi](n - 1) > [pi](n), let w = [w.sub.A]([pi]). If [pi](n - 1) < [pi](n), let w = [w.sub.B]([pi]). Since Pat(w,[SIGMA],n) = [pi] and w [member of] [W.sub.N], the theorem is proved.

Example 2. Let [pi] = [4,3,6,1,5,2]. By Theorem 2.1, N([pi]) = 4. If Pat(w,[SIGMA],n) = [pi], then Lemma 2.3 implies that [w.sub.4] [less than or equal to] [w.sub.6] [less than or equal to] [w.sub.2] < [w.sub.1] < [w.sub.5] < [w.sub.3[, and there are no more required strict inequalities. We assign [w.sub.4] = [w.sub.2] = 0, [w.sub.1] = 1, [w.sub.5] = 2, [w.sub.3] = 3. Since [pi](5) > [pi](6) and b = [pi](6) = 2, we can take w = [w.sub.A]([pi]) (with m = 2), so k = [[pi].sup.-1](3) = 2, u = [w.sub.1] = 1, and p = [w.sub.2][w.sub.3][w.sub.4][w.sub.5] = 0302. We get w = [up.sup.2][0.sup.[infinity]] = [1030203020.sup.[infinity]].

The following consequence of the proof of Theorem 2.1 will be used in Section 4.

Corollary 2.9 Let [pi] [member of] [S.sub.n], N = N([pi]), and let w [member of] [W.sub.N] be such that Pat(w,[SIGMA], n) = [pi]. Then the entries [w.sub.1][w.sub.2] ... [w.sub.n-1] are uniquely determined by [pi].

Note that, however, with the conditions of Corollary 2.9, [w.sub.n] is not always determined. In the case that [pi](n) [member of] {1, n} and [DELTA]([pi]) = 1, we have two choices for [w.sub.n]. In general, there is a lot of flexibility in the choice of [w.sub.m] for m [greater than or equal to] n. The choices w = [w.sub.A]([pi]) and w = [w.sub.B]([pi]) in the proof of Theorem 2.1 were made to simplify the proof of Proposition 2.8 for all cases at once.

3 An equivalent characterization

We start this section by giving an expression for N([pi]) that is sometimes more convenient to work with than the one in Theorem 2.1. We denote by [C.sub.n] the set of permutations in [S.sub.n] whose cycle decomposition consists of a unique cycle of length n. Let [T.sub.n] be the set of permutations [pi] [member of] [C.sub.n] with one distinguished entry [pi](i), for some 1 [less than or equal to] i [less than or equal to] n. We call the elements of [T.sub.n] marked cycles. We will use the symbol * to denote the distinguished entry, both in one-line and in cycle notation. Note that it is not necessary to keep track of its value, since it is determined once we know all the remaining entries. For example, [T.sub.3] = ([*,3,1], [2,*,1], [2,3,*], [*,1,2], [3,*,2], [3,1,*]}. Clearly, [absolute value of [T.sub.n]] = (n - 1)! x n = n!, since there are n ways to choose the distinguished entry.

Define a map [theta] : [S.sub.n] [right arrow] [T.sub.n] sending [pi] [??] [??] as follows. For each 1 [less than or equal to] i [less than or equal to] n with i [not equal to] [pi](n), let [??](i) be the entry immediately to the right of i in the one-line notation of [pi]. For i = [pi](n), let = * be [??](i) = * be the distinguished entry.

We can also give the following equivalent definition of [??]. If [pi] = [[pi](1), [pi](2), ..., [pi](n)], then [??] is the permutation with cycle decomposition ([pi](1),([pi])(2), ..., [pi](n)) with the entry [pi](1) distinguished. We write [??] = (*,[pi](2), ..., [pi](n)). For example, if [??] = [8,9,2,3,6,4,1,5,7], then [??] = (*,9,2,3,6,4,1,5,7), or in one-line notation, [??] = [5,3,6,1,7,4,*,9,2].

The map [theta] is a bijection between [S.sub.n] and [T.sub.n], since it is clearly invertible. Indeed, to recover [pi] from [??] [member of] [T.sub.n], write [??] in cycle notation, replace the * with the entry in (1, ..., n} that is missing, and turn the parentheses into brackets, thus recovering the one-line notation of [pi].

For [??] [member of] [T.sub.n], let des([??]) denote the number of descents of the sequence that we get by deleting the * from the one-line notation of [??]. That is, if [??] = [[a.sub.1], ..., [a.sub.j], *, [a.sub.j+1], ..., [a.sub.n-1]], then des([??]) = [absolute value of (i : 1 [less than or equal to] i [less than or equal to] n - 2, [a.sub.i] > [a.sub.i+1]}]. We can now state a simpler formula for N([pi]).

Proposition 3.1 Let [pi] [member of] [S.sub.n], [??] = [theta]([pi]). Then N([pi]) is given by

N([pi]) = 1 +des([??]) + [epsilon]([??]),

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For example, if [pi] = [8,9,2,3,6,4,1,5,7], then [??] = [5,3,6,1,7,4,*,9,2] has 4 descents, so N([pi]) = 1 + 4 + 0 = 5. If [pi] = [8,9,3,1,4,6,2,7,5], then [??] = [4,7,1,6,*,2,5,9,3] has 3 descents, so N([pi]) = 1 + 3 + 0 = 4. If [pi] = [3,4,2,1], then [??] = [*,1,4,2] has 1 descent, so N([pi]) = 1 + 1 + 1 = 3.

If [pi] [member of] [S.sub.n], we have by definition that N([pi]) = min{N : [pi] [member of] [Forb.sub.n] ([[summation].sub.N])} = min{N : [pi] [member of] [Allow.sub.n]([[summation].sub.N])}. As a consequence of Proposition 3.1 we recover Proposition 1.2, which in terms of the statistic N([pi]) can be reformulated as follows.

Corollary 3.2 Let n [greater than or equal to] 3. We have that

(a) for every [pi] [member of] [S.sub.n], N([pi]) [less than or equal to] n - 1;

(b) there is some [pi] [member of] [S.sub.n] such that N([pi]) = n - 1.

We define [S.sub.n,N ]= {[pi] [member of] [S.sub.n] : N([pi]) = N}. We are interested in the numbers [a.sub.n,N] = [absolute value of [S.sub.n,N]]. To avoid the trivial cases, we will assume that n, N [greater than or equal to] 2. From the definitions, [Allow.sub.n]([[summation].sub.M]) = [[universal].sup.M.sub.N=2][S.sub.n,N], [Forb.sub.n]([[summation].sub.M]) = [[universal].sup.n-1.sub.N=M+1] [S.sub.n,N]. Since the sets [S.sub.n,N] are disjoint, we have that

[absolute value of [Allow.sub.n]([[summation].sub.M]] = [M.summation over ([N=2])] [a.sub.n,N], [absolute value of [Ford.sub.n]([[summation].sub.M]] = [n-1.summation over ([N=M+1])] [a.sub.n,N].

The first few values of [a.sub.n,N] are given in Table 1. By symmetry considerations (5) it follows easily that all the [a.sub.n,N] are even.

The next result shows that, independently of n, there are exactly six permutations of length n that require the maximum number of symbols (i.e., n - 1) in order to be realized. This settles a conjecture from (1). Given a permutation [pi] [member of] [S.sub.n], we will use [[pi].sup.rc] to denote the permutation such that [[pi].sup.rc](i) = n + 1 - [pi](n + 1 - i) for 1 [less than or equal to] i [less than or equal to] n. If [sigma] is a marked cycle, then [[summation].sup.rc] is defined similarly, where if [sigma](i) is the marked entry of [pi], then [[summation].sup.rc](n + 1 - i) is the marked entry of [[summation].sup.rc]. It will be convenient to visualize [pi] [member of] [S.sub.n] as an n x n array with dots in positions (i, [pi](i)), for 1 [less than or equal to] i [less than or equal to] n. The first coordinate refers to the row number, which increases from left to right, and the second coordinate is the column number, which increases from bottom to top. Then, the array of [[pi].sup.rc] is obtained from the array of [pi] by a 180-degree rotation. Of course, the array of [[pi].sup.-1] is obtained from the one of [pi] by reflecting it along the diagonal y = x. Notice also that the cycle structure of [pi] is preserved in [[pi].sup.-1] and in [[pi].sup.rc]. A marked cycle can be visualized in the same way, replacing the dot corresponding to the distinguished element with a *.

Proposition 3.3 For every n [greater than or equal to] 3, [a.sub.n,n-1] = 6.

Proof: First we show that [a.sub.n,n-1] [greater than or equal to] 6 by giving six permutations in [S.sub.n,n-1]. Let m = |n/2], and let

[summation] = [n, n - 1, ..., m + 1, *, m, m - 1, ..., 2], [tau] = [*, 1, n, n - 1 ..., m + 2, m, m - 1, ..., 2] [member of] [T.sub.n]

(see Figure 1). Using Proposition 3.1, it is easy to check that if [??] [member of] {[summation], [[summation].sup.rc], [[summation].sup.-1], [([[summation].sup.-1]).sup.rc], [tau], [[tau].sup.rc]}, then N([pi]) = n - 1, and that the six permutations in the set are different.

[FIGURE 1 OMITTED]

Let us now show that there are no other permutations with N([pi]) = n - 1. We know by Proposition 3.1 that N([pi]) = n - 1 can only happen if des([??]) = n - 2, or if des([??]) = n - 3 and [epsilon]([??]) = 1.

Case 1: des([??]) = n - 2. In this case, all the entries in [??] other that the * must be in decreasing order. If the distinguished entry is neither [??](1) nor [??](n), then the * must be replacing either 1 or n; otherwise we would have that [??](1) = n and [??](n) = 1, so [??] would not be an n-cycle. It follows that in the array of [??], the entry corresponding to the * is either in the top or bottom row, or in the leftmost or rightmost column.

If the * is replacing 1 (i.e, it is is the bottom row of the array), we claim that the only possible n-cycle in which the other entries are in decreasing order is [??] = [summation]. Indeed, if we consider the cycle structure of [??] = (1, [??](1), [[??].sup.2](1), ..., [[??].sup.n-1](1)), we see that [??](1) = n and [[??].sup.2](1) = [??](n) = 2. Now, [[??].sup.i](1) [not equal to] 1 for 3 [less than or equal to] i [less than or equal to] n - 1), so the decreasing condition on the remaining entries forces [[??].sup.3](1) = [??](2) = n - 1, [[??].sup.4](1) = [??](n - 1) = 3, and so on. A similar argument, considering that rotating the array 180 degrees preserves the cycle structure, shows that if the * is replacing n (i.e, it is in the top row of the array), then necessarily [??] = [[summation].sup.rc].

If the distinguished entry is [??](1) (i.e, it is in the leftmost column of the array), then a symmetric argument, reflecting the array along y = x), shows that [??] = [[summation].sup.-1]. Similarly, if the distinguished entry is [??](n) (i.e, it is is the rightmost column of the array), then necessarily [??] = [([[summation].sup.-1]).sup.rc].

Case 2: des([??]) = n - 3 and [epsilon]([??]) = 1. The second condition forces [??] = [*,1, ...] or [??] = [..., n, *]. Let us restrict to the first case (the second one can be argued in a similar way if we rotate the array 180 degrees). We must have [??](3) > [??](4) > ... > [??](n). We claim that the only such [??] that is also an n-cycle is [??] = [tau]. Indeed, looking at the cycle structure [??] = ([[??].sup.-(n-1)](1), ..., [[??].sup.-1](1), 1), we see that [[??].sup.-1](1) = 2. Now, [[??].sup.-1](1) [not equal to] 1 for 2 [less than or equal to] i [less than or equal to] n - 1, so the decreasing condition on the remaining entries forces [[??].sup.-2](1) = [[??].sup.-1](2) = n, [[??].sup.-3](1) = [[??].sup.-1](n) = 3, [[??].sup.-4](1) = [[??].sup.-1](3) = n - 1, and so on.

4 The number of allowed patterns of a shift

In the rest of the paper, we will assume for simplicity that [w.sub.A]([pi]) and [w.sub.B]([pi]) are defined taking m = n - 1, so they are of the form [up.sup.n-1] [x.sup.[infinity]], with x = 0 or x = N - 1 respectively. The following variation of Lemma 2.7 will be useful later.

Lemma 4.1 Let w = [up.sup.n-1] [0.sup.[infinity]] [member of] [W.sub.N], where [absolute value of u] = k - 1 and [absolute value of p] = n - k for some 1 [less than or equal to] k [less than or equal to] n - 1, and p is primitive. If [pi] = Pat(w, [summation], n) is defined, then [pi](n) = [pi](k) - 1.

For n [greater than or equal to] 2, the set of patterns of length n that are realized by the shift on two symbols is [Allow.sub.n]([[summation].sub.2]) = [S.sub.n,2]. The next result gives the number of these permutations. Recall that [a.sub.n,2] = [absolute value of [S.sub.n,2]] and that [[psi].sub.2] (t) is the number of primitive binary words of length t.

Theorem 4.2 For n [greater than or equal to] 2,

[a.sub.n,2] = [n-1.summation over (t=1)] [[psi].sub.2](t)[2.sup.n-t-1].

Proof: Fix n [greater than or equal to] 2. We will construct a set W [subset] [W.sub.2] with the following four properties:

(i) for all w [member of] W, Pat(w, [[summation].sub.2], n) is defined,

(ii) for all w, w' [member of] W with w [not equal to] w', we have that Pat(w, [[summation].sub.2], n) [not equal to] Pat(w', [[summation].sub.2], n),

(iii) for all [pi] [member of] [Allow.sub.n]([[summation].sub.2]), there is a word w [member of] W such that Pat(w, [[summation].sub.2], n) = n,

(iv) [absolute value of W] = [[summation].sup.n-1.sub.t=1] [[psi].sub.2](t)[2.sup.n-t-1].

Properties (i)-(iii) imply that the map from W to [S.sub.n,2] sending w to Pat(w, [[summation].sub.2], n) is a bijection. Thus, [a.sub.n,2] = [absolute value of W] and the result will follow from property (iv).

Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where we use the notation [bar.0] = 1, [bar.1] = 0. Given binary words u, p of lengths n-t-1 and [tau] respectively, where p is primitive, and x = [[bar.p].sub.t], we will denote v(u, p) = [up.sup.n-1] [x.sup.[infinity]].

To see that W satisfies (i), we have to show that for any w [member of] W and any 1 [less than or equal to] i < j [less than or equal to] n, we have [w.sub.[i,[infinity])] [not equal to] [w.sub.[j,[infinity])]. This is clear because if x = 0 (resp. x = 1) both [w.sub.[i,[infinity])] and [w.sub.[j,[infinity])] end with [10.sup.[infinity]] (resp. [01.sup.[infinity])], with the last 1 (resp. 0) being in different positions in [w.sub.[i,[infinity])] and [w.sub.[j,[infinity])].

Now we prove that W satisfies (ii). Let u, u' be binary words of lengths n-t-1, n-t'-1, respectively, and let p, p' be primitive binary words of lengths t, t', respectively. Let w = v(u, p) and w' = v(u', p'), and let [pi] = Pat(w, [[summation].sub.2], n), [pi]' = Pat(w', [[summation].sub.2], n). We assume that w [not equal to] w', and want to show that [pi] = [pi]'. From w [not equal to] w' it follows that u [not equal to] u' or p [not equal to] p'.

Corollary 2.9 for N = 2 implies that if [w.sub.1][w.sub.2] ... [w.sub.n-1] [not equal to] [w'.sub.1][w'.sub.2] ... [w'.sub.n-1], then Pat(w, [[summation].sub.2], n) [not equal to] Pat(w', [[summation].sub.2], n). In particular, if t = t', then up [not equal to] u' p', so [pi] [not equal to] [pi]'.

We are left with the case that t [not equal to] t' and up = u' p' = [w.sub.1][w.sub.2] ... [w.sub.n-1]. Let us first assume that [w.sub.n-1] = 1 (and so [p.sub.t] = [p'.sub.t], = 1). By Lemma 4.1 with k = n - t, we have that [pi](n) = [pi](n - t) - 1, and similarly [pi]'(n) = [pi]'(n-t')-1. If we had that [pi] = [pi]', then [pi](n) = [pi]'(n) and so [pi](n-t) = [pi]'(n-t') = [pi] (n-t'). But t [not equal to] t', so this is a contradiction. In the case [w.sub.n-1] = 0, an analogous argument to the proof of Lemma 4.1 implies that [w.sub.[n-t,[infinity]] = [p.sup.n-1] [1.sup.[infinity]] < [p.sup.n-2] [1.sup.[infinity]] = [w.sub.[n,[infinity])] and there is no s such that [w.sub.[s,[infinity])] is strictly in between the two. Thus, [pi](n) = [pi](n - t) + 1, and similarly [pi]'(n) = [pi]'(n - t') + 1, so again [pi] [not equal to] [pi]'.

To see that W satisfies (iii) we use the construction from the proof of the upper bound in Theorem 2.1. Let [pi] [member of] [Allow.sub.n]([[summation].sub.2]). If [pi](n - 1) > [pi](n), let w = [w.sub.A]([pi]) = [up.sup.n-1] [0.sup.[infinity]]. By Lemma 2.4, [w.sub.n-1] = 1, so w [member of] W. Similarly, if [pi](n - 1) < [pi](n), let w = [w.sub.B]([pi]) = [up.sup.n-1] [1.sup.[infinity]]. Then [w.sub.n-1] = 0, so w [member of] W. In both cases, Pat(w, [[summaiton].sub.2], n) = [pi], so this construction is the inverse of the map w [??] Pat(w, [[summation].sub.2], n).

To prove (iv), observe that the union in the definition of W is a disjoint union. This is because the value of t determines the position of the last entry in w that is not equal to x. For fixed t, there are [2.sup.n-t-1] choices for u and [[psi].sub.2](t) choices for t, so the formula follows.

Example 3. For n = 4, we have
```W =  {00 0 0 0 [1.sup.[infinity]], 00 1 1 1 [0.sup.[infinity]], 01 0 0
0 [1.sup.[infinity]], 01 1 1 1 [0.sub.[infinity]], 10
0 0 0 [1.sub.[infinity]], 10 1 1 1 [0.sup.[infinity]],
11 0 0 0 [1.sub.[infinity]], 11 1 1 1
[0.sup.[infinity]], 0 01 01 01 [0.sup.[infinity]],
0 10 10 10 [1.sup.[infinity]], 1 01 01 01
[0.sup.[infinity]], 1 10 10 10 [1.sup.[infinity]],
001 001 001 [0.sup.[infinity]], 010 010 010 [1.sup.[infinity]],
011 011 011 [0.sup.[infinity]], 100 100 100
[1.sup.[infinity]], [101 101 101 [0.sup.[infinity]],
110 110 110 [1.sup.[infinity]]},
```

where each word is written as w = u p p p [x.sup.[infinity]]. The permutations corresponding to these words are
```[Allow.sub.4]([[summation].sub.2]) =  {1234, 1243, 3412, 1432, 4123,
2143, 4312, 4321,
1342, 1324, 4231,
4213,
2341, 2413, 2431, 3124,
3142, 3214}.
```

Theorem 4.2 can be generalized to find a formula for the numbers [a.sub.n,N], which count permutations that can be realized by the shift on N symbols but not by the shift on N - 1 symbols. The proof of the next result is more involved and is omitted here due to lack of space, but it can be found in (5).

Theorem 4.3 For any n, N [greater than or equal to] 2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

We finish with two curious conjectures that came up while studying forbidden patterns of shift systems. They are derived from experimental evidence, and it would be interesting to find combinatorial proofs.

For the first one, let [T.sup.0.sub.n] be the set of n-cycles where one entry has been replaced with 0. The set [T.sup.0.sub.n] is essentially the same as [T.sub.n], with the only difference that the * symbol in each element is replaced with a 0, so that it produces a descent if there is an entry to its left. We have checked this conjecture by computer for up to 9.

Conjecture 4.4 For any and any subset D [subset.bar] (1,2, ..., n - 1}, [absolute value of {[summation] [member of] [T.sup.0.sub.n] : D([summation]) = D}] = [absolute value of {[pi] [member of] [S.sub.n] : D([pi]) = D}].

In particular, the statistic des has the same distribution in [T.sup.0.sub.n] as in [S.sub.n], i.e,

[summation over ([summation] [member of] [T.sup.0.sub.n])] [x.sup.des([summation])+1] = [A.sub.n](x).

Our last conjecture concerns a divisibility property of the numbers an N which is not apparent from Theorem 4.3.

Conjecture 4.5 For every n, N [greater than or equal to] 3, [a.sub.n,N] is divisible by 6.

References

[1] J.M. Amigo, S. Elizalde and M. Kennel, Forbidden patterns and shift systems, J. Combin. Theory Ser. A 115 (2008), 485-504.

[2] J.M. Amigo, S. Elizalde and M. Kennel, Pattern avoidance in dynamical systems, Discrete Math. Theor. Comput. Sci. proc. AJ (2008), 71-82.

[3] J.M. Amigo, S. Zambrano and M.A.F. Sanjuan, True and false forbidden patterns in deterministic and random dynamics, Europhys. Lett. 79 (2007), 50001-p1, -p5.

[4] C. Bandt, G. Keller and B. Pompe, Entropy of interval maps via permutations, Nonlinearity 15 (2002), 1595-1602.

[5] S. Elizalde, The number of permutations realized by a shift, SIAM J. on Discrete Math, to appear.

[6] S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.

[7] I. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993), 189-215.

Sergi Elizalde

Department of Mathematics, Dartmouth College, Hanover, NH 03755-3551
```Tab. 1: The numbers [a.sub.n,N] = [absolute value of {[pi]
[member of] [S.sub.n] : N([pi]) = N}] for n [less than or
equal to] 8.

n\N      2       3       4        5       6       7

2        2
3        6
4       18       6
5       48      66       6
6      126     402     186        6
7      306    2028    2232      468       6
8      738    8790    19426   10212    1098        6
```