ON (SHAPE-)WILF-EQUIVALENCE FOR WORDS

Ting Guo^{∗}, Christian Krattenthaler^{†}, Yi Zhang^{‡}

∗College of Mathematics and Statistics, Hunan Normal University †Fakultät für Mathematik, Universität Wien ‡Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences

Abstract. Stankova and West showed that for any non-negative integer s and any permutation γ of {4, 5, …, s + 3} there are as many permutations that avoid 231γ as there are that avoid 312γ. We extend this result to the setting of words.

1. Introduction

Let π = π_{1}π_{2} ⋯ π_{n} be a permutation of {1, 2, …, n} and σ = σ_{1}σ_{2} ⋯ σ_{r} be a permutation of {1, 2, …, r}, r ≤ n. We say that the permutation π contains the pattern σ, if there are indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{r} ≤ n such that π_{i_{1}}π_{i_{2}} ⋯ π_{i_{r}} is in the same relative order as σ_{1}σ_{2} ⋯ σ_{r}. Otherwise, π is said to avoid the pattern σ, or, alternatively, we say that π is σ-avoiding. As usual, we write S_{n} for the set of all permutations of {1, 2, …, n}, and S_{n}(σ) for the set of permutations in S_{n} that avoid σ.

The enumeration of permutations which avoid certain patterns has been a flourishing research subject since the seminal article [10] of Simion and Schmidt, where this research subject was “defined.” The reader is referred to [8] and [4, Chapters 4 and 5] for in-depth accounts of the enumeration of pattern avoiding permutations.

We define the direct sum σ ⊕ τ of two permutations σ = σ_{1}σ_{2} ⋯ σ_{r} ∈ S_{r} and τ = τ_{1}τ_{2} ⋯ τ_{s} ∈ S_{s} as

σ ⊕ τ = σ_{1}σ_{2} ⋯ σ_{r}(τ_{1} + r)(τ_{2} + r) ⋯ (τ_{s} + r).

The starting point for the work on this paper was an email of Doron Zeilberger [12] to the second author saying^{1}:

2010 Mathematics Subject Classification. Primary 05A15; Secondary 05A17 05A19 05E10. Key words and phrases. Words, pattern avoidance, Ferrers diagrams, Ferrers shapes, growth dia-

grams, Wilf-equivalence, shape-Wilf-equivalence.

∗The work of the first author was done at the University of Vienna while she was visiting the Fakultät für Mathematik, supported by the China Scholarship Council.

†The work of the second author is partially supported by the Austrian Science Fund FWF, grant SFB F50 (Special Research Programme “Algorithmic and Enumerative Combinatorics”). WWW:

http://www.mat.univie.ac.at/~kratt.

‡The third author is supported by the Austrian Science Fund FWF, grant P29467-N32. Email:

zhangy@amss.ac.cn.

1Notation is slightly adapted in order to conform with the notation of our paper.

     According to http://en.wikipedia.org/wiki/Permutation pattern,
     Backelin, West & Xin (2007) proved that for any permutation
     beta and any positive integer k, the permutations
     12..k "+" beta and k....21 "+" beta are Wilf equivalent,
     and in 2002 Stankova and West proved that 231 "+" beta and
     312 "+" beta are Wilf equivalent.
     According to Vince Vatter and Jonathan Bloom you have nice
     proofs at least of the first result, in "Growth Diagrams, ...
     Ferrers Shapes".
     My main question is whether it is true, and whether there
     exists a proof, of the above two results generalized to words
     with a_{1} 1's, a_{2} 2's, ..., a_{m} m's, where the original case is

a_{1} = ... = a_{m} = 1.

Here, two patterns σ and τ are said to be Wilf-equivalent, denoted by σ ∼ τ, if |S_{n}(σ)| = |S_{n}(τ)| for all positive integers n. What Zeilberger refers to are the following two results.

Theorem 1 ([2, Theorem 2.1]). For all positive integers k, all non-negative integers s, and all patterns β ∈ S_{s}, the patterns 12 ⋯ k ⊕ β and k ⋯ 21 ⊕ β are Wilf-equivalent.

Theorem 2 ([11, Theorem 1]). For all non-negative integers s and all patterns β ∈ S_{s}, the patterns 231 ⊕ β and 312 ⊕ β are Wilf-equivalent.

In fact, these two theorems explain all instances of Wilf-equivalence (of single patterns) that are known up to this date, except for 1423 ∼ 3142 (and equivalent Wilfequivalence relations arising from reversal and/or complementation of patterns; cf. [2, pp. 134/135]).

Now, clearly, the notion of pattern avoidance can be straightforwardly adapted to words over the alphabet of positive integers. Given a word w = w_{1}w_{2} ⋯ w_{n} and a word x = x_{1}x_{2} ⋯ x_{r} with the letters w_{i} and x_{i} taken from the positive integers, we say that the word w contains the pattern x if there are indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{r} ≤ n such that w_{i_{1}}w_{i_{2}} ⋯ w_{i_{r}} is in the same relative order as x_{1}x_{2} ⋯ x_{r}. Otherwise, w is said to avoid the pattern x. Since in words there can be equal letters, by “same relative order” we mean that, if there is an equality x_{s} = x_{t} then there must also hold the equality w_{i_{s}} = w_{i_{t}}. Thus, Zeilberger asks whether Theorems 1 and 2 extend to words with a given number of 1’s, 2’s, …, m’s, the theorems themselves then being the special case where one considers words with exactly one 1, exactly one 2, …, and exactly one m.

As it turns out, the first question had already been answered by Jelínek and Mansour in [7]. The purpose of this note is to answer the second question.

Before we describe the corresponding results, it is however helpful to recall that the key concept behind the proofs of Theorems 1 and 2 is shape-Wilf-equivalence, a concept introduced in [2] (already non-explicitly present in [1]; see Section 2 for its definition). This is a stronger notion than Wilf-equivalence. In particular, if two permutations σ and τ are shape-Wilf-equivalent, then they are also Wilf-equivalent. The significance of shape-Wilf-equivalence is explained by the following proposition.

Proposition 3 ([2, Prop. 2.3]). If the permutations β and γ are shape-Wilf-equivalent, then for every permutation δ, β ⊕ δ and γ ⊕ δ are also shape-Wilf-equivalent.

In plain terms, given two shape-Wilf-equivalent permutations, by forming direct sums we can obtain a whole infinite family of pairs of shape-Wilf-equivalent permutations, which are automatically also pairs of Wilf-equivalent permutations. In particular, Theorems 1 and 2 follow from the following two results.

Theorem 4 ([2, Theorem 2.1]). For every positive integer k, the permutations 12 ⋯ k and k ⋯ 21 are shape-Wilf-equivalent.

Theorem 5 ([11, Theorem 1]). The permutations 231 and 312 are shape-Wilf-equiva-lent.

In view of Proposition 3, one sees that in Theorems 1 and 2 “Wilf-equivalent” may actually be replaced by “shape-Wilf-equivalent.”

In [7], Jelínek and Mansour show that Theorem 1 extends directly to the word setting. The key to prove this is again shape-Wilf-equivalence, here extended to words (see Section 2 for the definition; for the sake of the current discussion, it is only relevant to know that shape-Wilf-equivalence of x and y implies strong Wilf-equivalence of x and y, the latter meaning by definition that for all sequences a_{1}, a_{2}, …, a_{m} of positive integers there are as many words with a_{i} letters i, i = 1, 2, …, m, and avoiding x as there are words with a_{i} letters i, i = 1, 2, …, m, and avoiding y). In terms of this notion, Zeilberger’s questions translate into the questions whether 12 ⋯ k ⊕ β and k ⋯ 21 ⊕ β are strongly Wilf-equivalent, and whether 231 ⊕ β and 312 ⊕ β are strongly Wilf-equivalent, for any pattern β.

Proposition 6 ([7, Lemma 2.1]). Let x and y be two words with letters from {1, 2, …, k} and w another word. If x and y are shape-Wilf-equivalent for words then so are x ⊕ w and y ⊕ w.

For the definition of the direct sum of words see the end of Section 2.

Theorem 7 ([9, proof of Theorem 13, Eq. (4.6)]). The words 12 ⋯ k and k ⋯ 21 are shape-Wilf-equivalent for words.

If these two results are combined, the answer to Zeilberger’s first question is obtained.

Corollary 8 ([7, Fact 2.2]). For all words w, the words 12 ⋯ k ⊕ w and k ⋯ 21 ⊕ w are shape-Wilf-equivalent for words.

The situation is different for Theorems 2 and 5. The counterexamples in Section 3 demonstrate that Theorem 5 does not straightforwardly extend to the word setting, that is, that 231 and 312 are not shape-Wilf-equivalent for words. Moreover, our computer calculations strongly indicate that 231 ⊕ β and 312 ⊕ β are never Wilf-equivalent for words when β is a non-empty permutation, regardless of the exact notion of “Wilfequivalence” that we consider (see Conjecture 10). On the other hand, it seems more difficult to avoid 312 than 231. This vague statement is made more precise in Conjecture 11.

Nevertheless, weak versions of Theorems 2 and 5 hold true. If we do not insist on the “strict” patterns 231 and 312 but instead, say, interpret an occurrence of the patterns 231 and 312 to mean that the ‘2’ and the ‘3’ could also “be equal”, then it is possible to extend Theorems 2 and 5. Theorem 12 in Section 4 says that the sets of patterns {231, 221} and {312, 212} are shape-Wilf-equivalent for words, and Theorem 13 in the same section says that {231, 121} and {312, 211} are shape-Wilf-equivalent for words.

Furthermore, although shape-Wilf-equivalence of 231 and 312 for words is not true, the (strong) Wilf-equivalence of 231 and 312 for words (and, actually, of all permutation patterns of length 3) is again known and follows as a special case from another result of Jelínek and Mansour.

Theorem 9 ([7, Lemma 2.4]). For any k, all the patterns that consist of a single letter ‘1’, a single letter ‘3’ and k − 2 letters ‘2’ are strongly Wilf-equivalent.

Before describing our results, we need to collect definitions and notation in the next section.

2. Definitions and notation

We recall from the introduction that S_{n}(σ) denotes the set of all permutations of {1, 2, …, n} that avoid σ. We choose a similar notation in the word setting. We write W^{(a_{1},a_{2},...)}(x) for the set of all words consisting of a_{i} letters i, i = 1, 2, …, and avoiding x. More generally, given a set Ω of words, we write W^{(a_{1},a_{2},...)}(Ω) for the set of all words consisting of a_{i} letters i, i = 1, 2, …, and avoiding all x ∈ Ω. (For convenience, the set braces may be omitted in this notation.) Occasionally, we shall use the symbol W_{n,m}(x) to denote the set of all words of length n that use letters from {1, 2, …, m} and avoid the word x.

Next we reformulate pattern avoidance of permutations in terms of matrices. Clearly, any permutation π = π_{1}π_{2} ⋯ π_{n} can be represented by the corresponding permutation matrix M(π), which for us is the n×n matrix which contains a 1 in column j and row π_{j}, j = 1, 2, …, n, and all other entries are zero. When we display a matrix, our convention is that rows are ordered from bottom to top, so that row 1 is the lowest row and row n the top-most. For example, the left of Figure 1 shows the matrix corresponding to the permutation 352164. Alternatively, we may represent an n×n permutation matrix as a 0-1-filling of a square arrangement of cells, with n cells in each row and in each column, such that each row and each column contain exactly one 1 and otherwise 0’s. In the interest of better readability, instead of 1’s we write X’s, and we suppress the 0’s, see the right of Figure 1.

M(352164) = (\begin{matrix}0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{matrix}) X X X X X X

Figure 1. Matrix representation of 352164

Clearly, a permutation π avoids the permutation σ if and only if M(π) does not contain M(σ) as a submatrix. For example, our permutation 352164 avoids 1324 but does not avoid 231.

Pattern avoidance in words can also be formulated in terms of matrices. We may represent a word w = w_{1}w_{2} ⋯ with a_{1} letters 1, a_{2} letters 2, …, a_{m} letters m as a 0-1-filling of an m × (a_{1} + a_{2} + ⋯ + a_{m}) rectangle, by placing a 1 into the j-th column and w_{j}-th row, j = 1, 2, …, a_{1} + a_{2} + ⋯ + a_{m}, all other entries being 0. We denote this 0-1-filling by M(w). For example, the word 213314242 is represented by the filling of Figure 2.

X X X X X X X X X

Figure 2. The 0-1-filling corresponding to 213314242

Similarly as for permutations, a word w avoids the word x if and only if M(w) does not contain M(x) as a submatrix. For example, our word 213314242 avoids 3112 but does not avoid 123.

We are now in the position to define (strong) Wilf-equivalence and shape-Wilf-equivalence for words. Let λ be a Ferrers shape, which is a left-justified arrangement of cells with the property that the row-lengths are non-increasing from bottom to top. (That is, we use the French convention when we represent Ferrers shapes.) As usual, we encode λ in terms of (λ_{1}, λ_{2}, …) where λ_{i} is the length of the i-th row of λ (counted from bottom to top). We write W_{λ}^{(a_{1},a_{2},...)}(x) for the set of all 0-1-fillings with exactly one 1 in each column, with a_{i} 1’s in row i, i = 1, 2, …, and which avoid x. Here, for a 0-1-filling F of the Ferrers shape λ to avoid x means that there do not exist rows r_{1}, r_{2}, … and columns c_{1}, c_{2}, … such that the entries of F corresponding to these rows and columns form a matrix which is identical with M(x). Phrased differently, the important point is that the complete matrix M(x) is found as a submatrix in the filling. Figure 3 shows a 0-1-filling of shape (10, 10, 10, 7, 4, 4) with exactly one 1 in each column. It avoids for example the pattern 4312.

X X X X X X X X X X

Figure 3. A 0-1-filling of shape (10, 10, 10, 7, 4, 4)

More generally, given a set Ω of words, we write W_{λ}^{(a_{1},a_{2},...)}(Ω) for the analogous set of 0-1-fillings all of which avoid all x ∈ Ω.

We call two words x and y strongly Wilf-equivalent for words if

|W_{R(a)}^{(a_{1},a_{2},...)}(x)| = |W_{R(a)}^{(a_{1},a_{2},...)}(y)|  (2.1)

for all finite sequences a = a_{1}, a_{2}, … of positive integers, where R(a) denotes the m×(a_{1}+a_{2}+⋯) rectangle. Equivalently, in view of the earlier explained representations of words in terms of fillings, the words x and y are strongly Wilf-equivalent for words if and only if the number of words consisting of exactly a_{i} letters i, i = 1, 2, …, and avoiding x is the same as the number of words consisting of exactly a_{i} letters i, i = 1, 2, …, and avoiding y, for all finite sequences a_{1}, a_{2}, … of positive integers. On the other hand, “ordinary” Wilf-equivalence of words x and y means that |W_{n,m}(x)| = |W_{n,m}(y)| for all n and m.

We call two words x and y shape-Wilf-equivalent for words if

|W_{λ}^{(a_{1},a_{2},...)}(x)| = |W_{λ}^{(a_{1},a_{2},...)}(y)|  (2.2)

for all finite sequences a = a_{1}, a_{2}, … of positive integers and all shapes λ. We extend the notions of strong Wilf-equivalence and shape-Wilf-equivalence to sets of words, say Ω and Σ, by requiring that (2.1) respectively (2.2) hold with x replaced by Ω and y replaced by Σ for all finite sequences a_{1}, a_{2}, … of positive integers and shapes λ.

If we restrict the above definitions to a_{1} = a_{2} = ⋯ = 1, then they reduce to Wilfequivalence and shape-Wilf-equivalence for permutations.

Finally, given a word x = x_{1}x_{2} ⋯ x_{r} with letters from {1, 2, …, m} and another word y = y_{1}y_{2} ⋯ y_{s}, we define the direct sum x ⊕ y by

x ⊕ y = x_{1}x_{2} ⋯ x_{r}(y_{1} + m)(y_{2} + m) ⋯ (y_{s} + m).

3. Counterexamples

We have done calculations by computer for the word patterns 231 and 312. Consider the shapes λ_{1} = (5, 5, 4), λ_{2} = (5, 5, 5, 4), and λ_{3} = (6, 6, 6, 4). Table 1 presents the results of our computations for all possible sequences a = a_{1}, a_{2}, … of positive integers. (Recall that, since our 0-1-fillings always have exactly one 1 in each column, the sum of the a_{i}’s must equal the length of the longest row of the shape. Thus, for λ_{1} and λ_{2} the sum of the a_{i}’s must be 5, whereas for λ_{3} the sum of the a_{i}’s must be 6.)

a  (221) (212) (122) (311) (131) (113)
|W_{λ_{1}}^{a}(231)| 18  15  15  13  13  8
|W_{λ_{1}}^{a}(312)| 18  15  15  13  13  8
a  (2111) (1211) (1121) (1112)
|W_{λ_{2}}^{a}(231)| 25  26  25  21
|W_{λ_{2}}^{a}(312)| 25  25  26  21
a  (1113) (3111) (1311) (1131) (2112) (1212) (1122) (2211) (2121) (1221)
|W_{λ_{3}}^{a}(231)| 20  42  40  42  42  39  42  52  54  52
|W_{λ_{3}}^{a}(312)| 20  42  42  42  42  42  39  54  53  53

Table 1

We make the following observations.

(1) For λ_{1} and arbitrary sequences a = a_{1}, a_{2}, a_{3} of positive integers, the sets W_{λ_{1}}^{(a_{1},a_{2},a_{3})}(231) and W_{λ_{1}}^{(a_{1},a_{2},a_{3})}(312) have the same cardinality.

(2) For λ_{2}, although the total numbers of 0-1-fillings with exactly one 1 in each column and at least one 1 in each row that avoid 231 respectively 312 are the same, there exist positive integers a_{1}, a_{2}, a_{3}, a_{4} for which |W_{λ_{2}}^{(a_{1},a_{2},a_{3},a_{4})}(231)| is different from |W_{λ_{2}}^{(a_{1},a_{2},a_{3},a_{4})}(312)|.

(3) For λ_{3}, even the total numbers do not match. Instead, as one lets a_{1}, a_{2}, a_{3}, a_{4} grow, one finds more and more sequences of positive integers a_{1}, a_{2}, a_{3}, a_{4} for which |W_{λ_{3}}^{(a_{1},a_{2},a_{3},a_{4})}(231)| is different from |W_{λ_{3}}^{(a_{1},a_{2},a_{3},a_{4})}(312)|.

This establishes the following fact.

Fact. The patterns 231 and 312 are not shape-Wilf-equivalent for words.

Consequently, Proposition 6 cannot be applied to conclude that 231 ⊕ β and 312 ⊕ β are (strongly) Wilf-equivalent for words for arbitrary patterns β. However, the latter might still be true, at least for some patterns β. In order to clarify that point as well, we made more computer calculations.

First, we looked at the case where β = 1, that is, at words (and, more generally, 0-1-fillings) avoiding 2314 respectively 3124. We found that

|W_{7,5}(2314)| = 67853 ≠ 67854 = |W_{7,5}(3124)|,

and, with λ_{4} = (7, 7, 7, 7, 7), the finer enumerations

|W_{λ_{4}}^{(1,2,1,2,1)}(2314)| = 908 ≠ 909 = |W_{λ_{4}}^{(1,2,1,2,1)}(3124)|.

See Table 2 for more details.

a  (31111) (13111) (11311) (11131) (11113)
|W_{λ_{4}}^{a}(2314)| 640  640  640  635  640
|W_{λ_{4}}^{a}(3124)| 640  640  640  635  640
a  (22111) (21211) (21121) (21112) (12211) (12121) (12112) (11221) (11212) (11122)
|W_{λ_{4}}^{a}(2314)| 913  913  909  913  913  908  913  909  913  909
|W_{λ_{4}}^{a}(3124)| 913  913  909  913  913  909  913  909  913  909

Table 2

Furthermore, we have

|W_{8,5}(2314)| = 310540 ≠ 310563 = |W_{8,5}(3124)|.

Table 3 shows that, with λ_{5} = (8, 8, 8, 8, 8), in fact

|W_{λ_{5}}^{(a_{1},a_{2},a_{3},a_{4},a_{5})}(2314)| ≠ |W_{λ_{5}}^{(a_{1},a_{2},a_{3},a_{4},a_{5})}(3124)|

for all possible sequences (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}) of positive integers.

\begin{matrix}a & (13121) & (12131) & (11231) & (22121) & (12221) & (12122) & (11222) \\ |W_{λ_{5}}^{a}(2314)| & 2258 & 2245 & 2251 & 3162 & 3164 & 3163 & 3167 \\ |W_{λ_{5}}^{a}(3124)| & 2263 & 2251 & 2250 & 3167 & 3167 & 3167 & 3168 \end{matrix}

Table 3

For the case β = 12, that is, for 23145- respectively 31245-avoiding words (0-1-fillings), we found that

|W_{8,6}(23145)| = |W_{8,6}(23154)| = 1640298 ≠ 1640299 = |W_{8,6}(31245)| = |W_{8,6}(31254)|.

Here, the equalities follow from reversal and complementation of patterns and Corollary 8.

\begin{matrix}λ & (6664) & (88844) & (99933) & (99944) & (775333) & (777744) & (888664) & (888844) & (987654) \\ |W_{λ}(231)| & 425 & 4443 & 6177 & 13435 & 70 & 1012 & 6232 & 6160 & 6183 \\ |W_{λ}(312)| & 429 & 4443 & 6177 & 13435 & 70 & 1012 & 6352 & 6160 & 6303 \\ λ & (987655) & (987755) & (996644) & (997655) & (997744) & (997755) & (999663) & (999755) & (999944) \\ |W_{λ}(231)| & 7301 & 9133 & 6130 & 14602 & 12870 & 18266 & 21549 & 30517 & 28036 \\ |W_{λ}(312)| & 7375 & 9213 & 6130 & 14750 & 12870 & 18426 & 21645 & 31185 & 28036 \end{matrix} Table 4

The data seem to suggest the following.

Conjecture 10. For all non-empty permutations β, the patterns 231 ⊕ β and 312 ⊕ β are not Wilf-equivalent for words.

On the other hand, based on more computational data (see for example Table 4), we suspect that the following may be true.

Conjecture 11. For every Ferrers shape λ, we have |W_{λ}(231)| ≤ |W_{λ}(312)|, where W_{λ}(x) denotes the set of all 0-1-fillings of shape λ avoiding x with exactly one 1 in each column.

Remark. By going through the proof of Proposition 6 in [7], one sees that the validity of Conjecture 11 would imply that

|W_{λ}(231 ⊕ β)| ≤ |W_{λ}(312 ⊕ β)|

for all patterns β.

4. “Modified” shape-Wilf-equivalence of 231 and 312 for words

We now show that a shape-Wilf-equivalence result can be obtained if we do not insist on the “strictness” of the patterns 231 and 312. Namely, if in these patterns we include instances where there is equality between the letters corresponding to the ‘2’ and the ‘3’ in the patterns, or alternatively if we include instances where there is equality between the letters corresponding to the ‘1’ and the ‘2’ in the patterns, then shape-Wilf-equivalence results do hold. The precise formulations are given in the two theorems below.

Theorem 12. The sets of patterns {231, 221} and {312, 212} are shape-Wilf-equivalent for words.

Theorem 13. The sets of patterns {231, 121} and {312, 211} are shape-Wilf-equivalent for words.

Before we are able to prove these two theorems, we need to recall the essential ingredients of the bijective proof of Theorem 5 given by Bloom and Saracino in [3].

Shape-Wilf-equivalence for permutations (as defined in Section 2; see the paragraph after (2.2)) involves 0-1-fillings with exactly one 1 in each column, and with exactly one 1 in each row (the latter coming from the restriction a_{1} = a_{2} = ⋯ = 1). We call such fillings full rook placements from now on.

Consider a Ferrers shape λ and a full rook placement R on it. For each vertex v (by which we mean a corner of a cell) along the right/up border of λ we assign an integer I_{R}(v), which by definition is the length of the longest increasing chain of 1’s in the region to the left and below of v. The right of Figure 4 shows the numbers I_{R}(v) for the particular full rook placement R presented there, as well does the left of Figure 5. (At this point, the varying thickness of lines should be ignored.) Given a full rook placement R on λ, we denote the sequence of numbers I_{R}(v), where v ranges over the vertices along the right/up border of λ by I(R).

Bloom and Saracino show the following:

(1) A full rook placement R on λ that is 231-avoiding (as a 0-1-filling) is uniquely determined by I(R) (see [3, Theorem 2]).

(2) The possible sequences I(R), where R is a 231-avoiding full rook placement on λ, have a simple characterisation, by means of the so-called 231-conditions (see [3] for their definition).

(3) A full rook placement R on λ that is 312-avoiding (as a 0-1-filling) is uniquely determined by I(R) (see [3, Theorem 2]).

(4) The possible sequences I(R), where R is a 312-avoiding full rook placement on λ, have a simple characterisation, by means of the so-called 312-conditions (see [3] for their definition).

(5) A bijection α from 231- to 312-avoiding full rook placements of λ can be defined as follows: let R_{1} be a 231-avoiding full rook placement on λ. For each vertex v along the right/up border of λ calculate the number

\begin{cases}0, & if I_{R_{1}}(v) = 0, \\ N_{R_{1}}(v) − I_{R_{1}}(v) + 1, & otherwise, \end{cases}  (4.1)

where N_{R}(v) denotes the total number of 1’s in a full rook placement R in the region to the left and below of v. This defines a new sequence of non-negative numbers. Let R_{2} be the uniquely determined 312-avoiding full rook placement corresponding to that sequence. The map α : R_{1} → R_{2} is a bijection.

It should be noted that the full rook placements on the right of Figure 4 and on the left of Figure 5 correspond to each other under the bijection α.

Proof of Theorem 12. Let λ be a Ferrers shape and a_{1}, a_{2}, … a sequence of positive integers. We have to prove that |W_{λ}^{(a_{1},a_{2},...)}(231, 221)| = |W_{λ}^{(a_{1},a_{2},...)}(312, 212)|. We are going to achieve this by constructing a bijection between the sets W_{λ}^{(a_{1},a_{2},...)}(231, 221) and W_{λ}^{(a_{1},a_{2},...)}(312, 212).

Let T_{1} ∈ W_{λ}^{(a_{1},a_{2},...)}(231, 221). In general, the filling T_{1} is not a full rook placement since it may contain several 1’s in a row. However, we convert T into a full rook placement by replacing row i by a_{i} rows in the new filling, i = 1, 2, …, and rearranging the a_{i} 1’s in an increasing fashion from bottom/left to top/right so that each of these 1’s stays in its column but each of the a_{i} rows contains exactly one 1. For later reference, we call the region covered by these a_{i} rows the i-th band, and the obtained full rook placement R_{1}. It should be noted that the original filling is {231, 221}-avoiding if and only if the new filling — which necessarily is a full rook placement — is 231-avoiding. This construction is illustrated in Figure 4. The left of the figure shows a filling in W_{(10,10,10,7,4,4)}^{(2,2,3,1,1,1)}(231, 221). The filling on the right shows the result of the above described conversion. In the figure, the separations between the original rows are indicated by thick lines, whereas the newly created rows are separated by thin lines. The resulting filling is in W_{λ_{1}}^{(1,1,...,1)}(231), where λ_{1} = (10, 10, 10, 10, 10, 10, 10, 7, 4, 4).

X X X X X X X X X X  X X X X X X X X X X 0 1 2 3 3 3 2 2 2 3 3 3 4 54 3 3 2 2 1 0

Figure 4. The blowup of a filling

We now apply the bijection α to R_{1}, to obtain a 312-avoiding full rook placement R_{2}. The left of Figure 5 shows the result when we apply α to the full rook placement on the right of Figure 4.

Claim 1. In the i-th band, the 1’s in R_{2} are arranged in a decreasing fashion, from top/left to bottom/right, for each i.

Finally, we shrink the i-th band back to a single row, putting a 1 in those columns where R_{2} contained a 1. We denote the obtained filling by T_{2}. Since R_{2} was 312avoiding, the “compressed” filling will be {312, 212}-avoiding — if we take the above claim for granted. Thus, the filling T_{2} is in W_{λ}^{(a_{1},a_{2},...)}(312, 212). Figure 5 shows the above shrinking process applied to our running example.

From the construction, it is also obvious how the inverse mapping works. It involves however another claim.

Claim 2. If the inverse of α is applied to a full rook placement with the property that, in the i-th band, the 1’s are arranged in decreasing fashion, then we obtain a full rook placement where, in the i-th band, the 1’s are arranged in increasing fashion, i = 1, 2, . . ..

If we assume the truth of these two claims then the proof of Theorem 12 is complete.

X X X X X X X X X X 0 1 1 1 2 1 1 2 3 3 2 3 3 33 3 2 2 1 1 0 X X X X X X X X X X

Figure 5. The shrinking of a full rook placement

We now prove Claim 1. We want to establish that, if R_{1} is a 231-avoiding full rook placement with 1’s arranged in increasing fashion in the i-th band, then R_{2} = α(R_{1}) has 1’s arranged in decreasing fashion in the i-th band, i = 1, 2, . . .. Let us concentrate on the i-th band of R_{1}. We denote the vertices along the right border of the band by u_{0}, u_{1}, …, u_{a_{i}}. In order to follow the next arguments, it might be helpful to look at Figure 6. The left of Figure 6 is meant to be the sketch of the i-th band (with a_{i} = 4). The 1’s in the full rook placement R_{1} are indicated by X_{1}, X_{2}, . . ..

X_{1} X_{2} X_{3} X_{4}  u_{0} u_{1} u_{2} u_{3} u_{4} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  Y_{2}  Y_{3}  u_{0} u_{1} u_{2} u_{3} u_{4} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 6. The i-th band

We claim that

I_{R_{1}}(u_{j+1}) = I_{R_{1}}(u_{j}) + 1, for j = 1, 2, …, a_{i} − 1.  (4.2)

Indeed, by definition, I_{R_{1}}(u_{1}) is the length of the longest increasing chain of 1’s in the region to the left and below of u_{1}. Since there cannot be any 1’s in the region to the right and below of X_{2} because R_{1} is 231-avoiding, we must have I_{R_{1}}(u_{2}) = I_{R_{1}}(u_{1}) + 1. The same argument shows I_{R_{1}}(u_{3}) = I_{R_{1}}(u_{2}) + 1, etc., thus establishing our claim in (4.2).

In order to apply the bijection α, we have to calculate the numbers in (4.1), which then become lengths of increasing chains I_{R_{2}}(v) for some 312-avoiding full rook placement R_{2}. Because of (4.2), we have

I_{R_{2}}(u_{j+1}) = I_{R_{2}}(u_{j}), for j = 1, 2, …, a_{i} − 1.  (4.3)

Let us suppose that R_{2} has two 1’s in the i-th band which are in increasing order. Without loss of generality, we may assume that these two 1’s are located in neighbouring rows. The right of Figure 6 is meant to illustrate this situation, with Y_{2} and Y_{3} indicating the positions of these two 1’s. Since R_{2} is 312-avoiding, 1’s in the region to the right and below of Y_{2} must be arranged in decreasing order. Thus, together with Y_{2}, they form a decreasing chain. The number I_{R_{2}}(u_{2}) gives the length of the longest increasing chain in the region to the left and below of u_{2}. Because of the above observed arrangement of 1’s to the right and below of Y_{2}, one of the chains with length I_{R_{2}}(u_{2}) is one which ends in Y_{2}. However, this implies that I_{R_{2}}(u_{3}) = I_{R_{2}}(u_{2}) + 1, in contradiction with (4.3). Thus, Y_{2} and Y_{3} cannot be arranged in increasing fashion. The same argument applies to any two neighbouring rows in the i-th band. Thus, we have proven Claim 1.

The only remaining task for the completion of the proof of the theorem is to verify Claim 2. This is however completely analogous and is left to the reader. □

Proof of Theorem 13. This can be proven in a fashion which is analogous to the proof of Theorem 12. The major difference is that, here, a {231, 121}-avoiding filling is converted into a 231-avoiding full rook placement by rearranging the a_{i} 1’s in the i-th band in decreasing fashion, while a {312, 211}-avoiding filling is converted into a 312-avoiding full rook placement by rearranging the a_{i} 1’s in the i-th band in increasing fashion. We leave the details to the reader. □

In view of Proposition 6 and the fact that it can easily be extended to sets of patterns, Theorems 12 and 13 entail the following corollaries.

Corollary 14. For any word β, the sets of patterns {231 ⊕ β, 221 ⊕ β} and {312 ⊕ β, 212 ⊕ β} are shape-Wilf-equivalent for words.

Corollary 15. For any word β, the sets of patterns {231 ⊕ β, 121 ⊕ β} and {312 ⊕ β, 211 ⊕ β} are shape-Wilf-equivalent for words.

Remark. It is interesting to note that {312, 212}-avoiding words appear in a “Catalan” context in [5]. Let s = (s_{1}, s_{2}, …, s_{a}) be an a-tuple of positive integers. In the above paper, Gessel and Stanley’s [6] Stirling permutations are generalised there to Stirling s-(multi)permutations, which by definition are — in our language here — 212-avoiding words consisting of s_{1} letters 1, s_{2} letters 2, …, and s_{a} letters a. It is shown (see [5, Theorem 2.1]) that 312-avoiding Stirling s-permutations are in bijection with numerous other combinatorial objects subject to certain restrictions, including planted plane trees, lattice paths, non-crossing partitions, and dissections of polygons.

Acknowledgments

The authors thank Doron Zeilberger for raising the problems addressed in this paper, and Sergey Kitaev for very helpful correspondence.

References

[1] E. Babson and J. West, The permutations 123p_{4} ⋯ p_{m} and 321p_{4} ⋯ p_{m} are Wilf-equivalent, Graphs Combin. 16 (2000), 373–380.

[2] J. Backelin, J. West and G. Xin, Wilf-equivalence for singleton classes, Adv. Appl. Math. 38 (2007), 133–148.

[3] J. Bloom and D. Saracino, A simple bijection between 231-avoiding and 312-avoiding placements, J. Combin. Math. Combin. Comput. 89 (2014), 23–32.

[4] M. Bóna, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, 2004.

[5] C. Ceballos and R. S. Gonz’alez D’Léon, Signature Catalan combinatorics, preprint,

   arχiv:1805.03863.

[6] I. M. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory Ser. A 24 (1978), 24–33.

[7] V. Jelínek and T. Mansour, Wilf-equivalence on k-ary words, compositions, and parking functions, Electron. J. Combin. 16 (2009), Art. #R58, 9 pp.

[8] S. Kitaev, Patterns in Permutations and Words, Springer–Verlag, Heidelberg, Dordrecht, London, New York, 2011.

[9] C. Krattenthaler, Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Adv. Appl. Math. 37 (2006), 404–431.

[10] R. Simion and F. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985), 383–406.

[11] Z. Stankova and J. West, A new class of Wilf-equivalent permutations, J. Algebraic Combin. 15 (2002), 271–290.

[12] D. Zeilberger, email from October 20, 2014.

∗Key Laboratory of High Performance Computing and Stochastic Information Processing (HPCSIP, Ministry of Education of China), College of Mathematics and Statistics, Hunan Normal University, Changsha, Hunan 410081, P. R. China

 E-mail address: guoting@hunnu.edu.cn

†Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria.

 URL: http://www.mat.univie.ac.at/~kratt

‡Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenberger Str. 69, Linz, Austria