Given a permutation \(\pi\) of size \(n\), we consider the associated grid graph \(G_{\pi}\) whose \(i\)th column has height \(\pi_i\), with vertical edges between consecutive levels and horizontal edges between equal levels in adjacent columns. We investigate global degree statistics of these graphs when \(\pi\) ranges over the Catalan avoidance class \(\mathrm{Av}_n(213)\) (and, by reversal, also over \(\mathrm{Av}_n(312)\)). We obtain explicit closed formulas for two accumulated quantities over \(\mathrm{Av}_n(213)\): the total number of horizontal edges and, for each \(r\in\{1,2,3,4\}\), the total number of degree-\(r\) vertices. The proofs rely on the Catalan decomposition induced by the position of the minimum entry, which leads to gluing recurrences and algebraic ordinary generating functions, and are completed using universal identities for the total number of vertices and the sum of degrees. As an application, we derive asymptotic degree proportions for a uniformly random permutation in \(\mathrm{Av}_n(213)\): the expected proportion of degree-4 vertices, equivalently the global degree-4 proportion over the class, tends to \(1\), with a deficit of order \(n^{-1/2}\), contrasting with the unrestricted case.
We study global degree statistics in the grid graphs associated with permutations, restricting the underlying permutation to a Catalan avoidance class.
Let \(n\in\mathbb{N}\) and \([n]=\{1,2,\dots,n\}\). Let \(S_n\) be the set of all permutations of \([n]\). Following Blecher and Knopfmacher [1], to each \(\pi=\pi_1\pi_2\cdots \pi_n\in S_n\) we associate a grid graph \(G_\pi\) with \(n\) columns: column \(i\) has height \(\pi_i\); we place vertical edges between consecutive levels within each column and horizontal edges between equal levels in adjacent columns. For \(n\ge2\), every vertex of \(G_\pi\) has degree in \(\{1,2,3,4\}\) [1].
Two global quantities are immediate from the definition: the number of vertices satisfies \(|V(G_\pi)|=\sum\limits_{i=1}^n \pi_i=\binom{n+1}{2}\) (independent of \(\pi\)), and the number of vertical edges is \(|E_{vert}(G_\pi)|=\sum\limits_{i=1}^n(\pi_i-1)=\binom{n}{2}\). In contrast, the horizontal edges depend on \(\pi\) and are counted by \[H(\pi):=|E_{hor}(G_\pi)|=\sum\limits_{t=1}^{n-1}\min\{\pi_t,\pi_{t+1}\}.\]
In the unrestricted case (averaging over \(S_n\)), Blecher and Knopfmacher [1] obtain closed formulas for the total number of horizontal edges and for global degree totals. They also propose extending this program to avoidance classes \(\mathrm{Av}_n(\tau)\) with \(|\tau|=3\).
Pattern avoidance is a central theme in the modern theory of permutations, with foundational early work already in [2] and extensive treatments in standard references such as [3, 4]. For patterns of length \(3\), many classes are Catalan-enumerated and admit recursive descriptions; generating-tree constructions provide a systematic framework for such recursions [5], while bijections to Dyck paths and related lattice objects often yield explicit generating functions and refined statistics [6]. These perspectives motivate the approach taken here: we exploit a Catalan decomposition to derive algebraic ordinary generating functions and then extract coefficients and asymptotics using standard analytic-combinatorial tools [7, 8].
In this paper we treat completely the class \(\mathcal{A}_n:=\mathrm{Av}_n(213)\) (and, by reversal, \(\mathrm{Av}_n(312)\)). Unlike the unrestricted case, avoidance forces a rigid block structure: if the entry \(1\) occurs in position \(k\), then every value to the left of \(1\) is larger than every value to the right. This Catalan gluing is reflected in the column profile of \(G_\pi\) and produces a markedly different global degree distribution.
We focus on the following global totals, summed over \(\mathcal{A}_n\): \[H^{\mathcal{A}}(n):=\sum\limits_{\pi\in\mathcal{A}_n} H(\pi), \qquad Q_r^{\mathcal{A}}(n):=\sum\limits_{\pi\in\mathcal{A}_n}\#\{v\in V(G_\pi):\deg(v)=r\}\quad (r=1,2,3,4).\]
Our first main result gives a closed form for \(H^{\mathcal{A}}(n)\). Our second main result gives closed forms for \(Q_1^{\mathcal{A}}(n),\dots,Q_4^{\mathcal{A}}(n)\). As a consequence, the global proportion of degree-4 vertices, summed over the class, tends to \(1\) as \(n\to\infty\), with a leading correction of order \(n^{-1/2}\); this contrasts with the unrestricted case [1], where the limiting proportion for degree \(4\) equals \(1/2\).
The proofs are Catalan in nature: we start from the decomposition induced by the position of the minimum entry \(1\), translate local contributions into gluing identities and functional equations for ordinary generating functions algebraic over \(\mathbb{Q}(x,\sqrt{1-4x})\), and close the remaining degree totals using two universal identities (total number of vertices and sum of degrees). The paper is organized into four sections: Preliminaries; Horizontal edges; Vertex degree totals; and Asymptotic proportions and concluding remarks.
We collect basic definitions and notation: the grid graph \(G_\pi\), local degree-by-level criteria, Catalan enumeration and generating functions for \(\mathcal{A}_n=\mathrm{Av}_n(213)\), reversal symmetry, and the Catalan decomposition induced by the position of \(1\).
Definition 1. Let \(\pi=\pi_1\cdots \pi_n\in S_n\). The grid graph \(G_\pi\) has vertex set \[V(G_\pi)=\{(i,s):1\le i\le n,\ 1\le s\le \pi_i\}.\]
Two vertices \((i,s)\) and \((i',s')\) are adjacent if: (i) \(i=i'\) and \(|s-s'|=1\) (a vertical edge), or (ii) \(|i-i'|=1\) and \(s=s'\) (a horizontal edge), provided both vertices exist.
For \(n\ge2\), every vertex of \(G_\pi\) has degree in \(\{1,2,3,4\}\) []. We write \(\deg(v)\) for the degree of \(v\), and \(E_{vert}(G_\pi)\), \(E_{hor}(G_\pi)\) for the sets of vertical and horizontal edges.
Lemma 1. Let \(\pi\in S_n\) and consider a column \(i\) of height \(b=\pi_i\).
(i) If \(2\le i\le n-1\) (internal column) and \(a=\pi_{i-1}\), \(c=\pi_{i+1}\), then for \(1\le s\le b\) \[\label{eq:degByLevelInternal} \deg(i,s)=\mathbf{1}_{\{s>1\}}+\mathbf{1}_{\{s<b\}}+\mathbf{1}_{\{s\le a\}}+\mathbf{1}_{\{s\le c\}}. \tag{1}\]
(ii) If \(i=1\) and \(b=\pi_1\), \(c=\pi_2\), then for \(1\le s\le b\) \[\deg(1,s)=\mathbf{1}_{\{s>1\}}+\mathbf{1}_{\{s<b\}}+\mathbf{1}_{\{s\le c\}},\] and if \(i=n\) and \(a=\pi_{n-1}\), then for \(1\le s\le b=\pi_n\) \[\deg(n,s)=\mathbf{1}_{\{s>1\}}+\mathbf{1}_{\{s<b\}}+\mathbf{1}_{\{s\le a\}}.\]
Proof. Vertical neighbors exist exactly when \(s>1\) (a lower neighbor) and \(s<b\) (an upper neighbor). In an internal column there are two possible horizontal neighbors: to the left if \(s\le a\) and to the right if \(s\le c\). In an external column there is only one possible horizontal neighbor. Summing these contributions yields the stated formulas. ◻
Corollary 1. In an internal column with triple \((a,b,c)\), the number of degree-\(4\) vertices in the middle column equals \[\max\{0,\min(a,c,b-1)-1\}.\]
Proof. By Eq. (1), a level \(s\) has degree \(4\) iff \(2\le s\le b-1\) and \(s\le a\) and \(s\le c\), i.e. \(2\le s\le \min(a,c,b-1)\). The count is immediate. ◻
Corollary 2. Let \(2\le i\le n-1\). The top vertex \((i,\pi_i)\) has degree \(1\) iff \(\pi_i\ge 2\) and \(\pi_i>\max\{\pi_{i-1},\pi_{i+1}\}\).
Proof. Apply Eq. (1) with \(s=b=\pi_i\). Then \(\mathbf{1}_{\{s<b\}}=0\) and \(\mathbf{1}_{\{s>1\}}=1\) iff \(b\ge2\), while \(\mathbf{1}_{\{s\le a\}}=\mathbf{1}_{\{b\le a\}}\) and \(\mathbf{1}_{\{s\le c\}}=\mathbf{1}_{\{b\le c\}}\). Hence the degree equals \(1\) exactly when \(b\ge2\) and \(b>a\) and \(b>c\). ◻
Let \(\mathcal{A}_n=\mathrm{Av}_n(213)\subseteq S_n\). It is well known (see, e.g., [3, Ch. 4]) that \(|\mathcal{A}_n|\) is the \(n\)th Catalan number: \[C_n:=|\mathcal{A}_n|=\frac{1}{n+1}\binom{2n}{n}.\]
Write \(B_n:=\binom{2n}{n}\), so \(C_n=B_n/(n+1)\). The Catalan ordinary generating function is \[\label{eq:Cx} C(x)=\sum\limits_{n\ge 0} C_n x^n=\frac{1-\sqrt{1-4x}}{2x}, \tag{2}\] and it satisfies \(C(x)=1+xC(x)^2\).
For \(\pi=\pi_1\cdots\pi_n\in S_n\), define its reversal by \(\mathrm{rev}(\pi):=\pi_n\cdots\pi_1\).
Lemma 2. For every \(\pi\in S_n\), the graphs \(G_\pi\) and \(G_{\mathrm{rev}(\pi)}\) are isomorphic via \[\varphi:V(G_\pi)\to V(G_{\mathrm{rev}(\pi)}),\qquad \varphi(i,s)=(n+1-i,s).\]
In particular, \(H(\pi)=H(\mathrm{rev}(\pi))\) and, for each \(r\in\{1,2,3,4\}\), the number of degree-\(r\) vertices in \(G_\pi\) equals that in \(G_{\mathrm{rev}(\pi)}\).
Proof. The map \(\varphi\) is a bijection and preserves adjacencies: vertical edges remain within the same column at consecutive levels, and horizontal edges are reflected between adjacent columns. Hence degrees and degree counts are preserved. Moreover, \[H(\mathrm{rev}(\pi))=\sum\limits_{t=1}^{n-1}\min\{\pi_{n+1-t},\pi_{n-t}\}=H(\pi).\] ◻
Corollary 3. Reversal restricts to a bijection \(\mathrm{Av}_n(213)\leftrightarrow \mathrm{Av}_n(312)\). Consequently, all results of this paper for \(\mathcal{A}_n=\mathrm{Av}_n(213)\) hold verbatim for \(\mathrm{Av}_n(312)\).
Proof. Reversal sends the pattern \(213\) to \(312\) (and conversely). The rest follows from Lemma 2. ◻
Lemma 3.
Let \(\pi\in\mathcal{A}_n\) and let \(k\) be the position of \(1\), i.e. \(\pi_k=1\). Then every entry to the left of \(1\) is larger than every entry to the right of \(1\). In particular, if \(\ell:=k-1\) and \(r:=n-k\), there exist \(\alpha\in\mathcal{A}_\ell\) and \(\beta\in\mathcal{A}_r\) such that \[\label{eq:decomp} \pi=(\alpha+r+1)\ 1\ (\beta+1), \tag{3}\] where \(\alpha+r+1\) means adding \(r+1\) to each entry of \(\alpha\), and \(\beta+1\) means adding \(1\) to each entry of \(\beta\). Conversely, every concatenation of the form Eq. (3) lies in \(\mathcal{A}_n\).Proof. If there were positions \(p<k<q\) with \(\pi_p<\pi_q\), then the triple \((\pi_p,1,\pi_q)\) would realize the pattern \(213\) (the middle entry is the smallest, the right entry the largest, and the left entry lies strictly between them), a contradiction. Hence every entry left of \(1\) is larger than every entry right of \(1\). Standardizing the left and right blocks yields Eq. (3). The converse is immediate: in Eq. (3) no \(213\) pattern can cross the \(1\), and within each block avoidance is preserved under standardization. ◻
In particular, Lemma 3 yields the Catalan convolution. Indeed, for each choice of the position of \(1\), say with left block of length \(\ell\) and right block of length \(r\), where \(\ell+r=n-1\), the permutation is uniquely determined by an independent choice of \[\alpha\in\mathcal{A}_\ell \qquad\text{and}\qquad \beta\in\mathcal{A}_r.\]
Hence \[C_n=\sum\limits_{\ell+r=n-1} C_\ell C_r \qquad (n\ge 1).\]
We derive a gluing identity for the horizontal-edge statistic \(H(\pi)\) under the Catalan decomposition, translate it into a functional equation for \(H^{\mathcal{A}}(x)\), and solve it to obtain a closed form for \(H^{\mathcal{A}}(n)\).
Define \[H(\pi)=\sum_{t=1}^{n-1}\min\{\pi_t,\pi_{t+1}\}, \qquad H^{\mathcal{A}}(n):=\sum_{\pi\in\mathcal{A}_n} H(\pi).\]
For a statement \(A\) we write \(\mathbf{1}_{\{A\}}\in\{0,1\}\) for its indicator.
Lemma 4. Let \(\pi\in\mathcal{A}_n\) with decomposition \(\pi=(\alpha+r+1)\,1\,(\beta+1)\) as in Eq. (3), where \(|\alpha|=\ell\), \(|\beta|=r\), and \(\ell+r=n-1\). Then \[\label{eq:glueH213} H(\pi)=H(\alpha)+H(\beta) +\mathbf{1}_{\{\ell\ge 2\}}(\ell-1)(r+1)+\mathbf{1}_{\{r\ge 2\}}(r-1)+\mathbf{1}_{\{\ell\ge 1\}}+\mathbf{1}_{\{r\ge 1\}}. \tag{4}\]
Proof. Split the sum defining \(H(\pi)\) into adjacent pairs according to their position relative to \(\pi=(\alpha+r+1)\,1\,(\beta+1)\).
If \(\ell\ge2\), the pairs \((t,t+1)\) with \(1\le t\le \ell-1\) lie in the left block and satisfy \[\min\{\alpha_t+r+1,\alpha_{t+1}+r+1\}=(r+1)+\min\{\alpha_t,\alpha_{t+1}\},\] so their total contribution is \(H(\alpha)+(\ell-1)(r+1)\). If \(\ell\le1\) there are no such pairs.
If \(r\ge2\), the internal pairs in the right block contribute \(H(\beta)+(r-1)\) since \(\min\{\beta_t+1,\beta_{t+1}+1\}=1+\min\{\beta_t,\beta_{t+1}\}\). If \(r\le1\) there are no such pairs.
Finally, if \(\ell\ge1\), the pair between the last column of the left block and \(1\) contributes \(\min\{\alpha_\ell+r+1,1\}=1\). If \(r\ge1\), the pair between \(1\) and the first column of the right block contributes \(\min\{1,\beta_1+1\}=1\). Collecting terms yields Eq. (4). ◻
Proposition 1. With the convention \(H^{\mathcal{A}}(0)=0\), let \[H^{\mathcal{A}}(x):=\sum_{n\ge 1} H^{\mathcal{A}}(n) x^n.\]
Then \[\label{eq:HFE213} (1-2xC(x))\,H^{\mathcal{A}}(x)=x\bigl(xC'(x)-C(x)+1\bigr)\bigl(xC'(x)+2C(x)\bigr)+2\bigl(C(x)-1-xC(x)\bigr). \tag{5}\]
Proof. Sum Eq. (4) over all \(\pi\in\mathcal{A}_n\), grouping by \(\ell+r=n-1\) and the choices \(\alpha\in\mathcal{A}_\ell\), \(\beta\in\mathcal{A}_r\).
The contributions \(H(\alpha)\) and \(H(\beta)\) yield the convolution \(\sum_{\ell+r=n-1}(C_rH^{\mathcal{A}}(\ell)+C_\ell H^{\mathcal{A}}(r))\), which becomes \(2xC(x)H^{\mathcal{A}}(x)\) in OGFs.
Length-only terms become products: \[\sum_{\ell\ge0}\mathbf{1}_{\{\ell\ge2\}}(\ell-1)C_\ell x^\ell\cdot \sum_{r\ge0}(r+1)C_r x^r = \bigl(xC'(x)-C(x)+1\bigr)\bigl(xC'(x)+C(x)\bigr),\] and \[\sum_{\ell\ge0} C_\ell x^\ell\cdot \sum_{r\ge0}\mathbf{1}_{\{r\ge2\}}(r-1)C_r x^r = C(x)\bigl(xC'(x)-C(x)+1\bigr).\]
Finally, \[\sum_{n\ge1}\Bigl(\sum_{\ell+r=n-1}(\mathbf{1}_{\{\ell\ge1\}}+\mathbf{1}_{\{r\ge1\}})C_\ell C_r\Bigr)x^n =2\sum_{n\ge1}(C_n-C_{n-1})x^n=2\bigl(C(x)-1-xC(x)\bigr).\]
Combining contributions and moving \(2xC(x)H^{\mathcal{A}}(x)\) to the left yields Eq. (5). ◻
Theorem 1. For \(n\ge 1\), \[H^{\mathcal{A}}(n)=\frac{n}{2}\binom{2n}{n}-4^{\,n-1}.\]
Equivalently, the ordinary generating function \[H^{\mathcal{A}}(x):=\sum_{n\ge1}H^{\mathcal{A}}(n)x^n,\] is given by \[\label{eq:HxClosed213} H^{\mathcal{A}}(x)=x(1-4x)^{-3/2}-x(1-4x)^{-1}. \tag{6}\]
Proof. Starting from Eq. (5), and with the convention \(H^{\mathcal{A}}(0)=0\), we have \[\label{eq:HFE213-proof} (1-2xC(x))\,H^{\mathcal{A}}(x) = x\bigl(xC'(x)-C(x)+1\bigr)\bigl(xC'(x)+2C(x)\bigr) + 2\bigl(C(x)-1-xC(x)\bigr). \tag{7}\]
We express the right-hand side in terms of \((1-4x)^{1/2}\). Recall that \[\label{eq:Cclosed-proof} C(x)=\frac{1-\sqrt{1-4x}}{2x}, \qquad 1-2xC(x)=\sqrt{1-4x}. \tag{8}\]
Differentiating the identity \(C(x)=1+xC(x)^2\) gives \[C'(x)=C(x)^2+2xC(x)C'(x),\] so that \[(1-2xC(x))C'(x)=C(x)^2.\]
Using \(C(x)^2=\frac{C(x)-1}{x}\) and Eq. (8), we obtain \[xC'(x)=\frac{xC(x)^2}{1-2xC(x)} =\frac{C(x)-1}{1-2xC(x)} =\frac{1}{\sqrt{1-4x}}-C(x).\]
Hence \[\label{eq:two-factors-H} xC'(x)-C(x)+1=\frac{1}{\sqrt{1-4x}}-2C(x)+1, \qquad xC'(x)+2C(x)=\frac{1}{\sqrt{1-4x}}+C(x). \tag{9}\]
Substituting Eq. (8) and Eq. (9) into Eq. (7), and simplifying, yields \[(1-2xC(x))\,H^{\mathcal{A}}(x) = x(1-4x)^{-1} – x(1-4x)^{-1/2}.\]
Since \(1-2xC(x)=\sqrt{1-4x}\), division by \(\sqrt{1-4x}\) gives \[H^{\mathcal{A}}(x) = x(1-4x)^{-3/2} – x(1-4x)^{-1},\] which is Eq. (6).
Finally, \[[x^n]\bigl(x(1-4x)^{-3/2}\bigr) = [x^{n-1}](1-4x)^{-3/2} = \frac{n}{2}\binom{2n}{n},\] and \[[x^n]\bigl(x(1-4x)^{-1}\bigr)=4^{\,n-1}.\]
Hence \[H^{\mathcal{A}}(n)=\frac{n}{2}\binom{2n}{n}-4^{\,n-1},\] for all \(n\ge1\). ◻
We define the global degree totals \(Q_r^{\mathcal{A}}(n)\) and determine them explicitly for \(r=1,2,3,4\). The computation is completed using two universal identities: the total number of vertices and the sum of degrees.
For \(r\in\{1,2,3,4\}\) define \[Q_r^{\mathcal{A}}(n):=\sum_{\pi\in\mathcal{A}_n} \#\{v\in V(G_\pi):\deg(v)=r\}.\]
We adopt the initial conventions \[Q_r^{\mathcal{A}}(0)=0 \qquad (r=1,2,3,4),\] and also \[Q_r^{\mathcal{A}}(1)=0 \qquad (r=1,2,3,4),\] since the unique permutation of length \(1\) gives a grid graph with a single vertex of degree \(0\).
We also define two auxiliary global totals: \[V^{\mathcal{A}}(n):=\sum_{\pi\in\mathcal{A}_n}|V(G_\pi)|, \qquad \Sigma^{\mathcal{A}}(n):=\sum_{\pi\in\mathcal{A}_n}\sum_{v\in V(G_\pi)}\deg(v).\]
Proposition 2. For \(n\ge1\), \[ V^{\mathcal{A}}(n) = |\mathcal{A}_n|\cdot \frac{n(n+1)}{2} = \frac{n}{2}\binom{2n}{n},\label{eq:Vn}\ \tag{10}\] \[\Sigma^{\mathcal{A}}(n) = |\mathcal{A}_n|\cdot n(n-1)+2H^{\mathcal{A}}(n) = \frac{2n^2}{n+1}\binom{2n}{n}-2\cdot 4^{\,n-1}.\label{eq:SigmaClosed} \ \tag{11}\]
In particular, for \(n\ge2\), \[\label{eq:LinSystem} Q_1^{\mathcal{A}}(n)+Q_2^{\mathcal{A}}(n)+Q_3^{\mathcal{A}}(n)+Q_4^{\mathcal{A}}(n)=V^{\mathcal{A}}(n), \tag{12}\] \[\label{eq:LinSystem2} Q_1^{\mathcal{A}}(n)+2Q_2^{\mathcal{A}}(n)+3Q_3^{\mathcal{A}}(n)+4Q_4^{\mathcal{A}}(n)=\Sigma^{\mathcal{A}}(n). \tag{13}\]
Proof. For each \(\pi\in S_n\), \(|V(G_\pi)|=\sum_{i=1}^n \pi_i=\binom{n+1}{2}\), so summing over \(\mathcal{A}_n\) gives Eq. (10).
For \(\Sigma^{\mathcal{A}}(n)\), use the handshaking lemma: \(\sum_v\deg(v)=2|E(G_\pi)|\). Moreover \(|E_{ vert}(G_\pi)|=\binom{n}{2}\) is constant on \(S_n\), while \(|E_{ hor}(G_\pi)|=H(\pi)\). Summing yields \[\Sigma^{\mathcal{A}}(n)=2\Bigl(|\mathcal{A}_n|\cdot \binom{n}{2}+H^{\mathcal{A}}(n)\Bigr),\] and substituting Theorem 1 gives Eq. (11). The linear identities Eq. (12) and Eq. (13) are the direct translations in terms of degree totals. ◻
We next compute \(Q_1^{\mathcal{A}}(n)\) and \(Q_4^{\mathcal{A}}(n)\) explicitly; then \(Q_2^{\mathcal{A}}(n)\) and \(Q_3^{\mathcal{A}}(n)\) follow from Eq. (12) and Eq. (13).
Lemma 5. Let \(\pi\in S_n\). In the first column, the number of degree-\(1\) vertices equals \[\mathbf{1}_{\{\pi_1=1\}}+\mathbf{1}_{\{\pi_1>\pi_2\}},\] and in the last column it equals \[\mathbf{1}_{\{\pi_n=1\}}+\mathbf{1}_{\{\pi_{n-1}<\pi_n\}}.\]
Proof. Apply Lemma 1. In the first column, with \(b=\pi_1\) and \(c=\pi_2\), only the top vertex \((1,b)\) can have degree \(1\), and \[\deg(1,b)=\mathbf{1}_{\{b>1\}}+\mathbf{1}_{\{b\le c\}}.\]
Thus \(\deg(1,b)=1\) iff \(b=1\) or \(b>c\), i.e. \(\pi_1=1\) or \(\pi_1>\pi_2\). The last column is identical. ◻
Lemma 6. For \(m\geq 2\), define \[D_m:=\#\{\gamma\in\mathcal A_m:\gamma_1>\gamma_2\}, \qquad F_m:=\#\{\gamma\in\mathcal A_m:\gamma_{m-1}<\gamma_m\}.\]
Then \[D_m=F_m=C_{m-1}.\]
Proof. We first prove \(D_m=C_{m-1}\). Let \(\gamma\in\mathcal A_m\). By Lemma 3, we may write \[\gamma=(\alpha+r+1)\,1\,(\beta+1), \qquad |\alpha|=\ell,\quad |\beta|=r,\quad \ell+r=m-1.\]
If \(\ell=0\), then \(\gamma_1=1\), so no initial descent occurs. If \(\ell=1\), then \(\gamma_1=m\) and \(\gamma_2=1\), so an initial descent always occurs, contributing \(C_{m-2}\) choices. If \(\ell\geq 2\), the first two entries of \(\gamma\) lie in the left block, and the condition \(\gamma_1>\gamma_2\) is equivalent to \(\alpha_1>\alpha_2\). Hence \[D_m=C_{m-2}+\sum_{\ell=2}^{m-1}D_\ell C_{m-1-\ell}.\]
The claim is immediate for \(m=2\). Assume it holds for all smaller indices. By induction, using \(D_\ell=C_{\ell-1}\) for \(2\leq \ell\leq m-1\), we get \[D_m=C_{m-2}+\sum_{\ell=2}^{m-1}C_{\ell-1}C_{m-1-\ell}.\]
Writing \(j=\ell-1\), this becomes \[D_m=\sum_{j=0}^{m-2}C_jC_{m-2-j}=C_{m-1}.\]
Now we prove \(F_m=C_{m-1}\) directly, again using Lemma 3. If \(r=0\), then \(\gamma_m=1\), so no final ascent into the last entry is possible. If \(r=1\), then the final pair is \(1,2\), so every choice of \(\alpha\in\mathcal A_{m-2}\) contributes, giving \(C_{m-2}\) possibilities. If \(r\geq 2\), the last two entries of \(\gamma\) lie in the right block, and the condition \(\gamma_{m-1}<\gamma_m\) is equivalent to the corresponding final ascent in \(\beta\), counted by \(F_r\). Therefore \[F_m=C_{m-2}+\sum_{r=2}^{m-1}C_{m-1-r}F_r.\]
The claim is immediate for \(m=2\). Assume it holds for all smaller indices. By induction, \[F_m=C_{m-2}+\sum_{r=2}^{m-1}C_{m-1-r}C_{r-1}.\]
Writing \(j=r-1\), we obtain \[F_m=\sum_{j=0}^{m-2}C_{m-2-j}C_j=C_{m-1}.\]
Thus \(D_m=F_m=C_{m-1}\). ◻
Lemma 7. For \(n\ge2\), the total number of degree-\(1\) vertices contributed by the first and last columns satisfies \[Q_{1, ext}^{\mathcal{A}}(n)=4\,C_{n-1}.\]
Proof. By Lemma 5, \[Q_{1, ext}^{\mathcal{A}}(n)=\sum_{\pi\in\mathcal{A}_n}\Bigl( \mathbf{1}_{\{\pi_1=1\}}+\mathbf{1}_{\{\pi_1>\pi_2\}}+\mathbf{1}_{\{\pi_n=1\}}+\mathbf{1}_{\{\pi_{n-1}<\pi_n\}} \Bigr).\]
Each of the four sums equals \(C_{n-1}\). Indeed, \(\pi_1=1\) forces \(1\) to be first, leaving \(\mathcal{A}_{n-1}\) free on the right, hence contributes \(C_{n-1}\); similarly for \(\pi_n=1\). Finally, Lemma 6 gives \(\sum_\pi \mathbf{1}_{\{\pi_1>\pi_2\}}=D_n=C_{n-1}\) and \(\sum_\pi \mathbf{1}_{\{\pi_{n-1}<\pi_n\}}=F_n=C_{n-1}.\) ◻
Lemma 8. For \(n\geq 3\), the total number of degree-one vertices in internal columns satisfies \[Q^{\mathcal A}_{1,\mathrm{int}}(n)=(n-2)C_{n-1}.\]
Proof. Let \[P_n:=Q^{\mathcal A}_{1,\mathrm{int}}(n), \qquad P(x):=\sum_{n\geq 0}P_nx^n,\] with \(P_0=P_1=P_2=0\). By Corollary 2, a degree-one vertex in an internal column is precisely the top vertex of an internal column whose height is strictly larger than the heights of both adjacent columns.
Let \(\pi\in \mathcal A_n\), and write, by Lemma 3, its Catalan decomposition as \[\pi=(\alpha+r+1)\,1\,(\beta+1), \qquad |\alpha|=\ell,\quad |\beta|=r,\quad \ell+r=n-1.\]
We separate the internal peaks of \(\pi\) into inherited peaks and interface peaks.
First, every internal peak of \(\alpha\) remains an internal peak of \(\pi\), and similarly every internal peak of \(\beta\) remains an internal peak of \(\pi\). Summing over all choices of \(\alpha\in\mathcal A_\ell\) and \(\beta\in\mathcal A_r\), the inherited contribution is \[\sum_{\ell+r=n-1}\bigl(C_rP_\ell+C_\ell P_r\bigr) = 2\sum_{\ell+r=n-1}C_rP_\ell .\]
We now consider the interface peaks. The last column of the left block becomes an internal column of \(\pi\) only when \(\ell\geq 2\). In that case, since its right neighbour is the central column of height \(1\), it is an internal peak precisely when the last two entries of \(\alpha\) form a final ascent. By Lemma 6, this occurs in \(C_{\ell-1}\) choices of \(\alpha\).
Similarly, the first column of the right block becomes an internal column of \(\pi\) only when \(r\geq 2\). In that case, since its left neighbour is the central column of height \(1\), it is an internal peak precisely when the first two entries of \(\beta\) form an initial descent. Again by Lemma 6, this occurs in \(C_{r-1}\) choices of \(\beta\).
Therefore the total interface contribution is \[\sum_{\substack{\ell+r=n-1\\ \ell\geq 2}} C_r C_{\ell-1} + \sum_{\substack{\ell+r=n-1\\ r\geq 2}} C_\ell C_{r-1}.\]
By the Catalan convolution, each of these two sums equals \[\sum_{j=1}^{n-2} C_jC_{n-2-j} = C_{n-1}-C_{n-2}.\]
Hence, for \(n\geq 3\), \[P_n= 2\sum_{\ell+r=n-1}C_rP_\ell + 2(C_{n-1}-C_{n-2}).\]
Passing to ordinary generating functions gives \[P(x)=2xC(x)P(x)+2x^2C(x)(C(x)-1).\]
Thus \[P(x)=\frac{2x^2C(x)(C(x)-1)}{1-2xC(x)}.\]
Using \[C(x)=1+xC(x)^2, \qquad 1-2xC(x)=\sqrt{1-4x},\] we obtain equivalently \[P(x)=x\bigl(xC'(x)-C(x)+1\bigr).\]
Since \[xC'(x)=\sum_{n\geq 1}nC_nx^n,\] we have \[[x^n]P(x) = [x^{n-1}]\bigl(xC'(x)-C(x)+1\bigr) = (n-1)C_{n-1}-C_{n-1} = (n-2)C_{n-1},\] for every \(n\geq 3\). Therefore \[Q^{\mathcal A}_{1,\mathrm{int}}(n)=P_n=(n-2)C_{n-1},\] as claimed. ◻
Corollary 4. For \(n\geq 2\), \[Q_1^{\mathcal A}(n) = Q_{1,\mathrm{ext}}^{\mathcal A}(n) + Q_{1,\mathrm{int}}^{\mathcal A}(n) = (n+2)\,C_{n-1} = \frac{n+2}{2(2n-1)}\binom{2n}{n}.\]
Proof. For \(n=2\), there are no internal columns, so the identity follows directly. For \(n\geq 3\), sum Lemmas 7 and 8 and use \[C_{n-1}=\frac{1}{2(2n-1)}\binom{2n}{n}.\] ◻
We now turn to degree-\(4\) vertices. Note that degree \(4\) cannot occur in external columns.
Lemma 9. Let an internal column have height \(b\) with neighbors of heights \(a\) and \(c\). If one replaces \((a,b,c)\) by \((a+t,b+t,c+t)\) with \(t\ge1\), then the number of degree-\(4\) vertices in the middle column increases by \[\begin{cases} t, & b\ge 2,\\ t-1, & b=1. \end{cases}\]
Proof. By Corollary 1, before the shift the number of degree-\(4\) vertices is \(\max\{0,\min(a,c,b-1)-1\}\) and after the shift it is \(\max\{0,\min(a+t,c+t,b+t-1)-1\}=\max\{0,t+\min(a,c,b-1)-1\}\). If \(b\ge2\) then \(\min(a,c,b-1)\ge1\) and the increment is \(t\); if \(b=1\) the increment is \(\max\{0,t-1\}=t-1\). ◻
Define, for \(m\ge0\), \[J_m:=\#\{\gamma\in\mathcal{A}_m:\text{the entry }1\text{ lies in an internal position}\} =\begin{cases} C_m-2C_{m-1}, & m\ge 2,\\ 0, & m\le 1. \end{cases}\]
Theorem 2. For \(n\geq 2\), \[Q_4^{\mathcal A}(n) = \frac{4n^3-7n^2+29n-20}{4(n+1)(2n-1)} \binom{2n}{n} – 7\cdot 4^{\,n-2}.\]
Proof. Let \[Q_n:=Q_4^{\mathcal A}(n), \qquad Q_4^{\mathcal A}(x):=\sum_{n\geq 0}Q_nx^n,\] with \(Q_0=Q_1=0\). Let \(\pi\in\mathcal A_n\), and write, by Lemma 3, \[\pi=(\alpha+r+1)\,1\,(\beta+1), \qquad |\alpha|=\ell,\quad |\beta|=r,\quad \ell+r=n-1.\]
Since the column corresponding to the entry \(1\) has height \(1\), each column adjacent to it has a horizontal neighbour on that side only at level \(1\). Hence neither of the two columns adjacent to the entry \(1\) can contain a degree-\(4\) vertex. Therefore every degree-\(4\) vertex of \(G_\pi\) lies in an internal column entirely contained in the left block \(\alpha+r+1\) or in the right block \(\beta+1\).
Consider first the left block. Passing from \(\alpha\) to \(\alpha+r+1\) increases every column height by \(r+1\). Thus, by Lemma 9, each internal column of \(\alpha\) contributes \(r+1\) additional degree-\(4\) vertices, except possibly the unique column of height \(1\). This exceptional column contributes one less precisely when the entry \(1\) of \(\alpha\) lies in an internal position. Hence the total increment from the left block is \[(r+1)(\ell-2)_+ – \mathbf 1_{\{1\text{ is internal in }\alpha\}}.\]
Similarly, passing from \(\beta\) to \(\beta+1\) increases every column height by \(1\). Hence the total increment from the right block is \[(r-2)_+ – \mathbf 1_{\{1\text{ is internal in }\beta\}}.\]
Adding the inherited degree-\(4\) vertices from the two blocks and the two shift contributions gives \[\label{eq:Q4glue} Q_4(\pi) = Q_4(\alpha)+Q_4(\beta) +(r+1)(\ell-2)_+ +(r-2)_+ -\mathbf 1_{\{1\text{ is internal in }\alpha\}} -\mathbf 1_{\{1\text{ is internal in }\beta\}}. \tag{14}\]
Now sum Eq. (14) over all \(\alpha\in\mathcal A_\ell\) and \(\beta\in\mathcal A_r\), and then over all pairs \((\ell,r)\) with \(\ell+r=n-1\). Let \[J_m:=\#\{\gamma\in\mathcal A_m:\text{the entry }1\text{ lies in an internal position}\}.\]
Then \[J_m= \begin{cases} C_m-2C_{m-1}, & m\geq 2,\\ 0, & m\leq 1. \end{cases}\]
Therefore \[\label{eq:Q4recurrence} \begin{aligned} Q_n = \sum_{\ell+r=n-1} \Bigl( &C_rQ_\ell+C_\ell Q_r +\bigl((r+1)(\ell-2)_+ +(r-2)_+\bigr)C_\ell C_r-J_\ell C_r-C_\ell J_r \Bigr). \end{aligned} \tag{15}\]
Introduce \[T(x):=\sum_{m\geq 0}(m-2)_+C_mx^m, \qquad J(x):=\sum_{m\geq 0}J_mx^m.\]
Multiplying Eq. (15) by \(x^n\) and summing over \(n\geq 1\), we obtain \[Q_4^{\mathcal A}(x) = 2xC(x)Q_4^{\mathcal A}(x) +xT(x)\bigl((xC(x))'+C(x)\bigr) -2xC(x)J(x).\]
Equivalently, \[\label{eq:Q4FE213} (1-2xC(x))Q_4^{\mathcal A}(x) = xT(x)\bigl((xC(x))'+C(x)\bigr) -2xC(x)J(x). \tag{16}\]
We compute \(T(x)\) and \(J(x)\). Since \((m-2)_+=0\) for \(m=0,1,2\), \[T(x) = \sum_{m\geq 3}(m-2)C_mx^m = \sum_{m\geq 0}(m-2)C_mx^m+2+x,\] and hence \[\label{eq:TClosed} T(x)=xC'(x)-2C(x)+2+x. \tag{17}\]
Also, \[\label{eq:JClosed} J(x)=(1-2x)C(x)+x-1. \tag{18}\]
Substituting Eq. (17) and Eq. (18) into Eq. (16), and using \[C(x)=\frac{1-\sqrt{1-4x}}{2x}, \qquad 1-2xC(x)=\sqrt{1-4x}, \qquad xC'(x)=\frac{1}{\sqrt{1-4x}}-C(x),\] we obtain \[\label{eq:Q4xClosed} \begin{aligned} Q_4^{\mathcal A}(x) ={}& \frac14(1-4x)^{-3/2} -\frac{7}{16}(1-4x)^{-1} -\frac{11}{8}(1-4x)^{-1/2}+5C(x) +\frac98\sqrt{1-4x} -\frac92 -\frac1{16}(1-4x). \end{aligned} \tag{19}\]
We now extract coefficients. Write \[B_n:=\binom{2n}{n}.\]
For \(n\geq 2\), the polynomial terms in Eq. (19) do not contribute. We use \[[x^n](1-4x)^{-1/2}=B_n, \qquad [x^n](1-4x)^{-1}=4^n,\] and the correct identity \[[x^n](1-4x)^{-3/2}=(2n+1)B_n.\]
Moreover, \[[x^n]C(x)=C_n=\frac{1}{n+1}B_n.\]
Since \[\sqrt{1-4x}=1-2xC(x),\] we also have, for \(n\geq 1\), \[[x^n]\sqrt{1-4x} = -2C_{n-1} = -\frac{1}{2n-1}B_n.\]
Therefore, for \(n\geq 2\), \[Q_4^{\mathcal A}(n) = \left( \frac{2n+1}{4} -\frac{11}{8} +\frac{5}{n+1} -\frac{9}{8(2n-1)} \right)B_n -\frac{7}{16}4^n.\]
A direct simplification yields \[Q_4^{\mathcal A}(n) = \frac{4n^3-7n^2+29n-20}{4(n+1)(2n-1)} \binom{2n}{n} – 7\cdot 4^{\,n-2}.\]
This proves the theorem. ◻
Theorem 3. For \(n\ge2\), with \(B_n=\binom{2n}{n}\), we have \[\begin{aligned} Q_1^{\mathcal{A}}(n) &= \frac{n+2}{2(2n-1)}\,B_n,\\[2mm] Q_2^{\mathcal{A}}(n) &= \frac{(12n^2+44n-112)\,B_n+(2n^2+n-1)\,4^n}{16(n+1)(2n-1)},\\[2mm] Q_3^{\mathcal{A}}(n) &= \frac{(8n^2-96n+88)\,B_n+(6n^2+3n-3)\,4^n}{8(n+1)(2n-1)},\\[2mm] Q_4^{\mathcal{A}}(n) &= \frac{(4n^3-7n^2+29n-20)\,B_n}{4(n+1)(2n-1)}-7\cdot 4^{\,n-2}. \end{aligned}\]
Proof. The formulas for \(Q_1^{\mathcal{A}}(n)\) and \(Q_4^{\mathcal{A}}(n)\) are given by Corollary 4 and Theorem 2, respectively. Once these are known, the only remaining unknowns are \(Q_2^{\mathcal{A}}(n)\) and \(Q_3^{\mathcal{A}}(n)\). Eqs. (12) and (13) therefore form a nonsingular linear system of size \(2\times 2\) for these two quantities.
Set \[S_1:=V^{\mathcal{A}}(n)-Q_1^{\mathcal{A}}(n)-Q_4^{\mathcal{A}}(n) =Q_2^{\mathcal{A}}(n)+Q_3^{\mathcal{A}}(n),\] and \[S_2:=\Sigma^{\mathcal{A}}(n)-Q_1^{\mathcal{A}}(n)-4Q_4^{\mathcal{A}}(n) =2Q_2^{\mathcal{A}}(n)+3Q_3^{\mathcal{A}}(n).\]
Subtracting twice the first identity from the second gives \[Q_3^{\mathcal{A}}(n)=S_2-2S_1.\]
Then \[Q_2^{\mathcal{A}}(n)=S_1-Q_3^{\mathcal{A}}(n).\]
Substituting the closed forms for \(V^{\mathcal{A}}(n)\) and \(\Sigma^{\mathcal{A}}(n)\) from Proposition 2, together with the formulas for \(Q_1^{\mathcal{A}}(n)\) and \(Q_4^{\mathcal{A}}(n)\), and simplifying, yields \[\begin{aligned} Q_2^{\mathcal{A}}(n) &= \frac{(12n^2+44n-112)\,B_n+(2n^2+n-1)\,4^n}{16(n+1)(2n-1)},\\[2mm] Q_3^{\mathcal{A}}(n) &= \frac{(8n^2-96n+88)\,B_n+(6n^2+3n-3)\,4^n}{8(n+1)(2n-1)}. \end{aligned}\]
This completes the proof. ◻
Remark 1. For convenience, we record below the values of \(H^{\mathcal{A}}(n)\) and \(Q_r^{\mathcal{A}}(n)\) for \(n=2,3,4,5,10,15,20\): \[\begin{array}{c|ccccc} n & H^{\mathcal{A}}(n) & Q_1^{\mathcal{A}}(n) & Q_2^{\mathcal{A}}(n) & Q_3^{\mathcal{A}}(n) & Q_4^{\mathcal{A}}(n)\\ \hline 2 & 2 & 4 & 2 & 0 & 0\\ 3 & 14 & 10 & 12 & 8 & 0\\ 4 & 76 & 30 & 48 & 54 & 8\\ 5 & 374 & 98 & 183 & 272 & 77\\ 10 & 661636 & 58344 & 149958 & 385260 & 330218\\ 15 & 894945944 & 45465480 & 134972779 & 421374264 & 561568877\\ 20 & 1103587381256 & 38879790180 & 127291628176 & 441098003796 & 771195866048 \end{array}\]
Remark 2. If \(\pi\) is chosen uniformly at random from \(\mathcal{A}_n\), then \[\mathbb{E}\bigl[\#\{v\in V(G_\pi):\deg(v)=r\}\bigr]=\frac{Q_r^{\mathcal{A}}(n)}{C_n}\qquad (r=1,2,3,4),\] and \(\mathbb{E}[H(\pi)]=\dfrac{H^{\mathcal{A}}(n)}{C_n}\).
We extract limiting proportions for \(Q_r^{\mathcal{A}}(n)/V^{\mathcal{A}}(n)\) and record leading corrections, then briefly compare with the unrestricted case.
Let \(V^{\mathcal{A}}(n)=\frac{n}{2}B_n\) be the total number of vertices summed over \(\mathcal{A}_n\). Using the classical asymptotic \(B_n\sim \dfrac{4^n}{\sqrt{\pi n}}\) (see, e.g., [7, App. A]) together with Theorem 3, we obtain \[\frac{Q_1^{\mathcal{A}}(n)}{V^{\mathcal{A}}(n)}\to 0,\qquad \frac{Q_2^{\mathcal{A}}(n)}{V^{\mathcal{A}}(n)}\to 0,\qquad \frac{Q_3^{\mathcal{A}}(n)}{V^{\mathcal{A}}(n)}\to 0,\qquad \frac{Q_4^{\mathcal{A}}(n)}{V^{\mathcal{A}}(n)}\to 1.\]
Moreover, the subdominant term of \(Q_4^{\mathcal{A}}(n)\) is \(-7\cdot 4^{n-2}\), and therefore \[\frac{Q_4^{\mathcal{A}}(n)}{V^{\mathcal{A}}(n)}=1-\frac{7}{8}\sqrt{\pi}\,n^{-1/2}+O(n^{-1}).\]
This contrasts with the unrestricted case [1], where the limiting proportion for degree \(4\) equals \(1/2\).
Corollary 5. Let \(V^{\mathcal{A}}(n)=\frac{n}{2}B_n\). As \(n\to\infty\), \[\begin{aligned} \frac{Q_1^{\mathcal{A}}(n)}{V^{\mathcal{A}}(n)} &= \frac{1}{2n}+O(n^{-2}),\\ \frac{Q_2^{\mathcal{A}}(n)}{V^{\mathcal{A}}(n)} &= \frac{\sqrt{\pi}}{8}\,n^{-1/2}+O(n^{-1}),\\ \frac{Q_3^{\mathcal{A}}(n)}{V^{\mathcal{A}}(n)} &= \frac{3\sqrt{\pi}}{4}\,n^{-1/2}+O(n^{-1}),\\ \frac{Q_4^{\mathcal{A}}(n)}{V^{\mathcal{A}}(n)} &= 1-\frac{7\sqrt{\pi}}{8}\,n^{-1/2}+O(n^{-1}). \end{aligned}\]
Proof. Use \(B_n\sim \dfrac{4^n}{\sqrt{\pi n}}\) (e.g. [7, App. A]) together with the closed forms in Theorem 3. For \(Q_2^{\mathcal{A}}\) and \(Q_3^{\mathcal{A}}\), the \(4^n\) terms dominate the \(B_n\) terms by a factor of \(\sqrt{n}\), yielding the stated constants after dividing by \(V^{\mathcal{A}}(n)\sim \dfrac{\sqrt{n}}{2\sqrt{\pi}}\,4^n\). For \(Q_4^{\mathcal{A}}\), the main term matches \(V^{\mathcal{A}}(n)\) and the first correction comes from \(-7\cdot4^{n-2}=-(7/16)4^n\), giving the constant \(\frac{7\sqrt{\pi}}{8}\) at order \(n^{-1/2}\). Finally, \(Q_1^{\mathcal{A}}(n)\sim \frac14 B_n\) and dividing by \(V^{\mathcal{A}}(n)\sim \frac n2 B_n\) gives \(Q_1^{\mathcal{A}}/V^{\mathcal{A}}\sim (2n)^{-1}\). ◻
Remark 3. The asymptotic statements above concern global proportions obtained after summing over all permutations in \(\mathcal A_n\). They do not assert a probabilistic concentration result for a uniformly chosen permutation in \(\mathcal A_n\), since no variance estimates are derived here.
We thus complete, for the Catalan class \(\mathrm{Av}_n(213)\), the program initiated in [1]. In sharp contrast with the unrestricted model, the rigid Catalan decomposition forces the global degree distribution over the class to be asymptotically dominated by degree-4 vertices: the proportion of degree-\(4\) vertices tends to \(1\) as \(n\to\infty\), with a leading deficit of order \(n^{-1/2}\). By Corollary 3, the same formulas and asymptotic conclusions hold verbatim for \(\mathrm{Av}_n(312)\).
The class \(\mathrm{Av}_n(132)\) (and, by reversal, \(\mathrm{Av}_n(231)\)) has been considered in separate work [9]. Therefore, among the length-\(3\) avoidance classes, only \(\mathrm{Av}_n(123)\) and \(\mathrm{Av}_n(321)\) remain to be analyzed. While these two classes are again Catalan-enumerated, their structural decompositions differ substantially from the \(213\)/\(132\) cases, and closing the analogous functional equations will likely require pattern-specific pivots together with additional boundary statistics.
Blecher, A., & Knopfmacher, A. (2025). Vertex degrees in grid graphs of permutations. Discrete Mathematics Letters, 16, 8-14.
Simion, R., & Schmidt, F. W. (1985). Restricted permutations. European Journal of Combinatorics, 6(4), 383-406.
Bóna, M. (2022). Combinatorics of Permutations (3rd ed.). CRC Press.
Stanley, R. P. (1999). Enumerative Combinatorics (Vol. 2). Cambridge University Press.
West, J. (1995). Generating trees and the Catalan and Schröder numbers. Discrete Mathematics, 146(1-3), 247-262.
Krattenthaler, C. (2001). Permutations with restricted patterns and Dyck paths. Advances in Applied Mathematics, 27(2-3), 510-530.
Flajolet, P., & Sedgewick, R. (2009). Analytic Combinatorics. cambridge University press.
Banderier, C., & Flajolet, P. (2002). Basic analytic combinatorics of directed lattice paths. Theoretical Computer Science, 281(1-2), 37-80.
Huamaní, N. B. (2026). Vertex degrees in grid graphs of 132-avoiding permutations. Manuscript submitted for publication.
