Combinatorial Gray codes for classes of pattern avoiding permutations

arXiv:0704.2048v2 [math.CO] 9 Jan 2008 COMBINATORIAL GRAY CODES FOR CLASSES OF PATTERN AVOIDING PERMUTATIONS W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI Abstract. The past decade has seen a flurry of research into pattern avoiding permutations but little of it is concerned with their exhaustive generation. Many applications call for exhaustive generation of permutations subject to various constraints or imposing a particular generating order. In this paper we present generating algorithms and combinatorial Gray codes for several families of pattern avoiding permutations. Among the families under consideration are those counted by Catalan, large Schröder, Pell, even-index Fibonacci numbers and the central binomial coefficients. We thus provide Gray codes for the set of all permutations of {1, . . . , n} avoiding the pattern τ for all τ ∈ S3 and the Gray codes we obtain have distances 4 or 5. 1. Introduction A number of authors have been interested in Gray codes and generating algorithms for permutations and their restrictions (unrestricted [10], with given ups and downs [14, 18], involutions, and fixed-point free involutions [24], derangements [5], permutations with a fixed number of cycles [2]) or their generalizations (multiset permutations [13, 23]). A recent paper [12] presented Gray codes and generating algorithms for the three classes of pattern avoiding permutations: Sn (123, 132), Sn (123, 132,
p(p − 1) . . . 1(p + 1)), and permutations in Sn (123, 132) which have exactly n2 − k inversions. In [6] a general technique is presented for the generation of Gray codes for a large class of combinatorial families; it is based on the ECO method and produces objects by their encoding given by the generating tree (in some cases the obtained encodings can be translated into the objects). Motivated by these papers, we investigate the related problem for several new classes of pattern avoiding permutations. More specifically, we give combinatorial Gray codes for classes of pattern avoiding permutations which are counted by Catalan, Schröder, Pell, even-index Fibonacci numbers and the central binomial coefficients; the Gray codes we obtain have distances 4 or 5. Our work is different from similar work for combinatorial classes having the same counting sequence, see for instance [6, 22]. Indeed, as Savage [21, §7] points out: ‘Since bijections are known between most members of the Catalan family, a Gray code for one member of the family gives implicitly a listing scheme for every other member of the family. However, the resulting list may not look like Gray codes, since bijections need not preserve minimal changes between elements.’ Some direct constructions for Sn (231) exist but are, however, not Gray codes. For example, Bóna [8, §8.1.2] provides an algorithm for generating Sn (231). This 2000 Mathematics Subject Classification. Primary: 05A05, 94B25, Secondary: 05A15. Key words and phrases. Gray codes, pattern avoiding permutations, generating algorithms. 1 2 W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI algorithm is such that the successor of the permutation π = (n, n − 1, . . . 2, 1, 2n + 1, 2n, 2n − 1, . . . , n + 2, n + 1) is π ′ = (1, 2, . . . , n − 1, 2n + 1, n, n + 1, . . . , 2n). The number of places in which these two permutations differ is linear in n. In Section 2 we present a combinatorial Gray code for Sn (231) with distance 4. In Section 3 we present a Gray code for the Schröder permutations, Sn (1243, 2143), with distance 5. In Section 4 we present a general generating algorithm and Gray codes for some classes of pattern avoiding permutations and discuss its limits. The techniques we will use are: in Section 2 and 3 reversing sublists [20]; in Section 3 combinatorial bijections [12]; and in Section 4 generating trees [6]. Throughout this
paper, it is convenient to use the following notation. The num2n 1 ber cn = n+1 n is the n-th Catalan number. The large Schröder numbers rn are defined by r0 = 1 and for all n > 0, (1.1) rn = rn−1 + n X rk−1 rn−k . k=1 Let A(1) = 0, B(1) = 0 and for all i > 1, (1.2) (1.3) A(i) = c0 + . . . + ci−2 , and B(i) = r0 + . . . + ri−2 . The parity of these numbers will be extremely important in proving the Gray code properties of the generating algorithms for permutations we define later on in the paper. However, the parity of A(i) and B(i) are not explicitly used in the algorithms. Note that for all 0 < k ≤ 2n , A(2n + k) is odd iff n is even. One can easily show that B(i) is odd iff i = 2. For two permutations σ = σ1 σ2 . . . σn and τ = τ1 τ2 . . . τn in Sn , the metric d(σ, τ ) is the number of places in which they differ; and we denote by σ ◦ τ (or more compactly as στ ) their product, that is, the permutation π in Sn with πi = τσi for all i, 1 ≤ i ≤ n. In particular, when σ is the transposition (u, v), then (u, v) ◦ τ is the permutation π with πi = τi for all i, except that πu = τv and πv = τu . 2. A Gray code for Sn (231) Note that if (π(1), . . . , π(cn )) is an ordered list of elements of Sn (231) such that d(π(i), π(i + 1)) ≤ 4, then the operations of reverse, complement and their composition provide lists for Sn (132), Sn (213) and Sn (312), respectively, which preserve the distance between two adjacent permutations. 2.1. Generating 231-avoiding permutations. First we introduce some general notation concerning the list Dn that our algorithm will generate and then provide the necessary proofs to show that Dn is the desired object. For every n ≥ 0, let Dn denote a list consisting of cn entries, each of which is some permutation of {1, . . . , n}. The j-th entry is denoted Dn (j). In order that we may copy such a list, either in its natural or reversed order, we define Dni to be Dn if i is odd, and Dn reversed if i is even, for every positive integer i. Thus Dni (j) = Dni+1 (cn + 1 − j) for all 1 ≤ j ≤ cn . By Dn (j)+l we shall mean Dn (j) with every element incremented by the value l. Concatenation of lists is defined in the usual way, concatenation of any permutation with the null permutation yields the same permutation, i.e. [τ, ∅] = [∅, τ ] = τ . COMBINATORIAL GRAY CODES FOR CLASSES OF PERMUTATIONS 3 The list Dn is defined recursively as follows; D0 consists of a single entry which contains the null permutation that we denote as ∅. For any n ≥ 1, (2.1) Dn = i−1 cn−i h n cM i M M j+A(i)+1 n+i−1 (k) + (i − 1) , Di−1 (j), n, Dn−i i=1 j=1 k=1 where A(i) is defined in Equation (1.2) and ⊕ denotes the concatenation operator, e.g. 2 M 2 M (f (i, j)) = (f (1, 1), f (1, 2), f (2, 1), f (2, 2)) . i=1 j=1 Lemma 2.1. The list Dn contains all 231-avoiding permutations exactly once. Proof. Every permutation π ∈ Sn (231) may be decomposed as π = τ nσ, where τ ∈ Si−1 (231) and σ is a 231-avoiding permutation on the set {i, . . . , n − 1} which is order-isomorphic to a σ ′ ∈ Sn−i . In Dn , n assumes the positions i = 1, 2, . . . , n. For each position i of n, τ runs through Di−1 alternately forwards and backwards, forwards the last time. For each τ , σ runs through Di−1 +(i−1) alternately forwards and backwards, backwards the first time (see Table 1). The result follows by strong induction on n.  Lemma 2.2. For all n ≥ 2, Dn (1) = n123 · · · (n − 1) and Dn (cn ) = 123 · · · n. Proof. The proof proceeds by induction on n. We have D0 = ∅. Assume the result holds for each i = 0, 1, 2, . . . n − 1. Then by Equation (2.1), Dn (1) corresponds to the expression with i = 1, j = 1 and k = 1; 1+A(1)+1 Dn (1) = n Dn−1 2 (1) = n Dn−1 (1) = n Dn−1 (cn−1 ) = n123 · · · (n − 1). The last entry Dn (cn ) corresponds to the expression in Equation (2.1) with i = n, j = ci−1 and k = cn−i ; Dn (cn ) 2n−1 = Dn−1 (cn−1 ) n = 123 · · · n.  Theorem 2.3. For each q ∈ {1, 2, . . . cn − 1}, Dn (q) differs from its successor Dn (q + 1) by a rotation of two, three or four elements. Proof. The proof proceeds by induction. The result holds trivially for n = 1 since D1 consists of a single permutation. Assume the result holds for Di for each i = 1, 2, . . . n − 1. From Equation (2.1), there are 3 cases: (i) The current permutation corresponds to (i; j; k = t) and the next permutation corresponds to (i; j; k = t + 1), where t ∈ {1, 2, . . . cn−i − 1}. Therefore Dn (q) = Dn (q + 1) = j+A(i)+1 n+i−1 Di−1 (j) n Dn−i n+i−1 Di−1 (j) n (t) + (i − 1) j+A(i)+1 (t Dn−i + 1) + (i − 1), and by the induction hypothesis, d(Dn (q), Dn (q + 1)) = d(Dn−i (t), Dn−i (t + 1)) ≤ 4. 4 W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI (ii) The current permutation corresponds to (i, j = t, k = cn−i ) and the next permutation corresponds to (i; j = t + 1; k = 1), where t ∈ {1, 2, . . . ci−1 − 1}. Therefore t+A(i)+1 n+i−1 Di−1 (t) n Dn−i Dn (q) = n+i−1 Di−1 (t Dn (q + 1) = t+A(i)+1 Since Dn−i + 1) n t+A(i)+2 (cn−i ) = Dn−i (cn−i ) + (i − 1) t+A(i)+2 (1) Dn−i + (i − 1). (1), the induction hypothesis gives d(Dn (q), Dn (q + 1)) = d(Di−1 (t), Di−1 (t + 1)) ≤ 4. (iii) The current permutation corresponds to (i = t; j = ci−1 ; k = cn−i ) and the next permutation corresponds to (i = t + 1; j = 1; k = 1), where t ∈ {1, . . . n − 1}. Therefore Dn (q) = Dn (q + 1) = c n+t−1 t−1 Dt−1 (ct−1 ) n Dn−t +A(t)+1 1+A(t+1)+1 Dtn+t (1) n Dn−t−1 (cn−t ) + (t − 1) (1) + t. This divides into four cases, where in each case we use Lemma 2.2 and the fact that A(t + 1) = A(t) + ct−1 : (a) If n + t is odd and ct−1 + A(t) + 1 = A(t + 1) + 1 is odd, then Dn (q) = Dn (q + 1) = 1 2 3 . . . (t − 1) n t (t + 1) . . . (n − 1) 1 2 3 . . . (t − 1) t n (t + 1) . . . (n − 1). Here Dn (q +1) is obtained from Dn (q) via a single transposition of elements at positions (t, t + 1). (b) If n + t is odd and ct−1 + A(t) + 1 is even, then Dn (q) = 1 2 . . . (t − 1) n (n − 1) t (t + 1) . . . (n − 2) Dn (q + 1) = 1 2 . . . (t − 1) t n (n − 1) (t + 1) . . . (n − 2), for all t ≤ n − 3. Here Dn (q + 1) is obtained from Dn (q) via a rotation of the 3 elements at positions (t, t + 1, t + 2). If t = n − 2 then Dn (q) = Dn (q + 1) = 1 2 . . . (n − 3) n (n − 1) (n − 2) and 1 2 . . . (n − 3) (n − 2) n (n − 1). These permutations differ by a rotation of the 3 elements at positions (n − 2, n − 1, n). If t = n − 1 then Dn (q) = Dn (q + 1) = (n − 2) 1 2 . . . (n − 3) n (n − 1) and (n − 1) 1 2 . . . (n − 3) (n − 2) n. These permutations differ by a rotation of the 3 elements at positions (1, n− 1, n). (c) If n + t is even and ct−1 + A(t) + 1 is odd, then Dn (q) = (t − 1) 1 2 . . . (t − 2) n t (t + 1) . . . (n − 1) and Dn (q + 1) = t 1 2 . . . (t − 2) (t − 1) n (t + 1) . . . (n − 1) for all t ≥ 3. Here Dn (q + 1) is obtained from Dn (q) via a rotation of the 3 elements at positions (1, t, t + 1). The degenerate cases t = 1, 2 are dealt with in the same manner as those COMBINATORIAL GRAY CODES FOR CLASSES OF PERMUTATIONS 5 Table 1. The Gray code D6 for the set S6 (231) given by relation (2.1) and produced by Algorithm 1. Permutations are listed column-wise and changed entries are in bold. 612345 621345 613245 632145 631245 621435 612435 614235 614325 643125 643215 641325 642135 641235 631254 632154 613254 621354 612354 612534 612543 621543 621534 615234 615324 615243 615432 615423 654123 654213 654132 654321 654312 651432 651423 651243 652143 653124 653214 651324 652134 651234 165234 165324 165243 165432 165423 162543 162534 162354 163254 164235 164325 162435 163245 162345 126345 126435 126354 126543 126534 216534 216543 216354 216435 216345 312645 312654 321654 321645 132645 132654 213654 213645 123645 123654 123465 213465 132465 321465 312465 214365 124365 142365 143265 431265 432165 413265 421365 412365 512346 521346 513246 532146 531246 521436 512436 514236 514326 543126 543216 541326 542136 541236 154236 154326 152436 153246 152346 215346 215436 125436 125346 123546 213546 132546 321546 312546 412356 421356 413256 432156 431256 143256 142356 124356 214356 312456 321456 132456 213456 123456 at the end of part (b). (d) If n + t is even and ct−1 + A(t) + 1 is even, then Dn (q) = (t − 1) 1 2 . . . (t − 2) n (n − 1) t (t + 1) . . . (n − 2) Dn (q + 1) = t 1 2 . . . (t − 2) (t − 1) n (n − 1) (t + 1) . . . (n − 2), for all 3 ≤ t ≤ n − 3. Here Dn (q + 1) is obtained from Dn (q) via a rotation of the 4 elements at positions (1, t, t + 1, t + 2). The degenerate cases t = 1, 2, n − 2, n − 1 are dealt with in the same manner as those at the end of part (b).  In Table 1 is given the list D6 obtained by relation (2.1). The alert reader will note that there is no rotation of 4 elements in Table 1. Such a rotation is first observed when n = 7 and t = 3 (the permutation 2176345 becomes 3127645). 3. A Gray code for Schröder permutations The permutations Sn (1243, 2143) are called Schröder permutations and are just one of the classes of permutations enumerated by the Schröder numbers mentioned in the Introduction. Let Sn be the class of Schröder paths from (0,0) to (2n, 0) (such paths may take steps u = (1, 1), d = (1, −1) and e = (2, 0) but never go below the x-axis). This class Sn is enumerated by rn , see for instance [9]. In what follows, we will present a recursive procedure for generating all Schröder paths of length n. This procedure has the property that if the paths in Sn are 6 W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI Algorithm 1 Pseudocode for generating SN (231) using Equation (2.1). The list Dn is computed for each 1 ≤ n ≤ N . Here DnR denotes the reversal of list Dn . set D0 to a 1 × 0 matrix set D1 := [1] for n := 2 to N do τ state := n (mod 2) {1 means forwards and 0 means backwards} σstate := 0 for i := 1 to n do for l := 1 to i − 1 do if τ state = 0 then R τ =: Di−1 (l) else τ := Di−1 (l) end if for r := 1 to cn−i do if σstate=0 then R σ := Dn−i (r) + (i − 1) else σ := Dn−i (r) + (i − 1) end if new row:= [τ, n, σ] Append new row to Dn end for σstate := σstate + 1 (mod 2) end for τ state := τ state + 1 (mod 2) end for end for listed as (p1 , p2 , . . .), then the sequence of permutations (ϕ(p1 ), ϕ(p2 ), . . .) is a Gray code for Sn+1 (1243, 2143) with distance 5. First we briefly describe Egge and Mansour’s [9, §4] bijection ϕ : Sn 7→ Sn+1 (1243, 2143). Let p ∈ Sn and let si be the transposition (i, i + 1). Step 1: For all integers a, m with 0 ≤ a, m < n, if either of the points ((8m+1)/4, (8a+5)/4) or ((8m+5)/4, (8a+1)/4) is contained in the region beneath p and above the x-axis, then place a dot at that point. For such a dot, with coordinates (x, y), associate the label si where i = (1 + x − y)/2. Let j = 1. Step 2: Choose the rightmost dot that has no line associated with it (with label sk , say). Draw a line parallel to the x-axis from this dot to the leftmost dot that may be reached without crossing p (which has label sl , say). Let σj = sk sk−1 . . . sl , where si , applied to a permutation π, exchanges πi with πi+1 . If all dots have lines running through them, then go to step 3. Otherwise increase j by 1 and repeat step 2. Step 3: Let ϕ(p) = σj . . . σ2 σ1 (n + 1, n, . . . , 1). Example 3.1. Consider the path p ∈ S6 in the diagram. COMBINATORIAL GRAY CODES FOR CLASSES OF PERMUTATIONS 7 s2 s2 s1 s1 s2 s3 s3 s4 s5 s6 The dots indicate the points realized in Step 1 and the lines joining them indicate how each of the σ’s are formed. We have σ1 = s6 s5 , σ2 = s4 s3 s2 s1 , σ3 = s3 s2 s1 and σ4 = s2 . So ϕ(p) = = = σ4 σ3 σ2 σ1 (7, 6, 5, 4, 3, 2, 1) s2 s3 s2 s1 s4 s3 s2 s1 s6 s5 (7, 6, 5, 4, 3, 2, 1) (5, 2, 4, 6, 7, 1, 3). 3.1. Generating all Schröder paths. There are many ways to recursively generate all Schröder paths of length n. In what follows, we give one such procedure for generating the list Sn . This list has the property that the corresponding permutations, under the bijection ϕ, are a Gray code for Schröder permutations of distance 5. As in Section 2, we will use the convention that for any integer i, Sni = Sn if i is odd and Sni is Sn reversed, if i is even. Entry j of Sn is denoted Sn (j). In this notation we will have  Sn (j) if i is odd, i Sn (j) = Sn (rn + 1 − j) if i is even. Define S0 to be the list consisting of the single null Schröder path, denoted ∅. For all n ≥ 1, the paths are generated recursively via rn−1 (3.1) Sn = M (e Sn−1 (i)) ⊕ n rM i−1 rn−i  M M i=1 j=1 k=1 i=1 j+B(i)+1 n+i u Si−1 (j) d Sn−i  (k) . Sn starts with Sn−1 with each path preceded by e. There follow all the Schröder paths beginning with u. Let d be the partner of this u (the d that returns the path to the x axis). Then d assumes positions i = 2, 4, 6, . . . , 2n in the path. For each i, we have the paths in u α d β, where α runs through Si−1 alternately forwards and backwards, backwards the last time, and for each α, β runs through Sn−i alternately forwards and backwards, backwards the first time. Furthermore, we define Φn (j) := ϕ(Sn (j)) and (3.2) Φn := rn M Φn (j). j=1 For example, we have S1 = (e, ud) and S2 = (ee, eud, udud, ude, uudd, ued). Thus Φ1 = (21, 12) and Φ2 = (321, 312, 132, 231, 123, 213). The paths and permutations S3 , Φ3 , S4 and Φ4 are listed in Tables 2 and 3. For two paths p1 , p2 ∈ Sn , we write d(p1 , p2 ) for the number of places in which the two paths differ when each e is replaced by rr where r represents (1,0); e.g. d(e, ud) = 2 and d(ued, eud) = 2. Lemma 3.2. Equation (3.1) generates all Schröder paths of length n. 8 W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI Proof. This is routine by induction. The first concatenation operator forms all paths that begin with step e. If a path does not begin with e, then it does not touch the x axis for the first time until (2i, 0). A path of this form is uniquely expressed as uαdβ where α ∈ Si−1 and β ∈ Sn−i .  Lemma 3.3. For all n ≥ 1, Sn (1) = en and Sn (rn ) = uen−1 d. Proof. By Equation (3.1) we have that S1 (1) = e and S1 (2) = ud; so the result is true for n = 1. Assume it to be true for all m ≤ n − 1. Then Sn (1) = e Sn−1 (1) = e en−1 = en . Similarly, Sn (rn ) corresponds to Equation (3.1) with i = n, j = rn−1 , k = r0 , thus Sn (rn ) = 2n u Sn−1 (rn−1 ) d = u en−1 d = u en−1 d. Hence by induction the result is true for all n ≥ 1.  Under the bijection ϕ, we thus have Corollary 3.4. For all n > 0, Φn (1) = (n + 1) n . . . 1, Φn (rn ) = n . . . 1 (n + 1). Theorem 3.5. For each 1 ≤ q < rn , Sn (q) differs from Sn (q + 1) in at most 5 places and d(Φn (q), Φn (q + 1)) ≤ 5. Proof. This proof follows by strong induction and analyzing the different successors that occur in Equation (3.1). The statement in the Theorem holds for n = 0 because there is only one permutation. We assume the statement in the Theorem holds true for all 0 ≤ i ≤ n − 1. From Equation (3.1) there are five cases to consider: (i) If 1 ≤ q < rn−1 − 1, then Sn (q) = e Sn−1 (q) and Sn (q + 1) = e Sn−1 (q + 1). This gives d(Sn (q), Sn (q + 1)) = d(Sn−1 (q), Sn−1 (q + 1)), which is ≤ 5 by our hypothesis. Thus Φn (q) = (n + 1) Φn−1 (q) and Φn (q + 1) = (n + 1) Φn−1 (q + 1), and so d(Φn (q), Φn (q + 1)) ≤ 5. (ii) If q = rn−1 then by Equation (3.1) with (i = 1; j = 1; k = 1) and Lemma 3.3 we have Sn (rn−1 ) = e Sn−1 (rn−1 ) = e u en−2 d and 2 Sn (rn−1 + 1) = u d Sn−1 (1) = u d u en−2 d. Thus d(Sn (rn−1 ), Sn (rn−1 + 1)) = d(euen−2 d, uduen−2 d) = 2. The corresponding permutations are Φn (rn−1 ) = Φn (rn−1 + 1) = (n + 1) (n − 1) (n − 2) . . . 2 1 n and (n − 1) (n + 1) (n − 2) . . . 2 1 n, so that d(Φn (rn−1 ), Φn (rn−1 + 1)) = 2 ≤ 5. COMBINATORIAL GRAY CODES FOR CLASSES OF PERMUTATIONS 9 (iii) If Sn (q) corresponds to (i; j = ri−1 ; k = t) for some 1 ≤ t < rn−i in Equation (3.1) then Sn (q) = Sn (q + 1) = j+B(i)+1 n+i u Si−1 (ri−1 ) d Sn−i (t) and j+B(i)+1 n+i (t u Si−1 (ri−1 ) d Sn−i + 1), and the distance of the two paths is no greater than 5, by the induction hypothesis. Therefore j+B(i)+1 a ◦ (n + 1, . . . , n + 2 − i, ϕ(Sn−i Φn (q) = a ◦ (n + 1, . . . , n + 2 − Φn (q + 1) = (t))) and j+B(i)+1 (t i, ϕ(Sn−i + 1))), where a =  si si−1 . . . s1 , if n + i even, si−1 . . . s1 si si−1 . . . s1 , if n + i odd. Using the fact that if d(b, b′ ) ≤ x, then d(a ◦ b, a ◦ b′ ) ≤ x, we have by the induction hypothesis d(Φn (q), Φn (q + 1)) ≤ 5. (iv) If Sn (q) corresponds to Equation (3.1) with triple (i; j = t; k = rn−i ), where 1 ≤ t < ri−1 , then the successor Sn (q + 1) corresponds to Equation (3.1) with triple (i; j = t + 1; k = 1). Consequently, Sn (q) t+B(i)+1 n+i (t) d Sn−i = u Si−1 (rn−i ) and t+B(i)+2 n+i Sn (q + 1) = u Si−1 (t + 1) d Sn−i (1). t+B(i)+2 t+B(i)+1 (1), the result for Sn follows by the in(rn−i ) = Sn−i Since Sn−i n+i duction hypothesis applied to Si−1 . Now if t + B(i) + 2 is odd, then = n+i ϕ̂(u Si−1 (t) d) i (i − 1) . . . 1 and Φn (q + 1) = n+i ϕ̂(u Si−1 (t + 1) d) i (i − 1) . . . 1, Φn (q) n+i n+i where ϕ̂(u Si−1 (t) d) is ϕ(u Si−1 (t) d) with every element incremented by n+i n+i i. Since d(Si−1 (t), Si−1 (t + 1)) ≤ 5, we have that d(Φn (q), Φn (q + 1)) ≤ 5. The case where t + B(i) + 2 is even is handled in a similar manner with the suffix i(i − 1) . . . 1 replaced by (i − 1) . . . 1(i + 1). (v) If Sn (q) corresponds to Equation (3.1) with triple (i = t; j = ri−1 ; k = rn−i ), where 1 ≤ t < n, then Sn (q + 1) corresponds to Equation (3.1) with triple (i = t + 1; j = 1; k = 1). Consequently Sn (q) = Sn (q + 1) = r t−1 n+t u St−1 (rt−1 ) d Sn−t +B(t)+1 (rn−t ) and 1+B(t+1)+1 (1). u Stn+t+1 (1) d Sn−t−1 This divides into 4 sub-cases depending on the parity of the numbers n + t and rt−1 + B(t) + 1 = B(t + 1) + 1. Each case is easily resolved by applying Lemma 3.3. (a) If n + t is even and B(t + 1) + 1 is even, then Sn (q) = Sn (q + 1) = 2 2 u St−1 (rt−1 ) d Sn−t (rn−t ) = u et−1 d en−t and u St (1) d Sn−t−1 (1) = u et d en−t−1 , 10 W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI which differ in two positions. This gives Φn (q) = n (n − 1) . . . (n − t + 1) (n + 1) (n − t) (n − t − 1) . . . 1 and Φn (q + 1) = n (n − 1) . . . (n − t) (n + 1) (n − t − 1) . . . 1, for all 1 ≤ t ≤ n − 1. The two permutations differ by a transposing the elements at positions (t + 1, t + 2). (b) If n + t is odd and B(t + 1) + 1 is odd, then Sn (q) = Sn (q + 1) = u St−1 (rt−1 ) d Sn−t (rn−t ) = u uet−2 d d uen−t−1 d and 2 u St2 (1) d Sn−t−1 (1) = u uet−1 d d uen−t−2 d, which differ in five positions. This gives Φn (q) = Φn (q + 1) = (n − 1) · · · (n − t + 2)(n − t)n(n + 1)(n − t − 1) · · · 1(n − t + 1) and (n − 1) · · · (n − t + 1)(n − t − 1)n(n + 1)(n − t − 2) · · · 1(n − t), for all 2 ≤ t ≤ n − 2. These two permutations differ in five places (a transposition of the positions (t − 1, n) and a cycle of three elements at positions (t, t + 1, t + 2)). For t = 1 we have Φn (q) = Φn (q + 1) = n (n + 1) (n − 1) (n − 2) . . . 1 and (n − 1) n (n + 1) (n − 2) . . . 1, which differ by a cycle of three elements at positions (1,2,3). Similarly, for t = n − 1 we have Φn (q) = (n − 1) . . . 1 (n + 1) n and Φn (q + 1) = (n − 1) . . . 1 n (n + 1), which differ by transposing the entries in positions (n, n + 1). (c) If n + t is odd and B(t + 1) + 1 is even, then Sn (q) = Sn (q + 1) = 2 u St−1 (rt−1 ) d Sn−t (rn−t ) = u uet−2 d d en−t and u St2 (1) d Sn−t−1 (1) = u uet−1 d d en−t−1 . Thus Sn (q + 1) differs from Sn (q) in four positions. This gives Φn (q) = Φn (q + 1) = (n − 1) . . . (n − t + 1) n (n + 1) (n − t) . . . 1 and (n − 1) . . . (n − t) n (n + 1) (n − t − 1) . . . 1, for all t ≥ 2. The two permutations differ in three places (a rotation of three elements at positions (t, t + 1, t + 2)). The degenerate case t = 1 is handled in the same manner as in part (a). (d) If n + t is even and B(t + 1) + 1 is odd, then Sn (q) 2 = u St−1 (rt−1 ) d Sn−t (rn−t ) = u et−1 d uen−t−1 d and 2 Sn (q + 1) = u St (1) d Sn−t−1 (1) = u et d u en−t−2 d. Thus Sn (q + 1) differs from Sn (q) in five positions. This gives Φn (q) = n(n − 1) · · · (n − t + 2)(n − t)(n + 1)(n − t − 1) · · · 1(n − t + 1) and Φn (q + 1) = n(n − 1) · · · (n − t + 1)(n − t − 1)(n + 1)(n − t − 2) · · · 1(n − t), for all t ≤ n − 2. The two permutations differ in four places (the two disjoint transpositions of elements at positions (t, n + 1) and (t + 1, t + COMBINATORIAL GRAY CODES FOR CLASSES OF PERMUTATIONS 11 Table 2. The lists S3 and Φ3 . n 1 2 3 4 5 6 7 8 S3 (n) eee eeud eudud eude euudd eued udued uduudd Φ3 (n) 4321 4312 4132 4231 4123 4213 2413 1423 n 9 10 11 12 13 14 15 16 S3 (n) udude ududud udeud udee udee uedud uuddud uudde Φ3 (n) 2431 1432 3412 3421 3241 3142 1342 2341 n 17 18 19 20 21 22 S3 (n) uuedd uuuddd uuded uududd ueudd ueed Φ3 (n) 2134 1234 2314 1324 3124 3214 2)). The degenerate case t = n − 1 is handled in the same manner as in part (a).  The lists S3 , Φ3 , S4 and Φ4 are given in Table 2 and 3. Note that, unlike Φn , the list Sn is a circular Gray code; its first and last element have distance at most five. The choice of a Gray code for Schröder paths is critical in our construction of a Gray code for Sn (1243, 2143) since Egge and Mansour’s bijection ϕ, generally, does not preserves distances. For instance d(en , uen−1 d) = 2 but ϕ(en ) = (n + 1)n . . . 1 differs from ϕ(uen−1 d) = n . . . 1(n + 1) in all positions. Also, there already exists a distance five Gray code for Schröder paths [22] but it is not transformed into a Gray code for Sn (1243, 2143) by a known bijection. Finally, as in the previous section, both Gray codes presented above can be implemented in exhaustive generating algorithms. 4. Regular patterns and Gray codes Here we present a general generating algorithm and Gray codes for permutations avoiding a set of patterns T , provided T satisfies certain constraints. The operations of reverse, complement and their composition extend these to codes for T c , T r and T rc. Our approach is based on generating trees; see [1, 6, 7, 25] and the references therein. In [6] a general Gray code for a very large family of combinatorial objects is given; objects are encoded by their corresponding path in the generating tree and often it is possible to translate the obtained codes into codes for objects. The method we present here is, in a way, complementary to that of [6]: it works for a large family of patterns and objects are produced in ‘natural’ representation. It is also easily implemented by efficient generating algorithms. Its disadvantage is, for example, that it gives a distance-5 Gray code for S(231), and so is less optimal than the one given in Section 2; and it does not work for T = {1243, 2143} (the set of patterns considered in Section 3) since T does not satisfy the required criteria. We begin by explaining the generating trees technique in the context of pattern avoidance. The sites of π ∈ Sn are the positions between two consecutive entries, as well as before the first and after the last entry; and they are numbered, from right to left, from 1 to n + 1. For a permutation π ∈ Sn (T ), with T a set of forbidden patterns, i is an active site if the permutation obtained from π by inserting n + 1 into its i-th site is a permutation in Sn+1 (T ); we call such a permutation in Sn+1 (T ) a son of π. Clearly, if π ∈ Sn+1 (T ), by erasing n + 1 in π one obtains a permutation in Sn (T ); or equivalently, any permutation in Sn+1 (T ) is obtained 12 W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI Table 3. The lists S4 and Φ4 . n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 S4 (n) eeee eeeud eeudud eeude eeuudd eeued eudued euduudd eudude eududud eudeud eudee eudee euedud euuddud euudde euuedd euuuddd euuded euududd eueudd eueed udueed udueudd uduududd uduuded uduuuddd uduuedd uduudde uduuddud Φ4 (n) 54321 54312 54132 54231 54123 54213 52413 51423 52431 51432 53412 53421 53241 53142 51342 52341 52134 51234 52314 51324 53124 53214 35214 35124 15324 25314 15234 25134 25341 15342 n 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 S4 (n) uduedud ududee ududee ududeud udududud ududude ududuudd ududued udeued udeuudd udeude udeudud udeeud udeee uuddee uuddeud uuddudud uuddude uudduudd uuddued uedued ueduudd uedude uedudud uedeud uedee ueede ueedud ueuddud ueudde Φ4 (n) 35142 35241 35421 35412 15432 25431 15423 25413 45213 45123 45231 45132 45312 45321 34521 34512 14532 24531 14523 24513 42513 41523 42531 41532 43512 43521 43251 43152 41352 42351 n 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 S4 (n) uududde uududdud uudedud uudede uuuddde uuudddud uueddud uuedde uueedd uueuddd uuududdd uuudedd uuuudddd uuueddd uuudded uuuddudd uuedudd uudeed uudeed uudeudd uudududd uududed uuduuddd uuduedd ueuedd ueuuddd ueuded ueududd ueeudd ueeed Φ4 (n) 24351 14352 34152 34251 23451 13452 31452 32451 32145 31245 13245 23145 12345 21345 23415 13425 31425 32415 34215 34125 14325 24315 14235 24135 42135 41235 42315 41325 43125 43215 from a permutation in Sn (T ) by inserting n + 1 into one of its active sites. The active sites of a permutation π ∈ Sn (T ) are right justified if the sites to the right of any active site are also active. We denote by χT (i, π) the number of active sites of the permutation obtained from π by inserting n + 1 into its i-th active site. A set of patterns T is called regular if for any n ≥ 1 and π ∈ Sn (T ) • π has at least two active sites and they are right justified; • χT (i, π) does not depend on π but only on the number k of active sites of π; in this case we denote χT (i, π) by χT (i, k). In what follows we shall assume that T is a regular set of patterns. Several examples of regular patterns T , together with their respective χ functions, are given at the end of this section. Now we will describe an efficient (constant amortized time) generating algorithm for permutations avoiding a regular set of patterns; then we show how we can modify it to obtain Gray codes. If n = 1, then Sn (T ) = {(1)}; otherwise Sn (T ) = ∪π∈Sn−1 (T ) {σ ∈ Sn | σ is a son of π}. An efficient implementation is based on the following considerations and its pseudocode is given in Algorithm 2. COMBINATORIAL GRAY CODES FOR CLASSES OF PERMUTATIONS 13 Figure 1. (a) The generating tree induced by the call of Gen Avoid(1,2) for n = 4 and with χ defined by: χ(1, k) = k + 1 and χ(i, k) = i if i 6= 1. It corresponds to the forbidden pattern T = {321}. The active sites are represented by a dot. (b) The first four levels of the generating tree induced by the definition (4.2) with the same function χ; they yield the lists Ci (321) for the sets Si (321), 1 ≤ i ≤ 4. This tree is the Gray-code ordered version of the one in (a). Permutations in bold have direction down and the others direction up. 1234 : : : : : 123 : : : : 1234 : : : : : 1 2 4:3: 1 4:2:3: 123 : : : : 4: 1: 2: 3: 12 : : : 1 3:2: 1 3:2:4: 1 3 4:2: 12 : : : 3: 1: 2: 4: 3: 1: 2: 1 : : 3 1 4:2: 3 :1 :2 : 1 3 :2 : 1 : : 2: 1: 3: 4: 2: 1: 3: 2 1 4:3: 2 4:1:3: 2: 1: 2 3:1: (a) 2 3:1:4: 2 3 4:1: 3 4:1:2: 3 :1 :2 :4 : 3 1 4:2: 3 4:1:2: 1 4 :2 :3 : 4 :1 :2 :3 : 1 2 4 :3 : 2 3:1: 2 :1 : 1 3 4:2: 1 3 :2 :4 : 2 3:1:4: 2 3 4 :1 : 2 1 4:3: 2 :1 :3 : 2 4:1:3: 2 :1 :3 :4 : (b) The permutation obtained from π ∈ Sn−1 (T ) by inserting n into its first (rightmost) active site is πn. Let σ (resp. τ ) be the permutation obtained from π by inserting n into the i-th (resp. (i + 1)-th) active site of π. In this case τ is obtained by transposing the entries in positions n − i + 1 and n − i of σ. In addition, if χT (i, k) is calculable, from i and k, in constant time, then the obtained algorithm, Gen Avoid (Algorithm 2), runs in constant amortized time. Indeed, this algorithm satisfies the following properties: • the total amount of computation in each call is proportional with the number of direct calls produced by this call, • each non-terminal call produces at least two recursive calls (i.e., there is no call of degree one), and • each terminal call (degree-zero call) produces a new permutation, see for instance [19] and Figure 1 (a) for an example. Now we show how one can modify the generating procedure Gen Avoid sketched above in order to produce a Gray code listing. We associate to each permutation π ∈ Sn (T ) 14 W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI • a direction, up or down, and we denote by π 1 the permutation π with direction up and by π 0 the permutation π with direction down. A permutation together with its direction is called directed permutation. • a list of successors, each of them a permutation in Sn+1 (T ). The first permutation in the list of successors of π 1 has direction up and all others have direction down. The list of successors of π 0 is obtained by reversing the list of successors of π 1 and then reversing the direction of each element of the list. Let π ∈ Sn (T ) with k successors (or, equivalently, k active sites), and Lk be the unimodal sequence of integers (4.1) Lk =  1, 3, 5, . . . , k, (k − 1), (k − 3), . . . , 4, 2 if k is odd 1, 3, 5, . . . , (k − 1), k, (k − 2), . . . , 4, 2 if k is even. This list is very important in our construction of a Gray code; it has the following critical properties, independent of k: it begins and ends with the same element, and the difference between two consecutive elements is less than or equal to 2. For a permutation π with k active sites, the list of successors of π 1 , denoted by φ(π 1 ), is a list of k directed permutations in Sn+1 (T ): its j-th element is obtained from π by inserting n + 1 in the Lk (j)-th active site of π; and as stated above, the first permutation in φ(π 1 ) has direction up and all others have direction down. And we extend φ in natural way to lists of directed permutations: φ(π(1), π(2), . . .) is simply the list φ(π(1)), φ(π(2)), . . .. This kind of distribution of directions among the successors of an object is similar to that of [26]. Let dn = card(Sn (T )) and define the list dn−1 (4.2) Cn (T ) = Cn = M φ(Cn−1 (q)) q=1 where Cn (q) is the q-th directed permutation of Cn , anchored by C1 = (1)1 . We will show that the list of permutations in Cn (regardless of their directions) is a Gray code with distance 5 for the set Sn (T ). With these considerations in mind we have Lemma 4.1. • The list Cn contains all T -avoiding permutations exactly once; • The first permutation in Cn is (1, . . . , n) and the last one is (2, 1, 3, . . . , n). Lemma 4.2. If π i is a directed permutation in Cn (that is, π is a length n permutation and i ∈ {0, 1} is a direction), then two successive permutations in φ(π i ), say σ and τ , differ in at most three positions. Proof. Since φ(π 0 ) is the reverse of φ(π 1 ) it is enough to prove the statement for i = 1; so suppose that i = 1. Let σ and τ be the permutations obtained by inserting n + 1 in the Lk (j)-th and Lk (j + 1)-th active site of π, respectively, for some j. Since |Lk (j) − Lk (j + 1)| ≤ 2, d(σ, τ ) ≤ 3.  Let π i ∈ Cn and ℓ(π i ) denote the first (leftmost) element of the list φ(π i ), ℓ2 (π i ) = ℓ(ℓ(π i )), and ℓs (π i ) = ℓ(ℓs−1 (π i )). Similarly, r(π i ) denotes the last (rightmost) element of the list φ(π i ), and rs (π i ) is defined analogously. For π i ∈ Cn let dir(π i ) = i ∈ {0, 1}. By the recursive application of the definition of the list φ(π i ) we have the following lemma. COMBINATORIAL GRAY CODES FOR CLASSES OF PERMUTATIONS 15 Table 4. The Gray code list C5 (321) for the set S5 (321) given by relation (4.2) and with succession function χ in Paragraph 4.1. Permutations are listed column-wise in 14 groups; each group contains the sons of a same permutation in S4 (321), see Figure 1 b. In bold are permutations with direction down and the others with direction up. 12345 12534 51234 15234 12354 14253 14523 14235 41253 45123 41523 41235 12453 12435 31425 31452 34125 34512 34152 31254 35124 31524 31245 13425 13452 13254 13524 13245 23145 23514 23154 23451 23415 21435 21453 24135 24513 24153 21354 25134 21534 21345 Lemma 4.3. If π i ∈ Cn , then dir(ℓs (π i )) = 1 and dir(rs (π i )) = 0 for any s ≥ 1. Proof. ℓ(π i ), the first successor of π i has direction up for any i ∈ {0, 1}, and generally dir(ℓs (π i )) = 1 for s ≥ 1. Similarly, r(π i ), the last successor of π i has direction down for any i ∈ {0, 1}, and dir(rs (π i )) = 0 for s ≥ 1.  Lemma 4.4. If σ, τ ∈ Sn (T ) and d(σ, τ ) ≤ p, then, for s ≥ 1, d(rs (σ 0 ), ℓs (τ 1 )) ≤ p. Proof. r(σ 0 ) = (σ, (n + 1))0 and ℓ(τ 1 ) = (τ, (n + 1))1 . Induction on s completes the proof.  Theorem 4.5. Two consecutive permutations in Cn differ in at most five positions. Proof. Let σ i and τ j be two consecutive elements of Cn . If there is a π m ∈ Cn−1 such that σ i , τ j ∈ φ(π m ), then, by Lemma 4.2, σ and τ differ in at most three positions. Otherwise, let π m be the closest common ancestor of σ i and τ j in the generating tree, that is, π is the longest permutation such that there exists a direction m ∈ {0, 1} with σ i , τ j ∈ φ(φ(. . . φ(π m ) . . .)). In this case, there exist αa and β b successive elements in φ(π m ) (so that α and β differ in at most three positions) and an s ≥ 1 such that σ i = rs (αa ) and τ j = ℓs (β b ). If s = 1, then σ and τ are obtained from α and β by the insertion of their largest element in the first or second active site, according to a and b; in these cases σ and τ differ in at most five positions. (Actually, if a = b, then σ and τ differ as α and β, that is, in at most three positions.) If s > 1, by Lemma 4.3, dir(r(αa )) = . . . = dir(rs (αa )) = 0 and dir(ℓ(β b )) = . . . = dir(ℓs (β b )) = 1. Since r(αa ) and ℓ(β b ) differ in at most five positions, by Lemma 4.4, so are σ and τ .  The first and last permutations in Cn have distance two, so Cn is a circular Gray code, see Table 4. The generating algorithm Gen Avoid sketched in the beginning of this section and presented in Algorithm 2 can be easily modified to generate the list Cn (T ) for any set of regular patterns: it is enough to change appropriately the 16 W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI Algorithm 2 Pseudocode for generating permutations avoiding a set T of regular patterns characterized by the succession function χ(i, k). After the initialization of π by the length 1 permutation [1], the call of Gen Avoid(1, 2) produces Sn (T ). Its ordered version, as described in Section 4, produces distance-5 Gray codes. procedure Gen Avoid(size, k) if size = n then Print(π) else size := size + 1 π := [π, size] Gen Avoid(size, χ(1, k)) for i := 1 to k − 1 do π := (size − i + 1, size − i) ◦ π Gen Avoid(size, χ(i + 1, k)) end for for i := k − 1 to 1 by −1 do π := (size − i + 1, size − i) ◦ π end for end if end procedure order among its successive recursive calls by endowing each permutation with a direction as described above; see also Figure 1. 4.1. Several well-known classes of regular patterns. Below we give several classes of regular patterns together with the χ function. For each class, a recursive construction is given in the corresponding reference(s); it is based (often implicitly) on the distribution of active sites of the permutations belonging to the class. It is routine to express these recursive constructions in terms of χ functions and check the regularity of each class. Classes given by counting sequences: (i) 2n−1 [4]. T = {321, 312}, χT (i, k) = 2 (ii) Pell numbers [4]. T = {321, 3412, 4123}, χT (i, k) =  3 if i = 1 2 otherwise (iii) even-index Fibonacci numbers [4]. k + 1 if i = 1 - T = {321, 3412}, χT (i, k) = otherwise  2 3 if i = 1 - T = {321, 4123}, χT (i, k) = i otherwise (iv) Catalan numbers [17, 25]. - T = {312}, χT (i, k) = i+ 1 k + 1 if i = 1 - T = {321}, χT (i, k) = i otherwise (v) Schröder numbers [11].  k + 1 if i = 1 or i = 2 - T = {4321, 4312}, χT (i, k) = i otherwise COMBINATORIAL GRAY CODES FOR CLASSES OF PERMUTATIONS  k+1 i+1  k+1 - T = {4123, 4213}, χT (i, k) = i+2
(vi) central binomial coefficients 2n−2 [11]. n−1 - T = {4231, 4132}, χT (i, k) = 17 if i = 1 or i = k otherwise if i = k − 1 or i = k otherwise   k + 1 if i = 1 3 if i = 2 - T = {4321, 4231, 4312, 4132}, χT (i, k) =  i otherwise  3 if i = 1 - T = {4231, 4132, 4213, 4123}, χT (i, k) = i + 1 otherwise Variable length patterns:   k + 1 if i = 1 and k < p p if i = 1 and k = p (a) T = {321, (p + 1)12 . . . p}, χT (i, k) =  i otherwise See for instance [7, 4]. If p = 2, then we retrieve the case (i) above; p = 3 corresponds to T = {321, 4123} in case (iii); and p = ∞ corresponds to T = {321} in case (iv).   k + 1 if i = 1 and k < p p if i = 1 and k = p (b) T = {321, 3412, (p + 1)12 . . . p}, χT (i, k) =  2 otherwise See for instance [4]. If p = 2, then we retrieve the case (i) above; if p = 3, the case (ii); and p = ∞ corresponds to T = {321, 3412} in case (iii). (c) T = ∪τ ∈Sp−1  {(p + 1)τ p}. k+1 if k < p or i > k − p + 1 χT (i, k) = i + p − 1 otherwise See [3, 15, 16]. If p = 2, then we retrieve the case T = {312} in point (iv) above; and p = 3 corresponds to T = {4123, 4213} in point (v). Acknowledgments The authors kindly thank the anonymous referees for their helpful suggestions which have greatly improved the accuracy and presentation of this work. The first two authors would also like to thank Toast, Dublin, for their hospitality during the preparation of this document. References [1] Silvia Bacchelli, Elena Barcucci, Elisabetta Grazzini and Elisa Pergola, Exhaustive generation of combinatorial objects by ECO, Acta Informatica 40:8 (2004) 585-602. [2] Jean-Luc Baril, Gray code for permutations with a fixed number of cycles, Disc. Math. 30:13 (2007) 1559–1571. [3] Elena Barcucci, Alberto Del Lungo, Elisa Pergola and Renzo Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences, Disc. Math. Theor. Comp. Sci. 4:1 (2000) 31–44. [4] Elena Barcucci, Antonio Bernini and Maddalena Poneti, From Fibonacci to Catalan permutations, PuMA 17(1-2) (2006) 1–17. [5] Jean-Luc Baril and Vincent Vajnovszki, Gray code for derangements, Disc. App. Math. 140 (2004) 207–221. [6] Antonio Bernini, Elisabetta Grazzini, Elisa Pergola and Renzo Pinzani, A general exhaustive generation algorithm for Gray structures, Acta Informatica 44:5 (2007) 361–376. Also as preprint math.CO/0703262. 18 W.M.B. DUKES, M.F. FLANAGAN, T. MANSOUR AND V. VAJNOVSZKI [7] Timothy Chow and Julian West, Forbidden sequences and Chebyshev polynomials, Disc. Math. 204 (1999) 119–128. [8] Miklós Bóna. Combinatorics of Permutations. Chapman & Hall, 2004. [9] Eric S. Egge and Toufik Mansour, Permutations which avoid 1243 and 2143, continued fractions, and Chebyshev polynomials, Elec. J. Comb. 9:2 (2003) #R6. [10] Gideon Ehrlich, Loopless algorithms for generating permutations, combinations, and other combinatorial objects, J. ACM 20 (1973) 500–513. [11] Olivier Guibert, Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, PhD thesis, Université Bordeaux 1, 1995. [12] Asep Juarna and Vincent Vajnovszki, Some generalizations of a Simion-Schmidt bijection, The Computer Journal 50 (2007) 574–580. [13] C.W. Ko and Frank Ruskey, Generating permutations of a bag by interchanges, IPL 41:5 (1992) 263–269. [14] James F. Korsh, Loopless generation of up-down permutations, Disc. Math. 240:1-3 (2001) 97–122. [15] Darla Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Disc. Math. 218:1-3 (2000) 121–130. [16] Darla Kremer, Postscript: “Permutations with forbidden subsequences and a generalized Schröder number” [Disc. Math. 218 (2000) 121-130]. Disc. Math. 270:1-3 (2003) 332–333. [17] Jean Pallo, Some properties of the rotation lattice of binary trees, The Computer Journal 31 (1988) 564–565. [18] Dominique Roelants van Baronaigien and Frank Ruskey, Generating permutations with given ups and downs, Disc. Appl. Math. 36:1 (1992) 57–65. [19] Frank Ruskey, Combinatorial Generation, book in preparation. [20] Frank Ruskey, Simple combinatorial Gray codes constructed by reversing sublists, in ISAAC Conference, LNCS 762 (1993) 201–208. [21] Carla Savage, A Survey of Combinatorial Gray Codes, SIAM Rev. 39:4 (1997) 605–629. [22] Vincent Vajnovszki, Gray visiting Motzkins, Acta Informatica 38 (2002) 793-811. [23] Vincent Vajnovszki, A loopless algorithm for generating the permutations of a multiset, Theor. Comp. Sci. 307 (2003) 415-431. [24] Timothy Walsh, Gray codes for involutions, J. Combin. Math. Combin. Comput. 36 (2001) 95–118. [25] Julian West, Generating trees and the Catalan and Schröder numbers, Disc. Math. 146 (1994) 247–262. [26] Mark Weston and Vincent Vajnovszki, Gray codes for necklaces and Lyndon words of arbitrary base, PuMA 17(1-2) (2006) 175–182. Science Institute, University of Iceland, Reykjavı́k, Iceland. E-mail address: [email protected] Institute for Digital Communications, The University of Edinburgh, The King’s Buildings, Mayfield Road, Edinburgh EH9 3JL, Scotland. E-mail address: [email protected] Department of Mathematics, University of Haifa, 31905 Haifa, Israel. E-mail address: [email protected] LE2I UMR CNRS 5158, Université de Bourgogne B.P. 47 870, 21078 DIJON-Cedex France E-mail address: [email protected]