## On the asymptotic enumeration and limit shapes of monotone grid classes of permutations

Noura Alshammari † and David Bevan †

## Abstract

We exhibit a procedure to asymptotically enumerate monotone grid classes of permutations. This is then applied to compute the asymptotic number of permutations in any connected one-corner class. Our strategy consists of enumerating the gridded permutations, finding the asymptotic distribution of points between the cells in a typical large gridded permutation, and analysing in detail the ways in which a typical permutation can be gridded. We also determine the limit shape of any connected monotone grid class.

## 1 Introduction

We consider a permutation of length n (an n-permutation ) to be a linear ordering of the numbers 1, 2, . . . , n , and usually identify a permutation σ = σ 1 . . . σ n with its plot , the set of points ( i , σ i ) in the Euclidean plane. The monotone grid class Grid ( M ) is a set of permutations defined by a gridding matrix M whose entries are drawn from { , , } . This matrix specifies the permitted shape for plots of permutations in the class. Each entry of M corresponds to a cell in an M-gridding of a permutation. If the entry is , any points in the cell must form an increasing sequence; if the entry is , any points in the cell must form a decreasing sequence; if the entry is , then the cell must be empty. A permutation can have more than one M -gridding. See Figure 1 for an example. Formal definitions are given below.

The study of individual grid classes goes back to the work of Stankova [21] and Atkinson [3] in the 1990s on the skew-merged permutations. However, monotone grid classes were formally introduced (under a different name) in 2003 by Murphy and Vatter [19]. Huczynska and Vatter [18] were the first to call them 'grid classes' and to use the notation Grid ( M ) .

Exact enumerative results for monotone grid classes are rare. A few individual classes have been enumerated, such as the skew-merged permutations Grid ( ) whose generating function was determined by Atkinson [3]. However, only two general results are known. The first of these concerns skinny grid classes, which are those whose matrices have a single row. That is, Grid ( M ) is skinny if M is simply a vector over { , } . In the second author's PhD thesis [9], an

† Department of Mathematics and Statistics, The University of Strathclyde, Glasgow, Scotland. 2020 Mathematics Subject Classification: 05A05, 05A16.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-f2c0bc4b-a416-4c24-8dd6-b158253f56f6.jpg)

iterative procedure is presented which yields the generating function of any skinny monotone grid class, a result which was later generalized by Brignall and Sliaˇ can in [12] to skinny classes in which the contents of a single cell may be non-monotone. The other general result concerns polynomial grid classes (classes with growth rate equal to 1). The monotone grid class Grid ( M ) is polynomial if M has at most one or in any column or row. Homberger and Vatter [15] describe an algorithm which can enumerate any such class. Extending either of these general exact enumeration results seems very challenging. Perhaps the Combinatorial Exploration algorithmic framework described in [1] can be adapted to do so.

Given the difficulty of exact enumeration, our goal is the asymptotic enumeration of monotone grid classes. In [8], the second author proves that the exponential growth rate ,

$$\text{gr} ( \text{Grid} ( M ) ) \ \coloneqq \ \lim _ { n \to \infty } \left | \text{Grid} _ { n } ( M ) \right | ^ { 1 / n },$$

of Grid ( M ) exists and is equal to the square of the spectral radius of a certain graph associated with M . A simpler proof of (a more general version of) this result is given by Albert and

Vatter [2]. Thus we know that

$$\left | \text{Grid} _ { n } ( M ) \right | \, \sim \, \theta ( n ) \, g ^ { n },$$

where g is the growth rate of the class and θ ( n ) is subexponential; that is, lim n → ∞ θ ( n ) 1/ n = 1. We write f ( n ) ∼ g n ( ) to denote that lim n → ∞ f ( n ) / g n ( ) = 1.

Our primary contribution is a procedure to determine the asymptotic enumeration of a monotone grid class. This is first applied to skinny classes (Theorem 2.5). We then establish the asymptotic distribution of points between cells in a typical large gridded permutation (Theorem 3.8), and use this to determine grid class limit shapes (Theorem 3.9). Building on these results, the major part of our work then concerns the asymptotic enumeration of connected one-corner classes (Theorem 4.6). These are either L -shaped, T -shaped or X -shaped. See Section 4 for the relevant definitions.

We begin with a formal definition of an M -gridding. In this definition, in order to match the way we view permutations graphically, we index matrices from the lower left corner, with the order of the indices reversed from the normal convention. Thus, M 2,1 is the entry that is in the second column from the left and in the bottom row of M .

If M is a gridding matrix with t columns and u rows, then formally an M-gridding of a permutation σ of length n is a pair of integer sequences 0 = c 0 ⩽ c 1 ⩽ . . . ⩽ ct = n (the column dividers ) and 0 = r 0 ⩽ r 1 ⩽ . . . ⩽ ru = n (the row dividers ) such that for every column i and row j , the subsequence of σ with indices in ( ci -1, ci ] and values in ( rj -1, rj ] is increasing if Mi j , = , decreasing if Mi j , = , and empty if Mi j , = . For example, in the leftmost

gridding in Figure 1, we have c 1 = 2, c 2 = 6 and r 1 = 1. If the gridding matrix is clear from the context, we may just talk of a gridding of a permutation.

In practice, it is more natural to consider the assignment of points to cells that is induced by an M -gridding. With this perspective, we regard the row and column dividers to be the horizontal and vertical lines at half-integer positions that partition the plot of a permutation into cells. We follow this convention. With a minor abuse of terminology, we often refer to the matrix entries themselves as cells, calling entries blank cells, and and entries non-blank cells.

The grid class Grid ( M ) then consists of those permutations that have at least one M -gridding. We use Grid n ( M ) to denote the set of permutations of length n in Grid ( M ) . A permutation together with one of its M -griddings is called an M-gridded permutation (or just a gridded permutation if the gridding matrix is clear from the context). The gridded class , consisting of all M -gridded permutations, is denoted by Grid # ( M ) , and the set of M -gridded permutations of length n by Grid # n ( M ) . When we use σ # to denote a gridded permutation, its underlying permutation is σ .

Observe that if a gridding matrix M has dimensions t × u , then no permutation in Grid n ( M ) can have more than ( n + ) + 1 t u -2 griddings, because there are only n + 1 possible positions for each row and column divider. Since this is polynomial in n , the exponential growth rate of the gridded class is equal to that of the grid class [23, Proposition 2.1].

Building on this observation, our strategy for the asymptotic enumeration of Grid ( M ) consists of the following five steps:

- 1. Find the proportion of points that occur in each cell in a typical large M -gridded permutation.
- 2. Determine the asymptotic enumeration of the corresponding gridded class:

$$\left | \text{Grid} _ { n } ^ { \# } ( M ) \right | \, \sim \, \theta ^ { \# } ( n ) \, g ^ { n },$$

where g is the exponential growth rate of the class, and θ # ( n ) is subexponential.

- 3. Determine, for each ℓ ⩾ 1, how a typical large M -gridded permutation σ # must be structured so that its underlying permutation σ has exactly ℓ distinct M -griddings.
- 4. By combining steps 1 and 3, calculate, for each ℓ ⩾ 1, the asymptotic probability

$$P _ { \ell } \, \coloneqq \, \lim _ { n \to \infty } \mathbb { P } \left [ \sigma \, \text{has exactly $\ell$ distinct $M$-griddings $\colon \sigma^{#} \in \text{Grid}_{n}^{#}(M)$} \right ].$$

## 5. Let

$$\kappa _ { M } \, = \, \sum _ { \ell \geqslant 1 } P _ { \ell } / \ell \, = \, \lim _ { n \to \infty } \frac { | \text{Grid} _ { n } ( M ) | } { | \text{Grid} _ { n } ^ { \# } ( M ) | }.$$

Then ∣ ∣ Grid n ( M ) ∣ ∣ ∼ κ M θ # ( n ) g n .

The rest of the paper is structured as follows:

- · In Section 2, we consider skinny classes. We determine how points can 'dance' between the cells in a typical large gridded permutation. Hence, we deduce the asymptotic enumeration of any skinny class (Theorem 2.5).

- · Section 3 concerns the distribution of points between the cells in a typical large gridded permutation in a connected class (Theorem 3.8). This result is then used to determine the shape of a typical permutation in such a class (Theorem 3.9).
- · In Section 4, we apply our strategy to connected one-corner classes. We begin by finding the proportion of points in each cell in a typical large gridded permutation (Section 4.1). Then we determine the asymptotic enumeration of gridded connected one-corner classes (Proposition 4.3). The heart of this section consists of a detailed analysis of how typical permutations in these classes can be gridded, based on an examination of the eleven possible corner types (Sections 4.3-4.9). This then yields the asymptotic enumeration of any connected one-corner class (Theorem 4.6). We conclude by briefly considering the application of our approach to classes with more than one corner (Section 4.10).

## 2 Skinny classes

We begin with the simplest case, for which each of the five steps in the analysis is easy. Recall that Grid ( M ) is skinny if M is simply a / vector. Although, as mentioned above, a procedure is known which gives the generating function of any skinny class, this would be a very inefficient way of determining their asymptotic enumeration.

↦

Figure 2: The three ways of adding a new maximum point to a gridded permutation in the skinny class Grid # ( )

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-7fd360a0-bb4e-4c4d-a915-8bac5788cf4a.jpg)

We begin by exactly enumerating skinny gridded classes.

Proposition 2.1. If Grid ( M is a k-cell skinny grid class, then ) ∣ ∣ Grid # n ( M ) ∣ ∣ = k n .

Proof. Any M -gridded permutation can be uniquely constructed from the empty M -gridded permutation by repeatedly adding a new maximum point. This point may be placed in any one of the k cells. Moreover, there is only one way of adding a maximum to any particular cell, because of the monotonicity constraints. See Figure 2 for an illustration.

## 2.1 Peaks and peak points

̸

We now introduce some concepts that are important when analysing how permutations can be gridded. Firstly, given a skinny grid class Grid ( M ) , where M is the / vector ( m 1, . . . , mk ) , we say that a pair ( mi , mi + ) 1 of adjacent cells forms a peak if mi + 1 = mi . That is, a peak either looks like , which we say points up , or else looks like or , which we say points down . For example, Grid ( ) has three peaks, two pointing up and one pointing down.

Secondly, suppose we have a skinny grid class Grid ( M ) with a peak Λ , and that σ # is an M -gridded permutation with at least two points in each cell, witnessing the orientation of the cell. Then the peak point of Λ is the highest of the points of σ # in the two cells of Λ if Λ points up, and is the lowest of the points of σ # in Λ if Λ points down. For example, in the rightmost two gridded permutations in Figure 2, the peak point (of the only peak in the class) is circled.

Note that our use of the term 'peak' is nonstandard, differing from its traditional use to denote a consecutive 132 or 231 pattern in a permutation. For us a peak is part of a gridding matrix. On the other hand, a peak point is the central point of either a peak or valley (in the traditional sense) in a gridded permutation. These concepts are generalised further below, when we consider non-skinny classes.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-eb249f5c-6b9d-4ee4-9708-d50dbe329670.jpg)

Figure 3: The four distinct griddings of a permutation in Grid ( ) ; points which can dance are circled

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-3096b474-7aeb-4a92-8962-92346f4b0e7f.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-68166e9a-6247-425a-ae85-c8438d45d83d.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-02869237-44ad-41bc-841a-280633cc8f4f.jpg)

## 2.2 Dancing and constrained gridded permutations

Suppose Grid ( M ) is skinny and σ # ∈ Grid # ( M ) . If Q is a peak point of σ # , we say that Q can dance if Q is immediately adjacent to a column divider. The movement of this divider to the other side of Q results in another valid M -gridding of σ . We say that this new gridded permutation is the result of Q dancing . Conceptually, we consider Q as dancing from one cell to an adjacent one (although in fact it is the divider rather than the point that moves). See Figure 3 for an illustration. The notion of dancing is generalised below in Section 4.3, when we consider non-skinny classes.

The key to our approach is the fact that for most permutations the gridding possibilities are heavily restricted. To formalise this observation, we focus our attention on certain wellbehaved gridded permutations in which only peak points can dance. Suppose Grid ( M ) is skinny and σ # ∈ Grid # ( M ) . We say that σ # is M-constrained (or just constrained ) if

- (a) every M -gridding of its underlying permutation σ is the result of zero or more peak points of σ # dancing, and
- (b) in every M -gridding of σ , each cell contains at least two points.

For constrained gridded permutations, counting possible griddings is easy.

Proposition 2.2. If Grid ( M is a skinny grid class with p peaks, and ) σ # ∈ Grid # ( M is M-constrained, ) then σ has exactly 2 p distinct M-griddings.

Proof. Since σ # is constrained, every M -gridding of σ is the result of zero or more peak points of σ # dancing. Since each cell of σ # contains at least two points, σ # has p distinct peak points

(one for each peak), which can dance independently. For each peak point of σ # , we can choose whether it dances or not, yielding a total of 2 p distinct M -griddings for σ .

The following proposition gives sufficient conditions for a gridded permutation in a skinny class to be constrained.

Proposition 2.3. Suppose Grid ( M is skinny and ) σ # ∈ Grid # ( M is such that each cell contains at ) least four points and there are no two adjacent cells whose contents together form an increasing or decreasing sequence. Then σ # is M-constrained.

Proof. The contents of each cell of σ # consists of an increasing or decreasing sequence of points. However, there is no pair of adjacent cells whose contents together form an increasing or decreasing sequence.

Thus, in any M -gridding of σ , by the monotonicity constraints, there must be a divider between each pair of adjacent cells of σ # that have the same orientation and also a divider adjacent to each peak point of σ # . So any M -gridding of σ can be formed from σ # by zero or more of its peak points dancing.

Moreover, in any M -gridding of σ , at most two points from any cell of σ # (the first and the last) can be gridded in another cell. So each cell of any M -gridding of σ contains at least two points.

Constrained gridded permutations are of interest not only because it is easy to count their griddings, but also because almost all gridded permutations are constrained.

Proposition 2.4. If Grid ( M is skinny, then almost all M-gridded permutations are M-constrained: )

$$\lim _ { n \to \infty } \mathbb { P } \left [ \sigma ^ { \# } \, i s \, M { - c o n s t r a i n e d } \, \colon \sigma ^ { \# } \in \text{Grid} _ { n } ^ { \# } ( M ) \right ] \, = \, 1.$$

Proof. Suppose M has k cells. The number of n -point M -gridded permutations with exactly m points in a given cell equals

$$\binom { n } { m } ( k - 1 ) ^ { n - m } \ < \ n ^ { m } ( k - 1 ) ^ { n }.$$

Here, ( n m ) is the number of ways of choosing the points in the given cell, and ( k -1 ) n -m is the number of ways of distributing the remaining points. So the total number of n -point M -gridded permutations with fewer than four points in some cell is less than 4 kn 3 ( k -1 ) n , there being four choices for the value of m , and k choices of cell.

Similarly, the number of n -point M -gridded permutations with a given pair of adjacent cells forming an increasing or decreasing sequence of length m is less than

$$( m + 1 ) ( k - 1 ) ^ { n } \ < \ ( n + 1 ) ( k - 1 ) ^ { n }.$$

Here, ( k -1 ) n is an upper bound on the number of ways of distributing the points if we consider the pair of adjacent cells merged to form a single 'super cell', and the factor m + 1

is the number of choices for the position of the divider that splits the pair of cells. So the total number of n -point M -gridded permutations with two adjacent cells forming an increasing or decreasing sequence is less than ( n + ) ( 1 2 k -1 ) n + 1 , there being n + 1 choices for the value of m , and k -1 choices for the pair of cells.

Thus, by Propositions 2.1 and 2.3, the proportion of n -point M -gridded permutations which are not constrained is less than

$$\frac { 4 k n ^ { 3 } ( k - 1 ) ^ { n } \, + \, ( n + 1 ) ^ { 2 } ( k - 1 ) ^ { n + 1 } } { k ^ { n } } \, < \, 4 k n ^ { 3 } \left ( 1 - \frac { 1 } { k } \right ) ^ { n },$$

which converges to zero as n tends to infinity.

The asymptotic enumeration of skinny grid classes then follows directly from Propositions 2.1, 2.2 and 2.4.

Theorem 2.5. If Grid ( M is a k-cell skinny grid class with p peaks, then ) ∣ ∣ Grid n ( M ) ∣ ∣ ∼ 2 -p k n .

Proof. For almost all of the k n distinct M -gridded permutations, the underlying permutation has exactly 2 p M -griddings.

## 3 The distribution of points between cells

As we have seen, almost every large permutation in a given skinny class has the same number of griddings (that depends only on the number of peaks). In non-skinny classes this is not the case: the number of griddings may depend on the structure of the permutation. In order to determine the asymptotic probability that a permutation has a specific number of griddings, we need to know the proportion of points that occur in each cell in a typical large gridded permutation. This is the focus of this section.

Much of the analysis required can be found in the paper of Albert and Vatter [2] and (in a more sketchy form) in the second author's PhD thesis [9, Chapter 6]. However, neither of these works contains all that we need, so we reproduce the argument in full here. Our presentation combines ideas from both approaches.

We begin by introducing a family of matrices to record the number of points or proportion of points in each cell (Section 3.1). We then determine the asymptotic number of gridded permutations with a given distribution (Section 3.2). This is followed by calculating the distribution of points for which this enumeration is the greatest (Section 3.3). We then prove that this distribution is unique if the class is connected (Section 3.4). Finally, we establish in Theorem 3.8 that the distribution of points in almost all gridded permutations is close to this maximal distribution, This is then used to determine the limit shapes of connected classes (Theorem 3.9).

## 3.1 M -admissible and M -distribution matrices

Given a gridding matrix M , we say that a nonnegative real matrix A of the same dimensions as M is M admissible -if Ai j , is zero whenever Mi j , is blank. We refer to the sum of the entries of such a matrix as its weight .

We use integer M -admissible matrices to record the number of points in each cell. Suppose A = ( ai j , ) is an integer M -admissible matrix of weight n . Then Grid # A ( M ) denotes the subset of Grid # n ( M ) consisting of those M -gridded permutations with ai j , points in cell ( i , j ) , for each ( i , j ) . For example, the leftmost gridded permutation in Figure 1 on page 2 is an element of

$$\text{Grid} ^ { \# } _ { \binom { 2 } { 0 } \, 1 \, 0 } ( \Sigma ^ { \Sigma } ).$$

Thus Grid # n ( M ) can be partitioned into subsets as follows:

$$\text{Grid} _ { n } ^ { \# } ( M ) \, = \, \bigoplus _ { \| A \| = n } \text{Grid} _ { A } ^ { \# } ( M ),$$

where the disjoint union is over all integer M -admissible matrices of weight n . The number of gridded permutations in one of these subsets is given by the following product of multinomial coefficients.

Proposition 3.1. Suppose A = ( ai j , ) is an integer M-admissible matrix with dimensions r × s. Then,

$$| \text{Grid} _ { A } ^ { \# } ( M ) | \, = \, \prod _ { i = 1 } ^ { r } \binom { \sum _ { j = 1 } ^ { s } a _ { i, j } } { a _ { i, 1 }, a _ { i, 2 }, \dots, a _ { i, s } } \, \times \prod _ { j = 1 } ^ { s } \binom { \sum _ { i = 1 } ^ { r } a _ { i, j } } { a _ { 1, j }, a _ { 2, j }, \dots, a _ { r, j } }.$$

Proof. The ordering of points (increasing or decreasing) within a particular cell is fixed by the corresponding entry of M . However, for each row and for each column, the choice of which points occur in which cells can be made arbitrarily and independently. The multinomial coefficient in the first product counts the number of ways in which the points of a gridded permutation can be distributed horizontally between the cells in row i . Similarly, the term in the second product counts the number of ways in which the points can be distributed vertically between the cells in column j .

We use M -admissible matrices of weight one to record the proportion of points in each cell. We call such matrices M-distribution matrices . To avoid having to worry about rounding the number of points in each cell to an integer, we make use of Baranyai's Rounding Lemma [4], as a consequence of which we have the following result.

Proposition 3.2. Suppose Γ = ( γ i , j ) is an M-distribution matrix, and n is any positive integer. Then there exists an integer M-admissible matrix A = ( ai j , ) of weight n such that, for each i , j, we have | ai j , -n γ i , j | &lt; 1 .

In light of this, if Γ = ( γ i , j ) is an M -distribution matrix and n a positive integer, we use Grid # Γ n ( M ) to denote Grid # A ( M ) , where A is some integer M -admissible matrix of weight n each of whose entries differs from the corresponding entry of n Γ by less than one, the existence of such an A being guaranteed by Proposition 3.2. The exact choice of A is of no consequence to our arguments. Note that in any gridded permutation in Grid # Γ n ( M ) the proportion of points in cell ( i , j ) differs from γ i , j by less than 1/ n .

## 3.2 Asymptotics of gridded permutations with a given distribution

Suppose τ = γ 1 + γ 2 + . . . + γ k , where each γ i &gt; 0. Then Stirling's approximation gives the following asymptotic form for a multinomial coefficient.

$$\binom { \tau n } { \gamma _ { 1 } n, \gamma _ { 2 } n, \dots, \gamma _ { k } n } \, \sim \, \sqrt { \frac { \tau } { ( 2 \pi ) ^ { k - 1 } \gamma _ { 1 } \gamma _ { 2 } \dots \gamma _ { k } } } n ^ { - ( k - 1 ) / 2 } \left ( \frac { \tau ^ { \tau } } { \gamma _ { 1 } ^ { \gamma _ { 1 } } \gamma _ { 2 } ^ { \gamma _ { 2 } } \dots \gamma _ { k } ^ { \gamma _ { k } } } \right ) ^ { n }.$$

Hence, by Proposition 3.1, we have the following asymptotic enumeration of Grid # Γ n ( M ) .

Proposition 3.3. If Γ = ( γ i , j ) is an M-distribution matrix with row sums ρ i = ∑ j γ i , j and column sums κ j = ∑ i γ i , j , then

$$\left | \text{Grid} _ { \Gamma n } ^ { \# } ( M ) \right | \, \sim \, C n ^ { \beta } g ^ { n },$$

where

$$g \, = \, g ( \Gamma ) \, \coloneqq \, \prod _ { i } \frac { \rho _ { i } ^ { \rho _ { i } } } { \prod _ { j } \gamma _ { i, j } ^ { \gamma _ { i, j } } } \times \prod _ { j } \frac { \kappa _ { j } ^ { \kappa _ { j } } } { \prod _ { i } \gamma _ { i, j } ^ { \gamma _ { i, j } } },$$

and C and β are constants that only depend on Γ .

Note that g ( Γ ) = lim n → ∞ ∣ ∣ Grid # Γ n ( M ) ∣ ∣ 1/ n is the exponential growth rate of those M -gridded permutations whose points are distributed between the cells in the proportions specified by Γ .

To avoid problems below, we take the products in the denominators of the expression for g ( Γ ) to be over nonzero entries of Γ only.

## 3.3 Maximising the growth rate

Given a grid class Grid ( M ) , we would like to find an M -distribution matrix Γ = ( γ i , j ) for which the growth rate g ( Γ ) is greatest. We call such a matrix a maximal M -distribution matrix. The following result specifies equations that must be satisfied by the entries of such a matrix.

Proposition 3.4. Suppose Γ = ( γ i , j ) is a maximal M-distribution matrix. Then there exists a constant λ such that, for each nonzero entry γ i , j of Γ , we have

$$\frac { \gamma _ { i, j } ^ { 2 } } { \rho _ { i } \kappa _ { j } } \, = \, \lambda,$$

where ρ i = ∑ j γ i , j and κ j = ∑ i γ i , j are the row and columns sums of Γ .

Proof. We want to determine which choices of values for the γ i , j maximise g ( Γ ) , subject to the requirement that ∑ γ i , j = 1. This is a constrained optimisation problem, so we use the method of Lagrange multipliers. To simplify the algebra, we maximise log g ( Γ ) , which is of course equivalent to maximising g ( Γ ) . Viewing the nonzero γ i , j as formal variables, we introduce the auxiliary function

$$L ( \Gamma, \mu ) \, = \, \log g ( \Gamma ) \, - \, \mu ( 1 - \sum \gamma _ { i, j } ).$$

Then Γ must satisfy

$$\frac { \partial } { \partial \mu } L ( \Gamma, \mu ) \ = \ 0 \quad \text{and} \quad \frac { \partial } { \partial \gamma _ { i, j } } L ( \Gamma, \mu ) \ = \ 0,$$

for each nonzero γ i , j . The first of these requirements is simply the constraint that ∑ γ i , j = 1 (that is, Γ has weight one).

Now,

$$\log g ( \Gamma ) \, = \, \sum _ { i } \left ( \rho _ { i } \log \rho _ { i } - \sum _ { j } \gamma _ { i, j } \log \gamma _ { i, j } \right ) \, + \, \sum _ { j } \left ( \kappa _ { j } \log \kappa _ { j } - \sum _ { i } \gamma _ { i, j } \log \gamma _ { i, j } \right ).$$

Given i and j , for brevity let γ = γ i , j . Also let ρ = ρ i -γ and κ = κ j -γ be the sum of the entries other than γ in row i and in column j of Γ , respectively. Both ρ and κ are independent of γ , as are the contributions to L ( Γ , µ ) from any other row or column. Then,

$$\frac { \partial } { \partial \gamma _ { i, j } } L ( \Gamma, \mu ) \, & = \frac { \partial } { \partial \gamma } \Big ( ( \overline { \rho } + \gamma ) \log ( \overline { \rho } + \gamma ) \, + \, ( \overline { \kappa } + \gamma ) \log ( \overline { \kappa } + \gamma ) \, - \, 2 \gamma \log \gamma \, + \, \mu \gamma \Big ) \\ & = \left ( 1 + \log ( \overline { \rho } + \gamma ) \right ) \, + \, \left ( 1 + \log ( \overline { \kappa } + \gamma ) \right ) \, - \, 2 ( 1 + \log \gamma \, + \, \mu ) \\ & = \log \rho _ { i } \, + \, \log \kappa _ { j } \, - \, 2 \log \gamma _ { i, j } \, + \, \mu.$$

Thus,

$$\frac { \partial } { \partial \gamma _ { i, j } } L ( \Gamma, \mu ) \ = \ 0 \ \text{ only if} \ \ \frac { \gamma _ { i, j } ^ { 2 } } { \rho _ { i } \kappa _ { j } } \ = \ e ^ { \mu }.$$

The result follows by letting λ = e µ .

## 3.4 Uniqueness of the maximal distribution for connected classes

Albert and Vatter [2] give a different characterisation of maximal M -distribution matrices (in a more general context), using the theory of singular value decompositions of matrices.

Given a real matrix A , a non-negative real number s is a singular value for A if there exist unit vectors u and v such that A v = s u and A T u = s v . The vectors u and v are called left singular and right singular vectors for s , respectively. If s is a singular value for A then s 2 is an eigenvalue of both AA T and A A T . Moreover, every left singular vector for s is an eigenvector of AA T for the eigenvalue s 2 , and every right singular vector for s is an eigenvector of A A T for the eigenvalue s 2 .

Given a gridding matrix M , let M 01 be the binary matrix such that Mi j 01 , = 0 if Mi j , is blank, and Mi j 01 , = 1 otherwise. Maximal M -distribution matrices can be characterised as follows.

Proposition 3.5 (Albert and Vatter [2]) . Suppose Γ = ( γ i , j ) is a maximal M-distribution matrix. Then γ i , j = Mi j 01 , v u i j / s, where s is the greatest singular value of M 01 , and u and v are left and right singular vectors for s, respectively.

In general, left and right singular vectors may not be unique, so Grid ( M ) may have multiple maximal M -distribution matrices. However, if we limit which classes we consider, uniqueness can be guaranteed.

Given a gridding matrix M , its cell graph is the graph whose vertices are its non-blank cells, and in which two vertices are adjacent if they share a row or a column and all the cells between them are blank.

For example, the cell graph of

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-c1006c1b-b369-47ea-bd85-7c08952ad109.jpg)

If the cell graph of a gridding matrix is connected, then we also say that the matrix and the corresponding grid class are connected .

A connected grid class has a unique maximal distribution matrix. To prove that this is the case, we extend the notion of connectivity to real matrices. We say that a nonnegative matrix A is connected if there do not exist permutation matrices P and Q such that PAQ = ( R 0 0 S ) for some non-trivial R and S .

Proposition 3.6. If a nonnegative matrix A is connected, then its greatest singular value s has unique left and right singular vectors u and v , and the entries of u and v are all positive.

Proof. Consider A to be a weighted biadjacency matrix of a bipartite graph G . If A is connected then so is G AA . T and A A T are then symmetric weighted adjacency matrices of the projections G 1 and G 2 of G onto its two vertex sets (in which nodes are adjacent if they share a neighbour in G ). If G is connected, then so are G 1 and G 2. Thus AA T and A A T are both irreducible.

The result then follows from the Perron-Frobenius Theorem, given that s 2 is the principal eigenvalue of both AA T and A A T , with u and v the corresponding (unique positive) principal eigenvectors.

With this, we can prove that connectivity is a sufficient condition for a grid class to have a unique maximal M -distribution matrix.

Proposition 3.7. If Grid ( M is a connected grid class, then it has a unique maximal M-distribution ) matrix Γ = ( γ i , j ) . Moreover, γ i , j is positive if and only if Mi j , is not blank.

Proof. Since M is connected, then so is M 01 . Propositions 3.5 and 3.6 then guarantee that Γ is unique, with γ i , j = Mi j 01 , v u i j / , where s s is the greatest singular value of M 01 , and u and v are the unique left and right singular vectors for s . Since u and v are positive, γ i , j &gt; 0 if and only if Mi j , is not blank.

If M is connected, then we use Γ M to denote the unique maximal M -distribution matrix.

## 3.5 The distribution of points in a typical gridded permutation

We now prove that, if Grid ( M ) is connected, then the distribution of points between cells in almost all M -gridded permutations is close to that specified by Γ M .

Given any σ # ∈ Grid # n ( M ) , let σ # ( i , j ) denote the number of points of σ # in cell ( i , j ) , and let Γ σ # = ( σ # ( i , j ) / n ) be the M -distribution matrix recording the proportion of the points of σ # in each cell.

Theorem 3.8. If Grid ( M is connected and ) Γ M = ( γ i , j ) is the unique maximal M-distribution matrix, then for any ε &gt; 0 ,

$$\lim _ { n \to \infty } \mathbb { P } \left [ \, \max _ { i, j } \left | \sigma _ { ( i, j ) } ^ { \# } / n - \gamma _ { i, j } \right | \leqslant \varepsilon \, \colon \, \sigma ^ { \# } \in \text{Grid} _ { n } ^ { \# } ( M ) \right ] \, = \, 1.$$

Proof. For brevity, let Γ = Γ M , and let S n = { σ # ∈ Grid # n ( M ) : max , i j ∣ ∣ σ # ( i , j ) / n -γ i , j ∣ ∣ ⩽ ε } consist of those M -gridded n -permutations whose distribution of points is ε -close to Γ , the proportion of points in each cell differing by no more than ε from that specified by Γ .

Also, let S n = Grid # n ( M ) \S n be its complement, consisting of those M -gridded n -permutations whose distribution is ε -far from Γ , the proportion of points in some cell differing by more than ε from that specified by Γ .

For sufficiently large n , we have Grid # Γ n ( M ) ⊆ S n . Thus the exponential growth rate of S n is bounded below by g ( Γ ) :

$$\bar { \ } g r ( \mathcal { S } _ { n } ) \, \geqslant \, g r ( \text{Grid} _ { \Gamma n } ^ { \# } ( M ) ) \, = \, g ( \Gamma ).$$

Now let G n = { Γ σ # : σ # ∈ S } n be the collection of M -distribution matrices that record the distribution of points in M -gridded n -permutations whose distribution is ε -far from Γ . Then

$$\overline { \mathcal { S } } _ { n } \, = \, \bigcup _ { \Gamma ^ { \prime } \in \overline { \mathcal { G } } _ { n } } \text{Grid} _ { \Gamma ^ { \prime } n } ^ { \# } ( M ).$$

Since M is connected, Γ is the only M -distribution matrix with maximal growth rate. Together with the continuity of the function g ( ) · and the compactness of the space of M -distribution matrices, this implies that there exists some g ε &lt; g ( Γ ) such that, for every Γ ′ ∈ ⋃ n ⩾ 0 G n , we have g ( Γ ′ ) = gr ( Grid # Γ ′ n ( M ) ) ⩽ g ε .

Now |G n | &lt; ( n + ) 1 k , where k is the number of non-blank entries in M . Hence the exponential growth rate of S n is strictly bounded above by g ( Γ ) :

$$\text{gr} ( \overline { \mathcal { S } } _ { n } ) \, \leqslant \, g _ { \varepsilon } \, < \, g ( \Gamma ).$$

Thus lim n → ∞ |S n | / |S n | = 0 as required.

## 3.6 The shape of a typical permutation in a class

Theorem 3.8 and Proposition 3.4 enable us to calculate the asymptotic distribution of points in almost all gridded permutations in any connected class. From this we can also determine what the plot of a typical large permutation in such a class looks like. See Figure 4 for an illustration.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-5ee8dc53-279c-47df-a128-0dbc64e310f4.jpg)

Figure 4: Plots of permutations of length 60, 120, 180 and 240 in Grid # ( ) , and the limit shape of the class

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-5adcd50d-cb66-4390-9e63-6644f151494e.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-6365125f-0735-45e6-ae98-019fabdc685b.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-35715fa8-a4a3-4245-bdc0-45d93a6cfdca.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-62f89ce2-d446-4888-a481-b4cc961dcc9b.jpg)

To formalise this idea, we make use of certain probability measures on the unit square which act as analytic limits of sequences of permutations. We briefly introduce only those parts of the theory that we need to state our result. See the references below for more information.

A permuton is a probability measure µ on the unit square [ 0, 1 ] 2 with uniform marginals: µ ([ a b , ] × [ 0, 1 ]) = µ ([ 0, 1 ] × [ a b , ]) = b -a , for every 0 ⩽ a ⩽ b ⩽ 1. A permuton can be associated with any permutation by taking its plot, scaling it into the unit square, and replacing the points with small squares, as follows.

Suppose A ⊂ [ 0, 1 ] 2 is a rectangular region or a line segment. Then we use λ A to denote the unique probability measure on [ 0, 1 ] 2 with support A and mass uniformly distributed on A . If σ is an n -permutation, then, for i = 1, . . . , n , let S σ ( ) i be the small square region [( i -1 / ) n i , / n ] × [( σ ( ) i -1 / ) n , σ ( ) i / n ] . Then µσ = ∑ n i = 1 1 n λ S σ ( ) i is the permuton corresponding to σ . See Figure 5 for an example.

Permutons were introduced in [16, 17] with a different but equivalent definition. The measuretheoretic perspective was first used (a little earlier) in [20], and was later applied in [14], where the term 'permuton' first occurs.

Figure 5: The plot of the permutation π = 314592687, and a picture of its permuton µπ

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-61f3f9a6-67dd-4ce2-9a29-67ca7a66345f.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-d275df6a-94c3-44f8-8182-e3dcd75634e0.jpg)

Given a class of permutations C , it may be that almost all large permutations have the 'same shape'. Let σ n be a random n -permutation drawn uniformly from C n . If the sequence of random permutons ( µ σ n ) n ⩾ 1 converges in distribution to some permuton µ , then we say that µ is the limit shape of C . A sequence of permutons ( µ n ) n ⩾ 1 converges in distribution to a permuton µ if, for every ( x y , ) ∈ [ 0, 1 ] 2 , we have lim n → ∞ µ n ([ 0, x ] × [ 0, y ]) = µ ([ 0, x ] × [ 0, y ]) .

If M is connected, then Γ M specifies the asymptotic distribution of points between the cells in a random permutation in Grid # ( M ) . Since any permuton has uniform marginals, this also specifies the asymptotic position of the cell dividers. The points in each cell are monotonic, and points in cells that share a row or column may be arbitrarily interleaved, so the points in any cell asymptotically form a line segment across one of the diagonals of the cell. Thus Grid ( M ) has a deterministic limit shape µ M defined as follows.

As in the formal definition of an M -gridding on page 2, for simplicity, here we index matrices in the Euclidean manner from the lower left corner, counting rows from the bottom, and with the column index before the row index. Suppose Γ M = ( γ i , j ) is the unique maximal M -distribution matrix.

Let ci = ∑ i ′ ⩽ i ∑ j γ i ′ , j be the sum of the leftmost i columns of Γ M , and let rj = ∑ j ′ ⩽ j ∑ i γ i , j ′ be the sum of the lowermost j columns of Γ M . Then ci gives the position of the i th column divider in µ M , and rj gives the position of the j th row divider. Let pi j , = ( ci , rj ) be the point of their intersection. Then the line segment in the support of µ M for the non-blank cell ( i , j ) is given by

$$L ( i, j ) \, = \, \begin{cases} \{ ( 1 - x ) p _ { i - 1, j - 1 } \, + \, x p _ { i, j } \, \colon \, x \in [ 0, 1 ] \}, & \text{if $M_{i,j} = \mathbb{Z}$}, \\ \{ ( 1 - x ) p _ { i - 1, j } \, + \, x p _ { i, j - 1 } \, \colon \, x \in [ 0, 1 ] \}, & \text{if $M_{i,j} = \mathbb{Z}$}. \end{cases}$$

Finally, the limit shape is constructed by distributing mass uniformly along the line segment for each non-blank cell:

$$\mu _ { M } \, = \, \sum _ { \gamma _ { i, j } > 0 } \gamma _ { i, j } \lambda _ { L ( i, j ) }.$$

Thus we have the following.

Theorem 3.9. If Mis connected, then µ M, defined above, is the deterministic limit shape of Grid ( M . )

For example, by applying Theorem 3.8 and Proposition 3.4 we know that the unique maximal

( 1 1 1 )

$$\overline { \mathbb { N } } \text{-distribution matrix is} \begin{pmatrix} \frac { 1 } { 6 } & \frac { 1 } { 3 } & \frac { 1 } { 6 } \\ 0 & \frac { 1 } { 6 } & 0 \\ 0 & \frac { 1 } { 6 } & 0 \end{pmatrix}, yielding the limit shape at the right of Figure 4.$$

It seems likely that fluctuations about the limit shape of a grid class can be described by coupled Brownian motions, as in the case of square permutations (permutations in which

every point is a record) [11]. However, that is beyond our scope here. It should also be possible to determine the (possibly random) limit shapes of classes with more than one component. See [5, 6, 7] for other recent work on the limit shapes of permutation classes.

## 4 Connected classes with one corner

We say that a cell C of a gridding matrix is a corner cell or just a corner , if there is both another non-blank cell in the same row as C and also another non-blank cell in the same column as C . A cell that is not a corner is a non-corner cell.

For example, has three corners, one in the top row and two in the bottom row.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-95cf552f-cedc-4412-a3e9-6df0d5f543d5.jpg)

In this section we consider connected monotone grid classes that have a single corner. These are either L -shaped, T -shaped or X -shaped. See Figure 6 for an example of each. L -shaped and T -shaped classes come in four different orientations.

Figure 6: An L -shaped class, a T -shaped class, and an X -shaped class

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-ceabcdc0-83a4-4915-8921-506a446ffeeb.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-f8e15cb2-bd02-4919-a841-991d3ecfd3c3.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-5ef7d01f-58c1-46f2-a0a4-97de64500eb6.jpg)

The row containing the corner we call the main row , and the column containing the corner we call the main column . For brevity, non-corner cells in the main row are simply called row cells , and non-corner cells in the main column are called column cells . Thus each L , T or X -shaped class consists of a corner cell, some row cells and some column cells.

Throughout this section we assume that Grid ( M ) is a connected one-corner class with dimensions ( r + ) 1 × ( c + ) 1 . Thus M has r + c + 1 non-blank cells: the corner, r column cells, and c row cells. For example, for the L -shaped and X -shaped classes in Figure 6, we have r = 3 and c = 4.

Our analysis of connected one-corner classes is as follows. First, we apply Theorem 3.8 to determine the asymptotic distribution of points between the cells (Section 4.1). Then we use generating functions to establish the asymptotics of the number of gridded permutations in such a class (Section 4.2). This is followed by an investigation of the ways in which points can dance between cells, including the introduction of an appropriate notion for these classes of a constrained gridded permutation (Section 4.3).

We then introduce the different corner types that can appear in L , T and X -shaped classes, with Theorem 4.6 giving the asymptotics for these classes in terms of the corner type. This is then followed by a detailed examination of each of the corner types (Sections 4.5 to 4.8). To conclude, we prove that almost all gridded permutations are constrained (Section 4.9). Finally, we briefly consider how our approach can be extended beyond connected one-corner classes (Section 4.10).

## 4.1 The distribution of points between cells

For a connected one-corner class, the asymptotic distribution of points between the cells in a typical M -gridded permutation can easily be determined from Theorem 3.8 and Proposition 3.4. The asymptotic proportion of points in each row cell satisfies the same equations and hence these proportions are all equal. The same is true for the column cells.

We use α to denote the proportion of points in the corner cell, β to denote the proportion in each of the row cells, and γ the proportion in each of the column cells. So, for example, the unique maximal distribution matrix for the X -shaped class in Figure 6 has the form

$$\begin{pmatrix} 0 & \gamma & 0 & 0 & 0 \\ 0 & \gamma & 0 & 0 & 0 \\ \beta & \alpha & \beta & \beta & \beta \\ 0 & \gamma & 0 & 0 & 0 \end{pmatrix}.$$

Then, by Theorem 3.8 and Proposition 3.4, we know that α , β and γ are the unique positive solutions to the equations

$$\alpha + c \beta + r \gamma = 1 \ \text{ and } \ \frac { \alpha ^ { 2 } } { ( \alpha + c \beta ) ( \alpha + r \gamma ) } \ = \ \frac { \beta } { \alpha + c \beta } \ = \ \frac { \gamma } { \alpha + r \gamma }.$$

Solving these then yields

$$\alpha \, = \, \frac { 1 } { q }, \quad \beta \, = \, \frac { c - r + q - 1 } { 2 c q }, \quad \gamma \, = \, \frac { r - c + q - 1 } { 2 r q },$$

where

$$q \ = \ \sqrt { ( r + c + 1 ) ^ { 2 } - 4 c r }.$$

Note that

$$\intertext { w e u a } \lambda \ = \ \frac { \beta } { \alpha + c \beta } \ = \ \frac { \gamma } { \alpha + r \gamma } \ = \ \frac { \alpha ^ { 2 } } { ( \alpha + c \beta ) ( \alpha + r \gamma ) } \ = \ \frac { r + c + 1 - q } { 2 r c }$$

is the common value of the ratios from Proposition 3.4.

For example, if r = 3 and c = 4 then we have q = 4, α = 1 4 , β = 1 8 , γ = 1 12 and λ = 1 6 .

## 4.2 The asymptotics of gridded classes

For skinny monotone grid classes, exact enumeration of the gridded permutations is simple: a k -cell skinny grid class has exactly k n gridded n -permutations (Proposition 2.1). For nonskinny classes things are not so straightforward.

Our approach is to determine the generating function for the gridded class, using a technique first described in [9, Chapter 4]. We then extract the asymptotic growth of the number of gridded permutations from the generating function using standard methods from analytic combinatorics.

To determine the generating function for the gridded permutations in an L -shaped, T -shaped or X -shaped class we 'stitch together' two skinny classes, one formed by the main row and the other by the main column.

The bivariate generating function for the ( c + ) 1 -cell horizontal skinny gridded class H # formed from the main row, in which x is used to mark the points in the corner cell, is

$$H ^ { \# } ( z, x ) \ = \ \frac { 1 } { 1 - c z - z x }.$$

Similarly, the bivariate generating function for the ( r + ) 1 -cell vertical skinny gridded class V # formed from the main column, in which y is used to mark the points in the corner cell, is

$$V ^ { \# } ( z, y ) \ = \ \frac { 1 } { 1 - r z - z y }.$$

Thus, the set of pairs ( σ # h , σ # v ) , consisting of an H -gridded permutation σ # h and a V -gridded permutation σ # v , is enumerated by the product of the generating functions of the two skinny classes:

$$P ^ { \# } ( z, x, y ) \ = \ H ^ { \# } ( z, x ) V ^ { \# } ( z, y ) \ = \ \frac { 1 } { ( 1 - c z - z x ) ( 1 - r z - z y ) }.$$

To count M -gridded permutations, we are only interested in those pairs ( σ # h , σ # v ) for which the number of points of σ # h in the corner cell is the same as the number of points of σ # v in the corner cell. Any M -gridded permutation can be decomposed into such a pair, and any such pair combine in a unique way to form an M -gridded permutation, as illustrated in Figure 7.

+

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-b79f8d1d-28da-4a75-be7f-5c934365b5a0.jpg)

=

Figure 7:

Stitching together a

-gridded permutation and a

-gridded permutation

$$to create a | Z | Z | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |$$

In terms of the generating function P # ( z , x y , ) , we need to extract the terms in which x and y have the same exponent. However, we also need to correct for the double-counting of the points in the corner cell. Thus we want

$$\sum _ { m \geqslant 0 } \left [ x ^ { m } y ^ { m } \right ] P ^ { \# } ( z, \, x / \sqrt { z }, \, y / \sqrt { z } ).$$

Here, the division of the second and third arguments by √ z decreases the exponent of z by one for each point in the corner.

To extract the terms in which x and y have the same exponent, we let y = x -1 . This yields a Laurent series 1 in x , where x now records for each pair ( σ # h , σ # v ) the difference between the

1 A Laurent series is a power series in which terms of negative degree are permitted.

number of points of σ # h in the corner and the number of points of σ # v in the corner. We just want the constant term (when this difference is zero):

$$[ x ^ { 0 } ] P ^ { \# } ( z, \, x / \sqrt { z }, \, x ^ { - 1 } / \sqrt { z } ).$$

To extract this constant term, we use the following result.

Proposition 4.1 (Stanley [22, Section 6.3]) . If f ( x ) = f ( z , x ) is a Laurent series, then the constant term [ x 0 ] f ( x ) is given by the sum of the residues 2 of x -1 f ( x ) at those poles α ( z ) of f ( x ) for which lim z → 0 α ( z ) = 0 . These are known as the small poles.

In our case, has two poles, one at x 1 ( z ) = ( 1 -cz ) / √ z , and the other at x 2 ( z ) = √ z / 1 ( -rz ) . Only x 2 ( z ) is small. Thus all we need is the residue at x = x 2 ( z ) . This then yields the following generating function for M -gridded permutations in a connected class with one corner:

$$\L a s e, \quad x ^ { - 1 } P ^ { \# } ( z, \, x / \sqrt { z }, \, x ^ { - 1 } / \sqrt { z } ) \ = \ \frac { 1 } { ( 1 - c z - x \sqrt { z } ) ( x - r z x - \sqrt { z } ) }$$

$$F _ { M } ^ { \# } ( z ) \ = \ \sum _ { n \geqslant 0 } | \text{Grid} _ { n } ^ { \# } ( M ) | \, z ^ { n } \ = \ \frac { 1 } { 1 - ( r + c + 1 ) z + r c z ^ { 2 } }.$$

We extract the asymptotic growth of the number of gridded permutations from this generating function by using the following standard result.

Proposition 4.2 (see [13, Theorems IV.10 and VI.1]) . Suppose F z ( ) is the ordinary generating function of a combinatorial class C . Let ρ be the least singularity of F ( z ) on the positive real axis. If there are no other singularities on the radius of convergence and ρ is a pole of order r, then

$$| \mathcal { C } _ { n } | \, \sim \, c \rho ^ { - n } n ^ { r - 1 } \quad w h e r e \ \ c \, = \, \frac { \rho ^ { - r } } { ( r - 1 )! } \lim _ { z \to \rho } ( \rho - z ) ^ { r } F ( z ).$$

In the case that F z ( ) is a rational function with a denominator Q z ( ) of degree d , the exponential growth rate ρ -1 is the greatest root of the polynomial z d Q z ( -1 ) . Thus the growth rate of Grid # ( M ) , and hence also of Grid ( M ) , equals the larger of the two roots of the quadratic equation z 2 -( r + c + ) 1 z + rc = 0:

$$g _ { M } \, = \, \text{gr} ( \text{Grid} ( M ) ) \, = \, \frac { 1 } { 2 } ( r + c + 1 + q ),$$

where q is defined in equation (2) on page 16. From [2], we know that gM = g ( Γ M ) , so gM could also have been calculated from the proportions in equation (1) by using Proposition 3.3.

Since z = g -1 M is a simple pole of F M # ( z ) , the subexponential term is just a constant:

$$\theta _ { M } ^ { \# } ( n ) \ = \ ( r + c + 1 + q ) / 2 q \ = \ g _ { M } / q.$$

Thus the asymptotic growth of the number of gridded permutations in a connected one-corner class is given by the following proposition.

2 The residue of h x ( ) at x = α is the coefficient of ( x -α ) -1 in the Laurent expansion of h x ( ) around x = α . If α is a simple pole, then this is just the value of yh y ( + ) α at y = 0.

Proposition 4.3. If Mis connected with one corner and has dimensions ( r + ) 1 × ( c + ) 1 , then

$$\left | \text{Grid} _ { n } ^ { \# } ( M ) \right | \, \sim \, \theta ^ { \# } g ^ { n }, \, \ \text{where } \, \theta ^ { \# } \, = \, \frac { r + c + q + 1 } { 2 q } \, \ a n d \, \ g \, = \, \frac { r + c + q + 1 } { 2 },$$

with q

=

√

(

r

+

c

+ )

1

2

-

4

cr.

For example, if M has dimensions 4 × 5 ( r = 3 and c = 4), then ∣ ∣ Grid # n ( M ) ∣ ∣ ∼ 3 2 × 6 . n

## 4.3 Dancing: peaks, diagonals and tees

Generalising from skinny classes, we say that two non-blank cells that are adjacent (either horizontally or vertically) in a gridding matrix form a peak if one is increasing ( ) and the other is decreasing ( ). Thus, in addition to peaks that point up or down, we also have peaks that point left ( ) and peaks that point right ( ).

Given a gridded permutation σ # with at least two points in each cell in a gridded class with a peak Λ that points left or right, the peak point of Λ is the leftmost of the points of σ # in the two cells of Λ if Λ points left, and is the rightmost of the points of σ # in the two cells of Λ if Λ points right. For example, the rightmost circled point in the gridded permutation at the right of Figure 7 on page 17 is the peak point of a peak that points right.

Generalising the notion of dancing we introduced in Section 2.2, if Q is a peak point adjacent to the row or column divider which separates the two cells of the peak, then Q can dance. The movement of this divider to the other side of Q results in another valid gridding.

For one-corner classes, in addition to peaks, we also need to take into account diagonally adjacent pairs of cells that form diagonals , either or . For example, the X -shaped class at the right of Figure 6 on page 15 has two diagonals.

In addition, two peaks may combine to form a tee : that is, any of the four rotations of . For example, the T -shaped class in the centre of Figure 6 has a tee.

We say that a peak is a corner peak if one of its two cells is a corner cell, and that it is a noncorner peak otherwise. For example, the L -shaped class at the left of Figure 6 has one corner peak and four non-corner peaks. In connected one-corner classes, diagonals and tees only occur at corners: diagonals can only be formed by two cells which are adjacent to a corner, and tees can only be formed by a corner cell and two of its neighbours.

The presence of a diagonal or tee makes possible new ways for points to dance. The dancing of a peak point, which we now call peak dancing or dancing at a peak , involves only a single point. In contrast, diagonal dancing and tee dancing may involve more than one point.

Suppose that M is a gridding matrix, with a diagonal formed from two cells separated by a row divider and a column divider. Suppose that σ # is an M -gridded permutation, and that Q is a point of σ # in one of the two cells of the diagonal. If the simultaneous movement of both dividers immediately to the other side of Q results in another valid M -gridding of σ , then we say that Q can dance diagonally . See Figure 8 for an illustration. Note that any points that lie

Figure 8: The four -griddings of 518923467; the three circled points can dance diagonally

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-54f20cd5-aa51-497f-89e1-78a0469259b7.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-25546194-af2e-41ad-9f1e-a0c81037417e.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-cd7d13fe-9e35-4664-8e80-679b6341184e.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-99d88f74-3f16-49df-b4c5-8d5059083b30.jpg)

both horizontally and vertically between Q and the intersection of the dividers can also dance. This yields a monotone sequence of points all of which are able to dance.

Similarly, suppose that M is a gridding matrix, with a tee formed from a corner cell and two other cells, C 1 and C 2 say, separated by a row divider and a column divider. Suppose that σ # is an M -gridded permutation, and that Q is a point of σ # in one of the three cells of the tee. If there is an alternating sequence of one-step moves of the two dividers which leaves one of them immediately the other side of Q and results in another valid M -gridding of σ , then we say that Q can dance through the tee . See Figure 9 for an illustration.

Figure 9: The six -griddings of 816235749; the three circled points can dance through the tee

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-2fa92937-8d76-4cfa-a0de-74730f2b40c0.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-3518cb29-8428-43c0-82cd-9bb2ce40af35.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-136e352d-e8ad-448f-8924-d9f20cf51b14.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-5c8b6441-c75d-46d7-9f71-8baa1ef87044.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-220d34db-79a2-4344-bf1f-4727ded8b01d.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-24864b84-f8ab-4dde-b43b-7b94bfc7a4fa.jpg)

Again, any points that lie between Q and the intersection of the dividers can also dance, yielding a monotone sequence of points that can dance. Note, however, that the first (or last) point in this sequence, lying in C 1 say, may only be able to dance into the corner, and not be able to dance through to C 2. For example, the rightmost circled point in the gridded permutations in Figure 9 can't dance into the cell below the corner.

For almost all permutations in the classes we consider, the valid griddings are restricted to those that can be obtained through peak dancing, diagonal dancing and tee dancing. So, generalising the definition for skinny classes, if Grid ( M ) is a connected one-corner class we say that an M -gridded permutation σ # is M-constrained (or just constrained ) if

- (a) every M -gridding of its underlying permutation σ is the result of zero or more points of σ # dancing at a peak or diagonally or through a tee, and
- (b) in every M -gridding of σ , each non-blank cell contains at least two points.

We defer further analysis and a proof that most M -gridded permutations are constrained until Section 4.9, after a discussion of the different corner types.

## 4.4 Counting griddings

To complete our computation of the asymptotic growth of connected one-corner classes, we determine how a constrained M -gridded permutation σ # must be structured so that its under-

lying permutation σ has a given number of griddings. This depends on the orientation (either increasing or decreasing) of the corner cell and the orientation of each of its non-blank neighbours. Taking symmetries into account, there are eleven inequivalent corner types to consider. These are shown in Table 1 on page 23 below.

By combining this structural analysis with the asymptotic distribution of points between cells from Section 4.1, we then calculate, for each ℓ ⩾ 1, the asymptotic probability

$$P _ { \ell } \, = \, \lim _ { n \to \infty } \mathbb { P } \left [ \sigma \, \text{has exactly $\ell$ distinct $M$-griddings $\colon \sigma^{#} \in \text{Grid}^{#}_{n}(M)$} \right ].$$

Then, letting

$$\kappa _ { M } \, = \, \sum _ { \ell \geqslant 1 } P _ { \ell } / \ell \, = \, \lim _ { n \to \infty } \frac { | \text{Grid} _ { n } ( M ) | } { | \text{Grid} _ { n } ^ { \# } ( M ) | }$$

be the correction factor for the class, we conclude that ∣ ∣ Grid n ( M ) ∣ ∣ ∼ κ M θ # g n , where θ # and g are given by Proposition 4.3.

To determine the probabilities, we make repeated use of the following observation, recalling the definition of the common ratio λ in equation (3) on page 16.

Observation 4.4. Suppose Grid ( M is a connected one-corner class with dimensions ) ( r + ) 1 × ( c + ) 1 , and let α , β and γ be the asymptotic proportion of points of an M-gridded permutation in the corner cell, in any row cell, and in any column cell, respectively.

Then, in an M-gridded permutation, for each k ⩾ 1 , the asymptotic probability that the kth point from the top (or bottom) in the main row occurs in any given row cell equals λ = β / ( α + c β ) . Similarly, the asymptotic probability that the kth point from the left (or right) in the main column occurs in any given column cell also equals λ = γ / ( α + r γ ) .

̸

Moreover, for j = k, the events that the jth and kth points from the top or bottom in the main row occur in specific cells are asymptotically independent. And analogously for points in the main column.

Note also that if dancing can occur asymptotically independently in more than one location, then the corresponding correction factors multiply. This follows from the following arithmetic observation.

Observation 4.5. Given real sequences ( P i ′ ) i ⩾ 1 and ( P j ′′ ) j ⩾ 1 , let κ ′ = ∑ i ⩾ 1 P i ′ / i and κ ′′ = ∑ j ⩾ 1 P j ′′ / j.

$$S u p p o s e \, P _ { \ell } = \sum _ { i j = \ell } P _ { i } ^ { \prime } \, P _ { j } ^ { \prime \prime }. \, T h e n,$$

$$\sum _ { \ell \geqslant 1 } P _ { \ell } / \ell \, = \, \kappa ^ { \prime } \, \kappa ^ { \prime \prime }.$$

Proof.

$$\kappa ^ { \prime } \, \kappa ^ { \prime \prime } \, = \, \sum _ { i \geqslant 1 } \frac { P _ { i } ^ { \prime } } { i } \, \sum _ { j \geqslant 1 } \frac { P _ { j } ^ { \prime \prime } } { j } \, = \, \sum _ { i, j \geqslant 1 } \frac { P _ { i } ^ { \prime } \, P _ { j } ^ { \prime \prime } } { i j } \, = \, \sum _ { \ell \geqslant 1 } \frac { 1 } { \ell } \sum _ { i j = \ell } P _ { i } ^ { \prime } \, P _ { j } ^ { \prime \prime } \, = \, \sum _ { \ell \geqslant 1 } \frac { P _ { \ell } } { \ell }.$$

## Non-corner peaks

Before looking at each corner type in turn, we consider the effect of non-corner peaks. By definition, in any constrained M -gridded permutation, at each non-corner peak of M there is a peak point which can dance. So, if M has p non-corner peaks, these contribute a factor of 2 p to the number of possible M -griddings, in an analogous manner to skinny classes (Proposition 2.2). Thus, since almost all M -gridded permutations are M -constrained (see Theorem 4.8 below), the asymptotic enumeration of L , T and X -shaped classes is given by the following result.

Theorem 4.6. Suppose Grid ( M is a connected one-corner class with corner type ) τ , and p non-corner peaks, then

$$\left | \text{Grid} _ { n } ( M ) \right | \, \sim \, 2 ^ { - p } \, \kappa ( \tau ) \, \theta ^ { \# } \, g ^ { n },$$

where κ τ ( ) is the correction factor for a gridding matrix with the same corner type and dimensions as Mbut with no non-corner peaks, and θ # and g are as given by Proposition 4.3.

Note that the correction factor for the class is given by κ M = 2 -p κ τ ( ) .

## Worked example

Before turning to the calculation of the correction factors for each corner type, we very briefly illustrate our method with an example, by determining the asymptotic enumeration of the X -shaped class from Figure 6:

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-743dd02e-76db-4402-a22f-952d43e351be.jpg)

Firstly, from Proposition 4.3, since r = 3 and c = 4, we have ∣ ∣ Grid # n ( M X ) ∣ ∣ ∼ 3 2 × 6 . n

Secondly, M X has three non-corner peaks and has corner type X 0. Now, κ ( X 0 ) = ( 1 -λ ) 2 , and from equation (3) we know that λ = 1 6 .

Thus, by Theorem 4.6, we have

$$\left | \text{Grid} _ { n } ( M _ { \times } ) \right | \, \sim \, 2 ^ { - 3 } \times \left ( \frac { 5 } { 6 } \right ) ^ { 2 } \times \frac { 3 } { 2 } \times 6 ^ { n } \, = \, \frac { 2 5 } { 1 9 2 } \times 6 ^ { n }.$$

## Correction factors for corner types

We now calculate κ τ ( ) for each corner type τ . Table 1 summarises our results.

The subscripts in the names used for corner types are determined by reading the non-blank cells in normal reading order and treating as 0 and as 1 to give a binary number. For example, T 5 is since 5 = 01012. The symmetry giving the least subscript is chosen as the representative. Note that rotating a class by 90 ◦ switches the roles of r and c and of β and γ . We use τ R to denote a 90 ◦ rotation of corner type τ .

In the figures used below for each corner type, dots indicate where additional row and column cells may occur, as long as they don't create additional corner peaks, diagonals or tees.

We begin with the simplest of the corner types.

Table 1: The correction factors and the number of peaks ( P ), diagonals ( D ) and tees ( T ) for each of the eleven corner types

| τ   |   P |   D |   T | κ ( τ )                                                                    |
|-----|-----|-----|-----|----------------------------------------------------------------------------|
| L 0 |   0 |   0 |   0 | 1                                                                          |
| L 1 |   1 |   0 |   0 | 1 2 ( 1 + c αλ α + γ )                                                     |
| L 3 |   0 |   0 |   1 | λ ( 1 - λ ) ( 1 - ( c - 1 ) λ ) ( 1 - ( r - 1 ) λ )                        |
| L 4 |   2 |   0 |   0 | 1 4 ( 1 + r αλ α + β )( 1 + c αλ α + γ )                                   |
| L 7 |   0 |   1 |   0 | 1 - λ                                                                      |
| T 2 |   1 |   1 |   0 | 1 2 ( 1 + r αλ α + β ) ( 1 - λ )                                           |
| T 4 |   1 |   0 |   1 | 1 2 ( 1 + r αλ α + β ) λ ( 1 - λ ) ( 1 - ( c - 1 ) λ ) ( 1 - ( r - 1 ) λ ) |
| T 5 |   2 |   0 |   0 | 1 4 ( 1 + r αλ α + β ) 2                                                   |
| X 0 |   0 |   2 |   0 | ( 1 - λ ) 2                                                                |
| X 4 |   0 |   0 |   2 | ( λ ( 1 - λ ) ( 1 - ( c - 1 ) λ ) ( 1 - ( r - 1 ) λ ) ) 2                  |
| X 7 |   2 |   1 |   0 | 1 4 ( 1 + r αλ α + β )( 1 + c αλ α + γ ) ( 1 - λ )                         |

## Corner type L 0

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-421dd2ae-b335-40f9-a3c5-cb92155cbec8.jpg)

This corner type has no peaks, diagonals or tees. It can't occur in a T -shaped or X -shaped class. In a constrained gridded permutation, no dancing is possible, so the underlying permutation has a single gridding. Thus P 1 = 1, and P ℓ = 0 if ℓ &gt; 1. Hence κ ( L 0 ) = 1.

## 4.5 Corners with peaks

## Corner type L 1

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-5a419cd3-b2e6-4790-a253-61308a4ede69.jpg)

This corner type has one peak. It can't occur in an X -shaped class. As can be seen from the figures, the peak may be orientated in different ways with respect to the other cells adjacent to

the corner. However, the analysis is the same in every case, so we consider this to be a single corner type.

Given a constrained gridded permutation, let Q be the peak point, and let R be the lowest point in any of the row cells. Q is the only point that may be able to dance. It can't dance if it is above R in the corner cell. Otherwise (if it is below R , either in the corner cell or in the cell below the corner) it can dance. We say that point R is the controller , since it controls whether Q can dance or not. See Figure 10 for an illustration of the three cases.

Figure 10: Three -gridded permutations; the peak point is circled if it can dance

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-6a6b25c0-8126-4792-a84e-da05f1e9ca16.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-25b32fde-3c63-427b-9efc-24d07eb93dc7.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-7bb4a940-939d-455c-af20-04903143f83b.jpg)

The peak point, Q , is either in the corner or in the cell immediately below the corner. Thus the asymptotic probability that Q is in the corner equals α / ( α + γ ) , and the asymptotic probability that the lowest point in the main row is not in the corner equals c β / ( α + c β ) . These events are asymptotically independent, so

$$\mathbb { P } [ Q \, \text{can} ^ { \prime } t \, \text{done} ] \, \sim \, P _ { 1 } \, = \, \frac { \alpha } { \alpha + \gamma } \times \frac { c \beta } { \alpha + c \beta } \, = \, \frac { c \alpha \lambda } { \alpha + \gamma } \quad \text{and} \quad P _ { 2 } \, = \, 1 - P _ { 1 }.$$

Hence,

$$\kappa ( L _ { 1 } ) \ = \ P _ { 1 } + \frac { 1 } { 2 } P _ { 2 } \ = \ \frac { 1 } { 2 } \Big { ( } 1 + \frac { c \alpha \lambda } { \alpha + \gamma } \Big { ) } \ = \ \frac { 2 r } { 3 r - c + q - 1 }.$$

## Corner type L 4

This corner type has two peaks. It can't occur in an X -shaped class. Given a constrained gridded permutation, let Q 1 be the peak point at the left and Q 2 be the peak point at the top. The same analysis as for L 1 gives

$$\mathbb { P } [ Q _ { 1 } \, \text{can} ^ { \prime } t \, \text{done} ] \, \sim \, \frac { c \alpha \lambda } { \alpha + \gamma }, \quad \mathbb { P } [ Q _ { 2 } \, \text{can} ^ { \prime } t \, \text{done} ] \, \sim \, \frac { r \alpha \lambda } { \alpha + \beta }.$$

The event that Q 1 can dance depends on the points adjacent to the row divider below the corner, whereas the event that Q 2 can dance depends on the points adjacent to the column divider to the right of the corner. Thus these events are asymptotically independent. So, by Observation 4.5, we have

$$\kappa ( L _ { 4 } ) \ = \ \kappa ( L _ { 1 } ) \, \kappa ( L _ { 1 } ^ { R } ) \ = \ \frac { 1 } { 4 } \Big { ( } 1 + \frac { r \alpha \lambda } { \alpha + \beta } \Big { ) } \, \Big { ( } 1 + \frac { c \alpha \lambda } { \alpha + \gamma } \Big { ) } \ = \ \frac { 4 r c } { ( 3 r - c + q - 1 ) ( 3 c - r + q - 1 ) }.$$

## Corner type T 5

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-bf7862a1-70d8-4915-9109-cf7ff8169306.jpg)

This corner type also has two peaks. It can't occur in an L -shaped class. Given a constrained gridded permutation, let Q 1 and Q 2 be the two peak points. The same analysis as for L 1 gives

$$\mathbb { P } \left [ Q _ { 1 } \, \text{can} ^ { \prime } t \, \text{done} \right ] \, \sim \, \mathbb { P } \left [ Q _ { 2 } \, \text{can} ^ { \prime } t \, \text{done} \right ] \, \sim \, \frac { r \alpha \lambda } { \alpha + \beta }.$$

The event that one of the peak points can dance depends on the points adjacent to the column divider to the left of the corner, whereas the event that the other peak point can dance depends on the points adjacent to the column divider to the right of the corner. Thus these events are asymptotically independent. So, by Observation 4.5, we have

$$\kappa ( T _ { 5 } ) \ = \ \kappa ( L _ { 1 } ^ { R } ) ^ { 2 } \ = \ \frac { 1 } { 4 } \left ( 1 + \frac { r \alpha \lambda } { \alpha + \beta } \right ) ^ { 2 } \ = \ \frac { 4 c ^ { 2 } } { ( 3 c - r + q - 1 ) ^ { 2 } }.$$

## 4.6 Corners with diagonals

## Corner type L 7

This corner type has one diagonal. It can't occur in an X -shaped class. Let C R be the cell immediately to the right of the corner, and C B be the cell immediately below the corner.

Figure 11: A -gridded permutation; the five circled points, below Q 1 and to the right of Q 2, can dance; k 1 = 2 and k 2 = 3

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-82b03831-89b5-4a5d-b90e-a43af217d3c4.jpg)

Given a constrained gridded permutation, let Q 1 be the lowest point in the main row that is not in C R . Note that Q 1 may be in the corner cell. Let k 1 be the number of points in C R that lie below Q 1. Similarly, let Q 2 be the rightmost point in the main column that is not in C B ( Q 2 may also be in the corner cell), and let k 2 be the number of points in C B that lie to the

right of Q 2. These k 1 + k 2 points can dance diagonally, giving k 1 + k 2 + 1 distinct griddings of the underlying permutation. Note that both k 1 and k 2 may be zero. Points above Q 1 and points to the left of Q 2 can't dance. Points Q 1 and Q 2 are the controllers, because they control which points can dance. See Figure 11 for an illustration.

Now, by Observation 4.4, for each i ⩾ 0, we have

$$\mathbb { P } \left [ k _ { 1 } = i \right ] \, \sim \, \lambda ^ { i } ( 1 - \lambda ) \quad \text{and also} \quad \mathbb { P } \left [ k _ { 2 } = i \right ] \, \sim \, \lambda ^ { i } ( 1 - \lambda ).$$

The value of k 1 is asymptotically independent of the value of k 2. Thus, for each ℓ ⩾ 1, the asymptotic probability of having exactly ℓ griddings is

$$\mathbb { P } [ k _ { 1 } + k _ { 2 } + 1 = \ell ] \ = \ \sum _ { k _ { 1 } = 0 } ^ { \ell - 1 } \mathbb { P } [ k _ { 1 } = i ] \mathbb { P } [ k _ { 2 } = \ell - 1 - i ] \ \sim \ \ell \, \lambda ^ { \ell - 1 } ( 1 - \lambda ) ^ { 2 }.$$

Hence,

$$\kappa ( L _ { 7 } ) \ = \ \sum _ { \ell = 1 } ^ { \infty } \lambda ^ { \ell - 1 } ( 1 - \lambda ) ^ { 2 } \ = \ 1 - \lambda \ = \ 1 - \frac { r + c + 1 - q } { 2 r c }.$$

## Corner type T 2

This corner type has one peak and one diagonal. It can't occur in an L -shaped class.

Dancing at the peak depends on the points adjacent to the column divider to the right of the corner, whereas dancing on the diagonal depends on the points adjacent to the column divider to the left of the corner and points adjacent to the row divider below the corner. So these are asymptotically independent. Thus, from the analysis for L 1 and L 7, and by Observation 4.5, we have

$$\kappa ( T _ { 2 } ) \ = \ \kappa ( L _ { 1 } ^ { \text{R} } ) \, \kappa ( L _ { 7 } ) \ = \ \frac { 1 } { 2 } \left ( 1 + \frac { r \alpha \lambda } { \alpha + \beta } \right ) ( 1 - \lambda ).$$

## Corner type X 0

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-899f65e5-abcd-4473-b03e-4c05fb798d79.jpg)

This corner type has two diagonals. It can't occur in an L -shaped or T -shaped class.

Dancing on one of the diagonals depends on the points adjacent to the column divider to the left of the corner and points adjacent to the row divider below the corner, whereas dancing

on the other diagonal depends on the points adjacent to the column divider to the right of the corner and points adjacent to the row divider above the corner. So these are asymptotically independent. Thus, from the analysis for L 7, and by Observation 4.5, we have

$$\kappa ( X _ { 0 } ) \ = \ \kappa ( L _ { 7 } ) ^ { 2 } \ = \ ( 1 - \lambda ) ^ { 2 }.$$

## Corner type X 7

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-facb6cdc-0cae-4642-bfbb-7505e2b76fb4.jpg)

This corner type has two peaks and one diagonal. It can't occur in an L -shaped or T -shaped class.

Dancing at the two peaks depends on the points adjacent to the column divider to the left of the corner and points adjacent to the row divider above the corner, whereas dancing on the diagonal depends on the points adjacent to the column divider to the right of the corner and points adjacent to the row divider below the corner. So these are asymptotically independent. Thus, from the analysis for L 4 and L 7, and by Observation 4.5, we have

$$\kappa ( X _ { 7 } ) \ = \ \kappa ( L _ { 4 } ) \, \kappa ( L _ { 7 } ) \ = \ \frac { 1 } { 4 } \left ( 1 + \frac { r \alpha \lambda } { \alpha + \beta } \right ) \left ( 1 + \frac { c \alpha \lambda } { \alpha + \gamma } \right ) ( 1 - \lambda ).$$

## 4.7 Corners with tees

## Corner type L 3

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-b49fe263-f648-4c92-b36b-c7f55fd48857.jpg)

This corner type has one tee. It is the only one of the eleven corner types that can occur in L -shaped, T -shaped and X -shaped classes.

Analysis of this corner type is considerably more complex than for the corners we've considered so far. We analyse the main row by reading its points from the bottom. Similarly, we analyse the main column by reading its points from the right. Let C denote the corner cell, let C R be the cell immediately to the right of C , and let C B be the cell immediately below C .

## Sequences of points

We represent the sequence of points in the main row, when read from the bottom, by words over the alphabet { x y z , , } . The letter x represents a point in the corner cell C , the letter y represents a point in C R , and the letter z represents a point in some other cell of the main row. We

use subscripts to identify specific points. Thus x Q represents the occurrence of point Q in the corner cell. For example, the sequence of points in the main row of the gridded permutation at the left of Figure 12 is represented by the word x Q y x R y y z S x z y .

Simple regular expressions are used to denote sets specifying the possible ordering of the initial points. In these regular expressions, a ∗ denotes a sequence of zero or more copies of letter a . For example, z ∗ x Q consists of arrangements of points in the main row in which Q is the lowest point in the corner cell ( x Q being the first occurrence of x ) and where Q is below any points in C R , the only points below Q occurring elsewhere (represented by z ∗ ). Note that any ordering of points is permitted after the initial points specified by the regular expression.

By Observation 4.4, associated with x , y and z we have the following asymptotic probabilities:

$$p _ { \times } \, = \, 1 - c \lambda, \quad p _ { y } \, = \, \lambda, \quad p _ { z } \, = \, ( c - 1 ) \lambda.$$

By symmetry, for the location of points in the main column, when read from the right, the same approach yields the following asymptotic probabilities:

$$q _ { x } \, = \, 1 - r \lambda, \quad q _ { y } \, = \, \lambda, \quad q _ { z } \, = \, ( r - 1 ) \lambda.$$

The asymptotic probability that the points in the main row are in (the set denoted by) some regular expression is given by the product formed by replacing each x by p x , each y by p y and each z by p z , and replacing each x ∗ , y ∗ and z ∗ by 1/ 1 ( -p x ) , 1/ 1 ( -p y ) and 1/ 1 ( -p z ) , respectively. For example, the asymptotic probability that the arrangement of points in the main row is in z ∗ x Q equals p x / 1 ( -p z ) .

## The number of griddings

Recall, from the introduction to tee dancing on page 20, that a monotone sequence of points can dance. The points not at one of the ends of the sequence can dance between C R and C B through C . However, the first and last of these points may only be able to dance between C R and C or between C B and C , but not from C R to C B .

Each point that can dance between C R and C B contributes two to the number of griddings. However, a point that can only dance between C and either C R or C B contributes just one additional gridding. In our analysis below, we determine the contribution to the number of griddings from points in the main row, which we denote m 1, and also the contribution to the number of griddings from points in the main column, which we denote m 2. Including the original gridding, the total number of distinct griddings is then m 1 + m 2 + 1.

## Labelled points

Given a constrained gridded permutation, let Q be the lowest point in the corner cell C . Our analysis depends on whether or not Q is the peak point of each of the two peaks that form the tee.

If c &gt; 1 (so we have more than two columns), then let S be the lowest point in the main row that is in a cell other than C or C R . Similarly, if r &gt; 1, then let T be the rightmost point in the main column that is in a cell other than C or C B .

We consider three cases. In the first, Q is the peak point of both of the peaks that form the tee. In the second, Q is not the peak point of either of the peaks that form the tee. Finally, in the third, Q is the peak point of just one of the two peaks.

## Case 1: Q is the peak point of both of the peaks that form the tee

In Case 1, point Q is lower than every point in C R and to the right of every point in C B . If S is above Q , then Q is adjacent to the row divider below C and can dance vertically into C B , contributing one to the number of griddings. Similarly, if T is to the left of Q , then Q is adjacent to the column divider to the right of C and can dance horizontally into C R , again contributing one to the number of griddings.

Let R be the second lowest point in the corner cell C . That is, R is the point immediately above Q in the corner cell. Points R S , and T are the controllers, because they control which points can dance.

Let k 1 be the number of points in C R below both R and S (if c &gt; 1). These k 1 points are above Q , and thus can all dance through the tee to C B , each contributing 2 to the number of griddings. Similarly, let k 2 be the number of points in C B to the right of both R and T (if r &gt; 1). These k 2 points are to the right of Q , and can also all dance through to C R , again each contributing 2 to the number of griddings. Note that k 1 and k 2 may be zero. See Figure 12 for two gridded permutations satisfying the conditions of Case 1.

Figure 12: L 3 Case 1: -gridded permutations; the circled points can dance

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-4b5d2b0f-a99f-4788-a49b-13c5eecb0f04.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-28090204-2803-4bbb-9163-81e8667d3ae6.jpg)

In Case 1, the possible ordering of the points in the main row, reading from the bottom, is given by the regular expression z ∗ x Q , the only points below Q (if any) being in cells other than C and C R . So, the asymptotic probability that the points in the main row of a gridded permutation satisfy the conditions of Case 1 is given by

$$p _ { 1 } \, \coloneqq \, \mathbb { P } \left [ \text{Case 1} \right ] \, = \, \frac { p _ { \times } } { 1 - p _ { z } } \, = \, \frac { 1 - c \lambda } { 1 - ( c - 1 ) \lambda }.$$

For both the main row and the main column, we have three subcases. We analyse the main row, reading its points from the bottom. The analysis of the main column is analogous (reading its points from the right). The three subcases are as follows:

- 1a. S , if it exists, is above Q , which is the lowest point in the main row. S (if it exists) may be above or below R . There is no point in C R that is above S and below R . See the left of Figure 12 for examples in both the main row and the main column.

Q can dance vertically into C B . Thus m 1 = 2 k 1 + 1.

The possible ordering of the points in the main row, reading from the bottom, is given by the regular expression x Q y ∗ ∗ z x R . So, for each i ⩾ 0, we have

$$p _ { 1 \mathbf a } ( i ) \ \coloneqq \ \mathbb { P } \left [ \text{Case 1} \, \text{a and } k _ { 1 } = i \right ] \ = \ \frac { p _ { x } ^ { 2 } \, p _ { y } ^ { i } } { 1 - p _ { z } } \ = \ \frac { ( 1 - c \lambda ) ^ { 2 } \, \lambda ^ { i } } { 1 - ( c - 1 ) \lambda }.$$

- 1b. S is above Q and below R , and at least one point in C R is above S and below R . Again, Q is the lowest point in the main row. Let U be the lowest of these points. Note that U is not one of the k 1 points in C R below both R and S . Other points not in C or C R may lie below U . See the right of Figure 12 for an example.

Q can dance vertically into C B , contributing one to the number of griddings. And U can dance horizontally into the corner cell, but not from the corner into C B , so this contributes another gridding. Thus m 1 = 2 k 1 + 2.

The possible ordering of the points in the main row, reading from the bottom, is given by the regular expression x Q y ∗ z S z ∗ y U . So, for each i ⩾ 0, we have

$$p _ { 1 b } ( i ) \ \coloneqq \ \mathbb { P } [ \text{Case } 1 b \text{ and } k _ { 1 } = i ] \ \ = \ \frac { p _ { \times } p _ { y } ^ { i + 1 } \, p _ { z } } { 1 - p _ { z } } \ \ = \ \frac { ( 1 - c \lambda ) \, \lambda ^ { i + 1 } \, ( c - 1 ) \lambda } { 1 - ( c - 1 ) \lambda }.$$

1c. S is below Q . So Q can't dance vertically into C B , and k 1 = 0, since every point in C R is above Q and hence also above S . Thus m 1 = 0. See the right of Figure 12 for an example of this in the main column , in which the controller T is to the right of Q , so Q can't dance horizontally into C R , and m 2 = k 2 = 0.

The possible ordering of the points in the main row, reading from the bottom, is given by the regular expression z S z ∗ x Q . Thus,

$$p _ { 1 \text{c} } \ \coloneqq \ \mathbb { P } \left [ \text{Case } 1 \text{c and } k _ { 1 } = 0 \right ] \ = \ \frac { p _ { x } \, p _ { z } } { 1 - p _ { z } } \ = \ \frac { \left ( 1 - c \lambda \right ) \left ( c - 1 \right ) \lambda } { 1 - \left ( c - 1 \right ) \lambda }.$$

Table 2 gives the total number of griddings for each possibility in Case 1.

Table 2: The number of griddings for each combination of subcases in Case 1

|                |                 | Main row 1a m 1 = 2 k 1 + 1   | Main row 1b m 1 = 2 k 1 + 2   | Main row 1c m 1 = 0   |
|----------------|-----------------|-------------------------------|-------------------------------|-----------------------|
| Main column 1a | m 2 = 2 k 2 + 1 | 2 k 1 + 2 k 2 + 3             | 2 k 1 + 2 k 2 + 4             | 2 k 2 + 2             |
| Main column 1b | m 2 = 2 k 2 + 2 | 2 k 1 + 2 k 2 + 4             | 2 k 1 + 2 k 2 + 5             | 2 k 2 + 3             |
| Main column 1c | m 2 = 0         | 2 k 1 + 2                     | 2 k 1 + 3                     | 1                     |

We now the calculate, for each ℓ ⩾ 1, the probability P 1 ( ℓ ) : = P [ Case 1 and ℓ griddings . ]

Let q 1a ( ) i , q 1b ( ) i and q 1c be the subcase probabilities for the main column, formed from p 1a ( ) i , p 1b ( ) i and p 1c by replacing p x , p y , p z with q x , q y , q z , respectively.

Then, from Table 2, we have

- P 1 ( 1 ) = p 1c q 1c ,

$$P _ { 1 } ( 2 ) \ = \ p _ { 1 \mathfrak { a } } ( 0 ) \, q _ { 1 \mathfrak { c } } \, + \, p _ { 1 \mathfrak { c } } \, q _ { 1 \mathfrak { a } } ( 0 ),$$

$$P _ { 1 } ( 3 ) \, = \, p _ { 1 \mathfrak { a } } ( 0 ) \, q _ { 1 \mathfrak { a } } ( 0 ) \, + \, p _ { 1 \mathfrak { b } } ( 0 ) \, q _ { 1 \mathfrak { c } } \, + \, p _ { 1 \mathfrak { c } } \, q _ { 1 \mathfrak { b } } ( 0 ),$$

$$P _ { 1 } ( \ell ) \ = & \quad p _ { 1 \mathbf a } ( \frac { \ell - 2 } { 2 } ) \, q _ { 1 \mathbf c } \, + \, p _ { 1 \mathbf c } \, q _ { 1 \mathbf a } ( \frac { \ell - 2 } { 2 } ) \\ & + \sum _ { i = 0 } ^ { ( \ell - 4 ) / 2 } \left ( p _ { 1 \mathbf a } ( i ) \, q _ { 1 \mathbf b } ( \frac { \ell - 4 } { 2 } - i ) \, + \, p _ { 1 \mathbf b } ( \frac { \ell - 4 } { 2 } - i ) \, q _ { 1 \mathbf a } ( i ) \right ), \quad \ell \geqslant 4, \text{even}, \\ - \, \widehat { \sim } \quad & \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \ \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \ \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \,$$

$$P _ { 1 } ( \ell ) \, = \, & \quad \ p _ { 1 \mathbf b } ( \frac { \ell - 3 } { 2 } ) \, q _ { 1 \mathbf c } + p _ { 1 \mathbf c } q _ { 1 \mathbf b } ( \frac { \ell - 3 } { 2 } ) \\ & + \sum _ { i = 0 } ^ { ( \ell - 3 ) / 2 } p _ { 1 \mathbf a } ( i ) \, q _ { 1 \mathbf a } ( \frac { \ell - 3 } { 2 } - i ) \, + \sum _ { i = 0 } ^ { ( \ell - 5 ) / 2 } p _ { 1 \mathbf b } ( i ) \, q _ { 1 \mathbf b } ( \frac { \ell - 5 } { 2 } - i ), \quad \ell \geq 5, \text{ odd.}$$

After simplification, facilitated by using a computer algebra system, this yields

$$P _ { 1 } ( \ell ) \, = \, \begin{cases} \frac { \lambda ^ { ( \ell - 3 ) / 2 } \, p _ { \times } \, q _ { \times } \left ( ( \ell - 1 ) \, p _ { \times } \, q _ { \times } + ( \ell + 1 ) \, \lambda \, p _ { z } \, q _ { \times } \right ) } { 2 \, ( 1 - p _ { z } ) \, ( 1 - q _ { z } ) }, & \ell \geqslant 1, \, \text{odd}, \\ \frac { \ell \, \lambda ^ { ( \ell - 2 ) / 2 } \, p _ { \times } \, q _ { \times } \, ( p _ { \times } \, q _ { z } + p _ { z } \, q _ { \times } ) } { 2 \, ( 1 - p _ { z } ) \, ( 1 - q _ { z } ) }, & \ell \geqslant 2, \, \text{even}. \end{cases}$$

## Case 2: Q is not the peak point of either of the peaks that form the tee

In Case 2, there is a point in C R below Q and a point in C B to the right of Q . So Q can't dance into either C B or C R . Points Q S , and T are the controllers, controlling which points can dance.

Let k 1 be the number of points in C R below both Q and S (if c &gt; 1). These k 1 points can all dance through the tee to C B , each contributing 2 to the number of griddings. Similarly, let k 2 be the number of points in C B to the right of both Q and T (if r &gt; 1). These k 2 points can also all dance through to C R , again each contributing 2 to the number of griddings. See Figure 13 for a gridded permutation satisfying the conditions of Case 2. Again, k 1 and k 2 may be zero.

For both the main row and the main column, we have two subcases. We analyse the main row, the analysis of the main column being analogous.

- 2a. There is no point in C R above S and below Q S . may be above or below Q , or S may not exist. Since there is a point in C R below Q (by the definition of Case 2), in this subcase (only) we know that k 1 &gt; 0.
- The k 1 points in C R below both Q and S (if it exists) can all dance through to C B . Thus m 1 = 2 k 1.

Figure 13: L 3 Case 2: a -gridded permutation; the circled points can dance

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-21b8c07c-50ad-403d-82d1-b9427b056f00.jpg)

The possible ordering of the points in the main row, reading from the bottom, is given by the regular expression yy ∗ ∗ z x Q . So, for each i ⩾ 1, we have

$$p _ { 2 \mathbf a } ( i ) \ \coloneqq \ \mathbb { P } \left [ \text{Case 2a and } k _ { 1 } = i \right ] \ = \ \frac { p _ { \times } \, p _ { y } ^ { i } } { 1 - p _ { z } } \ = \ \frac { ( 1 - c \lambda ) \, \lambda ^ { i } } { 1 - ( c - 1 ) \lambda }.$$

2b. S is below Q with at least one point in C R above S and below Q . Let U be the lowest of these points. Note that U is not one of the k 1 points in C R that are below both Q and S . Other points not in C or C R may lie below U .

U can dance horizontally into the corner cell, but not from the corner into C B . Thus m 1 = 2 k 1 + 1.

The possible ordering of the points in the main row, reading from the bottom, is given by the regular expression y ∗ z S z ∗ y U . So, for each i ⩾ 0, we have

$$p _ { 2 \mathbf b } ( i ) \ \coloneqq \ \mathbb { P } \left [ \text{Case 2} \mathbf b \text{ and } k _ { 1 } = i \right ] \ = \ \frac { p _ { y } ^ { i + 1 } \, p _ { z } } { 1 - p _ { z } } \ = \ \frac { \lambda ^ { i + 1 } \, ( c - 1 ) \lambda } { 1 - ( c - 1 ) \lambda }.$$

Table 3 gives the total number of griddings for each possibility in Case 2.

Table 3: The number of griddings for each combination of subcases in Case 2

|                |                 | Main row 2a m 1 = 2 k 1   | Main row 2b m 1 = 2 k 1 + 1   |
|----------------|-----------------|---------------------------|-------------------------------|
| Main column 2a | m 2 = 2 k 2     | 2 k 1 + 2 k 2 + 1         | 2 k 1 + 2 k 2 + 2             |
| Main column 2b | m 2 = 2 k 2 + 1 | 2 k 1 + 2 k 2 + 2         | 2 k 1 + 2 k 2 + 3             |

We now calculate, for each ℓ ⩾ 1, the probability P 2 ( ℓ ) = P [ Case 2 and ℓ griddings . ]

Let q 2a ( ) i and q 2b ( ) i be the subcase probabilities for the main column, formed from p 2a ( ) i and p 2b ( ) i by replacing p x , p y , p z with q x , q y , q z , respectively.

Then, from Table 3, we have

$$\cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \\ P _ { 2 } ( 3 ) \ & = \ p _ { 2 b } ( 0 ) \ q _ { 2 b } ( 0 ), \\ P _ { 2 } ( \ell ) \ & = \sum _ { i = 1 } ^ { ( \ell - 2 ) / 2 } \left ( p _ { 2 a } ( i ) \ q _ { 2 b } \left ( \frac { \ell - 2 } { 2 } - i \right ) \, + \, p _ { 2 b } \left ( \frac { \ell - 2 } { 2 } - i \right ) q _ { 2 a } ( i ) \right ), \quad \ell \geqslant 4, \text{even}, \\ P _ { 2 } ( \ell ) \ & \sum _ { i = 1 } ^ { ( \ell - 1 ) / 2 - 1 } p _ { 2 a } ( i ) \ q _ { 2 a } \left ( \frac { \ell - 1 } { 2 } - i \right ) \, + \, \sum _ { i = 0 } ^ { ( \ell - 3 ) / 2 } p _ { 2 b } ( i ) \ q _ { 2 b } \left ( \frac { \ell - 3 } { 2 } - i \right ), \quad \ell \geqslant 5, \text{odd}.$$

## After simplification, this yields

$$\ell _ { 2 } & = \begin{cases} 0, & \ell = 1, \\ \frac { \left ( \ell - 2 \right ) \lambda ^ { \ell / 2 } \left ( p _ { \times } q _ { z } + p _ { z } q _ { \times } \right ) } { 2 \left ( 1 - p _ { z } \right ) \left ( 1 - q _ { z } \right ) }, & \ell \geqslant 2, \text{even}, \\ \frac { \lambda ^ { \left ( \ell - 1 \right ) / 2 } \left ( \left ( \ell - 3 \right ) p _ { \times } q _ { \times } + \left ( \ell - 1 \right ) \lambda \, p _ { z } q _ { z } \right ) } { 2 \left ( 1 - p _ { z } \right ) \left ( 1 - q _ { z } \right ) }, & \ell \geqslant 3, \text{odd}. \end{cases}$$

## Case 3: Q is the peak point of just one of the two peaks that form the tee

Case 3 combines Case 1 for the main row and Case 2 for the main column, or vice versa.

Suppose the main row satisfies Case 1 and the main column satisfies Case 2, as in Figure 14. Then Q can't dance into either C R or C B because of the points to its left in C B . Neither can the points in C R dance, because Q is below them. So m 1 = 0. On the other hand, the Case 2 analysis of the main column is still valid, the k 2 points in C B to the right of Q being able to dance through to C R .

The situation is analogous if the main row satisfies Case 2 and the main column satisfies Case 1. Table 4 gives the total number of griddings for each possibility in Case 3.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-93550fef-e658-48fe-8fa3-9f33f5f78e84.jpg)

$$\text{Figure 14} \colon L _ { 3 } \, \text{Case 3} \colon a \, \stackrel { | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |$$

Table 4: The number of griddings for each combination of subcases in Case 3

|                |                 | Main row 1 m 1 = 0   | Main row 2a m 1 = 2 k 1   | Main row 2b m 1 = 2 k 1 + 1   |
|----------------|-----------------|----------------------|---------------------------|-------------------------------|
| Main column 1  | m 2 = 0         |                      | 2 k 1 + 1                 | 2 k 1 + 2                     |
| Main column 2a | m 2 = 2 k 2     | 2 k 2 + 1            |                           |                               |
| Main column 2b | m 2 = 2 k 2 + 1 | 2 k 2 + 2            |                           |                               |

Thus, for each ℓ ⩾ 1, the probability P 3 ( ℓ ) = P [ Case 3 and ℓ griddings ] is given by

$$P _ { 3 } ( \ell ) \, = \, \begin{cases} 0, & \ell \, \cdots \, \ell \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \end{cases}. \\ P _ { 3 } ( \ell ) \, = \, \begin{cases} 0, & \ell = 1, \\ p _ { 2 b } ( \frac { \ell - 2 } { 2 } ) \, q _ { 1 } \, + \, p _ { 1 } \, q _ { 2 b } ( \frac { \ell - 2 } { 2 } ) \, = \, \frac { \lambda ^ { \ell / 2 } \, ( p _ { x } \, q _ { z } + p _ { z } \, q _ { x } ) } { ( 1 - p _ { z } ) \, ( 1 - q _ { z } ) }, & \ell \geqslant 2, \, \text{even}, \\ p _ { 2 a } ( \frac { \ell - 1 } { 2 } ) \, q _ { 1 } \, + \, p _ { 1 } \, q _ { 2 a } ( \frac { \ell - 1 } { 2 } ) \, = \, \frac { 2 \, \lambda ^ { ( \ell - 1 ) / 2 } \, p _ { x } \, q _ { x } } { ( 1 - p _ { z } ) \, ( 1 - q _ { z } ) }, & \ell \geqslant 3, \, \text{odd}, \\ \ell \, = \, \begin{cases} 0, & \ell \, \cdots \, \ell \, \cdots \, \ell \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \lambda \, \cdots \, \alpha \, \end{cases}.$$

where q 1 is the probability that the main column satisfies Case 1, formed from p 1 by replacing p x and p z with q x and q z , respectively.

We can now combine the three cases. The asymptotic probability that the underlying permutation of a gridded permutation has exactly ℓ griddings is

$$P _ { \ell } \ = \ P _ { \mathbf 1 } ( \ell ) + P _ { \mathbf 2 } ( \ell ) + P _ { \mathbf 3 } ( \ell ).$$

After considerable simplification, facilitated by using a computer algebra system, we have

$$P _ { \ell } \, = \, \begin{cases} \frac { p _ { x } \, p _ { z } \, q _ { x } \, q _ { z } } { ( 1 - p _ { z } ) \, ( 1 - q _ { z } ) }, & \ell = 1, \\ \frac { \ell \, \lambda ^ { ( \ell - 2 ) / 2 } \, ( \lambda + p _ { x } \, q _ { x } ) \, ( p _ { x } \, q _ { z } + p _ { z } \, q _ { x } ) } { 2 \, ( 1 - p _ { z } ) \, ( 1 - q _ { z } ) }, & \ell \geqslant 2, \text{even}, \\ \frac { \ell \, \lambda ^ { ( \ell - 3 ) / 2 } \, ( \lambda + p _ { x } \, q _ { x } ) \, ( p _ { x } \, q _ { x } + \lambda \, p _ { z } \, q _ { z } ) } { 2 \, ( 1 - p _ { z } ) \, ( 1 - q _ { z } ) }, & \ell \geqslant 3, \text{odd}. \end{cases}$$

Finally, after further simplification, this gives us the correction factor for the L 3 corner type:

$$\kappa ( L _ { 3 } ) \ = \ \sum _ { \ell \geqslant 1 } P _ { \ell } / \ell \ = \ \frac { \lambda \, ( 1 - \lambda ) } { ( 1 - p _ { z } ) \, ( 1 - q _ { z } ) } \ = \ \frac { \lambda \, ( 1 - \lambda ) } { ( 1 - ( c - 1 ) \lambda ) \, ( 1 - ( r - 1 ) \lambda ) }.$$

## Corner type T 4

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-4267e1c2-29ec-4740-8a9e-6cb6d224b811.jpg)

This corner type has one peak and one tee. It can't occur in an L -shaped class.

Dancing at the peak depends on the points adjacent to the column divider to the right of the corner, whereas tee dancing depends on the points adjacent to the column divider to the left of the corner and points adjacent to the row divider below the corner. So these are asymptotically independent. Thus, from the analysis for L 1 and L 3, and by Observation 4.5, we have

$$\kappa ( T _ { 4 } ) \, = \, \kappa ( L _ { 1 } ^ { \mathbb { R } } ) \, \kappa ( L _ { 3 } ) \, = \, \frac { 1 } { 2 } \left ( 1 + \frac { r \alpha \lambda } { \alpha + \beta } \right ) \frac { \lambda \, ( 1 - \lambda ) } { ( 1 - ( c - 1 ) \lambda ) \, ( 1 - ( r - 1 ) \lambda ) }.$$

## Corner type X 4

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-5d5880a4-9178-494a-90b5-e4848ebeeb45.jpg)

This corner type has two tees. It can't occur in an L -shaped or T -shaped class.

Dancing at one of the tees depends on the points adjacent to the column divider to the right of the corner and the row divider above the corner, whereas dancing at the other tee depends on the points adjacent to the column divider to the left of the corner and points adjacent to the row divider below the corner. So these are asymptotically independent. Thus, from the analysis for L 3, and by Observation 4.5, we have

$$\kappa ( X _ { 4 } ) \, = \, \kappa ( L _ { 3 } ) ^ { 2 } \, = \, \left ( \frac { \lambda \, ( 1 - \lambda ) } { ( 1 - ( c - 1 ) \lambda ) \, ( 1 - ( r - 1 ) \lambda ) } \right ) ^ { 2 }.$$

## 4.8 Comparison of corner types

The correction factors induce a partial order on the corner types, in which corner type τ 1 dominates corner type τ 2 if κ τ ( 1 ) &gt; κ τ ( 2 ) for all values of r and c . If this is the case, then a class with smaller asymptotic size is the result whenever a corner of type τ 1 is replaced with one of type τ 2 without changing the dimensions or the number of non-corner peaks.

The Hasse diagram of the corner type poset is shown in Figure 15. For a dashed edge, strict ordering is only satisfied under the condition specified, with the correction factors being equal otherwise. For example, if r = 1, then κ ( T 2 ) = κ ( L 4 ) .

Figure 15: The poset of corner types

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-509bb0a6-d9df-45a7-8461-aebb7cbc96b4.jpg)

## 4.9 Constrained gridded permutations

Recall that, if Grid ( M ) is a connected one-corner class, then an M -gridded permutation σ # is M -constrained if

- (a) every M -gridding of its underlying permutation σ is the result of zero or more points of σ # dancing at a peak or diagonally or through a tee, and
- (b) in every M -gridding of σ , each non-blank cell contains at least two points.

Suppose a gridded permutation satisfies Part (a) of this definition. Then, in order to satisfy Part (b), it is sufficient that, in each non-blank cell, there are at least two points that can't dance, since these points will be in the same cell in all griddings of the underlying permutation.

Non-corner peak points can always dance. However, the set of points which can dance at the corner is determined by the position of the controllers.

For peak dancing ( L 1) and diagonal dancing ( L 7), each controller is an extremal (lowest, highest, leftmost or rightmost) point in one of the cells. For diagonal dancing, the points which can dance are those that are in one of the cells adjacent to the corner and lie between the relevant controller and cell divider.

For tee dancing ( L 3), each controller is either an extremal point in a cell, or else is the second lowest or second highest point in the corner cell. As with diagonal dancing, points between a controller and the corresponding cell divider can dance. However, there may also be a single point that is not between the controller and cell divider that can dance. In addition, one or both of the extremal points in the corner cell may also be able to dance.

Figure 16: A constrained -gridded permutation; the circled points can dance

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-94da0e37-0406-4647-b41b-fde88986ba3f.jpg)

See Figure 16 for an example of a gridded permutation in a class with L 3 corner type and a non-corner peak: in each non-blank cell there are at least two points that can't dance. Note that we may need four points in a cell above a controller in the main row to guarantee two points that can't dance, since one point just above the controller may be able to dance, and the highest point may be a peak point that can dance.

In this context, we make the following definition. Given a gridded permutation, if C 1 and C 2 are two distinct cells in the same row, then they are interlocked if

- · C 1 contains at least four points above the second lowest point in C 2,
- · C 2 contains at least four points above the second lowest point in C 1,
- · C 1 contains at least four points below the second highest point in C 2, and
- · C 2 contains at least four points below the second highest point in C 1.

Similarly, if C 1 and C 2 are two distinct cells in the same column, then they are interlocked if

- · C 1 contains at least four points to the right of the second leftmost point in C 2,
- · C 2 contains at least four points to the right of the second leftmost point in C 1,
- · C 1 contains at least four points to the left of the second rightmost point in C 2, and
- · C 2 contains at least four points to the left of the second rightmost point in C 1.

Note that if two adjacent cells are interlocked, then their contents together don't form an increasing or decreasing sequence.

The following proposition gives sufficient conditions for a gridded permutation in a connected one-corner class to be constrained.

Proposition 4.7. Suppose Grid ( M is a connected one-corner class and ) σ # ∈ Grid # ( M is such that ) each pair of cells in the main row is interlocked and each pair of cells in the main column is interlocked. Then σ # is M-constrained.

Proof. Suppose we remove the row dividers from σ # , merging the cells in the main row into a single 'super cell'. This forms a horizontal skinny gridded permutation in which the contents of one cell are not monotone. Let us denote this σ ∥ . Similarly, if we remove the column dividers, the result is a vertical skinny gridded permutation σ = with one non-monotone cell. We now use an argument similar to that employed in the proof of Proposition 2.3 for skinny classes.

In any M -gridding of σ , by the monotonicity constraints, there must be a column divider between each pair of adjacent monotone cells of σ ∥ that have the same orientation, and also a column divider adjacent to each peak point of σ ∥ (where peaks are formed from two monotone cells). Similarly, there must be a row divider between each pair of adjacent monotone cells of σ = that have the same orientation, and also a row divider adjacent to each peak point of σ = . Thus, in any M -gridding of σ , there must be a divider between each pair of adjacent noncorner cells of σ # that have the same orientation and a divider adjacent to each non-corner peak point.

What of the dividers adjacent to the corner cell? For this, we require a case analysis of each corner type. But this is exactly what is presented in Sections 4.5 to 4.7. The interlocking of cells in σ # guarantees the existence of the controllers, which restrict the possible griddings to those that result from zero or more points of σ # dancing at a peak or diagonally or through a tee.

Moreover, in each non-blank cell there are at least two points that can't dance. So each cell of any M -gridding of σ contains at least two points.

Finally, we prove that almost all gridded permutations in a connected one-corner class are constrained.

Proposition 4.8. If Grid ( M is a connected one-corner class, then almost all M-gridded permutations ) are M-constrained:

$$\lim _ { n \to \infty } \mathbb { P } \left [ \sigma ^ { \# } \, i s \, M { \text{-constrained} } \, \colon \sigma ^ { \# } \in \text{Grid} _ { n } ^ { \# } ( M ) \right ] \, = \, 1.$$

Proof. It is sufficient to prove that almost all M -gridded permutations satisfy the conditions of Proposition 4.7. By Theorem 3.8, we know that the number of points in each non-blank cell of most n -point M -gridded permutations grows with n . So, given any pair of cells both in the main row or both in the main column, the probability that they are interlinked in an n -point M -gridded permutation converges to 1 as n tends to infinity.

## 4.10 Beyond connected one-corner classes

We conclude with some brief notes on extending our approach beyond L , T and X -shaped classes. Firstly, for any connected class, the asymptotic distribution of points between the cells in a typical gridded permutation can be established using the method presented in Section 3. Secondly, for any connected class whose cell graph is either acyclic or unicyclic, the approach of Section 4.2 using generating functions can be extended to give the asymptotic number of gridded permutations. For further details, see [9, Theorems 4.3 and 4.5].

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-09cd2ba9-00a0-4077-a50e-c172e3346038.jpg)

Figure 17: Three two-corner classes, and a four-corner snake, with no adjacent corners

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-8dd93730-47ce-4cf7-ac47-28bf1e28ccbe.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-c416f8e9-b023-41f6-9880-1f63535e8ed0.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-6a11429c-baec-44a1-9df7-17f5fb3a63a0.jpg)

Connected two-corner classes with no adjacent corner cells, such as the three shown in Figure 17, don't support any new possibilities for dancing, and are thus directly amenable to the analysis presented above. If corner orientations are restricted to northeast and southwest, then we have what we call a snake , such as the class at the right of Figure 17. The asymptotic enumeration of snakes with no adjacent corners also requires no additional analysis.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-b39f5fea-133b-4210-ad20-f28b7dc32f57.jpg)

Figure 18: Semi-skinny classes, with two adjacent corners

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-b64b89f4-3191-40ae-87af-24e6e8bac249.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00607v1-figure-2bdacd8b-7c31-4ec9-9cc4-aa16cecc3be6.jpg)

However, in general, connected two-corner classes with corners in adjacent cells, such as the semi-skinny (two row) classes shown in Figure 18, may exhibit non-corner diagonals . Dancing at non-corner diagonals interacts with the dancing at the corners, so additional analysis would be required. With three or more corners, the general situation quickly gets more complicated. With four or more corners, the cell graph may be unicyclic. See [10] for a detailed investigation of the structural complexity of unicyclic classes.

In general, disconnected classes are not directly amenable to our approach, because typical large gridded permutations in such classes may not be constrained. For example, in , the asymptotic expected number of points in the non-blank cell at the upper right is finite. Indeed, the asymptotic probability of that cell being empty or containing just a single point is positive. Further analysis would be required to handle this sort of situation.

## References

- [1] Michael Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson. Combinatorial Exploration: An algorithmic framework for enumeration. arXiv:2202.07715, 2022.
- [2] Michael Albert and Vincent Vatter. An elementary proof of Bevan's theorem on the growth of grid classes of permutations. Proc. Edinburgh Math. Soc. , 62(4):975-984, 2019.
- [3] M. D. Atkinson. Permutations which are the union of an increasing and a decreasing subsequence. Electron. J. Combin. , 5: R6, 1998.
- [4] Zsolt Baranyai. On the factorization of the complete uniform hypergraph. In Infinite and finite sets (Colloq., Keszthely, 1973) , pages 91-108. North-Holland, 1975.
- [5] Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, Mickaël Maazoun, and Adeline Pierrot. Universal limits of substitution-closed permutation classes. J. Eur. Math. Soc. , 22(11):3565-3639, 2020.
- [6] Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, Mickaël Maazoun, and Adeline Pierrot. Scaling limits of permutation classes with a finite specification: a dichotomy. Adv. Math. , 405:108513, 2022.
- [7] Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, and Adeline Pierrot. The Brownian limit of separable permutations. 46(4):2134-2189.
- [8] David Bevan. Growth rates of permutation grid classes, tours on graphs, and the spectral radius. Trans. Amer. Math. Soc. , 367(8):5863-5889, 2015.
- [9] David Bevan. On the growth of permutation classes . PhD thesis, The Open University, 2015.
- [10] David Bevan, Robert Brignall, and Nik Ruškuc. On unicyclic and pseudoforest monotone permutation grid classes.
- [11] Jacopo Borga and Erik Slivken. Square permutations are typically rectangular. Ann. Appl. Probab. , 30(5):21962233, 2020.
- [12] Robert Brignall and Jakub Sliaˇ can. Combinatorial specifications for juxtapositions of permutation classes. Electron. J. Combin. , 26(4): P4.4, 2019.

| [13]   | Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics . Cambridge University Press, 2009.                                                                                                                                               |
|--------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [14]   | Roman Glebov, Andrzej Grzesik, Tereza Klimošová, and Daniel Král'. Finitely forcible graphons and permu- tons. J. Combin. Theory Ser. B , 110:112-135, 2015.                                                                                     |
| [15]   | Cheyne Homberger and Vincent Vatter. On the effective and automatic enumeration of polynomial permu- tation classes. J. Symbolic Comput. , 76:84-96, 2016.                                                                                       |
| [16]   | Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, Balázs Ráth, and Rudini Menezes Sampaio. Limits of permutation sequences. J. Combin. Theory Ser. B , 103(1):93-113, 2013.                                                           |
| [17]   | Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, and Rudini Menezes Sampaio. Testing permutation properties through subpermutations. Theoret. Comput. Sci. , 412(29):3555-3567, 2011.                                                |
| [18]   | Sophie Huczynska and Vincent Vatter. Grid classes and the Fibonacci dichotomy for restricted permutations. Electron. J. Combin. , 13: R54, 2006.                                                                                                 |
| [19]   | Maximillian M. Murphy and Vincent R. Vatter. Profile classes and partial well-order for permutations. Elec- tron. J. Combin. , 9(2): R17, 2003.                                                                                                  |
| [20]   | Cathleen Battiste Presutti and Walter Stromquist. Packing rates of measures and a conjecture for the packing density of 2413. In Steve Linton, Nik Ruškuc, and Vincent Vatter, editors, Permutation Patterns . Cambridge University Press, 2010. |

[21] Zvezdelina E. Stankova. Forbidden subsequences. Discrete Math. , 132:291-316, 1994.

[22] Richard P. Stanley. Enumerative Combinatorics. Vol. 2 . Cambridge University Press, 1999.

[23] Vincent Vatter. Small permutation classes. Proc. London Math. Soc. , 103(5):879-921, 2011.
Noura Alshammari David Bevan
On the asymptotic enumeration and limit shapes of monotone grid classes of permutations
We exhibit a procedure to asymptotically enumerate monotone grid classes of
permutations. This is then applied to compute the asymptotic number of
permutations in any connected one-corner class. Our strategy consists of
enumerating the gridded permutations, finding the asymptotic distribution of
points between the cells in a typical large gridded permutation, and analysing
in detail the ways in which a typical permutation can be gridded. We also
determine the limit shape of any connected monotone grid class.