# Number of cycles in the graph of 312-avoiding permutations.

1 Introduction and preliminariesOne of the classical objects in combinatorics is the De Bruijn graph. This is the directed graph on vertex set [{0, 1, ..., q - 1}.sup.n], the set of all strings of length n over an alphabet of size q, whose directed edges go from each vertex [x.sub.1] ... [x.sub.n] to each vertex [x.sub.2] ... [x.sub.n+1]. That is, there is a directed edge from a string x to y if and only if the last n - 1 coordinates of x agree with the first n - 1 coordinates of y.

The De Bruijn graph has been much studied, especially in connection with combinatorics on words, and one of its well known properties is the fact that its number of directed cycles of length d, for d [less than or equal to] n, is given by

[1/d] [summation over ([epsilon]|d)] [mu] (d/e) [q.sup.[epsilon]], (i.i)

where the sum is over all divisors e of the length d, and where [mu] denotes the number theoretic Mobius function. Recall that [mu](n) is [(-1).sup.k] if n is a product of k distinct primes and is zero otherwise.

A natural variation on the De Bruijn graphs is obtained by replacing words over an alphabet by permutations of the set of integers {1, 2, ..., n}, where the overlapping condition determining directed edges in De Bruijn graphs is replaced by the condition that the head and tail of two permutations have the same standardization, that is, that their letters appear in the same order of size. As an example, this is the case with the permutations 24513 and 35124, since 4513 and 3512 both have their letters appearing in the same order of size, namely as 3412. This graph of overlapping permutations, denoted G(n), is what we study in this paper. Note that, apart from the path and cycle graphs mentioned in Section 3, all graphs in this paper are directed, although we don't explicitly refer to them as directed graphs.

The graph G(n) appeared in [4] in connection with universal cycles on permutations. It has also appeared in [7], where it was used as a tool in determining the asymptotic behavior of consecutive pattern avoidance, and in [2], where it is called the graph of overlapping patterns (see also [11, Section 5.6]).

A natural question about this graph, which does not seem to have been studied so far, is what its number of directed cycles is, the analogue to the question for which (1.1) is the answer. We have not been able to solve that problem (and we do not recognize the associated number sequences). We do here, however, solve that problem when the graph is restricted to permutations of length n avoiding the pattern 312, that is, permutations containing no three letters the first of which is the largest and the second one the smallest. We show here that the number of directed cycles of length d is

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

for d not exceeding n. Note the similarity between this and the expression in (1.1): the power [q.sup.[epsilon]] in (1.1) is replaced here by the central binomial coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is easy to see, due to straightforward symmetries, that permutations avoiding a particular one of the patterns 132, 213 and 231 yield a graph isomorphic to the one for 312, which is the representative we have chosen. It is also easy to see that permutations avoiding 123 (or, equivalently, 321) give rise to a nonisomorphic graph. For this latter case we have no solution for the number of cycles, and we do not recognize the number sequences counting the cycles in that graph.

Using similar techniques, we prove that the number of 312-avoiding affine permutations in [[??].sub.d] with k cut-points is given by the binomial coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This refines a result of Crites [6] who showed that the number of 312-avoiding affine permutations is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. As a corollary to our results we show that each affine permutation has a cut-point or is, in other words, decomposable.

The connection between cycles in the graph of overlapping permutations and affine permutations goes through bi-infinite sequences. A bi-infinite sequence (..., f (-1), f (0), f (1), f (2), ...) of distinct real numbers yields a bi-infinite walk where the ith edge is given by the standardization of f = (f (i),f (i + 1), ..., f (i + n)), that is, the unique permutation of {1, 2, ..., n + 1} whose letters appear in the same order of size as the numbers in f. This walk is a closed walk of length d if the sequence is periodic, in the sense that f (i) < f (j) if and only if f (i + d) < f (j + d). Thus, infinite d-periodic sequences correspond to d-cycles.

The paper is organized as follows. In Section 2 we introduce some definitions related to pattern avoidance, affine permutations and infinite sequences. The last of these play an important role in the proof of the main result, as do ordinary and cyclic compositions of an integer, which are introduced in Section 3. In Section 4 we give results on the number of affine 312-avoiding permutations with a given number of cut-points and show that every such permutation does have a cut-point. In Section 5 we present the main result, about the number of d-cycles in G(n, 312) and subsequently give a bijection that proves this, in Sections 6 and 7. The full version of the paper is available as [8], where we list several open problems in this area.

2 Pattern-avoiding permutations, affine permutations and infinite sequences

We first introduce some formal definitions that are needed later on.

For a permutation x = [x.sub.1] ... [x.sub.n] consisting of distinct real numbers, let [PI](x) denote the standardization of x, also known as the reduced form of x, that is, the unique permutation [pi] = [[pi].sub.1] ... [[pi].sub.n] in the symmetric group [G.sub.n] whose elements have the same relative order as those in x. In other words, [x.sub.i] < [x.sub.j] if and only if [[pi].sub.i] < [[pi].sub.j] for all 1 [less than or equal to] i < j [less than or equal to] n and [pi] is built on the set {1, 2, ..., n}. For example, [PI](3(-2)02) = 4123.

The graph of overlapping permutations G(n) has the elements of the symmetric group [G.sub.n] as its vertex set and for every permutation [sigma] = [[sigma].sub.1] ... [[sigma].sub.n+1] in [G.sub.n+1] there is a directed edge from [PI]([[sigma].sub.1] ... [[sigma].sub.n]) to [PI]([[sigma].sub.2] ... [[sigma].sub.n+1]).

A permutation [pi] = [[pi].sub.1][[pi].sub.2] ... [[pi].sub.n] [member of] [G.sub.n] avoids a permutation [tau] [member of] [G.sub.k] if there are no integers 1 [less than or equal to] [i.sub.1] < [i.sub.2] < ... < [i.sub.k] [less than or equal to] n such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In this context, t is called a pattern and we say that n avoids the pattern [tau]. Let [G.sub.n] ([tau]) denote the set of t-avoiding permutations in [G.sub.n]. Especially, we are interested in 312-avoiding permutations, which are those that have no indices i < j < k such that [[pi].sub.j] < [[pi].sub.k] < [[pi].sub.i]. It is well-known that the number of 312-avoiding permutations in [G.sub.n] is given by the nth Catalan number [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A cut-point for a permutation [pi] [member of] [G.sub.n] is an index j with 1 [less than or equal to] j [less than or equal to] n - 1 such that for all i and k satisfying 1 [less than or equal to] i [less than or equal to] j < k [less than or equal to] n we have that [[pi].sub.i] < [[pi].sub.k]. The cut-points split a permutation into components, each ending at a cut-point. A permutation without cut-points is said to be indecomposable (or, sometimes, irreducible). As an example, the permutation 31246758 has three cut-points, namely 3, 4, and 7, and components 312,4, 675 and 8, wheres 2413 is indecomposable. The following result is well-known (see, for instance, [5] or Stanley's list of Catalan interpretations [15]), and is easy to prove using the fact that every 312-avoiding permutation is of the form A1B, where each element of B is larger than every element of A, which implies that a 312-avoiding permutation is indecomposable precisely when B is empty.

Proposition 2.1 The number of 312-avoiding indecomposable permutations in [G.sub.n] is given by the Catalan number [C.sub.n-1].

An extension of the notion of permutations is affine permutations. While the symmetric group [G.sub.n] is the Weyl group [A.sub.d-1], the group of affine permutations [G.sub.d] is the affine Weyl group [[??].sub.d-1]. However, the combinatorial description of affine permutations is due to Lusztig (unpublished) and the first combinatorial study of them was conducted in [3, 9]. An affine permutation is a bijection [pi]: Z [right arrow] Z such that

[pi](i + d) = [pi](i) + d, (2.1)

[d-1.summation over (i=0)]([pi](i) - i) = 0. (2.2)

Note that the first condition implies that the values [pi](0) through [pi](d - 1) determine the whole affine permutation. The set of all affine permutations is denoted by [[??].sub.d].

We now extend the notion of an affine permutation to infinite sequences. An infinite sequence is defined to be an injective function f : Z [right arrow] R. Alternatively, one can think of an infinite sequence as a bi- infinite list (..., f (-1), f (0), f (1), f (2), ...) of distinct real numbers. We say that two infinite sequences f and g are equivalent if there is a strictly increasing continuous function T: R [right arrow] R such that g(i) = T (f (i)). It is straightforward that this is an equivalence relation. We think about the equivalence classes as bi-infinite permutations. Hence, it is natural to extend notions from permutation patterns theory to (bi-)infinite sequences.

A cut-point for a bi-infinite sequence f is an index j such that for all integers i [less than or equal to] j < k we have that f (i) < f (k). The inversion set for a bi-infinite sequence f is the set

Inv(f) = {(i, j) [member of] [Z.sup.2]: i < j, f (i) >f(j)}.

A bi-infinite sequence is periodic with period d, if for all integers i and j, f (i) < f (j) is equivalent to f (i + d) < f (j + d). Equivalently, a bi-infinite sequence is periodic with period d if the inversion set satisfies the condition (i, j) [member of] Inv(f) is equivalent to (i + d, j + d) [member of] Inv(f). Extending the notion of pattern-avoidance, we say that a bi-infinite sequence f avoids the pattern [sigma] [member of] [G.sub.n] if there are no integers [i.sub.1] < [i.sub.2] < ... < [i.sub.n] such that [PI](f ([i.sub.1])f ([i.sub.2]) ... f ([i.sub.n])) = [sigma].

3 Compositions and cyclic compositions

A composition of a non-negative integer d into k parts is a list of k positive integers ([a.sub.1], [a.sub.2], ..., [a.sub.k]) such that their sum is d. Let [[alpha].sub.1], [[alpha].sub.2], ... be a sequence of numbers and f (t) = [[summation].sub.i [greater than or equal to] 1] [[alpha].sub.i][t.sup.i] be the associated generating function. Form a new sequence [([[beta].sub.d,k]).sub.d [greater than or equal to] 1] by the relation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the sum is over all compositions of d into k parts. Additionally, we set [[beta].sub.0,k] to be the Kronecker delta [[delta].sub.0,k], which is equal to 1 if k = 0 and 0 otherwise. Also, let the sequence [([[beta].sup.d]).sub.d [greater than or equal to] 0] be defined by the sum [[beta].sub.d] = [[summation].sub.k [greater than or equal to] 0] [[beta].sub.d,k]. The following relations are classical generating functionology:

[summation over (d [greater than or equal to] 0)] [[beta].sub.d,k][t.sup.d] = [(f (t)).sup.k] and [summation over (d [greater than or equal to] 0)] [[beta].sub.d][t.sup.d] = [1/[1 - f(t)]]. (3.1)

If [[alpha].sub.i] is the cardinality of a set [S.sub.i], we can give a combinatorial interpretation to the number [[beta].sub.d,k], hence also [[beta].sub.d]. An enriched composition is a pair (a, s) where a is a composition ([a.sub.1], [a.sub.2], ..., [a.sub.k]) of d into k parts and s = ([s.sub.1], [s.sub.2], ..., [s.sub.k]) is a list of the same length such that the element s* belongs to the set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now [[beta].sub.d,k] is the number of enriched compositions of d into k parts, and [[beta].sub.d] is the number of enriched compositions of d.

A composition of d can be thought of as a subgraph of the path on d vertices. Note that each connected component of a subgraph of a path is also a path. The number of connected components of the subgraph is the number of parts of the composition. With this analogue in mind we define a cyclic composition to be a subgraph of the cycle on d vertices where each component is a path. Note that we rule out the case of the cycle being a subgraph of itself. Yet again, the number of paths is the number of components k. Observe that k is also the number of edges removed to obtain the subgraph. Since there are d edges in a cycle, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] cyclic compositions of d into k parts for k [greater than or equal to] 1. For instance, there are (2) = 6 cyclic compositions of 4 into two parts, namely, two consisting of two 2s and four consisting of 1 and 3.

To be more formal, let [Z.sub.d] denote both the integers modulo d and the cycle of length d, where we connect i and i + 1 modulo d. A cyclic composition is a set partition P = {[B.sub.1], [B.sub.2], ..., [B.sub.k]} where each block [B.sub.i] is a path in the cycle [Z.sub.d]. Equivalently, each block [B.sub.i] is the image of an interval [[p.sub.i]; [q.sub.i]] of integers under the quotient map Z [right arrow] [Z.sub.d] with the restriction 0 [less than or equal to] [q.sub.i] - - [p.sub.i] [less than or equal to] d - 1. Also, let [a.sub.i] be [q.sub.i] - [p.sub.i] + 1, that is, the cardinality of the interval [[p.sub.i], [q.sub.i]] and the associated path.

Similarly to compositions, we construct new sequences [([[gamma].sub.d,k]).sub.d [greater than or equal to] 1] and [([[gamma].sub.d]).sub.d [greater than or equal to] 1] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the sum is over all cyclic compositions P of d into k parts and [a.sub.i] is the size of the ith part. Also, let [[gamma].sub.d] denote the sum [[gamma].sub.d] = [[summation].sub.k [greater than or equal to] 1] [[gamma].sub.d,k].

Proposition 3.1 The generating functions for [[gamma].sub.d,k] and [[gamma].sub.d] are given by

[summation over (d [greater than or equal to] k)] [[gamma].sub.d,k][t.sup.d] = tf'(t)[(f (t)).sup.k-1] = [t/k] D [((f(t)).sup.k]) and (3.2)

[summation over (d [greater than or equal to] 1)] [[gamma].sub.d][t.sup.d] = tf'(t)/[1 - f(t)], (33)

where D is the differential operator with respect to t.

Proof: To observe the first relation, consider the component containing the vertex 1 of the cycle. Also, assume that this component has size i. Then there are i possibilities how to choose the component. This is encoded by the generating function [[summation].sub.i [greater than or equal to] 1] i[[alpha].sub.i][t.sup.i] = tf'(t). Next we have to choose a composition of d - i into k - 1 parts, which is given by [(f (t)).sup.k-1]. The first result follows from multiplication of generating functions. The second result follows from summing (3.2) over all k.

As a brief example of equation (3.3), note that setting [[alpha].sub.i] = 1 enumerates the number of cyclic compositions. We have f (t) = 1/(1 - t) - 1 and obtain [[summation].sub.d>1] [[gamma].sub.d][t.sup.d] = 1/(1 - 2t) - 1/(1 - t), yielding the answer of [2.sup.d] - 1 for the number of cyclic compositions of d.

Combining generating functions (3.1) and (3.2) we have the following result.

Corollary 3.2 The two quantities [[beta].sub.d,k] and [[gamma].sub.d,k] are related by

[[gamma].sup.d,k] = [d/k] [[beta].sub.d,k]. (3.4)

An enriched cyclic composition is a pair (P, s) where P is a cyclic composition {[B.sub.1], [B.sub.2], ..., [B.sub.k]} of d into k parts and s = ([s.sub.1], [s.sub.2], ..., [s.sub.k]) is a list of the length k such that the element s* belongs to the set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now [[gamma].sub.d,k] has the combinatorial interpretation as the number of enriched cyclic compositions of d into k parts, and [[beta].sub.d] is the number of enriched cyclic compositions of d.

Let C(t) and CB(t) denote the generating functions for the Catalan numbers and the central binomial coefficients, that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 3.3 Let [[alpha].sub.i] = [C.sub.i-1] + [[delta].sub.i,1] where [[delta].sub.i,1] denotes the Kronecker delta. Then the central binomial coefficient is given by the sum

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

where the sum is over all cyclic compositions P of d and d [greater than or equal to] 1.

Proof: First, observe that [[summation].sub.i [greater than or equal to] 1] [[alpha].sub.i][t.sup.i] = t + tC(t). The result now follows from equation (3.3) and the identity

CB(t) - 1 = t(t + tC(t))'/[1 - t - tC(t)].

The following two well-known identities involving the Catalan numbers are worth keeping in mind in the next section, where we prove similar results regarding affine 312-avoiding permutations. We have

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

where the sum is over all compositions of d into k parts. The numbers in the right hand side give Catalan's triangle, sequence A009766 in [12]. One of many things they enumerate is the set of 312-avoiding permutations of length d that split into (at most) k components. Namely, such a permutation can be decomposed as [A.sub.1] [A.sub.2] ... [A.sub.k] where every letter of [A.sub.i] is smaller than each letter of [A.sub.j] for i < j. Since each component is an indecomposable 312-avoiding permutation, these permutations with k components are counted by the left hand side. By a similar argument we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the sum is over all compositions of d.

By combining Corollary 3.2 and (3.5) we have:

Lemma 3.4 The following identity holds

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

where the sum is over all cyclic compositions P of d into k parts.

4 312-avoiding affine permutations

Before we continue, we take a detour to study 312-avoiding affine permutations. Recall that an affine permutation [pi] [member of] [[??].sub.d] is 312-avoiding if there are no indices x < y < z such that [pi](y) < [pi](z) < [pi](x). Crites [6] proved the following result for affine permutations.

Theorem 4.1 (Theorem 6 in [6]) The number of 312-avoiding affine permutations in [[??].sub.d] is given by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We give a refinement of this result. Recall that a cut-point for an affine permutation [pi] is an index j such that for i [less than or equal to] j < k the inequality [pi](i) < [pi](k) holds. Especially, if j is a cut-point, then so is any index congruent to j modulo d. Hence, we count the number of equivalence classes of cut-points.

Theorem 4.2 ([8]) Let k be a positive integer and k [less than or equal to] d. The number of 312-avoiding affine permutations in [[??].sub.d] that have k cut-points modulo d is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 4.3 Every 312-avoiding affine permutation in [[??].sub.d] has a cut-point.

Proof: Since the sum of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for k from 1 to d is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and by Theorem 4.1, all the 312-avoiding affine permutations have been accounted for.

5 The graph of 312-avoiding permutations

Recall that G(n) denotes the directed graph of overlapping permutations, that is, it has the vertex set [[??].sub.m] and for every permutation [sigma] = [[sigma].sub.1] ... [[sigma].sub.m+1] in [G.sub.m+1] there is a directed edge from [PI]([[sigma].sub.1] ... [[sigma].sub.m]) to [PI]([[sigma].sub.2] ... [[sigma].sub.m+1]) labelled [sigma]. Furthermore, let G(n, [tau]) be the graph of overlapping t-avoiding permutations, that is, it is the subgraph of G(n) having the vertex set [G.sub.n]([tau]) and the edge set [G.sub.n+1](t).

A closed walk of length d in a graph is a list of d edges ([e.sub.1], [e.sub.2], ..., [e.sub.d]) such that head([e.sub.i]) = tail([e.sub.i+1]) for 1 [less than or equal to] i [less than or equal to] d - 1 and head([e.sub.d]) = tail([e.sub.1]), where for a directed edge e, head(e) is the node the edge points to, while tail(e) is the other node incident to e. Thus, (1342,2314, 2134) and its cyclic shift (2134,1342, 2314) are two different closed walks.

Define an equivalence on the set of closed walks by cyclic shifting, that is, the two closed walks ([e.sub.1], [e.sub.2], ..., [e.sub.d]) and ([e.sub.i], [e.sub.i+1], ..., [e.sub.d], [e.sub.1], [e.sub.2], ..., [e.sub.i-1]) are equivalent for any i. Then a d-cycle is defined to be an equivalence class of size d. For instance, the graph G(3,312) has six closed walks of length 2, namely,

(1234, 1234), (4321, 4321), (1324, 2143), (2143, 1324), (2314, 3241) and (3241, 2314).

However, the graph G(3,312) has only two 2-cycles, since the first two closed walks yield 1-cycles while the forth (resp., sixth) walk is equivalent to the third (resp., fifth) walk.

The number of closed walks is given by the following result.

Theorem 5.1 The number of closed walks of length d in G(n, 312), for d [less than or equal to] n, is given by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A bijective proof of Theorem 5.1 will be given in the following two sections.

Theorem 5.2 The number of d-cycles in G(n, 312), for d [less than or equal to] n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Let h(d) denote the number of d-cycles. A closed walk of length d can be obtained by choosing a divisor e of d, an e-cycle and a starting point on the cycle. By repeating the e-cycle d/e times we obtain a closed walk of length d. Hence, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The result now follows by classical Mobius inversion.

6 The bijection

It remains to show that the number of closed walks of length d in G(n, 312) is given by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We do this by constructing a bijection between closed walks and enriched cyclic compositions. This bijection goes via infinite sequences. Let [Q.sub.d] denote the set of all closed walks of length d in the graph G(n, 312).

Given a cyclic composition on [Z.sub.d], we enrich each part of size a either with a 312-avoiding indecomposable permutation from the symmetric group [G.sub.a], or, if a = 1, with the symbol D (for "Down"). Note that if a = 1, then the enrichment is either the identity permutation 1 in [G.sub.1] or the symbol D. Let [E.sub.d] denote the set of all these enriched cyclic compositions. Note that the number of enrichments of a part of size a is the Catalan number [C.sub.a-1] plus the Kronecker delta [[delta].sub.a,1]. Hence, by Lemma 3.3, we know that the total number of these structures is the central binomial coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We now describe a bijection [PHI]: [E.sub.d] [right arrow] [Q.sub.d]. Let B = ([B.sub.1], [B.sub.2], ..., [B.sub.k]) be an enriched cyclic composition in [E.sub.d]. Recall that the ith block [B.sub.i] is the image of the interval [[p.sub.i], [q.sub.i]] under the quotient map Z [right arrow] [Z.sub.d]. If the enrichment on the part [B.sub.i] is a permutation, we view it as a permutation [[pi].sub.i] on the set [[p.sub.i], [q.sub.i]]. Let [[bar.B].sub.i] be the set [[bar.B].sub.i] = [U.sub.j[member of]z] [[p.sub.i] + jd, [q.sub.i] + jd]. Note that [bar.[B.sub.1]], [bar.[B.sub.2]], ..., [bar.[B.sub.k]] is a partition of the integers Z. Furthermore, extend n* by the relation [[pi].sub.i] (j + d) = [[pi].sub.i] (j) + d. That is, now [[pi].sub.i] is a bijection on the set [bar.[B.sub.i]]. Next we use the fact that the exponential function exp: R [right arrow] [R.sub.>0] is strictly increasing and its negative - exp: R [right arrow] [R.sub.<0] is strictly decreasing, where [R.sub.>0] (resp., [R.sub.<0]) is the set of all possible (resp., negative) real numbers. Construct an infinite sequence f by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By construction, the infinite sequence f is d-periodic. Furthermore, we claim that f is 312-avoiding. Assume not, that is, there are three integers x < y < z such that f (y) < f (z) < f (x). If f (y) < 0 then so is f (z). But the negative values of f form a decreasing sequence, since this is a subsequence of -exp(j). This contradicts f (y) < f (z). Now assume that f (y) > 0. Since f (x) > f (y), x has to belong to the same interval [B.sub.i] + j x d as y. Similarly, since f (x) > f (z), z has to belong to the same interval [B.sub.i] + j x d as x. This contradicts to the fact that the block [B.sub.i] was enriched with a 312-avoiding permutation.

Finally, we construct an infinite walk (..., [[sigma].sub.-1], [[sigma].sub.0], [[sigma].sub.1], [[sigma].sub.2], ...) in the graph G(n, 312) by letting [[sigma].sub.i] be the standardization [PI](f (i), f (i + 1), ..., f (i + n)). Note that this permutation is 312-avoiding and as an edge in the graph it has the tail [PI](f (i), f (i + 1), ..., f (i + n - 1)) and the head n(f (i + 1), f (i + 2), ..., f (i + n)). Since f is d-periodic the infinite walk has period d. Restricting the walk to ([[sigma].sub.1], [[sigma].sub.2], ..., [[sigma].sub.d]) gives a closed walk in the set [[sigma].sub.d]. This completes the description of the map [PHI].

One can always lift an infinite walk in the graph to an infinite sequence. However, as Remark 6.1 shows, an infinite walk could lift to several non-equivalent sequences, and they do not all have the desired properties. Thus, when lifting a walk to a sequence we have the additional requirements in Conditions (7.1) and (7.2). Their interpretation is that we do not introduce an inversion in the infinite sequence, unless we are required to do so by a local condition.

Remark 6.1 Consider the two infinite sequences

[h.sub.1](n) = n + [(-1).sup.n] and [h.sub.2](n) = n + 2[(-1).sup.n].

Observe that they both encode the same 2-cycle in G(2,312). That is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

However, note that [h.sub.2] is not 312-avoiding, whereas [h.sub.1] is. Furthermore, [h.sub.2] does not have any cut- points, whereas [h.sub.1] does. Hence, when constructing the inverse map to [PHI] we have to be careful in constructing an infinite sequence which is 312-avoiding. This is the reason for the appearance of the two conditions (7.1) and (7.2) in the next section.

7 The inverse bijection

We now construct the inverse map of [PHI]. Given the closed walk ([[sigma].sub.1], [[sigma].sub.2], ..., [[sigma].sub.d]) in [Q.sub.d] we extend it to an infinite walk by letting [[sigma].sub.j+d] = [[sigma].sub.j] for all integers j.

We are going to find a sequence ..., g(-1), g(0), g(1), g(2), ... such that [PI](g(i), g(i + 1), ..., g(i + n)) = [[sigma].sub.i] for all integers i. To find such a sequence, let g(k) = [[sigma].sub.1](k) for 1 [less than or equal to] k [less than or equal to] n + 1. Now alternate the following two steps to extend g to all of the integers.

(+) Assume that we have picked the values g(i), g(i + 1), ..., g(j - 1) of the sequence. We will now pick the value of g(j). That is, we are extending the sequence in the positive direction. Let [sigma] be the permutation [[sigma].sub.i-n]. Let a and b be the real numbers (including [+ or -][infinity]) given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where s is the shift s = j - n - 1. Then any real number x in the open interval (a, b) satisfies [PI](g(j - n), ..., g(j - 1), x) = [sigma]. However, we have one more requirement, we will pick x as large as possible with respect to the already picked values g(i), g(i + 1), ..., g(j - n - 1). That is, we pick g(j) = x such that

max(a, {g(k): g(k) < b, i [less than or equal to] k [less than or equal to] j - 1}) < x < b. (7.1)

(-) Now we extend the sequence in the negative direction. Assume that we have picked the values g(i + 1), g(i + 2), ..., g(j) of the sequence. We will now pick the value of g(i). Let [sigma] now denote the permutation [[sigma].sub.i]. Let the two bounds a and b be given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where s = i - 1. Yet again, any real number x in the open interval (a, b) satisfies [PI](x, g(i + 1), ..., g(i + n)) = [sigma]. However, now we pick x as small as possible with the already picked values g(i + 1), ..., g(j). That is, we pick g(i) = x such that

a < x < min(b, {g(k): g(k) > a, i + 1 [less than or equal to] k [less than or equal to] j}) (7.2)

The purpose of the two conditions (7.1) and (7.2) is to avoid introducing any extra inversions in the sequence g. These conditions will come into play at the end of this construction in the case when the set D (to be defined soon) is empty.

Claim 7.1 The sequence g is locally 312-avoiding, that is, if i < j < k, where k - i [less than or equal to] n then [PI](g(i), g(j), g(k)) [not equal to] 312.

This holds true since [[sigma].sub.i] is 312-avoiding.

Claim 7.2 For all i we have g(i) [not equal to] g(i + d).

Since d [less than or equal to] n and n(g(i), g(i + 1), ..., g(i + d), ..., g(i + n)) is a permutation, g(i) and g(i + d) are distinct.

Claim 7.3 For i < j and j - i < n the inequality g(i) < g(j) is equivalent to g(i + d) < g(j + d).

Since [[sigma].sub.i] = [[sigma].sub.i+d] we have the string of the equivalences g(i) < g(j) [??] [[sigma].sub.i](1) < [[sigma].sub.i] (j - i + 1) [??] [[sigma].sub.i+d] (1) < [[sigma].sub.i+d] (j - i +1) [??] g(i + d) < g(j + d).

Hence, the infinite sequence g decomposes into d sequences, each of which is monotone. We now partition the integers Z into two sets D = {i: g(i) > g(i + d)} and U = {i: g(i) < g(i + d)}. Note that since d [less than or equal to] n we have that i [member of] D is equivalent to i + d [member of] D. That is, D consists of the sequences that are decreasing and U of the increasing sequences.

Claim 7.4 The subsequence [{g(i)}.sub.i[member of]d] is decreasing.

Assume that it is not decreasing. Then there are two entries i, j [member of] D such that i < j, j - i [less than or equal to] d - 1 and g(i) < g(j). Also, we have that g(j - d) > g(j). Combining the last two inequalities we have that [PI](g(j - d), g(i), g(j)) = 312, contradicting that the sequence is not decreasing.

Claim 7.5 The values of the sequence [{g(i)}.sub.i[member of]D] are all smaller than the values of [{g(j)}.sub.j[member of]U].

We begin when i and j are close to each other, that is, when i < j < i + d, i [member of] D and j [member of] U. Assume that g(i) > g(j). Then we have the string of inequalities g(i - d) > g(i) > g(j) > g(j - d) implying that n(g(i - d), g(j - d), g(i)) = 312, a contradiction. Hence, we conclude that g(i) < g(j). Now pick i' [member of] D and j' [member of] U. If i' < j' let i = i' and j = j' - d x [(j' - i')/d] .If i' > j' let i = i' - d x [(i' - j')/d] and j = j'. (Here [*] and [*] are the usual floor and ceiling functions.) In both cases we have i [member of] D, j [member of] U and i < j < i + d. Furthermore, we have that g(i') [less than or equal to] g(i) < g(j) [less than or equal to] g(j'), proving the claim.

Now assume that D is non-empty. The case when D is empty requires an extra argument, which we postpone to the end of this section. Pick [p.sub.1] to be an element in the set D. Decompose the interval [[p.sub.1], [p.sub.1] + d - 1] of cardinality d into smaller intervals, according to the rules:

(d) If i [member of] D [intersection] [[p.sub.1], [p.sub.1] + d - 1] then let the singleton {i} = [i, i] be an interval in the decomposition. Moreover, enrich this singleton with the symbol D.

(u) If i [less than or equal to] j, i - 1, j + 1 [member of] D and [i, j] [subset] U [intersection] [[p.sub.1], [p.sub.1] + d - 1] then we use the argument at the end of Section 3 to decompose the interval [i, j] into smaller intervals, each enriched with an indecomposable 312-avoiding permutation. That is, we use the permutation [pi](g(i), g(i + 1), ..., g(j)) to decompose the interval.

Let the decomposition of the interval [[p.sub.1], [p.sub.1] + d - 1] be {[[p.sub.1], [q.sub.1]], [[p.sub.2], [q.sub.2]], ..., [[p.sub.l], [q.sub.l]]}, where [q.sub.i] + 1 = [p.sub.i+1]. Extend this decomposition to a decomposition [{[[p.sub.i], [q.sub.i]]}.sub.i[member of]Z] of the integers Z by letting [p.sub.i+l] = [p.sub.i] + d and [q.sub.i+l] = [q.sub.i] + d. Note that under the quotient map Z [right arrow] [Z.sub.d] we obtain a cyclic composition.

Claim 7.6 If the intervals [[p.sub.i], [q.sub.i]] and [[p.sub.k], [q.sub.k]] are not enriched with the symbol D, i < k, x [member of] [[p.sub.i], [q.sub.i]] and z [member of] [[p.sub.k], [q.sub.k]] then we have g(x) < g(z).

First assume that z - x [less than or equal to] d. If there is no interval [[p.sub.j], [q.sub.j]] between these two intervals (i < j < k) which is enriched with the symbol D then the inequality follows by the decomposition into indecomposable permutations in part (u) above. If there is an interval [[p.sub.j], [q.sub.j]] in between which is enriched with the symbol D, then consider the pattern [PI](g(x), g([p.sub.j]), g(z)). Since [[p.sub.j], [q.sub.j]] is enriched by D we have that g([p.sub.j]) < g(x) and g([p.sub.j]) < g(z). Hence, if g(x) > g(z), we obtain the pattern 312, a contradiction. Finally, if z - x > d, we obtain the inequality by using that U consists of the increasing sequences.

The last claim states that we do not lose information if we view the permutation enriching the interval [[p.sub.i], [q.sub.i]] as a bijection on this interval. The resulting composition, viewed as a cyclic composition with its enrichment, is the inverse image of the map [PHI].

When the set D is empty, we need to be more careful to show that the sequence g has a cut-point. We will use an argument similar to that in the second proof of Corollary 4.3. However, there is an added complication since all we know is that g is locally 312-avoiding. By condition (7.1) we have the following lemma.

Lemma 7.7 Assume that j < k and g(j) > g(k). Then there is a chain j = [j.sub.0] < [j.sub.1] < ... < [j.sub.l] = k such that g([j.sub.0]) > g([j.sub.1]) > ... > g([j.sub.l]) and [j.sub.h+1] - [j.sub.h] [less than or equal to] n for all indices h.

Proof: When we selected the value of g([j.sub.l]), we picked this value in an interval (a, b) where b was one of the values from the list g([j.sub.l] - n), ..., g([j.sub.l] - 2), g([j.sub.l] - 1). Hence, let [j.sub.l-1] be the index such that g([j.sub.l-1]) = b.

Assume that g(j) < g([j.sub.l-1]). Condition (7.1) states that we picked g([j.sub.l]) as large as possible in the interval (a, b). Hence, the assumption g(j) < g([j.sub.l-1]) implies that g(j) < g([j.sub.l]), a contradiction. We conclude that g(j) > g([j.sub.l-1]). By iterating this argument we obtain the chain.

Let P be the poset {(i, g(i)): i [member of] Z} with the order defined by (x, y) [less than or equal to] P (z, w) if x [greater than or equal to] z and y [less than or equal to] w. Let (i, g(i)) be a minimal element in this poset and let (j, g(j)) be an element larger than or equal to the minimal element (i, g(i)) maximizing the second coordinate. Observe that i - j [less than or equal to] d. The local 312-avoidance condition implies that the poset order between (i, g(i)) and (j, g(j)) is a chain. That is, we have the string of inequalities g(j) > g(j + 1) > ... > g(i - 1) > g(i).

The remaining case is to show that there is no index k such that i < k and g(i) < g(k) < g(j). First pick j' in the interval [j, i - 1] such that g(j' + 1) < g(k) < g(j'). Next use Lemma 7.7 to pick the first element of the chain [j'.sub.1] such that j' < [j'.sub.1] [less than or equal to] j' + n and g(j' + 1) < g([j'.sub.1]) < g(j'). However, this is a 312-pattern, contradicting the assumption that there is such a k. Hence, we conclude that the sequence g has a cut-point.

Let the cut-point be [p.sub.1] - 1. Consider the composition of the interval [[p.sub.1], [p.sub.1] + d - 1] consisting of one part. That is, this part is the interval [[p.sub.1], [p.sub.1] + d - 1]. Now, in a way similar to part (u) above, we decompose this interval into smaller intervals, each enriched with an indecomposable 312-avoiding permutations using the permutation [PI](g([p.sub.1]), g([p.sub.1] + 1), ..., g([p.sub.1] + d - 1)). This completes the inverse of [PHI] in the case when the set D is empty.

References

[1] T. VAN AARDENNE-EHRENFEST AND N. G. DE BRUIJN, Circuits and trees in oriented linear graphs, Simon Stevin, 28 (1951), 203-217.

[2] S. AVGUSTINOVICH AND S. KITAEV, On uniquely k-determined permutations, Discrete Math., 308 (2008), 1500-1507.

[3] A. BJORNER AND F. BRENTI, Affine Permutations of Type A, Electron. J. Combin., 3 (1996), R18.

[4] F. R. K. CHUNG, P. DIACONIS AND R. GRAHAM, Universal cycles for combinatorial structures, Discrete Math., 110 (1992), 43-59.

[5] A. CLAESSON AND S. KITAEV, Classification of bijections between 321- and 132-avoiding permutations, Sem. Lothar Combin., 60 (2008/09), Art. B60d, 30pp.

[6] A. CRITES, Enumerating pattern avoidance for affine permutations, Elec. J. Comb., 17 (2010), R127.

[7] R. EHRENBORG, S. KITAEV AND P. PERRY, A spectral approach to consecutive pattern-avoiding permutations, J. Comb., 2 (2011), 305-353.

[8] R. EHRENBORG, S. KITAEV AND E. STEINGRIMSSON, Number of cycles in the graph of 312-avoiding permutations, arXiv:1310.1520.

[9] R. EHRENBORG AND M. READDY, Juggling and applications to q-analogues, Discrete Math., 157 (1996), 107-125.

[10] C. FLYE SAINT-MARIE, Solution to question 48, l'Intermediare des Mathematiciens, 1 (1894), 107-110.

[11] S. KITAEV, "Patterns in Permutations and Words," Monographs in TCS, Springer, Heidelberg, 2011.

[12] OEIS Foundation Inc. (2011), The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[13] Y. PURI AND T. WARD, A dynamical property unique to the Lucas sequence, Fibonacci Quart., 39 (2001), 398-402.

[14] Y. PURI AND T. WARD, Arithmetic and growth of periodic orbits, J. Integer Seqs., 4 (2001), #01.2.1.

[15] R. P. STANLEY, Catalan addendum, http://www-math.mit.edu/~rstan/ec/.

Richard Ehrenborg (1) * Sergey Kitaev (2) ([dagger]) Einar Steingrimsson (2) ([double dagger])

(1) Department of Mathematics, University of Kentucky, Lexington, KY 40506-0027, USA

(2) Department of Computer and Information Sciences, University of Strathclyde, Glasgow G1 1XH, UK

* Email: jrge@ms.uky.edu. Partially supported by National Science Foundation grant DMS 0902063 and National Security Agency grant H98230-13-1-0280.

([dagger]) Email: sergey.kitaev@cis.strath.ac.uk.

([double dagger]) Email: einar@alum.mit.edu. Supported by grant no. 090038013 from the Icelandic Research Fund.

Printer friendly Cite/link Email Feedback | |

Author: | Ehrenborg, Richard; Kitaev, Sergey; Steingrimsson, Einar |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 7373 |

Previous Article: | An equivariant rim hook rule for quantum cohomology of Grassmannians. |

Next Article: | Splines, lattice points, and (arithmetic) matroids. |

Topics: |