text:
# Example 2.1

ON THE DIAGRAM OF 132-AVOIDING PERMUTATIONS
Astrid Reifegerste

Institut für Mathematik, Universität Hannover

Welfengarten 1

D-30167 Hannover, Germany

reifegerste@math.uni-hannover.de
October 15, 2002

Abstract. The diagram of a $`132`$-avoiding permutation can easily be characterized: it is simply the diagram of a partition. Based on this fact, we present a new bijection between $`132`$-avoiding and $`321`$-avoiding permutations. We will show that this bijection translates the correspondences between these permutations and Dyck paths given by Krattenthaler and by Billey-Jockusch-Stanley, respectively, to each other. Moreover, the diagram approach yields simple proofs for some enumerative results concerning forbidden patterns in $`132`$-avoiding permutations.

1 Introduction

Let $`𝒮_n`$ denote the symmetric group on $`\{1,\mathrm{},n\}`$. Given a permutation $`\pi =\pi _1\mathrm{}\pi _n𝒮_n`$ and a permutation $`\tau =\tau _1\mathrm{}\tau _k𝒮_k`$, we say that $`\pi `$ contains the pattern $`\tau `$ if there is a sequence $`1i_1<i_2<\mathrm{}<i_kn`$ such that the elements $`\pi _{i_1}\pi _{i_2}\mathrm{}\pi _{i_k}`$ are in the same relative order as $`\tau _1\tau _2\mathrm{}\tau _k`$. Otherwise, $`\pi `$ avoids the pattern $`\tau `$, or alternatively, $`\pi `$ is $`\tau `$-avoiding. We denote by $`𝒮_n(\tau )`$ the set of all permutations in $`𝒮_n`$ which avoid $`\tau `$.
It is an often quoted fact that $`|𝒮_n(\tau )|`$ is equal to the $`n`$th Catalan number $`C_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right)`$ for each pattern $`\tau 𝒮_3`$. Because of obvious symmetry arguments, from an enumerative viewpoint there are only two distinct cases to consider, $`\tau \{123,321\}`$ and $`\tau \{132,213,231,312\}`$. Several authors established bijections between permutations avoiding a pattern of each of these classes. The first one was given by Simion and Schmidt ; West described in  a construction using trees; and recently, Krattenthaler  connected the $`123`$-avoiding and $`132`$-avoiding permutations via Dyck paths.
In Section 2, we present a bijection between $`𝒮_n(321)`$ and $`𝒮_n(132)`$ based on another interesting combinatorial object, the diagrams.
Our construction has the advantage that the excedances of a permutation in $`𝒮_n(321)`$ are precisely the descents of its image in $`𝒮_n(132)`$.
An excedance of $`\pi `$ is an integer $`i\{1,\mathrm{},n1\}`$ such that $`\pi _i>i`$. Here the element $`\pi _i`$ is called an excedance letter for $`\pi `$. Given a permutation $`\pi `$, we denote the set of excedances of $`\pi `$ by $`𝖤(\pi )`$ and the number $`|𝖤(\pi )|`$ by $`\mathrm{𝖾𝗑𝖼}(\pi )`$. An integer $`i\{1,\mathrm{},n1\}`$ for which $`\pi _i>\pi _{i+1}`$ is called a descent of $`\pi `$. If $`i`$ is a descent, we say that $`\pi _{i+1}`$ is a descent bottom for $`\pi `$. The set of descents of $`\pi `$ is denoted by $`𝖣(\pi )`$, its cardinality is denoted by $`\mathrm{𝖽𝖾𝗌}(\pi )`$, as usual.
Given a permutation $`\pi 𝒮_n`$, let $`i_1<i_2<\mathrm{}<i_e`$ be the excedances of $`\pi `$ and $`j_1<j_2<\mathrm{}<j_{ne}`$ the remaining positions. It characterizes $`321`$-avoiding permutations that both subwords $`\pi _{i_1}\pi _{i_2}\mathrm{}\pi _{i_e}`$ and $`\pi _{j_1}\pi _{j_2}\mathrm{}\pi _{j_{ne}}`$ are increasing. Thus any $`321`$-avoiding permutation is uniquely determined by its excedances and excedance letters.
There are several correspondences between restricted permutations and lattice paths, in particular, Dyck paths. A Dyck path is a path in the $`(x,y)`$-plane from the origin to $`(2n,0)`$ with steps $`[1,1]`$ (called up-steps) and $`[1,1]`$ (called down-steps) that never falls below the $`x`$-axis.
For $`321`$-avoiding permutations such a bijection was given by Billey, Jockusch and Stanley ; for $`132`$-avoiding permutations Krattenthaler proposed a correspondence to Dyck paths in . In Section 3 we will show that the Dyck path obtained for any $`\pi 𝒮_n(321)`$ by the first mentioned correspondence and the Dyck path associating by Krattenthaler’s correspondence with the image (with respect to our bijection) $`\sigma 𝒮_n(132)`$ of $`\pi `$ are the same.
Moreover, it will turn out that the diagram of a $`132`$-avoiding permutation is closed related to the corresponding Dyck path. This yields a simple explanation for the connections between the number of inversions of the permutation and several parameters of the Dyck path recently appeared in . Further, we use this relation to enumerate restricted partitions of prescribed rank.
In Section 4 the diagram approach will be used to obtain some enumerative results concerning the restriction of $`132`$-avoiding permutations by additional patterns. These results are already known (see ) but we will give a bijective proof of them.
The paper ends with a note on how to obtain the number of occurrences of the pattern $`132`$ in an arbitrary permutation via the diagram.

2 A bijection between $`132`$-avoiding and $`321`$-avoiding permutations

Let $`𝒴_n:=\{(\lambda _1,\mathrm{},\lambda _{n1}):0\lambda _{n1}\lambda _{n2}\mathrm{}\lambda _1n1,\lambda _ini\text{ for all }i\}`$ be the set of partitions whose Young diagram fits in the shape $`(n1,n2,\mathrm{},1)`$. (We will identify a partition with its Young diagram and vice versa.) In \[15, Sect. 3.2\] (or ), we describe a bijection $`𝒮_n(321)𝒴_n`$ which takes the permutation $`\pi `$ with excedances $`i_1,\mathrm{},i_e`$ to the diagram with corners $`(i_k,n+1\pi _{i_k})`$ where $`k=1,\mathrm{},e`$. For $`132`$-avoiding permutations a simple correspondence to partitions with restricted diagram can be given, as well.
The key object in our derivation is the diagram of a permutation (for an introduction see \[10, chap. 1\]). Given a permutation $`\pi 𝒮_n`$, we obtain the diagram $`D(\pi )`$ of $`\pi `$ as follows. Let $`\pi `$ be represented by an $`n\times n`$-array with a dot in each of the squares $`(i,\pi _i)`$. (The other cells are white.) Shadow all squares due south or due east of some dot and the dotted cell itself. The diagram $`D(\pi )`$ is defined as the region left unshaded after this procedure.

###### Example 2.1

The diagram of $`\pi =\mathrm{4\hspace{0.25em}2\hspace{0.25em}8\hspace{0.25em}3\hspace{0.25em}6\hspace{0.25em}9\hspace{0.25em}7\hspace{0.25em}5\hspace{0.25em}1\hspace{0.25em}10}𝒮_{10}`$ contains the white squares of

By the construction, each of the connected components of $`D(\pi )`$ is a Young diagram. Their corners are defined to be the elements of the essential set $`(\pi )`$ of the permutation $`\pi `$. In , Fulton introduced this set which together with a rank function was used as a tool for algebraic treatment of Schubert polynomials. In , Eriksson and Linusson characterized the essential sets that can arise from arbitrary permutations, as well as those coming from certain classes of permutations.
It is very easy to characterize the diagrams of $`132`$-avoiding permutations.

###### Theorem 2.2

Let $`\pi 𝒮_n`$ be a permutation not equal to the identity. Then $`\pi `$ is $`132`$-avoiding if and only if its diagram consists of only one component and $`(1,1)D(\pi )`$.

Proof. If there are indices $`i<j<k`$ such that $`\pi _i<\pi _k<\pi _j`$, then the square $`(j,\pi _k)`$ belongs to $`D(\pi )`$, but it is not connected with $`(1,1)`$:

Clearly, the existence of such a square is also sufficient for $`\pi `$ containing the pattern $`132`$.
Note that the square $`(1,1)`$ must be an element of $`D(\pi )`$ for any $`132`$-avoiding permutation $`\pi \mathrm{id}`$, otherwise we would have $`\pi _1=1`$ and hence $`\pi _i=i`$ for all $`i=1,\mathrm{},n`$. $`\mathrm{}`$

Thus the diagram $`D(\pi )`$ of a permutation $`\pi 𝒮_n(132)`$ is the graphical representation of a partition. By construction, $`D(\pi )`$ is just the diagram of an element of $`𝒴_n`$: the square $`(i,j(i))`$ belongs to $`D(\pi )`$ if and only if no index $`ki`$ satisfies $`\pi _kj`$. Thus we have $`j(i)ni`$.
This yields a simple bijection between $`321`$-avoiding and $`132`$-avoiding permutations on $`\{1,\mathrm{},n\}`$ which is in the following denoted by $`\mathrm{\Phi }`$.
Let $`i_1,\mathrm{},i_e`$ be the excedances of $`\pi 𝒮_n(321)`$. Then the diagram of the corresponding permutation $`\mathrm{\Phi }(\pi )`$ is equal to the Young diagram with corners $`(i_k,n+1\pi _{i_k}),k=1,\mathrm{},e`$. Recovering $`\mathrm{\Phi }(\pi )`$ from $`D(\mathrm{\Phi }(\pi ))`$ is trivial: row by row, put a dot in the leftmost shaded square such that there is exactly one dot in each column.

###### Example 2.3

For the permutation $`\pi =\mathrm{1\hspace{0.25em}4\hspace{0.25em}7\hspace{0.25em}2\hspace{0.25em}3\hspace{0.25em}8\hspace{0.25em}5\hspace{0.25em}6\hspace{0.25em}10\hspace{0.25em}9}𝒮_{10}(321)`$ we have $`𝖤(\pi )=\{2,3,6,9\}`$. Hence it corresponds to the permutation with the diagram

and we obtain $`\mathrm{\Phi }(\pi )=\mathrm{8\hspace{0.25em}9\hspace{0.25em}5\hspace{0.25em}4\hspace{0.25em}6\hspace{0.25em}7\hspace{0.25em}2\hspace{0.25em}3\hspace{0.25em}10\hspace{0.25em}1}𝒮_{10}(132)`$.

As observed by Fulton in , every row of a permutation diagram containing a white corner (that is an element of the essential set) corresponds to a descent. Thus we have $`\mathrm{𝖽𝖾𝗌}(\mathrm{\Phi }(\pi ))=\mathrm{𝖾𝗑𝖼}(\pi )`$ for all $`\pi 𝒮_n(321)`$. But there is more to it than that: the excedance set of $`\pi `$ and the descent set of $`\mathrm{\Phi }(\pi )`$ have not only the same number of elements; the sets are even identical.

###### Proposition 2.4

We have $`𝖤(\pi )=𝖣(\mathrm{\Phi }(\pi ))`$ for all $`\pi 𝒮_n(321)`$.

Proof. Any excedance $`i`$ of $`\pi `$ corresponds to a corner $`(i,n+1\pi _i)`$ of $`D(\mathrm{\Phi }(\pi ))`$. Obviously, by constructing $`\mathrm{\Phi }(\pi )`$ from its diagram we obtain a descent of $`\mathrm{\Phi }(\pi )`$ at the position $`i`$. $`\mathrm{}`$

Every $`321`$-avoiding permutation is completely determined by its excedances and excedance letters. Our bijection shows that it is sufficient for fixing a $`132`$-avoiding permutation to know the descents, the descent bottoms, and the first letter.
Let $`i_1<\mathrm{}<i_e`$ be the excedances of $`\pi 𝒮_n(321)`$, and let $`\sigma :=\mathrm{\Phi }(\pi )`$. Then we have

$`\sigma _1=n+2\pi _{i_1},`$
$`\sigma _{i_k+1}=n+2\pi _{i_{k+1}}\text{for }k=1,\mathrm{},e1,`$
$`\sigma _{i_e+1}=1.`$
It is clear from the construction that these elements are precisely the left-to-right minima of $`\sigma `$. (A left-to-right minimum of a permutation $`\sigma `$ is an element $`\sigma _i`$ which is smaller than all elements to its left, i.e., $`\sigma _i<\sigma _j`$ for every $`j<i`$.) Based on this, we can determine the permutation $`\sigma `$ since $`\sigma `$ is $`132`$-avoiding.

###### Example 2.5

Let again $`\pi =1\underset{¯}{4}\underset{¯}{7}\mathrm{\hspace{0.25em}2\hspace{0.25em}3}\underset{¯}{8}\mathrm{\hspace{0.25em}5\hspace{0.25em}6}\underset{¯}{10}\mathrm{\hspace{0.25em}9}𝒮_{10}(321)`$. (The underlined positions are just the excedances of $`\pi `$.) As described above, we obtain the left-to-right minima of $`\mathrm{\Phi }(\pi )`$ and their positions:

$$8\mathrm{\hspace{0.25em}5\hspace{0.25em}4}\mathrm{\hspace{0.25em}2}\mathrm{\hspace{0.25em}1},$$

and hence, by putting the remaining elements $`a=3,6,7,9,10`$ on the first possible position following $`a1`$, the permutation $`\mathrm{\Phi }(\pi )=\mathrm{8\hspace{0.25em}9\hspace{0.25em}5\hspace{0.25em}4\hspace{0.25em}6\hspace{0.25em}7\hspace{0.25em}2\hspace{0.25em}3\hspace{0.25em}10\hspace{0.25em}1}`$.

###### Remarks 2.6

*
* In Chapter 1 of , Macdonald defined the dominant permutations. This special case of vexillary (or $`2143`$-avoiding) permutations is characterized by the following equivalent conditions:

+ $`D(\pi )`$ is the diagram of a partition.
    + The code $`c`$ of $`\pi `$ is a partition, that is, $`c_ic_{i+1}`$ for all $`i=1,\mathrm{},n1`$.
(For a permutation $`\pi `$ the $`i`$th component of its code counts the number of indices $`j>i`$ satisfying $`\pi _j<\pi _i`$.) As mentioned above, we may assume in (i) that $`D(\pi )`$ is an element of $`𝒴_n`$. Thus $`𝒮_n(132)`$ is precisely the set of all dominant permutations. In particular, there are $`C_n`$ such permutations.
* For any permutation $`\pi 𝒮_n`$ the number of squares in the $`i`$th row of $`D(\pi )`$ is equal to the $`i`$th component $`c_i`$ of its code (see \[10, p. 9\]). Hence it follows that $`|D(\pi )|=c_1+\mathrm{}+c_n=\mathrm{𝗂𝗇𝗏}(\pi )`$, where $`\mathrm{𝗂𝗇𝗏}(\pi )`$ denotes the number of inversions of $`\pi `$.
* In \[15, Sect. 3.2\] (or in ), we prove that the number of excedances has the Narayana distribution over $`𝒮_n(321)`$. Consequently, the number of diagrams fitting in the shape $`(n1,n2,\mathrm{},1)`$ and having $`k`$ corners is given by the Narayana number $`N(n,k+1)=\frac{1}{n}\left(\genfrac{}{}{0pt}{}{n}{k}\right)\left(\genfrac{}{}{0pt}{}{n}{k+1}\right)`$. Thus the bijection immediately shows that the statistic $`\mathrm{𝖽𝖾𝗌}`$ is Narayana distributed over $`𝒮_n(132)`$.
* Also in \[15, Sect. 2.3\], an involution on $`𝒮_n(321)`$ was established which proves the symmetry of the joint distribution of the pair $`(\mathrm{𝖾𝗑𝖼},\mathrm{𝗂𝗇𝗏})`$ over $`𝒮_n(321)`$. For $`\pi 𝒮_n(321)`$ let $`\sigma =\sigma _1\mathrm{}\sigma _n`$ be the image with respect to this map. Then the reverse $`\sigma _n\mathrm{}\sigma _1𝒮_n(123)`$ corresponds to $`\mathrm{\Phi }(\pi )𝒮_n(132)`$ by the bijection due to Simion and Schmidt (see \[17, Prop. 19\]).
* In \[7, p. 7\], Fulmek has given a ”‘graphical”’ construction of a map from $`𝒮_n`$ to the set of Dyck paths of length $`2n`$ whose restrictions on $`𝒮_n(321)`$ and $`𝒮_n(312)`$, respectively, are bijections. Based on the graph of a permutation $`\pi 𝒮_n`$ he considered the union of all points which are in the southeast of some left-to-right maximum. The corresponding path is defined to be the boundary of this region. It is easy to see that the region above the path is just the connected component of all squares of rank zero belonging to the diagram of the inverse of $`\pi _n\pi _{n1}\mathrm{}\pi _1`$. (See also  for a description how to obtain an arbitrary permutation from its ranked essential set.)

3 Correspondences to Dyck Paths

For $`321`$-avoiding, as well as for $`132`$-avoiding permutations one-to-one correspondences to lattice paths were given by several authors. In \[1, p. 361\], Billey, Jockusch and Stanley established a bijection $`\mathrm{\Psi }_{BJS}`$ between $`321`$-avoiding permutations on $`\{1,\mathrm{},n\}`$ and Dyck paths of length $`2n`$. Recently in \[9, Sect. 2\], Krattenthaler exhibited a Dyck path correspondence $`\mathrm{\Psi }_K`$ for $`132`$-avoiding permutations. Our bijection $`\mathrm{\Phi }`$ translates these constructions into each other.

###### Theorem 3.1

Let $`\pi 𝒮_n(321)`$. Then we have $`\mathrm{\Psi }_{BJS}(\pi )=\mathrm{\Psi }_K(\mathrm{\Phi }(\pi ))`$.

Proof. Let $`\pi 𝒮_n(321)`$ with the excedances $`i_1<\mathrm{}<i_e`$, and let $`\sigma :=\mathrm{\Phi }(\pi )`$. The bijection $`\mathrm{\Psi }_{BJS}`$ constructs the Dyck path corresponding to $`\pi `$ as follows:

* Let $`a_k:=\pi _{i_k}1`$ for $`k=1,\mathrm{},e`$ and $`a_0:=0,a_{e+1}:=n`$. Furthermore, let $`b_k:=i_k`$ for $`k=1,\mathrm{},e`$ and $`b_0:=0,b_{e+1}:=n`$.
* Generate the Dyck path (starting at the origin) by adjoining $`a_ka_{k1}`$ up-steps and $`b_kb_{k1}`$ down-steps for $`k=1,\mathrm{},e+1`$.

As shown in the preceding section, the elements

$`c_1`$ $`:=`$ $`\sigma _1=n+2\pi _{i_1},`$
$`c_{k+1}`$ $`:=`$ $`\sigma _{i_k+1}=n+2\pi _{i_{k+1}}\text{for }k=1,\mathrm{},e1,`$
$`c_{e+1}`$ $`:=`$ $`\sigma _{i_e+1}=\mathrm{\hspace{0.33em}1}`$
are the left-to-right minima of $`\sigma `$. With the convention $`c_0:=n+1`$ we have $`c_{k1}c_k=a_ka_{k1}`$ for all $`k=1,\mathrm{},e+1`$. For the number $`d_k`$ of the positions between the $`k`$th and (including) the $`(k+1)`$st left-to-right minimum we obtain $`d_k=b_kb_{k1}`$ for $`k=1,\mathrm{},e+1`$. (Let $`n+1`$ be the position of the imaginary $`(e+2)`$nd minimum, so $`d_{e+1}=nb_e`$.)
Hence the translation of $`\mathrm{\Psi }_{BJS}`$ by $`\mathrm{\Phi }`$ constructs the Dyck path corresponding to $`\sigma 𝒮_n(132)`$ as follows:

* Let $`c_1>\mathrm{}>c_{e+1}`$ be the left-to-right minima of $`\sigma `$. Furthermore, let $`d_k`$ be one plus the number of the letters in $`\sigma `$ between $`c_k`$ and $`c_{k+1}`$ for $`k=1,\mathrm{},e+1`$. Initialize $`c_0:=n+1`$.
* Generate the Dyck path (starting at the origin) by adjoining $`c_{k1}c_k`$ up-steps and $`d_k`$ down-steps for $`k=1,\mathrm{},e+1`$.

But this is precisely the description of $`\mathrm{\Psi }_K`$ proposed in . $`\mathrm{}`$

###### Example 3.2

Let $`\pi =\mathrm{1\hspace{0.25em}4\hspace{0.25em}7\hspace{0.25em}2\hspace{0.25em}3\hspace{0.25em}8\hspace{0.25em}5\hspace{0.25em}6\hspace{0.25em}10\hspace{0.25em}9}𝒮_{10}(321)`$, and let $`\sigma =\mathrm{\Phi }(\pi )=\mathrm{8\hspace{0.25em}9\hspace{0.25em}5\hspace{0.25em}4\hspace{0.25em}6\hspace{0.25em}7\hspace{0.25em}2\hspace{0.25em}3\hspace{0.25em}10\hspace{0.25em}1}`$. Billey-Jockusch-Stanley’s bijection takes $`\pi `$ to the Dyck path

which is exactly the path corresponding to $`\sigma `$ by Krattenthaler’s bijection.

The following results use the (now obvious) fact that the Dyck path $`\mathrm{\Psi }_K(\pi )`$ and the diagram of a $`132`$-avoiding permutation $`\pi `$ are closely related to each other. Given a permutation $`\pi 𝒮_n(132)`$, its diagram $`D(\pi )`$ is just the region bordered by the lines between the lattice points $`(0,0)`$ and $`(n,n)`$ and between $`(n,n)`$ and $`(2n,0)`$, respectively, and the path $`\mathrm{\Psi }_K(\pi )`$. (The northwest-to-southeast diagonals correspond to the diagram columns.)

###### Example 3.3

For $`\pi =\mathrm{8\hspace{0.25em}9\hspace{0.25em}5\hspace{0.25em}4\hspace{0.25em}6\hspace{0.25em}7\hspace{0.25em}2\hspace{0.25em}3\hspace{0.25em}10\hspace{0.25em}1}𝒮_{10}(132)`$ we obtain:

In , the authors studied the statistic $`e_k`$ that counts the number of increasing subsequences of length $`k+1`$ in a permutation. Expressing $`e_k(\pi )`$ in terms of the Dyck path $`\mathrm{\Psi }_K(\pi )`$, some applications were given in  which relate various combinatorial structures to $`132`$-avoiding permutations. The translation of the statistic into Dyck path characteristics becomes now immediately clear.

###### Corollary 3.4

For any permutation $`\pi 𝒮_n(132)`$ consider the associated Dyck path $`\mathrm{\Psi }_K(\pi )`$ and denote the height of the starting point of its $`i`$th step by $`w_i(\pi )`$. Then we have

* $`w_1(\pi )+\mathrm{}+w_{2n}(\pi )=n^22\mathrm{𝗂𝗇𝗏}(\pi )`$.
* $`w_{i_1}(\pi )+\mathrm{}+w_{i_s}(\pi )=\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)\mathrm{𝗂𝗇𝗏}(\pi )`$, where $`i_1,\mathrm{},i_s`$ are the indices of the down-steps.

Proof. As remarked in 2.6b), we have $`|D(\pi )|=\mathrm{𝗂𝗇𝗏}(\pi )`$ for all $`\pi 𝒮_n`$.
a) The sum of heights of the Dyck path $`(\text{})^n(\text{})^n`$ (where exponentiation denotes repetition) is equal to $`n^2`$. Any square of $`D(\pi )`$ reduces this value by 2:

b) The sum of all down-step heights counts the number of squares of the slanting lattices below the path:

For the path $`(\text{})^n(\text{})^n`$ this number is $`\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)`$. $`\mathrm{}`$

###### Remarks 3.5

*
* The sum of the heights of all steps is easily seen to equal the area of the Dyck path. It was shown in \[2, Sect. 3.1\] that the sum relates to the statistic $`2e_1+e_0`$ for $`132`$-avoiding permutations.
* For a correspondence between fountains of coins and $`132`$-avoiding permutations,  used that $`e_1(\pi )+e_0(\pi )`$ is equal to the sum of the heights of the down-steps in $`\mathrm{\Psi }_K(\pi )`$.

On the other hand, from  we can derive enumerative results for the partitions in $`𝒴_n`$ and (using the bijection $`\mathrm{\Phi }`$) for $`321`$-avoiding permutations.
By \[2, Prop. 7\], the distribution of right-to-left maxima in $`𝒮_n(132)`$ is given by the ballot numbers. (A right-to-left maxima of a permutation $`\pi `$ is an element $`\pi _i`$ which is larger than all $`\pi _j`$ with $`j>i`$.) The number of permutations in $`𝒮_n(132)`$ with $`k`$ such maxima equals the ballot number

$$b(n1,nk)=\frac{k}{2nk}\left(\genfrac{}{}{0pt}{}{2nk}{n}\right).$$

Among other things, the ballot number $`b(n,k)`$ counts the number of the lattice paths from $`(0,0)`$ to $`(n+k,nk)`$ with up-steps and down-steps only, never falling below the $`x`$-axis. It is well known that $`b(n,k)=\left(\genfrac{}{}{0pt}{}{n+k}{n}\right)\left(\genfrac{}{}{0pt}{}{n+k}{n+1}\right)=\frac{n+1k}{n+1}\left(\genfrac{}{}{0pt}{}{n+k}{n}\right)`$. (For instance, see \[6, p. 73\].)
For their bijective proof,  used Krattenthaler’s map: $`\mathrm{\Psi }_K`$ translates any right-to-left maximum of $`\pi 𝒮_n(132)`$ into a return of the associated Dyck path. (A return of a Dyck path is a down-step landing on the $`x`$-axis.). The number of returns of Dyck paths is known to have a distribution given by $`b(n1,nk)`$. (This result was given in .)

###### Corollary 3.6

The number of permutations $`\pi 𝒮_n(321)`$ with $`k1`$ elements $`\pi _i=i+1`$ is equal to $`b(n1,nk)`$.

Proof. By the construction of $`\mathrm{\Psi }_{BJS}(\pi )`$, a return, except the last (down-) step, appears if and only if $`i`$ is an excedance of $`\pi `$ with $`\pi _i=i+1`$. The very last step of $`\mathrm{\Psi }_{BJS}(\pi )`$ is a return by definition. $`\mathrm{}`$

###### Corollary 3.7

The number of diagrams fitting in $`(n1,n2,\mathrm{},1)`$ with $`k1`$ corners in the diagonal $`i+j=n`$ equals $`b(n1,nk)`$.

###### Remark 3.8

In comparison with this, the Narayana number $`N(n,k)=\frac{1}{n}\left(\genfrac{}{}{0pt}{}{n}{k1}\right)\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$ counts the number of restricted diagrams with $`k1`$ corners (see also Remark 2.6c)).
The condition $`i+j=n`$ on a corner $`(i,j)`$ of the diagram $`D(\pi )`$ also occurs in the following section in context with the pattern $`213`$ in a $`132`$-avoiding permutation $`\pi `$.

We can also use the relation between diagrams and Dyck paths to obtain more information about the restricted partitions. For instance, the number of partitions in $`𝒴_n`$ of a prescribed rank can easily be derived from a known result for paths. (The (Durfee) rank of a partition $`\lambda `$, denoted by $`\mathrm{rank}(\lambda )`$, is the largest integer $`i`$ for which $`\lambda _ii`$, or equivalently, the length of the main diagonal of the diagram of $`\lambda `$.)

###### Lemma 3.9

Let $`\pi 𝒮_n(132)`$. With the above notation we have $`w_{n+1}(\pi )=n2\mathrm{rank}(D(\pi ))`$.

Proof. This is an immediate consequence of the relation between $`D(\pi )`$ and $`\mathrm{\Psi }_K(\pi )`$. $`\mathrm{}`$

###### Theorem 3.10

Let $`r(n,k)`$ denote the number of partitions in $`𝒴_n`$ of rank $`k`$. Then we have

$$r(n,k)=\left(\frac{n+12k}{n+1k}\left(\genfrac{}{}{0pt}{}{n}{k}\right)\right)^2\text{for all }0k\frac{n}{2}.$$

Proof. Given a partition $`\lambda 𝒴_n`$ of rank $`k`$, let $`\pi 𝒮_n(132)`$ be the (uniquely determined) permutation whose diagram equals the diagram of $`\lambda `$. By the lemma, both the first ”half” and the second ”half” of $`\mathrm{\Psi }_K(\pi )`$ are paths from $`(0,0)`$ to $`(n,n2k)`$ only consisting of up-steps and down-steps and never falling below the $`x`$-axis (for the latter one, consider the reflection on the line $`x=n`$). Thus, $`r(n,k)`$ is the square of the number of precisely those paths. Feller’s Ballot Theorem (see \[6, p. 73\]) enumerates the paths from the origin to $`(n,t)`$ with $`n,t1`$ which neither touch (that is, there is no return) or cross the $`x`$-axis. Their number is equal to $`\frac{t}{n}\left(\genfrac{}{}{0pt}{}{n}{\frac{nt}{2}}\right)`$. Consequently, there are

$$\frac{t+1}{n+1}\left(\genfrac{}{}{0pt}{}{n+1}{\frac{nt}{2}}\right)$$

paths from $`(0,0)`$ to $`(n,t)`$ where $`n,t0`$ with up-steps and down-steps never going below the $`x`$-axis (returns are allowed). To see this, insert an up-step before the first step and define its starting point to be the origin. The resulting path satisfies the conditions of Feller’s theorem. Conversely, each path from $`(0,0)`$ to $`(n+1,t+1)`$ without returns can easily be transformed into an admissible path by deleting the first (up-) step and redefining the origin. Taking $`t=n2k`$ we obtain

$$r(n,k)=\left(\frac{n2k+1}{n+1}\left(\genfrac{}{}{0pt}{}{n+1}{k}\right)\right)^2=\left(\frac{n+12k}{n+1k}\left(\genfrac{}{}{0pt}{}{n}{k}\right)\right)^2$$

for all $`k=0,\mathrm{},\frac{n}{2}`$. $`\mathrm{}`$

###### Remark 3.11

By the proof, the positive root $`q(n,k)`$ of $`r(n,k)`$ counts the number of paths which begin at the origin, end at $`(n,n2k)`$, consist of up-steps and down-steps, and stay above the $`x`$-axis. Clearly, $`q(n,0)=1`$ and $`q(n,\frac{n}{2})=C_{\frac{n}{2}}`$ for all $`n`$. Obviously, $`q(n,k)`$ satisfies the recurrence $`q(n,k)=q(n1,k1)+q(n1,k)`$. (The right-hand side is just the number of paths ending at $`(n1,n2k+1)`$ and $`(n1,n2k1)`$, respectively.) Thus the numbers $`q(n,k)`$ are exactly the entries in the counter diagonals of the Catalan’s triangle.

4 Forbidden patterns in 132-avoiding permutations

Now we will use the correspondence between $`𝒮_n(132)`$ and $`𝒴_n`$ for the enumeration of multiple restrictions on permutations. The results concerning the Wilf-equivalence of several pairs $`\{132,\tau \}`$ where $`\tau 𝒮_k`$ are already known, see , , , . (We say that $`\{132,\tau _1\}`$ and $`\{132,\tau _2\}`$ are Wilf-equivalent if $`|𝒮_n(132,\tau _1)|=|𝒮_n(132,\tau _2)|`$ for all $`n`$.) While the proofs given in these papers are analytical we present bijective ones.

###### Theorem 4.1

Let $`\pi 𝒮_n(132)`$ be a permutation not equal to the identity, and $`k3`$. Then

* $`\pi `$ avoids $`k(k1)\mathrm{}1`$ if and only if $`D(\pi )`$ has at most $`k2`$ corners. In particular, we have $`\mathrm{𝖽𝖾𝗌}(\pi )k2`$.
* $`\pi `$ avoids $`12\mathrm{}k`$ if and only if $`D(\pi )`$ contains the diagram $`(n+1k,nk,\mathrm{},1)`$.
* $`\pi `$ avoids $`213\mathrm{}k`$ if and only if every corner $`(i,j)`$ of $`D(\pi )`$ satisfies $`i+jn+3k`$.

Proof.
a)    Obviously, $`\pi `$ contains a decreasing subsequence of length $`k`$ if the diagram of $`\pi `$ has at least $`k1`$ corners. On the other hand, if there are at most $`k2`$ corners in $`D(\pi )`$, we have $`\mathrm{𝖽𝖾𝗌}(\pi )k2`$ and hence $`\pi 𝒮_n(k\mathrm{}1)`$. (Note that each corner of $`D(\pi )`$ corresponds to a descent in $`\pi `$.)

b) If the diagram $`(n+1k,nk,\mathrm{},1)`$ fits in $`D(\pi )`$ then we have $`\pi _in+3ki`$ for all $`i`$. Hence any increasing subsequence of $`\pi `$ is of length at most $`k1`$: if $`\pi _i=n+3ki`$ then $`i1`$ elements from $`i+k3`$ many ones in $`\{n+4ki,n+5ki,\mathrm{},n\}`$ appear in $`\pi _1\mathrm{}\pi _{i1}`$.
Conversely, let $`i`$ be the smallest integer with $`i+\pi _i<n+3k`$. Furthermore, choose $`j`$ such that $`\pi _j=n+3ki`$ (by definition of $`i`$, we have $`j>i`$), and let $`\pi _{i_1}<\mathrm{}<\pi _{i_{k2}}`$ be the elements of $`\{n+4ki,n+5ki,\mathrm{},n\}`$ which are not equal to $`\pi _1,\mathrm{},\pi _{i1}`$. Note that $`j<i_1<\mathrm{}<i_{k2}`$ since $`\pi `$ is $`132`$-avoiding. Thus $`\pi _i\pi _j\pi _{i_1}\mathrm{}\pi _{i_{k2}}`$ is an increasing sequence.

c)    Let $`(i,j)`$ be the top corner of $`D(\pi )`$ for which $`i+j<n+3k`$. By removing the rows $`1,\mathrm{},i`$ and the columns $`\pi _1,\mathrm{},\pi _i`$, we obtain the diagram of a permutation $`\sigma 𝒮_{ni}(132)`$ whose letters are in the same relative order as $`\pi _{i+1}\mathrm{}\pi _n`$ where $`\sigma _1=\pi _{i+1}j<\pi _i`$. As discussed in the proof of part b), the element $`\sigma _1`$ is the first one of an increasing

sequence of length $`(ni)\sigma _1+1`$ in $`\sigma `$. (Since $`\sigma _1j<n+3ki`$ the index $`l=1`$ is the smallest one with $`l+\sigma _l<(ni)+3k`$.) Clearly, the first $`j+1\sigma _1`$ terms are restricted by $`j`$. Thus there is an increasing sequence of length $`n(i+j)>k3`$ in $`\sigma `$ whose all elements are larger than $`\pi _i`$. Note that the elements $`j+1,j+2,\mathrm{},\pi _i1`$ appear in $`\pi _1\mathrm{}\pi _{i1}`$.
To prove the converse, suppose that every corner of $`D(\pi )`$ satisfies the condition given above. Then we have $`\pi _i+i>n+3k`$ for all $`i𝖣(\pi )`$. Hence for each descent $`i`$ of $`\pi `$ there exist at most $`k3`$ elements $`\pi _j`$ with $`j>i`$ and $`\pi _j>\pi _i`$. Since $`\pi `$ is $`132`$-avoiding these elements form an increasing sequence. Thus there is no pattern $`2134\mathrm{}k`$ in $`\pi `$. $`\mathrm{}`$

###### Remarks 4.2

*
* From the statement of a), it follows that the maximum length of a decreasing subsequence of $`\pi 𝒮_n(132)`$ is equal to the number of corners of $`D(\pi )`$ plus one, or in terms of permutation statistics, $`\mathrm{𝖽𝖾𝗌}(\pi )+1`$. It is well-known that the length of the longest decreasing sequence can easily be obtained for any permutation in $`𝒮_n`$ via the Robinson-Schensted correspondence: it is just the number of rows of one of the tableaux $`P`$ and $`Q`$ corresponding to $`\pi 𝒮_n`$.
It is clear from the construction that every left-to-right-minimum of $`\pi `$ appears in the first column of $`P`$. Any other entry of this column must be the largest element of a $`132`$-pattern in $`\pi `$. Hence in case of $`132`$-avoiding permutations the elements of the first column of $`P`$ are precisely the left-to-right-minima. As observed in Section 2, these minima are just the descent bottoms and the first letter of $`\pi `$. Thus for $`\pi 𝒮_n(132)`$ the tableau $`P`$ has $`\mathrm{𝖽𝖾𝗌}(\pi )+1`$ rows.
* By part b), the length of a longest increasing subsequence of $`\pi 𝒮_n(132)`$ equals the maximum value of $`n+1i\lambda _i`$ with $`1in1`$ where $`\lambda _i0`$ is the length of the $`i`$th row of $`D(\pi )`$. This also follows from Remark 2.6b) according to which $`\lambda _i`$ is equal to the $`i`$th component of the code of $`\pi `$. Thus $`ni\lambda _i`$ counts the number of elements on the right of $`\pi _i`$ which are larger than $`\pi _i`$. (Since $`\pi `$ contains no pattern $`132`$ these elements appear in increasing order.)

###### Corollary 4.3

$`|𝒮_n(132,k(k1)\mathrm{}1)|=\frac{1}{n}_{i=1}^{k1}\left(\genfrac{}{}{0pt}{}{n}{i}\right)\left(\genfrac{}{}{0pt}{}{n}{i1}\right)`$ for all $`n`$ and $`k3`$.

Proof. As mentioned in 2.6c) the number of partitions in $`𝒴_n`$ whose diagram has exactly $`i`$ corners is equal to the Narayana number $`N(n,i+1)=\frac{1}{n}\left(\genfrac{}{}{0pt}{}{n}{i}\right)\left(\genfrac{}{}{0pt}{}{n}{i+1}\right)`$. Thus there are $`_{i=0}^{k2}N(n,i+1)`$ diagrams with at most $`k2`$ corners. $`\mathrm{}`$

The following result also follows from a special case of \[13, Th. 2.6\].

###### Corollary 4.4

$`|𝒮_n(132,12\mathrm{}k)|=|𝒮_n(132,213\mathrm{}k)|`$ for all $`n`$ and $`k3`$.

Proof. There is a simple bijection between the restricted diagrams which contain $`(n+1k,nk,\mathrm{},1)`$ and those ones whose all corners satisfy the condition $`i+jn+3k`$. (Note that the empty diagram associating with the identity in $`𝒮_n`$ belongs to the latter ones.) For each corner $`(i,j)`$ of the diagram $`(n+1k,nk,\mathrm{},1)`$ we have $`i+j=n+2k`$. Thus every diagram containing $`(n+1k,nk,\mathrm{},1)`$ is uniquely determined by its corners outside this shape (which are precisely the corners with $`i+jn+3k`$). Given such a diagram $`D`$, the corresponding diagram $`D^{}`$ is defined to be this one whose corners are the corners of $`D`$ which are not contained in $`(n+1k,nk,\mathrm{},1)`$. Conversely, for any diagram $`D^{}`$ whose all corners satisfy $`i+jn+3k`$ we construct the corresponding diagram $`D`$ as the union of $`D^{}`$ and $`(n+1k,nk,\mathrm{},1)`$. $`\mathrm{}`$

While the above conditions can be checked without effort, the characterization of the avoidance of the patterns considered now is more technical.
Given a permutation $`\pi 𝒮_n(132)`$, let $`\lambda _1,\mathrm{},\lambda _l`$ be the positive parts of the partition with the diagram $`D(\pi )`$. Let $`a_i:=n(i+\lambda _i)`$ for $`i=1,\mathrm{},l`$ and $`b_i:=n(i+\lambda _i^{})`$ for $`i=1,\mathrm{},\lambda _1`$ where $`\lambda ^{}`$ denotes the conjugate of $`\lambda `$. Furthermore, for $`i=1,\mathrm{},l`$ let $`h_i`$ be the length of the longest increasing sequence in $`b_{\lambda _i}b_{\lambda _i1}\mathrm{}b_1`$ whose first element is $`b_{\lambda _i}`$. We call the number $`h_i`$ the height of $`a_i`$.
For example, the permutation $`\pi =\mathrm{8\hspace{0.25em}9\hspace{0.25em}5\hspace{0.25em}4\hspace{0.25em}6\hspace{0.25em}7\hspace{0.25em}2\hspace{0.25em}3\hspace{0.25em}10\hspace{0.25em}1}𝒮_{10}(132)`$ generates the diagram of $`\lambda =(7,7,4,3,3,3,1,1,1)`$:

So we obtain $`a(\pi )=(2,1,3,3,2,1,2,1,0)`$ and $`h(\pi )=(3,3,1,2,2,2,1,1,1)`$. (Note that we have $`b(\pi )=(0,2,1,3,3,2,1)`$.)

###### Theorem 4.5

Let $`\pi 𝒮_n(132)`$ be a permutation, and let $`a(\pi ),h(\pi )`$ be as above. Then $`\pi `$ avoids the pattern $`s(s+1)\mathrm{}k12\mathrm{}(s1)`$, where $`2sk`$ and $`k3`$, if and only if the longest decreasing subsequence of $`a(\pi )`$ which ends in an element of height $`s1`$ is of length at most $`ks`$.

Proof. Let $`i_1`$ be an integer such that $`a_{i_1}a_i`$ for all $`i<i_1`$. Hence a decreasing sequence whose first element is $`a_{i_1}`$ can not be extended to the left. Then $`\lambda _{i_1}<\lambda _{i_11}`$ where $`\lambda _0:=n`$. (Note that the condition $`\lambda _i<\lambda _{i1}`$ is equivalent to $`a_{i1}a_i`$.) As shown in Section 2, the element $`\pi _{i_1}`$ is a left-to-right minimum of $`\pi `$. Thus any increasing subsequence in $`\pi `$ which starts with $`\pi _{i_1}`$ is left maximal. In particular, we have $`\pi _{i_1}=\lambda _{i_1}+1`$.
Now let $`a_j`$ be an element of $`a(\pi )`$ with $`a_j<a_{i_1}`$, $`j>i_1`$, and $`a_{i_1+1},\mathrm{},a_{j1}>a_j`$. Since $`ji>\lambda _i\lambda _j`$ for $`i=i_1,i_1+1,\mathrm{},j1`$, all the elements $`\lambda _j+1,\lambda _j+2,\mathrm{},\lambda _{i_1}`$ occur in $`\pi _{i_1+1}\pi _{i_1+2}\mathrm{}\pi _{j1}`$. Hence $`\pi _{i_1}<\pi _j`$.
Consequently, if $`a_{i_1}>a_{i_2}>\mathrm{}>a_{i_r}`$ (with $`i_1<i_2<\mathrm{}<i_r`$) is a sequence such that there is no integer $`i`$ with $`i_l<i<i_{l+1}`$ and $`a_{i_l}>a_ia_{i_{l+1}}`$ for any $`l`$, then $`\pi _{i_1}<\pi _{i_2}<\mathrm{}<\pi _{i_r}`$ is an increasing subsequence of $`\pi `$ which is maximal with respect to the property that $`\pi _{i_1}`$ and $`\pi _{i_r}`$ are its first and last elements, respectively. (Since $`\pi `$ avoids the pattern $`132`$, the relations $`\pi _{i_1}<\pi _{i_l}`$ for $`l=2,\mathrm{},r`$ imply that $`\pi _{i_1},\mathrm{},\pi _{i_r}`$ are increasing.)
It is clear from the definition that $`h_i`$ is the maximal length of an increasing sequence of dots southwest of the dot representing $`\pi _i`$ which begins at the top dot southwest of $`(i,\pi _i)`$. Thus, if $`a_{i_r}`$ is an element of height $`s1`$ then there exist at least $`s1`$ integers $`i_r<j_1<j_2<\mathrm{}<j_{s1}`$ with $`\pi _{j_1}<\mathrm{}<\pi _{j_{s1}}<\pi _{i_r}`$. Since $`\pi `$ is $`132`$-avoiding, we even have $`\pi _{j_1}<\mathrm{}<\pi _{j_{s1}}<\pi _{i_1}`$. Choosing $`i_1`$ and $`i_r`$ minimal and maximal, respectively, proves the assertion. $`\mathrm{}`$

For any permutation $`\pi 𝒮_n(132)`$ denote by $`l_s(\pi )`$ the largest integer $`l`$ such that $`\pi `$ contains the shifted pattern $`s(s+1)\mathrm{}l12\mathrm{}(s1)`$ where $`s2`$. By the theorem, $`l_s(\pi )`$ is equal to $`s1`$ plus the maximum length of a decreasing sequence in $`a(\pi )`$ whose smallest element is of height at least $`s1`$.
It is clear that the sequence $`L(\pi ):=(l_2(\pi )1,l_3(\pi )2,\mathrm{})`$ is a partition, that is, $`l_s(\pi )+1l_{s+1}(\pi )`$ for all $`s`$. Since $`\pi `$ avoids $`s(s+1)\mathrm{}k12\mathrm{}(s1)`$ if and only if no pattern $`(k+2s)`$
$`(k+3s)\mathrm{}k12\mathrm{}(k+1s)`$ occurs in $`\pi ^1`$, the partition $`L(\pi ^1)`$ is the conjugate of $`L(\pi )`$. (Obviously, for any permutation $`\pi 𝒮_n`$ the diagram of the inverse $`\pi ^1`$ is just the transpose of $`D(\pi )`$. Hence the set $`𝒮_n(132)`$ is closed under inversion.)

###### Remark 4.6

Using the relation between the diagram $`D(\pi )`$ and the Dyck path $`\mathrm{\Psi }_K(\pi )`$, it is easy to see that the number $`a_i`$ is just the height at which the $`i`$th down-step of $`\mathrm{\Psi }_K(\pi )`$ ends. (We only consider the down-steps before the last up-step.) The numbers $`b_i`$ needed for the construction of $`h(\pi )`$ are (in reverse order) the starting heights of the up-steps after the first down-step. Thus the height $`h_i`$ is precisely the number of (not necessarily consecutive) up-steps of increasing starting heights following the $`i`$th down-step in $`\mathrm{\Psi }_K(\pi )`$. Hence, in case of $`s=2`$ the theorem yields the second part of \[9, Lemma $`\mathrm{\Phi }`$\].

We shall prove now that the number of permutations in $`𝒮_n`$ which avoid both $`132`$ and the pattern $`s(s+1)\mathrm{}k12\mathrm{}(s1)`$ with $`k3`$ and $`s\{1,\mathrm{},k\}`$ does not depend on $`s`$.

###### Proposition 4.7

Let $`\pi 𝒮_n(132)`$, and let $`l`$ be the maximum length of an increasing subsequence of $`\pi `$. Then $`\pi `$ corresponds in a one-to-one fashion to a permutation $`\sigma 𝒮_n(132)`$ with $`l_2(\sigma )=l`$.

Proof. Let $`\lambda `$ and $`\mu `$ be the partitions whose diagrams equal $`D(\pi )`$ and $`D(\sigma )`$, respectively. Given $`\lambda =(\lambda _1,\mathrm{},\lambda _{n1})𝒴_n`$, we define the sequence $`\widehat{\mu }`$ by

$$\widehat{\mu }_i:=\{\begin{array}{ccc}\lambda _i+1& & \text{if }\lambda _i+i<n\hfill \\ 0& & \text{if }\lambda _i+i=n\hfill \end{array}$$

for $`i=1,\mathrm{},n1`$, and obtain the partition $`\mu `$ by sorting $`\widehat{\mu }`$. (Delete all parts $`\widehat{\mu }_i=0`$ with nonzero $`\widehat{\mu }_{i+1}`$ and add the corresponding number of zeros at the end of the sequence.) It is obvious that $`\mu 𝒴_n`$, and it is easy to see that the map $`\lambda \mu `$ is injective, and thus a bijection on $`𝒴_n`$. To recover $`\lambda `$ from $`\mu `$, first set $`\widehat{\lambda }_i:=\mu _i1`$ for all positive $`\mu _i`$. Then for any $`\mu _i=0`$ let $`j`$ be the largest integer for which $`\widehat{\lambda }_j+jn1`$, and define $`\widehat{\lambda }`$ to be the sequence obtained by inserting $`n1j`$ between $`\widehat{\lambda }_j`$ and $`\widehat{\lambda }_{j+1}`$. If there is no such an integer $`j`$ then prepend $`n1`$ to $`\widehat{\lambda }`$. The partition resulting from this procedure is defined to be $`\lambda `$.
Consider now the sequence $`\overline{a}(\pi )=(ni\lambda _i)_{i=1,\mathrm{},n1}`$. (For the statement of Theorem 4.5 it suffices to consider the reduced sequence $`a(\pi )`$ which is obtained by omitting the final terms $`\overline{a}_i=ni`$. By Remark 4.2b), we have $`l=\mathrm{max}\overline{a}_i+1`$. Let $`j_1`$ be an integer satisfying $`\overline{a}_{j_1}=l1`$. Using the definition of $`\overline{a}(\pi )`$ in terms of the Dyck path $`\mathrm{\Psi }_K(\pi )`$, it is obvious that there exist some integers $`j_1<j_2<\mathrm{}<j_{l1}n1`$ with $`\overline{a}_{j_i}=li`$ for $`i=1,\mathrm{},l1`$. By Remark 4.6, the number $`\overline{a}_i(\pi )`$ is the height of the ending point of the $`i`$th down-step of $`\mathrm{\Psi }_K(\pi )`$. (Note that the length $`l`$ is equal to the maximum height of a peak of $`\mathrm{\Psi }_K(\pi )`$.) By the construction, the elements of the sequence $`a(\sigma )`$ correspond to the nonzeros of $`\overline{a}(\pi )`$. In particular, we have $`a_i(\sigma )>a_j(\sigma )`$ for any $`i<j`$ if and only if the $`i`$th positive element of $`\overline{a}(\pi )`$ is larger than the $`j`$th positive one. Thus the elements corresponding to $`\overline{a}_{j_1},\overline{a}_{j_2},\mathrm{},\overline{a}_{j_{l1}}`$ form a decreasing sequence of maximal length in $`a(\sigma )`$. (For $`l=1`$ we have $`\lambda =(n1,n2,\mathrm{},1)`$, i.e., $`\pi =n(n1)\mathrm{}1`$ and hence $`\mu =\mathrm{}`$, i.e., $`\sigma =\mathrm{id}𝒮_n`$.) Consequently, $`l_2(\sigma )=(l1)+1`$. (Note that any element $`a_i(\sigma )`$ is of height at least 1.) $`\mathrm{}`$

The following result can be derived from the corresponding generating functions which were given for the first time by Chow and West (\[3, Th. 3.1\]). Several different analytical proofs appeared recently in \[9, Th. 2, Th. 6\] and \[12, Th. 3.1\].

###### Corollary 4.8

$`|𝒮_n(132,12\mathrm{}k)|=|𝒮_n(132,23\mathrm{}k1)|=|𝒮_n(132,k12\mathrm{}(k1))|`$ for all $`n`$ and $`k3`$.

Proof. The first identity is an immediate consequence of the preceding proposition. For the second one use that $`\pi `$ avoids $`23\mathrm{}k1`$ if and only if $`\pi ^1`$ contains no pattern $`k12\mathrm{}(k1)`$. $`\mathrm{}`$

###### Corollary 4.9

For any $`s2`$ there are as many partitions $`\lambda 𝒴_n`$ for which $`i+\lambda _in+2s`$ for all $`i`$ as such ones for which the sequence $`a(\pi )`$ for the corresponding permutation contains no element of height at least $`s1`$.

Proof. If $`\lambda 𝒴_n`$ satisfies the condition $`i+\lambda _in+2s`$ for all $`i`$ then its diagram contains $`(n+1s,ns,\mathrm{},1)`$. By Theorem 4.1b), this is equivalent to being $`12\mathrm{}s`$-avoiding for the corresponding permutation. On the other hand, it follows from Theorem 4.5 (where $`k=s`$) that any permutation $`\pi 𝒮_n(132)`$ avoids the pattern $`s12\mathrm{}(s1)`$ if and only if every element of $`a(\pi )`$ is of height at most $`s2`$. Thus Corollary 4.8 proves the assertion. (Let $`\tau `$ be the partition associating with $`\pi `$. Then $`\lambda \mu \tau :=\mu ^{}`$ yields the desired bijection where $`\lambda \mu `$ is the map appearing in the proof of 4.7, and $`\mu ^{}`$ denotes the conjugate of $`\mu `$.) $`\mathrm{}`$

Now we can generalize the result from Proposition 4.7 for any $`s2`$.

###### Proposition 4.10

Let $`\pi 𝒮_n(132)`$, and let $`ls1`$ be the maximum length of an increasing subsequence of $`\pi `$. Then $`\pi `$ corresponds in a one-to-one fashion to a permutation $`\sigma 𝒮_n(132)`$ with $`l_s(\sigma )=l`$.

Proof. For $`ls1`$ we have $`i+\lambda _in+2s`$ for all parts $`\lambda _i`$ of the partition corresponding to $`\pi `$. (Note that $`l`$ is the maximum difference $`n+1(i+\lambda _i)`$.) In this case, by Corollary 4.9, $`\lambda `$ corresponds to a partition whose associated permutation satisfies $`l_s=s1`$. Thus we may assume that $`ls`$.
The argument is completely parallel to that used to prove Proposition 4.7 but the construction of the bijection is more complicated. We preserve the notation of the proof of 4.7.
Given $`\lambda =(\lambda _1,\mathrm{},\lambda _{n1})𝒴_n`$, we define the sequence $`\widehat{\mu }`$ by

$$\widehat{\mu }_i:=\{\begin{array}{ccc}\lambda _i+s1& & \text{if }\lambda _i+i<n+2s\hfill \\ 0& & \text{if }\lambda _i+i=n+2s\hfill \\ \mathrm{}& & \mathrm{}\hfill \\ s2& & \text{if }\lambda _i+i=n\hfill \end{array}$$

for $`i=1,\mathrm{},n+1s`$, and $`\widehat{\mu }_i:=\lambda _i`$ otherwise. If there exists any integer $`i`$ with $`\widehat{\mu }_i<s1`$ and $`\widehat{\mu }_{i+1}s1`$ then sort $`\widehat{\mu }`$ as follows: If $`\widehat{\mu }_i>0`$ then increase $`\widehat{\mu }_{i+1}`$ by $`1`$. Interchange $`\widehat{\mu }_i`$ and $`\widehat{\mu }_{i+1}`$. After this procedure we have $`\widehat{\mu }=\tau _1\tau _2`$ where $`\tau _1`$ is a partition with parts at least $`s1`$, and $`\tau _2`$ is a subsequence containing elements of $`\{0,\mathrm{},s2\}`$ only. (Note that both $`\tau _1`$ and $`\tau _2`$ are nonempty for $`s3`$. Since $`ls`$ there is an integer $`i`$ satisfying $`i+\lambda _i<n+2s`$ and hence $`\widehat{\mu }_is1`$. On the other hand, $`\widehat{\mu }_{n+2s},\mathrm{},\widehat{\mu }_{n1}s2`$ by definition.) It is clear from the construction that $`i+\widehat{\mu }_in`$, and it is easy to see that the map $`\lambda \widehat{\mu }`$ is injective. To recover $`\lambda `$ from $`\widehat{\mu }`$, first define a sequence $`\widehat{\lambda }`$ by $`\widehat{\lambda }_i:=\widehat{\mu }_i+1s`$ for all indices $`i`$ with $`\widehat{\mu }_is1`$ and $`\widehat{\lambda }_i:=\widehat{\mu }_ii+n+2s`$ otherwise where $`i=1,\mathrm{},n+1s`$. If there exists any integer with $`\widehat{\lambda }_i<\widehat{\lambda }_{i+1}`$ then decrease $`\widehat{\mu }_i`$ by 1 if $`\widehat{\mu }_{i+1}`$ is positive, interchange $`\widehat{\mu }_i`$ and $`\widehat{\mu }_{i+1}`$, and determine $`\widehat{\lambda }`$ again for the resulting sequence $`\widehat{\mu }`$. (This procedure will be done while $`\widehat{\lambda }`$ is not a partition.) Adding $`\widehat{\mu }_{n+2s},\mathrm{},\widehat{\mu }_{n1}`$ at $`\widehat{\lambda }`$ completes the partition $`\lambda `$.
If $`\tau _2`$, and hence $`\widehat{\mu }`$, is a partition then set $`\mu :=\widehat{\mu }`$. The partitions $`\lambda 𝒴_n`$ for which this case occurs are characterized by the following conditions:

* $`\lambda _{n+2s}=\mathrm{}=\lambda _{n1}=0`$.
* If $`i+\lambda _in+2s`$ for any $`ins`$ then $`\lambda _{i+1}<\lambda _i`$.

Suppose that there exists an integer $`in+2s`$ with $`\widehat{\mu }_i=\lambda _i>0`$. By Remark 4.6, the $`i`$th down-step of $`\mathrm{\Psi }_K(\pi )`$ ends at a point of height $`n(i+\lambda _i)n(n+2s+\lambda _i)=s2\lambda _is3`$. Since $`ls`$ there is an integer $`j`$ with $`j+\lambda _j<n+2s`$. (Obviously, $`j<n+2si`$.) The ending point of the corresponding down-step is of height at least $`s1`$. Thus there must exist an integer $`k`$ with $`j<k<i`$ such that $`k+\lambda _k=n+2s`$, that is, $`\widehat{\mu }_k=0`$. The second condition is evident. (In case $`s=2`$ the above conditions are satisfied for all partitions in $`𝒴_n`$.)
If $`\tau _2`$ is not ordered then we obtain the partition $`\mu `$ by increasing all elements of $`\widehat{\mu }`$ which are smaller than $`s1`$ and smaller than an element to their right.
Consider the sequences $`\overline{a}(\pi )`$ and $`a(\sigma )`$ again. By the construction, each element of $`\overline{a}(\pi )`$ which is at least $`s1`$ corresponds to a term $`a_i`$ of $`a(\sigma )`$ whose height is at least $`s1`$ or for which there exists an element $`a_j`$ with $`i<j`$ and $`h_j(\sigma )s1`$. (Then necessarily $`a_ia_j`$.) In particular, we have $`a_{i_1}(\sigma )>a_{i_2}(\sigma )`$ for any $`i_1<i_2i_3`$ where $`h_{i_3}(\sigma )s1`$ if and only if the corresponding elements in $`\overline{a}(\pi )`$ are in the same order. Analogously to the proof of Proposition 4.7 this yields the assertion. $`\mathrm{}`$

An analytical proof of the following result was given in \[13, Th. 2.4\].

###### Corollary 4.11

$`|𝒮_n(132,12\mathrm{}k)|=|𝒮_n(132,s(s+1)\mathrm{}k12\mathrm{}(s1))|`$ for all $`n`$ and $`k3`$ and $`2sk`$.

Proof. This follows immediately from the previous proposition. $`\mathrm{}`$

5 A final note

In Section 2 we have shown that the diagram of a permutation indicates the existence of some subsequences of type $`132`$. But in positive case, we even obtain the exact number of occurrences.
In , Fulton defined the following rank function on the essential set. Given a corner $`(i,j)`$ of the diagram $`D(\pi )`$, i.e. $`(i,j)(\pi )`$, its rank is defined by the number of dots northwest of $`(i,j)`$ and denoted by $`\rho ((i,j))`$.
It is clear from the construction that the number of dots in the northwest is the same for all diagram squares which are connected. (This yields the fundamental property of the ranked essential set of a permutation $`\pi `$, that it uniquely determines $`\pi `$.) So, we can extend the rank function on $`D(\pi )`$. The information about the number of sequences of type $`132`$ containing in a permutation is encoded by the ranks of its diagram squares.

###### Theorem 5.1

Let $`\pi 𝒮_n`$ be a permutation, and let $`D(\pi )`$ be its diagram. Then the number of occurrences of the pattern $`132`$ in $`\pi `$ is equal to

$$\underset{(i,j)D(\pi )}{}\rho ((i,j)).$$

Proof. Extending the arguments of Theorem 2.2, it is easy to see that each square $`(i,j)`$ of $`D(\pi )`$ corresponds to exactly $`\rho ((i,j))`$ subsequences of type $`132`$ in $`\pi `$, namely the sequences $`k\pi _ij`$ where $`k`$ ranges over all column indices of dots northwest of $`(i,j)`$:

$`\mathrm{}`$

###### Remark 5.2

As mentioned above, we have $`|D(\pi )|=\mathrm{𝗂𝗇𝗏}(\pi )`$ for all $`\pi 𝒮_n`$. Hence the non-weighted sum $`_{(i,j)D(\pi )}1`$ counts the number of occurrences of the pattern $`21`$ in $`\pi `$.

###### Example 5.3

The ranked diagram of $`\pi =\mathrm{4\hspace{0.25em}2\hspace{0.25em}8\hspace{0.25em}3\hspace{0.25em}6\hspace{0.25em}9\hspace{0.25em}7\hspace{0.25em}5\hspace{0.25em}1\hspace{0.25em}10}𝒮_{10}`$ is

Thus $`\pi `$ contains $`20`$ subsequences of type $`132`$ and 18 inversions.

In , Mansour and Vainshtein studied the generating function for the number of permutations on $`n`$ letters containing exactly $`r0`$ occurrences of pattern $`132`$.

Acknowledgement I am grateful to Toufik Mansour for pointing me to some literature relating to restricted permutations.

References