Printer Friendly

Adjacent transformations in permutations.

1 Introduction

In [LPRW10], the authors consider the equivalence class induced on [S.sub.n] when one is permitted to replace a consecutive set of elements in a permutation with the same elements in a different order, where the sequence removed and the sequence replacing it must each match as a pattern any sequence in a given replacement set, which is a subset of some [S.sub.k]. Here match as a pattern means to have all the same order relations. For instance, if the given replacement set is {123,132}, then 12453 is equivalent to 14235, because we can perform the replacement 12453 [right arrow] 14253 followed by 14253 [right arrow] 14235.

We write #Classes(n; {A}) to denote the number of equivalence classes into which [S.sub.n] is divided by the replacement set A. We use [C.sub.n](A) to denote the equivalence class of the identity, and [c.sub.n](A) its size.

In [LPRW10], the authors restricted their attention to replacement sets selected from [S.sub.3], in which each replacement can be viewed as fixing one of the three elements and exchanging the other two. We look at sets of patterns, such as {123, 231}, which do not meet this condition, and were therefore excluded from their paper. We focus on the characterization and enumeration of the class containing the identity permutation, and indeed with our new results we now know the enumeration of this class in all cases.

One of the earliest references for transformations in permutations is in Knuth's Art of Computer Programming [Knu73] where we find the idea of sorting a permutation by passage through a stack, illustrated by a chain of railway wagons which can be interchanged by the instrument of a spur of track.

Because in the present case we are almost always concerned with the question of whether or not a given permutation can be restored to the identity, it is perhaps not too fanciful to imagine a similar context, where we are examining whether a permutation can be sorted, with some local (mechanical or logical) circuits but under global control.

We have divided our paper into sections based on the number of patterns contained in the replacement set, and in an appendix we give a summary table of [c.sub.n](A) for all replacement sets A, both those enumerated in the present work, and those known previously.

Two operations familiar from the literature of permutation patterns, reversal and complementation, have a natural role in this context. It is clear that two permutations are equivalent with respect to a given replacement set if and only if their reversals (complements) are equivalent with respect to the reversal (complement) of the replacement set. Thus a result cited in the summary table may actually be the reversal (R), or reverse complement (RC), of another entry. In particular, since 123 is its own reverse complement, one can always try applying reverse-complementation to one class containing 123 to obtain another one.

2 Replacement sets of size 2

2.1 123 [left and right arrow] 231

Definition 2.1 Let [sigma] = [[sigma].sub.1] ... [[sigma].sub.n] be a permutation, a satisfies the position parity condition if for all i [member of] {1 ... n}, then, taking the set {[[sigma].sub.1] ... [[sigma].sub.4]} in increasing order, the rank of [[sigma].sub.i] is congruent to i (mod 2).

Example 2.1 The permutation [sigma] = 45123 satisfies position parity, because [[sigma].sub.1] = 4 is the smallest element of {4}, [[sigma].sub.2] = 5 is the 2nd-smallest element of {4, 5}, [[sigma].sub.3] = 1 is the smallest element of {4, 5, 1}, [[sigma].sub.4] = 2 is the 2nd-smallest element of {4, 5, 1, 2} and [[sigma].sub.5] = 3 is the 3rd-smallest element of {4,5,1, 2,3}. The permutation 4612375 also satisfies position parity, but 21 does not.

Proposition 2.1 Let [sigma] [member of] [S.sub.n]. Then [sigma] [member of] [C.sub.n](123, 231) if and only if it satisfies position parity. Moreover it is possible to step from the identity permutation to a using only steps of form 123 [left and right arrow] 231.

Proof: Let [sigma] = [[sigma].sub.1] ... [[sigma].sub.n] be a permutation satisfying position parity. To obtain [sigma] from the identity, begin by placing the rightmost element, [[sigma].sub.n]. By position parity, [[sigma].sub.n] must have the same parity as n, and since it occupies position [[sigma].sub.n] in the identity, it needs to move an even number of positions, n - [[sigma].sub.n]. We move it forward two steps at a time, using only moves 123 [right arrow] 231 (where [[sigma].sub.n] plays the role of 1), which we can do because the identity permutation has all its elements in increasing order. We call the permutation which results [[sigma].sup.(n)]; the element in position n is the correctly-placed [[sigma].sub.n], and the elements in the other n - 1 positions are in increasing order.

Now do the same thing to place [[sigma].sub.n-1] in position n - 1, obtaining a permutation [[sigma].sup.(n-1)], and in general at step k a permutation [[sigma].sup.(n-k+1)], in which the final k elements are correctly placed, and the first n - k elements are in increasing order, from which it follows that the next element to be placed, [[sigma].sub.n-k], occupies the position corresponding to its rank in the set {[[sigma].sub.1] ... [[sigma].sub.n-k]} written in increasing order. So it has to move an even number of positions and we place it with moves 123 [right arrow] 231. At the nth step, we have obtained the permutation [sigma] = [[sigma].sup.(0)].

Conversely, let [sigma] [member of] [C.sub.n](123, 231). A case study proves that position parity is kept under the transformations 123 [left and right arrow] 231. As a can be reached from the identity which has position parity this concludes the proof.

Remark 2.1 Let [sigma] [member of] [C.sub.n](123, 231), then the proof gives us a canonical path to obtain a from the identity, using only steps of form 123 [left and right arrow] 231: we start by placing [[sigma].sub.n], then [[sigma].sub.n-1], etc.

Corollary 2.1 The number of permutations in the equivalence class of the identity on n elements is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (n terms).

Proof: We will place elements from right to left. Let [sigma] [member of] [C.sub.n](123, 231), then the rank of an in {[[sigma].sub.1] ... [[sigma].sub.n]} is of the same parity as n, which gives [??]n/2[??] choices for [[sigma].sub.n], [??]n-1/2[??] choices for [[sigma].sub.n-1], and so forth.

3 Replacement sets of size 3

3.1 123 [left and right arrow] 213 [left and right arrow] 231

We will characterize and enumerate [C.sub.n](123, 213, 231) in Proposition 3.1 and Corollary 3.1. We will first need the following two lemmas.

Lemma 3.1 Let [sigma] be a permutation of size n such that n is immediately to the right of n - 1. Then a can be obtained from the identity using transformations 123 [left and right arrow] 213 [left and right arrow] 231.

Proof: Let [tau] be the pattern obtained by deleting n - 1 and n from [sigma]. We will first construct [tau](n - 1)n, then position n - 1 and n appropriately. Because (n - 1) and n are the two largest elements in the permutation, they can always be moved together as far as desired to the left using 123 [right arrow] 231, or to the right using 231 [right arrow] 123, as long as they remain together.

So, beginning with the identity permutation, first advance (n - 1) and n so that they are just to the right of [[tau].sub.1]. Now, letting n - 1 play the role of 3, and using either 123 [right arrow] 213 or 213 [right arrow] 123 as appropriate, [[tau].sub.1] can be moved one position to the left (if it is not already at the leftmost position). And (n - 1) and n can then be repositioned so that they remain just to its right. Repeat until t1 is in the leftmost position.

Now reposition (n - 1) and n just to the right or [[tau].sub.2] and, as before, advance [[tau].sub.2] to where it belongs, in the second position. Continue until we have built up [tau](n - 1)n, one element at a time. Since (n - 1) and n remain free to move as a block, advance them as necessary to obtain the permutation [sigma].

Lemma 3.2 Given a permutation [alpha]ijk[sigma][gamma] such that the elements of [sigma] are all less than k and k < i < j, it is possible to move to any permutation [alpha]i[sigma]'kjl[sigma]"[gamma] using transformations 123 [left and right arrow] 213 [left and right arrow] 231, where [sigma] = [sigma]' [union] [sigma] [union]{l} and l = max [sigma] - [sigma]'.

Proof: We begin by applying 231 [right arrow] 213 to ijk to obtain [alpha]ikj[sigma][gamma]. Now, if kj[sigma] is considered as a permutation having n elements, k and j represent the largest elements, n - 1 and n. But Lemma 3.1 says that any permutation having n immediately following n - 1 is equivalent to any other, and we can therefore obtain [sigma]'kjl[sigma]" from kj[sigma], and therefore [alpha]i[sigma]'kjl[sigma]"[gamma] from [alpha]ikj[sigma][gamma].

Proposition 3.1 Let [sigma] be a permutation of size n. Then [sigma] [member of] [C.sub.n](123, 213, 231) if and only if n - 1 is to the left of n in [sigma].

Proof: Since n - 1 is to the left of n in the identity, and since in each of the patterns 123, 213, and 231, the relative order of the two largest elements is preserved, then n - 1 must remain to the left of n.

Now suppose that [sigma] is of size n and has n - 1 to the left of n. We will show that [sigma] can be reached from the identity. If n - 1 is immediately to the left of n, we have the result by Lemma 3.1. If not, decompose [sigma] as [alpha](n - 1)[beta]n[gamma]. By Lemma 3.1, we can reach [alpha](n - 1)nk[beta]'[gamma], where k = max[beta] and [beta]' = [beta] - {k}.

Now, to obtain [sigma], we proceed by induction on the number of right-to-left maxima of [beta], using Lemma 3.2. Let [k.sub.1], [k.sub.2] ... be the right-to-left maxima of [beta], such that [beta] = [[beta].sup.(1)][k.sub.1][[beta].sup.(2)][k.sub.2] ... and set [[beta].sup.(-i)] = [[beta].sup.(i)] [[beta].sup.(i+1)] [k.sub.i+1].... Then we have [alpha] (n - 1) nk[beta]'[gamma] = [alpha] (n - 1) n [k.sub.1] [[beta].sup.(-1)][gamma]. By Lemma 3.2, from [alpha] (n - 1) n [k.sub.1] [[beta].sup.(-1)] [gamma] we can reach [alpha] (n - 1) [[beta].sup.(1)] [k.sub.1] n [k.sub.2] [[beta].sup.(-2)] [gamma]. Setting [alpha]' = [alpha] (n -1) [[beta].sup.(1)] we can apply again Lemma 3.2 to reach [alpha] (n - 1) [[beta].sup.(1)] [k.sub.1] [[beta].sup.(2)] [k.sub.2] n [k.sub.3] [[beta].sup.(-3)] [gamma], and so we can reach [alpha] by applying Lemma 3.2 as many times as there are right-to-left maxima in [beta].

Corollary 3.1 The number of permutations of size n equivalent to the identity is [c.sub.n](123, 213, 231) = n!/2.

3.2 123 [left and right arrow] 132 [left and right arrow] 231

Proposition 3.2 Let [sigma] be a permutation of size n. Then [sigma] [member of] [C.sub.n](123,132, 231) if and only if the left-to-right minima of [sigma] are all in odd positions.

Proof: The identity has only one left-to-right minimum, namely in position 1, which is an odd position. Now consider applying the permitted transfomations to a permutation. A move 123 [right arrow] 132 neither adds nor removes a left-to-right minimum. However, a move 123 [right arrow] 231 may either displace a left-to-right minimum or create a new one, but in either case does so two places to the right of an existing left-to-right minimum (and, conversely, the reverse move might either displace or create a left-to-right minimum two places to the left). Exactly the same is true for moves 132 [left and right arrow] 231. Therefore repeated application of these rules to a permutation (such as the identity) which has all its left-to-right minima in odd positions can never introduce a left-to-right minimum in an even position.

Now we need to show that all such permutations can be obtained beginning with the identity. Let [sigma] be a permutation with all left-to-right minima in odd positions. We will show by induction that we can obtain the permutations [[sigma].sup.(k)] in which the final k elements match those of [sigma], and the remaining n - k elements are in increasing order. When k = 0, we have the identity.

Suppose we have obtained from the identity a permutation [tau] in which the final k elements are the same as those of [sigma] and in which the first n - k elements are in increasing order. We will place [[sigma].sub.n-k] in position n - k. If [[sigma].sub.n-k] is the smallest (and therefore leftmost) of the first n - k elements of [tau], then [[sigma].sub.n-k] is a left-to-right minimum of [sigma], and therefore n - k is odd. Since [[sigma].sub.n-k] = [[tau].sub.1] and the first n - k elements of [tau] are increasing, we can move it to position n - k by repeated moves of type 123 [right arrow] 231. If [[sigma].sub.n-k] is not the smallest of the first n - k elements of [tau], then [[sigma].sub.n-k] = [[tau].sub.i] with i > 1. If i is of the same parity as n - k, it is easy to move [[sigma].sub.n-k] using 123 [right arrow] 231. Otherwise, we place [[sigma].sub.n-k] = [[tau].sub.i] in position n - k - 1, then place [[tau].sub.i-1] in position n - k - 2. At this point, [[tau].sub.i-1][[tau].sub.i][[tau].sub.n-k] forms a pattern 123, so we can use 123 [right arrow] 132 to place [[tau].sub.i] = [[sigma].sub.n-k] in position n - k. Finally, we can use 231 [right arrow] 123 (letting [[tau].sub.i-1] play the role of 1) to return [[tau].sub.i-1] to position i - 1, so that the initial n - k - 1 elements are again in increasing order. The resulting permutation matches [sigma] in the final k +1 positions, and has the initial n - k - 1 elements in increasing order.

3.3 123 [left and right arrow] 231 [left and right arrow] 312

Definition 3.1 For convenience we will refer to the permutations in equivalence classes of size 1 as isolated permutations. That is, an isolated permutation is carried to nothing under any of the permitted transformations, equivalently, it does not contain any pattern in the replacement set.

Proposition 3.3 Let [sigma] be a permutation of size n. Then [sigma] [member of] [C.sub.n](123, 231,312) if and only if [sigma] is an even permutation which is not isolated.

Proof: The transformations 123 [left and right arrow] 213 [left and right arrow] 312 conserve the parity of the number of inversions, so each class contains only permutations of the same parity. In particular, if [sigma] [member of] [C.sub.n](123, 231, 312) then [sigma] is even.

Conversely suppose that [sigma] is an even permutation which is not isolated. Let K be the equivalence class containing [sigma] and let [tau] be an element of K with a minimal number of inversions. We will show that [tau] is the identity. We know that [tau] does not contain a 231 or a 312, because replacing these by 123 reduces the number of inversions. Since K does not consist of a single isolated permutation, it is possible to make a move from [tau], so it contains a 123.

Suppose there is an index i such that [[tau].sub.i-2] < [[tau].sub.i-1] < [[tau].sub.i] > [[tau].sub.i+1] > [[tau].sub.i+2]. As [tau] avoids 231, [[tau].sub.i+1][[tau].sub.i] [[tau].sub.i+1] must be a 132, and so [[tau].sub.i-2][[tau].sub.i-1][[tau].sub.i] [[tau].sub.i+1] is a 1243. Since 1243 [right arrow] 2413 [right arrow] 2134, we can move from [tau] to [tau]' = [[tau].sub.i] ... [[tau].sub.i-3][[tau].sub.i-1][[tau].sub.i-2] [[tau].sub.i+1][[tau].sub.i][[tau].sub.i+2] ... [[tau].sub.n], which has the same number of inversions as [tau]. But [[tau].sub.i+1][[tau].sub.i][[tau].sub.i+2] forms a 231, and so using 231 [right arrow] 123 we can obtain a permutation with strictly fewer inversions, contradicting the minimality of [tau].

Similarly, if there is an index i such that [[tau].sub.i-2] > [[tau].sub.i-1] > [[tau].sub.i] < [[tau].sub.i+1] < [[tau].sub.i+2], and using the fact that [tau] avoids 312, we can again obtain a permutation with strictly fewer inversions than [tau].

We will say that [tau] satisfies property P(i,k) if [[tau].sub.i] < [[tau].sub.i+1] < ... < [[tau].sub.i+k-1] < [[tau].sub.i+k], [[tau].sub.i-1] > [[tau].sub.i] and [[tau].sub.i+k] > [[tau].sub.k+1]. Suppose that there exists an index i and a k [greater than or equal to] 2 such that [tau] satisfies P(i, k). Since [tau] avoids 312, [[tau].sub.i-1][[tau].sub.i][[tau].sub.i+1] forms a 213, and since [tau] avoids 231, [[tau].sub.i+k-1][[tau].sub.i+k][[tau].sub.i+k+1] forms a 132. Thus [[tau].sub.i+k-2][[tau].sub.i+k-1][[tau].sub.i+k][[tau].sub.i+l+1] forms a 1243. Since 1243 [right arrow] 2413 [right arrow] 2134, we can move from [tau] to [tau]' = [[tau].sub.1] ... [[tau].sub.i+k-3][[tau].sub.i+k-1] [[tau].sub.i+k-2] [[tau].sub.i+k+1][[tau].sub.i+k] [[tau].sub.i+k+2] ... [[tau].sub.n], which has the same number of inversions as [tau], and satisfies P(i, k - 2). By induction this allows us to assume that [tau] satisfies P(i, k) for k = 2 or k = 3. First, suppose k = 2, so that [[tau].sub.i-1][[tau].sub.i] [[tau].sub.i+1][[tau].sub.i+2][[tau].sub.i+3] forms a 21354. Via 21354 [right arrow] 25134 [right arrow] 12534 [right arrow] 12345, we can obtain a permutation with fewer inversions, a contradiction. Then supoose k = 3, so that [[tau].sub.i-1][[tau].sub.i][[tau].sub.i+1][[tau].sub.i+2] [[tau].sub.i+3][[tau].sub.i+4] forms a 213465. Again we can obtain a permutation with fewer inversions, via 213465 [right arrow] 241365 [right arrow] 246135 [right arrow] 246513 [right arrow] 462513 [right arrow] 461253 [right arrow] 146253 [right arrow] 145623 [right arrow] 156423 [right arrow] 156234 [right arrow] 125634 [right arrow] 123564 [right arrow] 123456.

Recall that [tau] contains some 123. Let j be the smallest index with [[tau].sub.j] < [[tau].sub.j+1] < [[tau].sub.j+2]. Then either j = 1 or [[tau].sub.j-1] > [[tau].sub.j] (for otherwise we could have used j - 1). Let m be the largest integer with [[tau].sub.j] < [[tau].sub.j+1] < ... < [[tau].sub.j+m-1] < [[tau].sub.j+m]. By construction, m [greater than or equal to] 2, and j + m = n or [[tau].sub.j+m+1] < [[tau].sub.j+m] (by the maximality of m).

If j [not equal to] 1 and j + m [not equal to] n then [tau] satisfies P (j, m), contrary to our assumption.

Now suppose that j [not equal to] 1 and j + m = n. Then we know that [[tau].sub.j-1] > [[tau].sub.j] < [[tau].sub.j+1], and since [tau] avoids 312, [[tau].sub.j-1][[tau].sub.j][[tau].sub.j+1] forms a 213. If j - 1 = 1 then [tau] has only one inversion, which is impossible as [tau] is even. So j - 2 [greater than or equal to] 1. If [[tau].sub.j-2] > [[tau].sub.j-1] then the index j satisfies [[tau].sub.j-2] > [[tau].sub.j-1] > [[tau].sub.j] < [[tau].sub.j+1] < [[tau].sub.j+2], which we know is not the case. Thus [[tau].sub.j-2] < [[tau].sub.j-1] > [[tau].sub.j] and since t avoids 231, [[tau].sub.j- 2][[tau].sub.j-1][[tau].sub.j] forms a 132. If j - 2 = 1 then [tau] again has one inversion, which is impossible. Thus j - 3 [greater than or equal to] 1 and [[tau].sub.j-3] > [[tau].sub.j-2], otherwise the index j - 3 contradicts the minimality of j. Furthermore, [[tau].sub.j-3] < [[tau].sub.j-1] because [tau] has no 312, and so [[tau].sub.j-3][[tau].sub.j-2][[tau].sub.j-1][[tau].sub.j] [[tau].sub.j+1][[tau].sub.j+2] forms a 214356. Now we can use 214356 [right arrow] 214635 [right arrow] 213465, which by an argument above can be mapped to 123456, thus producing a permutation with fewer inversions than [tau].

We show symmetrically that the case j = 1 and j + m [not equal to] n is impossible. The only other possibility is that j = 1 and j + m = n, which means that t is the identity, and we are done.

Thanks to the preceding proposition, we have a characterization of the set [C.sub.n](123, 231, 312). Instead of enumerating this set we compute the complementary one among even permutations [S.sup.e](n). This set contains all even permutations that avoid patterns 123, 231 and 312. We will denote by [S.sub.n](123, 231, 312) the set of permutations of size n that avoid patterns 123, 231 and 312. Following article [KM05], denote by [s.sub.e](n; [i.sub.1]; ...; [i.sub.k]) (resp. [s.sub.o](n; [i.sub.1]; ...; the number of even (resp. odd) permutations n [member of] [S.sub.n](123, 231, 312) such that [[pi].sub.1][[pi].sub.2] ... [[pi].sub.k] = [i.sub.1][i.sub.2] ... [i.sub.k]. Consider the transformation rot on permutations that consists in left multiplying the permutation by n 12 ... n-1. This transformation rot is a bijection of [S.sub.n](123, 231, 312). Moreover when the size of a permutation is even, the transformation rot flips the parity and we have [s.sub.o](2n; a+1) = [s.sub.e](2n; a) and [s.sub.e](2n; a+1) = [s.sub.o](2n; a). When the size of permutation is odd rot preserves parity and we have [s.sub.o](2n + 1; a +1) = [s.sub.o](2n +1; a) and [s.sub.e](2n +1; a +1) = [s.sub.e](2n +1; a).

Proposition 3.4 For all n, x such that 1 [less than or equal to] x [less than or equal to] n:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: The proof is by induction on the size of the permutations. When the result holds for permutations of size n, we we call this property [H.sub.n]. Clearly [H.sub.3] holds: [s.sub.o](3; 1, 2) + [s.sub.o](3; 1, 3) = 1 and [s.sub.e](3; 1, 2) + [s.sub.e](3; 1, 3) = 0 because 123 is excluded and 132 is odd.

Proof for permutations of size 2n + 2 Suppose [H.sub.2n+1] holds. We prove [H.sub.2n+2].

We prove the result [s.sub.o](2n + 2; 1, 2x) = se(2n + 2; 1, 2x) by induction on x. In fact as [s.sub.o] (2n + 2; 1, 2) = [s.sub.e](2n + 2; 1, 2) = 0 the property is true for x = 1. Suppose it has been verified for x < [x.sub.0]. We call this property [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The equality [s.sub.o](2n + 2; 1, 2[x.sub.0]) = [s.sub.o](2n + 2; 1, 2[x.sub.0] - 2) + [s.sub.o](2n + 2; 1, 2[x.sub.o], 2) + [s.sub.o](2n + 2; 1, 2[x.sub.0], 3) [s.sub.o](2n + 2; 1, 2[x.sub.0] - 2, 2n + 2) - [s.sub.o](2n + 2; 1, 2[x.sub.0] - 2, 2n +1) holds and is easily proved by considering that permutations [sigma] in [S.sub.o](2n + 2; 1, 2[x.sub.0]) that do not have 2 or 3 as the third element are in one- to-one correspondence with those in [S.sub.o](2n + 2; 1,2[x.sub.0] - 2) that do not have 2n + 2 or 2n +1 as the third element by rotating twice (i.e. decreasing by 2) every element of [sigma] except its first one. Moreover, [s.sub.o](2n + 2; 1, 2[x.sub.0] - 2, 2n + 2) = 0 and [s.sub.o](2n + 2; 1, 2[x.sub.0] -2, 2n + 1) = 0 as the first 3 elements of these permutations are in increasing order.

As [s.sub.o](2n + 2; 1, i, j) = [s.sub.o](2n + 1; i - 1, j - 1) = [s.sub.o](2n + 1; 1, 2n + 2 + j - i) for j < i the preceding equality can be written as:

[s.sub.o](2n + 2; 1, 2[x.sub.0]) = [s.sub.o](2n + 2; 1, 2[x.sub.0] - 2) + [s.sub.o](2n +1; 1, 2n + 4 - 2[x.sub.0]) + [s.sub.o](2n + 1; 1, 2n + 5 - 2[x.sub.0]).

We also have the same equality with [s.sub.e] instead of [s.sub.o].

By property [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we have [s.sub.o](2n+2; 1, 2[x.sub.0] - 2) = [s.sub.e](2n + 2; 1, 2[x.sub.0] - 2). If [x.sub.0] < n+1, then by property [H.sub.2n+i] we have [s.sub.o](2n + 1; 1, 2n + 4 - 2[x.sub.0]) + [s.sub.o](2n +1; 1, 2n + 5 - 2[x.sub.0]) = [s.sub.e](2n + 1; 1, 2n + 4 - 2[x.sub.0]) + [s.sub.e](2n + 1; 1, 2n + 5 - 2[x.sub.0]). Hence [s.sub.o](2n + 2; 1, 2[x.sub.0]) = [s.sub.e](2n + 2; 1, 2[x.sub.0]).

If [x.sub.0] = n + 1, then by property [H.sub.2n+1] we have [s.sub.o](2n +1; 1, 2) + [s.sub.o](2n +1; 1,3) = [s.sub.e](2n + 1; 1, 2) + [s.sub.e](2n + 1; 1, 3) + [(-1).sup.n+1]. Hence [s.sub.o](2n + 2; 1, 2n + 2) = [s.sub.e](2n + 2; 1, 2n + 2) + [(- 1).sup.n+1].

Proof for permutations of size 2n + 3 : Suppose [H.sub.2n+2] holds. We prove [H.sub.2n+3].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If x > 1 as 2n+4-2x is even and 2n+4-2x < 2n+2 by induction we have [s.sub.e](2n+2; 1,2n+4-2x) = [s.sub.o](2n + 2; 1, 2n + 4 - 2x). Thus we finally have if x > 1:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If x = 1 the same calculus leads to a difference of [(-1).sup.n+2].

Theorem 3.1 The number of even permutations [s.sub.e](n) and the number of odd permutations [s.sub.o](n) in [S.sub.n](123, 231, 312) satisfy the following equations :

[s.sub.o](2k) = [s.sub.e](2k) = [E.sub.2k-1]/2 [s.sub.o](2k + 1) + [s.sub.e](2k + 1) = [E.sub.2k] , [s.sub.o](2k +1) = [s.sub.e](2k + 1) + (2k + 1)[(-1).sup.k]

Proof: By [KM05], [absolute value of [S.sub.n](123,231, 312)] = [E.sub.n-1] where [E.sub.n] is the n- Euler number (Sloane A000111). In particular [s.sub.o](2k + 1) + [s.sub.e](2k + 1) = [E.sub.2k].

When the size of permutation is even, the transformation rot flips the parity hence [s.sub.o](2k) = k[s.sub.e](2k; 1)+ k[s.sub.o](2k; 1) = [s.sub.e](2k). But [s.sub.o](2k) + [s.sub.e](2k) = [E.sub.2k-1] so [s.sub.o](2k) = [s.sub.e](2k) = [E.sub.2k-i]/2

When the size of the permutation is odd, transformation rot preserves parity. Permutations in [S.sub.2k+1](123, 231, 312) can be grouped in sets of size 2k +1 of permutations of the same parity which are equivalence classes of the relation rot. Note that in each class, only one permutation begins with 1. Hence, [s.sub.o](2k + 1) = (2k +1)[s.sub.o](2k + and [s.sub.e](2k + 1) = (2k +1)[s.sub.e](2k + 1;1). But [s.sub.o](2k + = [[summation].sup.2k+1.sub.i=2] [s.sub.o](2k + 1; 1, i) and Proposition 3.4 concludes that [s.sub.o](2k + 1) = [s.sub.e](2k + 1) + (2k + 1)[(-1).sup.k].

Corollary 3.2 The number [c.sub.n](123, 213, 231) of permutations of size n equivalent to the identity is [c.sub.2k](123, 213, 231) = (2k)!-[E.sub.2k-1]/2 and [c.sub.2k+i](123, 213, 231) = (2k+1)!-[E.sub.2k]+(2k+1)[(- 1).sup.k]/2

4 Replacement sets of size 4

4.1 123 [left and right arrow] 132 [left and right arrow] 213 [left and right arrow] 231

Lemma 4.1 Let [sigma] [member of] [S.sub.n] have [[sigma].sub.n] = n. Then [sigma] [member of] [C.sub.n](123,132, 213, 231).

Proof: Beginning with the identity, we will show by induction on k < n - 1 that we can reach a permutation [[sigma].sup.(k)] in which the first k elements are the same as those of [sigma] and the rest are in increasing order. The identity is [[sigma].sup.(0)]. Suppose that we have reached [[sigma].sup.(k)]. If [[sigma].sup.(k+1)] = [[sigma].sup.(k)], we are done. Otherwise we use 123 [right arrow] 231 as often as necessary to advance [[sigma].sub.k+1] (playing the role of 2), together with the element which follows it, to positions k + 1 and k + 2. (We know that there is a following element as an = n.) Next we use 231 [right arrow] 213 to switch the following element (playing the role of 3) to position k + 3, when we can begin a chain of 132 [right arrow] 123 to restore it to its original location.

Proposition 4.1 Let [sigma] [member of] [S.sub.n]. Then [sigma] [member of] [c.sub.n](123, 132, 213, 231) if and only if a does not begin with n.

Proof: No permutation [sigma] [member of] [c.sub.n](123, 132, 213, 231) can begin with n because n can only participate in a transformation as a 3, and none of the transformations places a 3 in the leftmost position.

Conversely, let [sigma] be a permutation which does not begin with n, and let [tau] be the pemutation obtained from [sigma] by deleting the n. By Lemma 4.1, we can obtain [tau]n from the identity. To obtain [sigma], we merely need to reposition the n, which we can do using 123 [right arrow] 132 and 213 [right arrow] 231 as necessary.

Corollary 4.1 [c.sub.n](123, 132, 213, 231) = n! - (n - 1)! = (n - 1) * (n - 1)!

4.2 123 [left and right arrow] 132 [left and right arrow] 231 [left and right arrow] 321

Lemma 4.2 Let [sigma] [member of] [S.sub.n] have [[sigma].sub.1] = 1. Then [sigma] [member of] [C.sub.n](123, 132, 231, 321).

Proof: We will show that we can obtain successively the permutations [[sigma].sup.(k)] in which the last k elements match [sigma] and the first n - k elements are in increasing order. The identity is [[sigma].sup.(0)]. Suppose that we have obtained [[sigma].sup.(k)]. By using 123 [right arrow] 231 repeatedly, we can place [[sigma].sub.n-k] = [[sigma].sup.(k).sub.i] in position n - k or in position n - k - 1. We remark that i [not equal to] 1 because [[sigma].sup.(k).sub.1] = 1 = [[sigma].sub.1] = [[sigma].sub.n-k]. If [[sigma].sub.n-k] has arrived in position n - k then we have constructed [[sigma].sup.(k+1)]. If conversely it is in position n - k - 1, then by using 123 [right arrow] 231 repeatedly, we can move [[sigma].sup.(k).sub.i-1] to position n - k - 2, then we can use 123 [right arrow] 132 on the three elements [[sigma].sup.(k).sub.i-1][[sigma].sup.(k).sub.i][[sigma].sup.(k).sub.n-k], which moves [[sigma].sup.(k).sub.i] = [[sigma].sub.n-k] to position n - k. Finally we use 231 [right arrow] 123, with [[sigma].sup.(k).sub.i-1] in the role of 1, as often as necessary to return [[sigma].sup.(k).sub.i-1] to its original location, thus obtaining [[sigma].sup.(k+1)].

Proposition 4.2 [sigma] [member of] [c.sub.n](123, 132, 231, 321) if and only if 1 occupies an odd position in [sigma].

Proof: In the identity, 1 occupies an odd position, and since 1 can only participate in a transformation as the smallest element, none of the possible transformations can change the parity of the position occupied by 1. Conversely, let [sigma] be a permutation having the element 1 in odd position, and let [tau] be the permutation obtained from [sigma] by deleting the 1. By Lemma 4.2, we can obtain 1t from the identity. Then we can use 123 [right arrow] 231 or 132 [right arrow] 321 as necessary to move the element 1 to its correct position.

Corollary 4.2 The number of permutations equivalent to the identity under 123 [left and right arrow] 132 [left and right arrow] 231 [left and right arrow] 321 is [c.sub.n](123, 132, 231, 321) = (n - 1)![??]n/2[??].

4.3 123 [left and right arrow] 132 [left and right arrow] 231 [left and right arrow] 312

Proposition 4.3 The only permutations of length n not belonging to [c.sub.n](123, 132, 231, 312) are isolated permutations, i.e. belong to classes of size 1.

Proof: Suppose [sigma] belongs to a class K of size greater than 1, and let [tau] be a permutation in K having the smallest number of inversions. We will show that [tau] is the identity. First, [tau] cannot contain any 132, 231 or 312, because such a string could be replaced by 123, yielding a permutation with a strictly smaller number of inversions. But K contains at least two permutations, therefore some replacement in [tau] is possible, and therefore [tau] contains a 123.

Now if [tau] is not the identity, because [tau] has no 231 or 132, [tau] must consist of a decreasing sequence followed by an increasing sequence. Consider the string at the junction of these two parts, x1bc, where x > 1 < b < c (as [tau] is not the identity and contains a 123, x, b and c exist). Note that x < b because [tau] contains no 312, so we have 1 < x < b < c. Now we make the transformations x1bc [right arrow] xc1b [right arrow] 1xcb [right arrow] 1xbc, arriving at a permutation with one fewer inversion than [tau]. Therefore [tau] can only be the identity.

Proposition 4.4 The permutations which are not in [c.sub.n](123, 132, 231, 312) are those which are obtained from [D.sub.n] = n (n - 1) ... 1 by taking an element other than 2 and placing it at the end.

Proof: By proposition 4.3, the permutations not in [c.sub.n](123, 132, 231, 312) are isolated, i.e. contain no 123, 132, 231 or 312. Because they have no 132 or 231, they must be a descending sequence followed by an increasing sequence. Because they have no 123, the increasing sequence can have length at most 2. Therefore they look like [D.sub.n] with one element (possibly 1) relocated to the end. But the relocated element cannot be 2 because the permutations contain no 312.

Corollary 4.3 The number of permutations in [c.sub.n](123, 132, 231, 312) is [c.sub.n](123, 132, 231, 312) = n! - (n - 1). Moreover #Classes(n; {123, 132, 231, 312}) = n.

4.4 123 [left and right arrow] 132 [left and right arrow] 312 [left and right arrow] 321

Proposition 4.5 The only permutations of length n not belonging to [c.sub.n](123, 132, 312, 321) are isolated.

Proof: Suppose [sigma] belongs to a class K of size greater than 1, and let [tau] be a permutation in K having the smallest number of inversions. We will show that [tau] is the identity. First, [tau] cannot contain any 132, 312 or 321, because such a string could be replaced by 123, yielding a permutation with a strictly smaller number of inversions. But K contains at least two permutations, therefore some replacement in [tau] is possible, and therefore [tau] contains a 123. Now if [tau] is not the identity, it must either contain a 123 followed by a descent, or a 123 preceded by a descent. In the first case we have abcx with a < b < c and b > x (because [tau] avoids 132), and we can make the transformations abcx [right arrow] acbx [right arrow] axbc, arriving at a permutation with two fewer inversions. In the second case we have xabc with a < b < c and a < x < b ([tau] avoids 312), and we can make the transformations xabc [right arrow] xcba [right arrow] cbxa [right arrow] caxb [right arrow] axcb [right arrow] axbc, arriving at a permutation with one fewer inversion. Therefore [tau] can only be the identity.

Proposition 4.6 The permutations not belonging to [c.sub.n](123, 132, 312, 321) are just the two wedge alternations open on the right as illustrated below.

Proof: By proposition 4.5, the permutations not equivalent to the identity are those which contain no 123, 132, 312 or 321. Because there is no 123 or 321, the permutations must alternate ascents and descents. But because there is no 132 or 312, each descent must set a new left-to-right minimum, and each ascent a new left-to-right maximum.

[ILLUSTRATION OMITTED]

Corollary 4.4 The number of permutations in [c.sub.n](123, 132, 312, 321) is [c.sub.n](123, 132, 312, 321) = n! - 2. Moreover #Classes(n; {123,132, 312, 321}) = 3.

4.5 123 [left and right arrow] 132 [left and right arrow] 213 [left and right arrow] 321

Proposition 4.7 The only permutations not equivalent to the identity under 123 [left and right arrow] 132 [left and right arrow] 213 [left and right arrow] 321 are the isolated permutations.

Proof: Suppose a belongs to a class K of size greater than 1, and let [tau] be a permutation in K having the smallest number of inversions. We will show that [tau] is the identity. First, [tau] cannot contain any 132, 213 or 321, because such a string could be replaced by 123, yielding a permutation with a strictly smaller number of inversions. But K contains at least two permutations, therefore some replacement in [tau] is possible, and therefore [tau] contains a 123.

Now if [tau] is not the identity, it must either contain a 123 followed by a descent, or a 123 preceded by a descent. In the first case we have abcx with a < b < c and b > x ([tau] avoids 132), and we can make the transformations abcx [right arrow] acbx [right arrow] axbc, arriving at a permutation with two fewer inversions. In the second case we have xabc with a < b < c and x > b ([tau] avoids 213), and we can make the transformations xabc [right arrow] xbac [right arrow] abxc, arriving at a permutation with two fewer inversions. Therefore [tau] can only be the identity.

Proposition 4.8 The only permutations not belonging to [c.sub.n](123, 132, 213, 321) are the alternating permutations in which the elements in odd positions form a decreasing sequence, and the elements in even positions form also a decreasing sequence.

Proof: By Proposition 4.7, the permutations are those with none of the four patterns. Because there is no 123 or 321, these permutations must be alternating; because there is no 123, 132 or 213, two elements which are situated two positions apart must be decreasing.

Proposition 4.9 The number of permutations in [c.sub.n](123, 132, 213, 321) is [c.sub.n](123, 132, 213, 321) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where c(n) is the nth Catalan number.

Proof: We will denote the number of isolated permutations by [d.sub.n]; as a result of proposition 4.7 we know that [c.sub.n](123, 132, 213, 321) = n! - [d.sub.n]. The isolated permutations are the permutations which are alternating, and such that the sequences ([[sigma].sub.2k])k and [([[sigma].sub.2k+1]).sub.k] are decreasing. It follows that [d.sub.n] = [a.sub.n] + [b.sub.n], where [a.sub.n] is the number of isolated permutations of size n with n in position 1, and [b.sub.n] is the number of isolated permutations of size n with n in position 2.

Let [sigma] be an isolated permutation of size n with n in position 1. We set [[alpha].sub.k] = n - [[sigma].sub.2k+1] - k for k [greater than or equal to] 0. Since [([[sigma].sub.2k+1]).sub.k] decreases and [[sigma].sub.1] = n, [([[alpha].sub.k]).sub.k] is non decreasing and [[alpha].sub.0] = 0. Moreover, because [sigma] is alternating and [([[sigma].sub.2k+1]).sub.k] and [([[sigma].sub.2k]).sub.k] are decreasing, [for all]k [greater than or equal to] 1, [[sigma].sub.2k] < [[sigma].sub.2k+1] and [[sigma].sub.s] < [[sigma].sub.2k+1] if 2k + 2 [less than or equal to] s [less than or equal to] n, so [[sigma].sub.2k+1] > n - 2k and [[alpha].sub.k] < k if k [greater than or equal to] 1.

If we represent the points (k, [[alpha].sub.k]) thus obtained, the result is a non decreasing sequence of [??]n/2[??] points situated strictly below the diagonal, except for [[alpha].sub.0] = 0. We can verify that this map is bijective with such sequences of points, and thus with the set of Dyck paths of length [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: connect each point to the next with a sequence of rightward steps followed by a sequence of upward steps, and then rotate the resulting diagram accordingly Figure 1. Thus [a.sub.n] = c([??]n-1/2[??]), by the well-known Catalan enumeration of Dyck paths. Now let a be an isolated permutation with [[sigma].sub.2] = n, and set [[alpha].sub.k] = n + 1 - [[sigma].sub.2k] - k for k [greater than or equal to] 1. As [([[sigma].sub.2k]).sub.k] is decreasing and [[sigma].sub.2] = n, [([[gamma].sub.k]).sub.k] is non decreasing and [[alpha].sub.1] = 0. Furthermore, as [sigma] is alternating and [([[sigma].sub.2k]).sub.k] and [([[sigma].sub.2k+1]).sub.k] are decreasing, [for all]k [greater than or equal to] 1, [[sigma].sub.2k-1] < [[sigma].sub.2k] and as < [[sigma].sub.2k] if 2k + 1 [less than or equal to] s [less than or equal to] n, so [[sigma].sub.2k] > n +1 - 2k and [[alpha].sub.k] < k if k [greater than or equal to] 1.

[FIGURE 1 OMITTED]

If we represent the points (k, [[alpha].sub.k]) thus obtained, the result is an increasing sequence of [??]n/2[??] points situated strictly below the diagonal. Again, this map is bijective, and by adding a point at (0, 0) we have, as above, a bijection with Dyck paths of length [??]n/2[??]. So [b.sub.n] = c([??]n/2[??]).

Corollary 4.5 #Classes(n; {123, 132, 213, 321}) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4.6 123 [left and right arrow] 231 [left and right arrow] 312 [left and right arrow] 321

The equivalence class of the identity under 123 [left and right arrow] 231 [left and right arrow] 312 [left and right arrow] 321 consists of the reversals of the permutations in the equivalence class of [D.sub.n] = n, n - 1 ... 1 under the transformations 321 [left and right arrow] 132 [left and right arrow] 213 [left and right arrow] 123, considered in the previous section. But we know that [D.sub.n] was in the class of the identity under these transformations, because it was not isolated. This observation gives us immediately:

Proposition 4.10 The only permutations not belonging to [c.sub.n](123, 231, 312,321) are the alternating permutations in which the elements in odd positions form an increasing sequence, and the elements in even positions form an increasing sequence.

The number of permutations in [c.sub.n](123, 231, 312, 321) is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where c(n) is the nth Catalan number.

Moreover, #Classes(n; {123, 231, 312, 321}) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

5 Replacement sets of size 5

5.1 123 [left and right arrow] 132 [left and right arrow] 213 [left and right arrow] 231 [left and right arrow] 312

Proposition 5.1 #Classes(n; {123,132,213, 231, 312}) = 2, and the two equivalence classes are [c.sub.n](123, 132, 213, 231, 312) and {[D.sub.n]} where [D.sub.n] = n (n-1) ... 1.

Proof: Let [sigma] be a permutation not in [c.sub.n](123, 132, 213, 231, 312): by section 4.3, [[sigma].sub.1] ... [[sigma].sub.n-1] is decreasing and [[sigma].sub.n] [not equal to] 2. And by section 4.1, applying reverse complements, [[sigma].sub.n] = 1, and so [sigma] = [D.sub.n]. Conversely, it is clear that [D.sub.n] [not member of] [C.sub.n](123, 132, 213, 231, 312), because [D.sub.n] contains only the pattern 321 and so is isolated.

5.2 Remaining cases

Proposition 5.2 If n [greater than or equal to] 4 there is only a single equivalence class for the sets {123, 132, 213, 231, 321}, {123, 132, 213, 312, 321}, {123, 132, 231, 312, 321} or {123, 213, 231, 312, 321}.

Proof: We will prove the first of the four statements, as the four proofs are straightforward and all very similar. Suppose, conversely, that we can find a permutation [sigma] which is not in [c.sub.n](123, 132, 213, 231, 321); then by section 4.4, applying reverse complements, [sigma] is a wedge alternation >, so by section 4.5 [sigma] is alternating and the sequences [([[sigma].sub.2k]).sub.k] and [([[sigma].sub.2k+1]).sub.k] are both decreasing, which is impossible.

6 Summary table
    Replacement set                  Enumeration               Sloane

  123,132 or 123, 213         [??]n/2[??]![??]n/2[??]!        A010551
       123, 231               [??]n/2[??]![??]n/2[??]!        A010551

       123, 312               [??]n/2[??]![??]n/2[??]!        A010551

       123, 321             [MATHEMATICAL EXPRESSION NOT      A001405
                               REPRODUCIBLE IN ASCII]
     123,132, 213                [3, 7, 35,135, 945]
     123,132, 231           [MATHEMATICAL EXPRESSION NOT      A000246
                               REPRODUCIBLE IN ASCII]
     123,132, 312                       n!/2                  A001710
     123,132, 321               [3, 9, 54, 285, 2160]
     123, 213, 231                      n!/2                  A001710
     123, 213, 312          [MATHEMATICAL EXPRESSION NOT      A000246
                               REPRODUCIBLE IN ASCII]
     123, 213, 321              [3, 9, 54, 285, 2160]
     123, 231, 312              [3, 8,45, 313, 2310]
     123, 231, 321              [3, 9, 54, 285, 2160]
     123, 312, 321              [3, 9, 54, 285, 2160]
   123,132, 213, 231                n! - (n - 1)!

   123,132, 213, 312                n! - (n - 1)!

   123,132, 213, 321       n! /c([??]n-1/2[??]) /c([??]N/
                                       2[??])

   123,132, 231, 312                n! - (n - 1)

   123,132, 231, 321            (n - 1)!r[??]N/2[??]
   123,132, 312, 321                   n! - 2

  123, 213, 231, 312                n! - (n - 1)

  123, 213, 231, 321                   n! - 2

  123, 213, 312, 321             (n - 1)![??]N/2[??]

  123, 231, 312, 321             n! - c([??]n-1/2) -
                                   c([??]n/2[??])

123,132, 213, 231, 312                 n! - 1
      Other cases                        n!

    Replacement set         Proof             Characterisation

  123,132 or 123, 213     [LPRW10]
       123, 231              2.1           [for all]k the rank of
                                           [[sigma].sub.k] among
                                            [[sigma].sub.1] ...
                                       [[sigma].sub.k] is of the same
                                                parity as k
       123, 312           2.1 (RC)         [for all] the rank of
                                           [[sigma].sub.k] among
                                            [[sigma].sub.k] ...
                                           [[sigma].sub.n] is odd
       123, 321           [LPRW10]

     123,132, 213         [CEH+01]
     123,132, 231            3.2            left-to-right minima
                                            are in odd position
     123,132, 312         3.1 (RC)             1 is left of 2
     123,132, 321         [LPRW10]
     123, 213, 231           3.1             n - 1 is left of n
     123, 213, 312        3.2 (RC)      right-to-left maxima are in
                                       positions of same parity as n
     123, 213, 321        [LPRW10]
     123, 231, 312           3.3       Non-isolated even permutations
     123, 231, 321        [LPRW10]
     123, 312, 321        [LPRW10]
   123,132, 213, 231         4.1       [[sigma].sub.1] [not equal to]
                                                     n
   123,132, 213, 312      4.1 (RC)     [[sigma].sub.n] [not equal to]
                                                     1
   123,132, 213, 321         4.5       [sigma] is not alternating or
                                                the sequence
                                           ([[sigma].sub.2k])k or
                                        ([[sigma].sub.2k+1])k is not
                                                 decreasing
   123,132, 231, 312         4.3            [[sigma].sub.1] ...
                                          [[sigma].sub.n-1] is not
                                      decreasing or [[sigma].sub.n] =
                                                     2
   123,132, 231, 321         4.2            1 is in odd position
   123,132, 312, 321         4.4           [sigma] is not a wedge
                                               alternation <
  123, 213, 231, 312      4.3 (RC)          [[sigma].sub.2] ...
                                           [[sigma].sub.n] is not
                                      decreasing or [[sigma].sub.1] =
                                                   n - 1
  123, 213, 231, 321      4.4 (RC)         [sigma] is not a wedge
                                               alternation >
  123, 213, 312, 321      4.2 (RC)      n and its position have the
                                                same parity
  123, 231, 312, 321         4.6       [sigma] is not alternating or
                                                the sequence
                                           ([[sigma].sub.2k])k or
                                       ([[sigma].sub.2k+1] )k is not
                                                 increasing
123,132, 213, 231, 312       5.1         All except n(n - 1) ... 1
      Other cases            5.2                    All


References

[[CEH.sup.+]01] Julien Cassaigne, Marc Espie, Florent Hivert, Daniel Krob, and Jean-Christophe Novelli. The chinese monoid. Internat. J. Algebra Comput., 11(3):301-334, 2001.

[KM05] Sergey Kitaev and Toufik Mansour. Simultaneous avoidance of generalized patterns. Ars Combinatoria, 75:267-288, 2005.

[Knu73] Donald E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison Wesley, Reading MA, 3rd edition, 1973.

[LPRW10] Stephen Linton, James Propp, Tom Roby, and Julian West. Constrained swapping in permutations. In Proceedings of FPSAC 2010, 2010.

Adeline Pierrot (1), Dominique Rossini (2)([dagger]) and Julian West (3)

(1) LIAFA, University Paris Diderot, Paris, France

(2) LIX, EEcole Polytechnique, Palaiseau, France

(3) Heilbronn Institute for Mathematical Research, University of Bristol, Bristol, UK

([dagger]) This work was supported by ANR Gama and Magnum
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Pierrot, Adeline; Rossin, Dominique; West, Julian
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUFR
Date:Jan 1, 2011
Words:8589
Previous Article:Tableaux and plane partitions of truncated shapes (extended abstract).
Next Article:The brick polytope of a sorting network.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters