This paper fits in the intersection between two disparate areas of combinatorics. Namely, graph theory and the combinatorics of Catalan words. A Catalan word with n parts is defined as a word w = w1w2⋯wn over the set of positive integers in which w1 = 1 and 1 ≤ wk ≤ wk − 1 + 1 for k = 2, 3, …, n. In order to study the intersection of the two areas, a specific type of graph called a grid graph is defined for each Catalan word. The main thrust of the paper is investigating the degrees of vertices in grid graphs. For each of the possible fixed degrees i ∈ {1, 2, 3, 4}, we find generating functions DFi(x) where the coefficient of xn is the total number of vertices of degree i in all grid graphs with n parts.
A Catalan word with \(n\) parts is defined to be a word \(w=w_1 w_2 \cdots w_n\) of length \(n\) over the set of positive integers in which \(w_1=1\) and \(1 \le w_k \le w_{k-1}+1\) for \(k=2,3, \ldots ,n\). Catalan words can be represented geometrically as bargraphs and combinatorial studies of these bargraphs have attacted recent interest in the literature, see [4, 7, 8].
We will represent Catalan words with parts of any size as graphs with vertices and edges, which we call grid graphs. By a grid graph we mean that a Catalan word with \(n\) parts is represented by \(n\) columns of vertices bottom justified on the \(x\) axis. The \(i\)th part of size \(k\) is represented as the \(i\)th vertical column (counted from left to right) with \(k\) vertices each connected by an edge to all the neigbouring vertices in that column, as well as to vertices at the same height in a neighbouring column. This implies that any vertex has degree (in the graph sense) taken from the set \(\{1,2,3,4\}\). (The case \(n=1\) with a single vertex is exceptional, since then the vertex has degree 0). In Figure 1 below, we give an example of a grid graph and its equivalent bargraph.
For the grid graph on the left, there are five vertices of degree 2 (of which three are corners) and one of degree 4. All vertices in the grid graph have degrees in the set \(\{1,2,3,4\}\) as asserted above. For the bargraph, all vertices have degree in the set \(\{2,3,4\}\). There is no point in using colour for the left sketch since a grid graph has no dependence on area. A corner in both types of graph is defined as a degree 2 vertex which is connected to one horizontal and one vertical edge.
Catalan words are well known to be in bijection with Dyck paths and therefore Catalan words with \(n\) parts are counted by the Catalan numbers \(C_n=\frac{1}{n+1}\binom{2n}{n}\).
The reader may be wondering at the motivation for setting the combinatorics of Catalan words in the context of graph theory. There are some precedents as well as benefits for this setting in the current authors’ own recent work, which explored grid graphs in the context of integer compositions and integer partitions, see [1] and [2]. In recent years there has been extensive study of combinatorial objects represented as bargraphs. This includes Catalan words. One possibility for turning bargraphs into graphs was studied by Mansour et al. in [5, 7, 9]. In this case the intersections of the horizontal and vertical edges of the squares of the bargraph are turned into vertices and the line segment between these vertices becomes edges. Also, an essential part of this conception is the total area contained by the bargraph. Properties of the degrees of the vertices of the bargraphs of Mansour and Ramirez are then studied in [7]. A comparison of the left and right pictures in Figure 1 shows that the graphs obtained from the bargraph representation have a very different structure to the grid graphs being proposed in the current paper. In particular one notices that vertices of degree one play a prominent role in our grid graphs whereas bargraphs can have no vertices of degree one. This stems in part from the new idea which replaces each part of size \(i\) by a vertical column of \(i\) vertices. In the bargraph sense a part of size \(i\) is made up of a column of \(i\) squares each of which has four vertices, some of which are shared with adjacent parts in the bargraph as well as squares that are above and below in the same column.
This gives some insight into the contrast between the two underlying theoretical frameworks of grid graphs versus the traditional presentation of integer compositions, integer partitions and Catalan words as bargraphs. To explicate this point a little further: bargraphs explicitly in their conception conceive of each positive integer \(n\) as representing an underlying area of size \(n\). It seems to the current authors that the contained area concept of \(n\) is more simply represented as a count of \(n\) vertices. This has led to the purely graph theoretic conception which this paper explores, as opposed to a mixture of graph theoretic and underlying area conception of the bargraph model.
The current paper is structured as follows: In section 2, we obtain a generating function for vertices and edges in grid graphs. Sections 3-6 thereafter, contain the arguments required for enumerating vertices of degree 1-4 respectively.
There are two different types of arguments given in the various Sections. These have been chosen primarily under the criterion of simplicity. We categorise these arguments as:
1. Return to level one decompositions.
2. Adding a slice. (A geometrical method originally introduced by Temperley in [10]). Temperley’s method and others were surveyed in [3].
Sections 2 and 6 use argument 2 and the other Sections use argument 1.
We denote the set of all Catalan words with \(n\) parts by \(\it{A_n}\) and we represent these as grid graphs with edges and vertices as described in the introductory section. We let \(\pi_G\) be the grid graphs representing the Catalan word \(\pi\). Because of the obvious bijection between \(\pi_G\) and \(\pi\), we will in future suppress this difference and simply refer to both representations as \(\pi\). In these graphs the \(i\)th column represents the \(i\)th part of the Catalan word.
For any grid graph \(\pi\), we denote the number of vertices of \(\pi\) by \(vert(\pi)\) and the number of vertical and horizontal edges in \(\pi\) by \(v(\pi)\) and \(h(\pi)\) respectively. As illustration, the left hand grid graph shown in Figure1 has \(vert(\pi)=18\), \(v(\pi)=9\) and \(h(\pi)=12\). The right hand grid graph has a different value for each of these statistics.
We define the generating function \(A_n(y)\) as
\[\label{eq2.1} A_n(y) :=\sum\limits_{\pi \in A_n} y^{vert(\pi)} e_v^{v(\pi)} e_h^{h(\pi)}. \tag{1}\]
Also, \[\label{eq2.2} B(x, y):= B(x, y; e_v, e_h) := \sum _{n \ge 0} A_n(y) x^n, \tag{2}\] where \(n\) is the number of columns in the graph and the invariants \(e_v\) and \(e_h\) have been suppressed on the left side for the sake of brevity.
In order to study \(B(x, y)\), we introduce the notation \[B(x, y|b_1b_2 \cdots b_s) = \sum\limits_{n \ge 0}x^n\sum\limits_{\pi =\pi' b_1 b_2 \cdots b_s \in \it{A_n}}y^{vert(\pi)}e_v^{v(\pi)} e_h^{h(\pi)}.\]
By definition, we have \[B(x, y) = 1 +\sum\limits_{a \ge 1 }B(x,y|a).\]
If \(a=1\),
\[\begin{aligned} \label{eq2.3} B(x, y|1)&=x y+\sum\limits_{b \ge 1} x y B(x, y|b), \end{aligned} \tag{3}\] and if \(a\ge 2\), \[\begin{aligned} \label{eq2.4} B(x, y|a)&=\sum\limits_{b \ge a} x y^a B(x, y|b)+ x y^a B(x, y|a-1). \end{aligned} \tag{4}\]
Now define
\[\label{eq2.5} B(x,y,z):= 1+\sum\limits_{a \ge 1} B(x,y|a) z^{a-1}. \tag{5}\]
Multiply Eqs. (3) and (4) by \(z^{a-1}\) for the appropriate \(a\) and sum over \(a \ge 1\). We obtain
\[\begin{aligned} B(x,y,z)&=1+x y+\sum\limits_{b \ge 1} x y B(x, y|b)+\sum\limits_{a\ge 2} z^{a-1}\left(\sum\limits_{b \ge a} x y^a B(x, y|b)\right)\notag\\ &\qquad+\sum\limits_{a\ge 2} z^{a-1}\left( x y^a B(x, y|a-1)\right)\notag\\ &=1+x y+(B(x,y,1)-1)x y +\frac{x y^2 z }{1- y z}\left(B(x,y,1)-B(x,y,y z )\right)\notag\\ &\qquad+x y^2 z (B(x,y,y z )-1). \end{aligned} \tag{6}\]
We rewrite this equation in the following form:
\[\begin{aligned} &B(x,y,z)=a(z)+ b(z)B(x, y, c z), \end{aligned} \tag{7}\] where \(b(z)=x y^2 z -\frac{x y^2 z }{1- y z}=-\frac{x y^3 z^2 }{1- y z}\), \(c=y\) and where \[\begin{aligned} a(z) =1+x y-x y -x y^2 z -B(x,y,1) x y \left(1-\frac{yz }{1-yz }\right). \end{aligned}\]
Moreover, since each grid graph with the size of the last column being \(a\) can be written as either \(a\), or \(\pi'ba\) in which \(a \le b+1\) and \(\pi'\) may be empty, we obtain if \(a=1\), \[\begin{aligned} B(x, y|1)&=x y +\sum\limits_{b \ge 1}B(x, y|b1)=x y+\sum\limits_{b \ge 1} x y e_h B(x, y|b), \label{B(x, y|1)} \end{aligned} \tag{8}\] and if \(a\ge 2\),
\[\begin{aligned} B(x, y|a)&=\sum\limits_{b\ge {a-1}} B(x, y|ba)=\sum\limits_{b \ge a} x y^a e_v^{a-1} e_h^{a}B(x, y|b)+ x y^a e_v^{a-1} e_h^{a-1}B(x, y|a-1). \label{B(x, y|a)} \end{aligned} \tag{9}\]
Now define
\[B(x,y,z):= 1+\sum\limits_{a \ge 1} B(x,y|a) z^{a-1}. \label{Bdef} \tag{10}\]
Multiply Eqs. (8) and (9) by \(z^{a-1}\) for the appropriate \(a\) and sum over \(a \ge 1\). We obtain
\[\begin{aligned} B(x,y,z)&=1+x y+\sum\limits_{b \ge 1} x y e_h B(x, y|b)+\sum\limits_{a\ge 2} z^{a-1}\left(\sum\limits_{b \ge a} x y^a e_v^{a-1} e_h^{a}B(x, y|b)\right)\notag\\ &\qquad+\sum\limits_{a\ge 2} z^{a-1}\left( x y^a e_v^{a-1} e_h^{a-1}B(x, y|a-1)\right)\notag\\ &=1+x y+(B(x,y,1)-1)x y e_h+\frac{x y^2 z e_h^2 e_v }{1- e_h e_v y z}\left(B(x,y,1)-B(x,y,y z e_h e_v)\right)\notag\\ &\qquad+x y^2 z e_v e_h (B(x,y,y z e_v e_h)-1). \label{R1} \end{aligned} \tag{11}\]
We write this as
\[\begin{aligned} &B(x,y,z)=a(z)+ b(z)B(x, y, c z), \label{R2} \end{aligned} \tag{12}\] where \[\begin{aligned} b(z)&=\frac{x y^2 z e_v e_h(1-e_h(1+e_v y z))}{1- e_h e_v y z}, \end{aligned}\]
\[c=ye_he_v,\] and \[\begin{aligned} a(z)&=1+x y-x y e_h-x y^2 z e_v e_h +B(x,y,1) x y e_h \left(1+\frac{yz e_h e_v}{1-yz e_h e_v}\right). \end{aligned}\]
A few steps of iteration yields:
\[\begin{aligned} &b(z)B(x,y, c z)=a(c z)b(z)+ b(z)b(c z) B(x, y, c^2 z), \end{aligned} \tag{13}\] and \[\begin{aligned} &b(z)b(cz)B(x,y, c^2 z)=a(c^2 z) b(cz) b(z)+ b(z)b(c z)b(c^2 z) B(x, y, c^3 z). \end{aligned} \tag{14}\]
Repeating and summing to infinity under the assumption that \(|z|\le 1\) and \(|c|< 1\), we obtain
\[\begin{aligned} &B(x,y,z)=\sum\limits_{i \ge 0}a(c^i z)\prod_{j=0}^{i-1} b(c^j z), \label{RS} \end{aligned} \tag{15}\] and by returning to the original variables, we have
\[\begin{aligned} B(x,y,z)&=\sum\limits_{i \ge 0}\left(1+x y-x y e_h-x y^2 c^i z e_v e_h +B(x,y,1) xy e_h\left(1+\frac{y c^i z e_h e_v}{1- e_h e_v y c^i z}\right)\right)\notag\\ &\qquad\times c^{i(i-1)/2} x^i y^{2i} z^i e_v^i e_h^i\prod_{j=0}^{i-1} \frac{1-e_h(1+e_v y c^j z)}{1- e_h e_v y c^j z}. \end{aligned} \tag{16}\]
Finally, substituting \(z=1\), we obtain \[\begin{aligned} &B(x,y,1)\notag\\ &=\sum\limits_{i \ge 0}\left(1+x y-x y e_h-x y^2 c^i e_v e_h\right) c^{i(i-1)/2} x^i y^{2i} e_v^i e_h^i\prod_{j=0}^{i-1} \frac{1-e_h(1+e_v y c^j)}{1- e_h e_v y c^j}\notag\\ &~~~ +\sum\limits_{i \ge 0}B(x,y,1) xy e_h\left(1+\frac{y c^i e_h e_v}{1- e_h e_v y c^i }\right) c^{i(i-1)/2} x^i y^{2i} e_v^i e_h^i\prod_{j=0}^{i-1} \frac{1-e_h(1+e_v y c^j)}{1- e_h e_v y c^j}, \end{aligned} \tag{17}\]
or solving for \(B(x,y,1)\),
\[\begin{aligned} B(x,y,1)&=\frac{\sum\limits_{i \ge 0}\left(1+x y-x y e_h-x y^2 c^i e_v e_h\right) c^{i(i-1)/2} x^i y^{2i} e_v^i e_h^i\prod_{j=0}^{i-1} \frac{1-e_h(1+e_v y c^j)}{1- e_h e_v y c^j}}{1-\sum\limits_{i \ge 0}xy e_h\left(1+\frac{y c^i e_h e_v}{1- e_h e_v y c^i }\right) c^{i(i-1)/2} x^i y^{2i} e_v^i e_h^i\prod_{j=0}^{i-1} \frac{1-e_h(1+e_v y c^j)}{1- e_h e_v y c^j}}. \end{aligned}\]
Replacing with the original variable for \(c\), we have therefore proved the following theorem.
Theorem 2.1. The generating function for the number of grid graphs is given by \[\begin{aligned} &B(x,y;e_v,e_h)\notag\\ &=\frac{\sum\limits_{i \ge 0}\left(1+x y-x y e_h-x y ( e_v e_h y)^{i+1} \right) x^i y^{i(i+3)/2} e_v^{i(i+1)/2} e_h^{i(i+1)/2} \prod_{j=0}^{i-1} \frac{1-e_h-(e_v e_h y)^{j+1} }{1- (e_v e_h y)^{j+1}}}{1-\sum\limits_{i \ge 0}\frac{x^{i+1} y^{(i+1)(i+2)/2} e_v^{i(i+1)/2} e_h^{(i^2+i +2)/2}}{1- (e_v e_h y)^{i+1}} \prod_{j=0}^{i-1} \frac{1-e_h-(e_v e_h y)^{j+1} }{1- (e_v e_h y)^{j+1}}}, \label{mgf} \end{aligned} \tag{18}\] where \(x\) tracks the number of parts in the grid graph and \(y\) tracks the number of vertices. The number of vertical edges is tracked by \(e_v\) and the number of horizontal edges is tracked by \(e_h\).
Substituting \(e_v=1\) and \(e_h=1\) into Eq. (18) and simplifying, we obtain \[\begin{aligned} B(x,y;1,1) &=1+\frac{\sum\limits_{i \ge 1}(-1)^{i-1}x^i y^{i^2}\prod_{j=1}^{i-1} \frac{1}{1- y^{j}}}{1-\sum\limits_{i \ge 1}(-1)^{i-1}x^i y^{i^2}\prod_{j=1}^{i} \frac{1}{1- y^{j}}}, \label{B(1,1)} \end{aligned} \tag{19}\] which matches the generating function translated from Callan et al in [4]. By translation, we mean that the area of Catalan bargraphs tracked by \(q\) in their generating function has been replaced by our invariant \(y\) which is tracking the number of vertices in our grid graph context of Catalan words.
Substituting \(e_h=1\) into Eq. (18), we obtain \[\begin{aligned} B(x,y;e_v,1)=\frac{\sum\limits_{i \ge 0}(-1)^i \left(1 -x y ( e_v y)^{i+1} \right) x^i y^{i(i+2)} e_v^{i(i+1)} \prod_{j=0}^{i-1} \frac{ 1 }{1- (e_v y)^{j+1}}}{1-\sum\limits_{i \ge 0}(-1)^i x^{i+1} y^{(i+1)^2} e_v^{i(i+1)} \prod_{j=0}^{i} \frac{1 }{1- (e_v y)^{j+1}}}, \label{B(e_v)} \end{aligned} \tag{20}\] which is the generating function for Catalan word grid graphs according to number of parts and vertical edges. Since this generating function has number of vertical edges one less than the number of vertices in each column we can modify Eq. (19) in order to track the number of vertical edges. We obtain \[B(x,y;e_v,1)=1+\frac{\sum\limits_{i \ge 1}(-1)^{i-1}x^i y^{i^2} e_v^{i^2-i}\prod_{j=1}^{i-1} \frac{1}{1- (e_v y)^{j}}}{1-\sum\limits_{i \ge 1}(-1)^{i-1}x^i y^{i^2} e_v^{i^2-i}\prod_{j=1}^{i} \frac{1}{1- (e_v y)^{j}}}. \label{A2} \tag{21}\]
We leave it to the reader to verify the equality between the right hand sides of Eqs. (20) and (21).
Next, putting \(e_v=1\) into the Eq. (18) in Theorem 2.1, we obtain
\[\begin{aligned} B(x,y;1,e_h)=\frac{\sum\limits_{i \ge 0}\left(1+x y-x y e_h-x y (e_h y)^{i+1} \right) x^i y^{i(i+3)/2} e_h^{i(i+1)/2} \prod_{j=0}^{i-1} \frac{1-e_h-(e_h y)^{j+1} }{1- (e_h y)^{j+1}}}{1-\sum\limits_{i \ge 0}\frac{x^{i+1} y^{(i+1)(i+2)/2} e_h^{(i^2+i +2)/2}}{1- (e_h y)^{i+1}} \prod_{j=0}^{i-1} \frac{1-e_h-(e_h y)^{j+1} }{1- (e_h y)^{j+1}}}. \end{aligned} \tag{22}\]
Remark 2.2. By repeating the recursive process only tracking the variable \(e_h\) and not \(e_v\) we obtain the following simpler generating function \[\begin{aligned} B(x,y,1,q) &=\frac{\sum\limits_{i \ge 0}x^{i+1} e_h^{i(i+1)/2} y^{i(i+3)/2+1}\prod_{j=0}^{i-1} \frac{ (1-e_h-(e_hy)^{j+1} )}{1-(e_hy)^{j+1} }}{1-\sum\limits_{i \ge 0}\frac{x^{i+1}y^{i(i+3)/2+1}e_h^{i(i+1)/2+1} }{1-(e_hy)^{i+1}} {\prod_{j=0}^{i-1} \frac{ (1-e_h-(e_hy)^{j+1} )}{1- (e_hy)^{j+1} }}}. \end{aligned} \tag{23}\]
In the sections that follow, we obtain generating functions tracking the total number of vertices of a fixed degree across all grid graphs.
A vertex of degree one always occurs in the first part, \(1\), of a Catalan grid graph (except if the grid graph is \(1\) itself, in which case it is of degree \(0\)). It will occur at the top vertex of an interior part of size \(a+1\) iff that part is preceded by a part \(a\) and followed by a part \(b\) where \(b \le a\). We call this configuration a peak. Examples of this assertion can be seen in Figure 1. Also, a vertex of degree 1 will occur in the last part iff that part is a \(1\) or alternatively, if that part is larger than the preceding part. In other words an interior part has a single (topmost) vertex of degree one iff that vertex is a peak of the Catalan grid graph. Next, we develop a bi-variate generating function to count all interior peaks across all Catalan grid graphs. As in a previous section, we denote the set of all Catalan words with \(n\) parts by \(\it{A_n}\) and define the following generating function: \[\begin{aligned} P(x,q):=\sum\limits_{n \ge 1} x^n \sum\limits_{w \in \it{A_n} } q^{\text{degree 1 vertices}(w)} , \end{aligned} \tag{24}\] where \(n=|w|\) is the number of parts in \(w\).
We use the first return decomposition for Catalan grid graphs to develop a functional equation for \(P(x,q)\). Let \(w\) be a nonempty Catalan word, and let \(w = 1w_1^Rw_2\) be the first return decomposition, with \(w_1,w_2\in \it{A_n}\) or empty and where \(w_1^R\) represents the word \(w_1\) where each part has been increased by 1. We obtain the following functional equation: \[\begin{aligned} P(x,q)&=x(1+P(x,q))(1+P(x,q))-\underbrace{xP^2(x,q)}_0+(\underbrace{x^2 q(1+ P(x,q))}_{1}\notag\\ &\qquad+ x\underbrace{(P(x,q)-x)- x P(x,q)}_2) P(x,q) \notag\\ &=x + 2x P(x,q) + x^2 q P(x,q) + x^2 q P^2(x,q) + x (P(x,q)-x)P(x,q) -x^2 P^2(x,q), \end{aligned} \tag{25}\] where underbrace 0 represents the case where both \(w_1\) and \(w_2\) are non empty. This is dealt with separately in the next line and therefore removed here. Underbrace 1 represents either a single part in \(w_1\) or multiple parts ending in an increase and resulting in an extra peak and consequent \(q\), provided it is followed by non empty \(w_2\). Underbrace 2 represents the complementary cases to 1 and so have no \(q\).
This has solution \[\begin{aligned} P(x,q)=\frac{1-2x+(1-q)x^2-\sqrt{1-4x+2(1-q) x^2 +(1-q)^2 x^4}}{2x(1-(1-q)x)}. \end{aligned} \tag{26}\]
As explained at the beginning of this section, the latter generating function tracks all internal degree one vertices. Next, we find the gf for the total number of internal degree one vertices which we name \(DP(x):=\frac{\partial}{\partial q}P(x,q)|_{q=1}.\) This yields \[\begin{aligned} DP(x)=\frac{1}{2}\left(-1+x+\frac{1-3x}{\sqrt {1-4x}}\right). \label{DP} \end{aligned} \tag{27}\]
For non-internal degree one vertices in the first part, we need to count all of these except where the grid graph has only one part. The generating function for the total number of these is \[\begin{aligned} DP_1(x):= (C(x)-1) -x, \label{DP1} \end{aligned} \tag{28}\] where \(C(x)\) is the Catalan word generating function. For non-internal degree one vertices in the last part, we need to count all of those ending either in an increase or a \(1\) in the last part. The generating function for the total number of these is \[\begin{aligned} DP_2(x):= (C(x)-1) 2 x. \label{DP2} \end{aligned} \tag{29}\]
Adding together Eqs. (27), (28) and (29) we obtain that the overall gf for the total number of degree 1 vertices in all grid graphs, namely \(DF_1\) is given by \[\begin{aligned} DF_1(x)=\frac{1-x-5x^2}{2x}+\frac{-1+3x+5x^2}{2x\sqrt{1-4x}}. \end{aligned}\]
So we have proved the following theorem.
Theorem 3.1. The total number of vertices of degree 1 in Catalan word grid graphs with \(n\) parts, where the number of parts is tracked by \(x\) is given by the coefficient of \(x^n\) in \[\begin{aligned} DF_1(x)=\frac{1-x-5x^2}{2x}+\frac{-1+3x+5x^2}{2x\sqrt{1-4x}}, \label{Totd1vertices} \end{aligned} \tag{30}\]
where for \(n\ge 2\), \[\begin{aligned} DF_1(x)= \frac{1}{2} \left(3 \binom{2 n}{n}+5 \binom{2 n-2}{n-1}-\binom{2 n+2}{n+1}\right). \label{Totd1[x^n]} \end{aligned} \tag{31}\] The series expansion for this begins \[\begin{aligned} DF_1(x)=4x^2+10x^3+29 x^4+91 x^5+300x^6+1023x^7+3575x^8 +O(x^9). \end{aligned} \tag{32}\]
Asymptotically as \(n \to \infty\), by singularity analysis (see [6]) of the generating function in Eq. (30), or by Stirling’s formula applied to (31), the number of degree 1 vertices, denoted by \(r_1(n)\) is given by \[r_1(n)\sim \frac{4^{n-1}}{2\sqrt {\pi n}}. \label{r_1} \tag{33}\]
A degree 2 vertex in a grid graph may occur in three types which we may call a left corner (labeled \(c_l\)), a right corner (labeled \(c_r\)) or a horizontal middle (\(h\)). We illustrate all of these in the Figure 2 before defining them formally.
Here are the formal definitions.
A left corner is a vertex connected to two edges, one vertical and one horizontal. The vertex is at the left point of the horizontal and the top point of the vertical.
A right corner is a vertex connected to two edges, one vertical and one horizontal. The vertex is at the right point of the horizontal.
A horizontal middle is a vertex connected to two edges, both horizontal.
Remark 4.1. There is a right corner at the bottom vertex of the final column iff this column is not a 1.
As in the previous Section, we will use a first return decomposition to obtain a separate generating function for each of these types.
Firstly, those of type \(h\) can occur only in the bottom row of a grid graph and not in the first or last column. We count these across all grid graphs. If the number of vertices is \(n\), this is equivalent to counting the number of internal ones in all grid graphs of \(n\) with three or more parts, therefore excluding those which occur in the first or last parts.
First, we develop a bi-variate generating function to count all interior ones across all Catalan grid graphs. As in a previous section, we denote the set of all Catalan words with \(n\) parts by \(\it{A_n}\) and define the following generating function: \[\begin{aligned} P_{ic}(x,q):=\sum\limits_{n \ge 1} x^n \sum\limits_{w \in \it{A_n} } q^{\text{interior columns of height 1 of }w} , \end{aligned} \tag{34}\] where \(n=|w|\) is the number of parts in \(w\).
Using the first return decomposition as per the previous Section, any grid graph \(w\) may be written as \(w=1w_1^Rw_2\). However, here we do not need to consider separate cases for \(w_1\) or \(w_2\) being empty as this will be allowed in the following functional equation: \[\begin{aligned} P_{ic}(x,q)=xC(x)(q(P_h(x,q)-x)+x+1), \end{aligned} \tag{35}\] which has solution \[\begin{aligned} P_{ic}(x,q)=\frac{(1-\sqrt{1-4x})(1+x-qx)}{2-q+q\sqrt{1-4x}}. \label{P_{ic}} \end{aligned} \tag{36}\]
Next define the following generating function: \[\begin{aligned} P_{l}(x,q):=\sum\limits_{n \ge 1} x^n \sum\limits_{w \in \it{A_n} } q^{\text{left corners of}\ w} , \end{aligned} \tag{37}\] where \(n=|w|\) is the number of parts in \(w\).
Again using the first return decomposition, we obtain \[\begin{aligned} P_{l}(x,q)=x(1+q(P_{l}(x,q)-x)+x)(1+P_{l}(x,q)), \end{aligned} \tag{38}\] which has solution \[\begin{aligned} P_{l}(x,q)=\frac{1-x-q x-x^2+q x^2-\sqrt{4 q x \left(-x-x^2+q x^2\right)+\left(1-x-q x-x^2+q x^2\right)^2}}{2 q x}. \label{P_l} \end{aligned} \tag{39}\]
Finally, we define the following generating function: \[\begin{aligned} P_{r}(x,q):=\sum\limits_{n \ge 1} x^n \sum\limits_{w \in \it{A_n} } q^{\text{right corners of}\ w}, \end{aligned} \tag{40}\] where \(n=|w|\) is the number of parts in \(w\).
Again using the first return decomposition, we obtain \[\begin{aligned} P_{r}(x,q) &=\underbrace{\underbrace{x}_{0}+\underbrace{x^2 q}_{1} +\underbrace{x(P_{r}(x,q|1)-x)q^2}_{2}+\underbrace{{x(P_{r}(x,q)-P_r(x,q|1))}}_{3}}_{\text{no first return}}\notag\\ &\qquad+\underbrace{(x+x^2 +x(P_r(x,q|1)-x)q+\frac{x}{q}(P_r(x,q)-P_r(x,q|1))P_r(x,q)}_{\text{has a first return}}, \end{aligned} \tag{41}\] where underbrace 0 is where \(w_1\) is empty, underbrace 1 is where \(w_1\) has one part, underbrace 2 is where \(w_1\) has multiple parts ending in \(1\) and underbrace 3 is for the case where \(w_1\) has multiple parts not ending in \(1\). Also, any graph graph ending in 1 may consist only of ones (with gf \(\frac{x}{1-x}\)), or it has a rightmost part which is not one (and the generating function is \(\frac{1}{q}(P_{r}(x,q)-P_{r}(x,q|1))\) for the part of the c-word to the left of any final ones). This leads to gf: \[\begin{aligned} P_{r}(x,q|1)=\frac{1}{q}(P_{r}(x,q)-P_{r}(x,q|1))\frac{x}{1-x}+\frac{x}{1-x}. \label{P_r P_r(|1)} \end{aligned} \tag{42}\]
By solving the above two equations simultaneously, we obtain \[\begin{aligned} P_{r}(x,q)&=\frac{q+x-3 q x+q x^2-q^2 x^2-x^3+2 q x^3-q^2 x^3}{2 \left(x-x^2+q x^2\right)}\notag\\ &\qquad-\frac{(q+x-q x) \sqrt{1-4 x+2 x^2-2 q x^2+x^4-2 q x^4+q^2 x^4}}{2 \left(x-x^2+q x^2\right)}. \label{P_r} \end{aligned} \tag{43}\]
Finally, we would like to obtain the gf for the total number of degree 2 vertices. To achieve this we first obtain the gf for the total number of degree 2 vertices of each type. We obtain from Eq. (36), the gf for the total number of type \(h\) vertices which we call \(DP_{ic}\) as \[\begin{aligned} DP_{ic}= \frac{2(1-2x-2x^2-\sqrt{1-4x})}{(1+\sqrt{1-4x})^2} . \label{DP_{ic}} \end{aligned} \tag{44}\]
Similarly, the gf for the total number of type \(l\) vertices which we call \(DP_{l}\) is obtained by differentiating Eq. (39) to obtain \[\begin{aligned} DP_{l}=\frac{1-3x-x^2}{2x\sqrt{1-4x}}-\frac{1-x-x^2}{2x} . \label{DP_l} \end{aligned} \tag{45}\]
Finally by the same method and naming convention, we obtain from Eq. (43) \[\begin{aligned} DP_{r}=\frac{-1+6x-7x^2}{2x\sqrt{1-4x}}+\frac{1-4x+x^2}{2x}. \label{DP_r} \end{aligned} \tag{46}\].
Adding together the previous three equations, we obtain the overall gf for the total number of degree 2 vertices in all grid graphs, called \(DF_2(x)\), is given by \[\begin{aligned} DF_2(x)=\frac{1-2 x-4 x^2}{1+\sqrt{1-4 x}-2 x}-\frac{1-4 x-4 x^2}{\left(1+\sqrt{1-4 x}-2 x\right) \sqrt{1-4 x}} . \end{aligned}\]
So we have proved the following Theorem
Theorem 4.2. The total number of vertices of degree 2 in Catalan word grid graphs with \(n\) parts, where the number of parts is tracked by \(x\) is given by the coefficient of \(x^n\) in \[\begin{aligned} DF_2(x)&=\frac{1-2 x-4 x^2}{1+\sqrt{1-4 x}-2 x}-\frac{1-4 x-4 x^2}{\left(1+\sqrt{1-4 x}-2 x\right) \sqrt{1-4 x}}\notag\\ &=\frac{1-4 x-2 x^2+4 x^3}{2 x^2}-\frac{1-6 x+4 x^2+12 x^3 }{2 x^2 \sqrt{1-4 x}}, \label{Totd2vertices} \end{aligned} \tag{47}\] where for \(n\ge 3\), \[\begin{aligned} DF_2(x)=-2 \binom{2 n}{n}-\frac{1}{2} \binom{2 n+4}{n+2}+3 \binom{2 n+2}{n+1}-6 \binom{2 n-2}{n-1}. \end{aligned} \tag{8}\]
The series expansion for this begins \[\begin{aligned} DF_2(x)=x^2+8 x^3+34 x^4+132 x^5+501 x^6+1892 x^7+7150 x^8+27092 x^9+O\left(x^{10}\right) . \label{DF_2series} \end{aligned} \tag{49}\]
Asymptotically as \(n \to \infty\), the number of degree 2 vertices, denoted by \(r_2(n)\) is given by \[r_2(n)\sim \frac{4^{n}}{2\sqrt {\pi n}} . \label{r_2} \tag{50}\]
A degree 3 vertex in a grid graph may occur in one of two ways. which we may call a horizontal middle (\(h\)), or a vertical middle (\(v\)) . We illustrate all of these in the Figure 3 below, before defining them formally.
Here are the formal definitions.
A horizontal middle (\(h\)) is a vertex connected to three edges, one vertical and two horizontal. The vertex may be either at the top or bottom point of the vertical.
A vertical middle (\(v\)) is a vertex connected to three edges, two vertical and one horizontal. The vertex can only be at the right point of the horizontal.
As in a previous section, we denote the set of all Catalan words with \(n\) parts by \(\it{A_n}\) and define the following multivariate generating function: \[\begin{aligned} P_h(x,q,v):=\sum\limits_{n \ge 1} x^n \sum\limits_{w \in \it{A_n} } q^{\text{horizontal middles}\; (w)} v^{\text{interior ones}\;(w)} , \end{aligned} \tag{51}\] where \(n=|w|\) is the number of parts in \(w\).
Using the first return decomposition as per the previous Section, any grid graph \(w\) may be written as \(w=1{w_1}^R w_2\) where \({w_1}^R\) represents a raised Catalan word.
If empty \(w_2\) follows, the generating function for \(w_1^R\) is \[\begin{aligned} w_1^R=1+x+q(P_h(x,q,q^2)-x), \end{aligned} \tag{52}\] where coefficient \(q\) of the third right side term tracks the \(h\) vertex at the bottom of the initial raised \(1\) and where the third parameters of \(P_h\) is \(q^2\) because every interior 1 (i.e., exponent of the third parameter) has a contribution of \(2\) after raising. As already defined above the middle parameter \(q\) of \(P_h\) tracks the number of \(h\) vertices before raising \(w_1\).
This results (from using the first return decomposition) in the following functional equation \[\begin{aligned} P_h(x,q,v)&= \underbrace{x(1+x+q(P_h(x,q,q^2)-x))}_{\text{$w_2$ empty}}\notag\\ &\qquad+\underbrace{x(1+q x+q^2(P_h(x,q,q^2)-x))(v P_h(x,q,v)-vx+x)}_{\text{$w_2$ non-empty}}. \end{aligned} \tag{53}\]
Actually what we want is the gf for the total number of occurrences of degree 3 vertices of type \(h\). To simplify this calculation we differentiate the previous equation with respect to \(q\) and then set \(q=1\). First, we define \(DP_h:=\frac{\partial P_h(x,q,v) }{\partial q}|_{q=1}\). Doing this we obtain: \[\begin{aligned} DP_h &= x\left(2\frac{\partial P_{ic}(x,v) }{\partial v}+\frac{\partial P_h(x,1,1) }{\partial q}+P_h(x,1,1)-x\right ) +x(1+P_h(x,1,1))vDP_h\notag\\ &\quad+x\left(x+2\frac{\partial P_{ic}(x,v) }{\partial v}+\frac{\partial P_h(x,1,1) }{\partial q}+2(P_h(x,1,1)-x)\right)(v P_h(x,1,v)-vx+x),\notag\\ \label{DP_h} \end{aligned} \tag{54}\] where \(P_{ic}\) is taken from Eq. (36) and \(DP_{ic}\) is taken from Eq. (44) with \(q\) replaced by \(v\) in those Equations. Putting \(v=1\) into Eq. (54), we obtain \[\begin{aligned} DP_h|_{v=1}&=x\left(2\frac{\partial P_{ic}(x,v) }{\partial v}+\frac{\partial P_h(x,1,1) }{\partial q}+P_h(x,1,1)-x\right ) +x(1+P_h(x,1,1))DP_h\notag\\ &\quad+x\left(x+2\frac{\partial P_{ic}(x,v) }{\partial v}+\frac{\partial P_h(x,1,1) }{\partial q}+2(P_h(x,1,1)-x)\right)P_h(x,1,1). \end{aligned} \tag{55}\]
Solving for \(DP_h\) leads to the following theorem.
Theorem 5.1. The total number of type \(h\) vertices of degree 3 in Catalan word grid graphs with \(n\) parts, where the number of parts is tracked by \(x\) is given by the coefficient of \(x^n\) in \[\begin{aligned} DP_h(x)&=\frac{4-4 \sqrt{1-4 x}-8 x+2 \left(-5+\sqrt{1-4 x}\right) x^2}{\left(1+\sqrt{1-4 x}\right)^2 \sqrt{1-4 x}}\notag\\ &= \frac{2-8 x+x^2+7 x^3}{2 x^2}+\frac{-2+12x-13x^2-13x^3+4x^4}{2 x^2 \sqrt{1-4 x}}, \label{Totd3vertices} \end{aligned} \tag{56}\] where for \(n \ge 2\), \[\begin{aligned} DP_h(x)&= -\frac{13} {2}\binom{2 n}{n}-\binom{2 n+4}{n+2}+6 \binom{2 n+2}{n+1}-\frac{13}{2} \binom{2 n-2}{n-1}+2 \binom{2 n-4}{n-2}. \end{aligned} \tag{57}\]
Next, we concentrate on vertical middles and define \[\begin{aligned} P_v(x,q):=\sum\limits_{n \ge 1} x^n \sum\limits_{w \in \it{A_n} } q^{\text{vertical middles}\; (w)} , \end{aligned} \tag{58}\] where \(n=|w|\) is the number of parts in \(w\).
Once again we use the first return decomposition for Catalan grid graphs to develop a functional equation for \(P_v(x,q)\). Let \(w\) be a nonempty Catalan word, and let \(w = 1w_1^Rw_2\) be the first return decomposition, with \(w_1,w_2\in \it{A_n}\) or empty, in which case they are represented by \(1\). We obtain the following functional equation: \[\begin{aligned} P_v(x,q)&=x(1+\underbrace{q(P_v(x,q)-P_v(x,q|1))}_{\text{$w_1$ does not end in 1}}+P_v(x,q|1))(1+P_v(x,q)), \end{aligned} \tag{59}\] because \(w_1\) not ending in a 1 induces an extra \(q\), owing to the extra \(v\) in the last column when raised.
Following a similar analysis to that which produced Eq. (42), we have the following \[\begin{aligned} P_{v}(x,q|1)=(P_{v}(x,q)-P_{v}(x,q|1))\frac{x}{1-x}+\frac{x}{1-x}. \end{aligned} \tag{60}\]
By simultaneously solving the two equations immediately above, we obtain \[\begin{aligned} P_{v}(x,q)&=\frac{1-x-q x-2 x^2+2 q x^2-\sqrt{1-2 x-2 q x-3 x^2+2 q x^2+q^2 x^2}}{2 \left(q x+x^2-q x^2\right)}. \end{aligned} \tag{61}\]
We have therefore proved the following theorem.
Theorem 5.2. The bivariate generating function for the number of type \(v\) vertices of degree 3 in Catalan word grid graphs with \(n\) parts, where the number of parts is tracked by \(x\) and the number of such vertices is tracked by \(q\) is given by the coefficient of \(x^n q^j\) in \[\begin{aligned} P_{v}(x,q)&=\frac{1-x-q x-2 x^2+2 q x^2-\sqrt{1-2 x-2 q x-3 x^2+2 q x^2+q^2 x^2}}{2 \left(q x+x^2-q x^2\right)}. \end{aligned} \tag{62}\]
Next we obtain the total number \(DP_v\) of type \(v\) vertices by differentiating Eq. (62) with respect to \(q\) and putting \(q=1\). We obtain
Theorem 5.3. The total number of type \(v\) degree three vertices in Catalan grid graphs with \(n\) parts is given by the coefficient of \(x^n\) in \[\begin{aligned} DP_v(x)=\frac{1-\sqrt{1-4 x}+2 \left(-2+\sqrt{1-4 x}\right) x+2 x^2}{2 \sqrt{1-4 x} x}. \label{DP_v} \end{aligned} \tag{63}\]
Finally, we add together Eqs. (56) and (63) to obtain the final theorem of this Section.
Theorem 5.4. The total number of degree three vertices in all grid graphs with \(n\) parts is given by the coefficient of \(x^n\) in \[\begin{aligned} DF_3(x)=\frac{2-2 \sqrt{1-4 x}-3 x-x\sqrt{1-4 x} -7 x^2+x^2\sqrt{1-4 x} }{\sqrt{1-4 x} \left(1+\sqrt{1-4 x}-2 x\right)} . \label{DF_3(x)} \end{aligned} \tag{64}\]
This generating function has series expansion beginning \[\begin{aligned} DF_3(x)=4 x^3+27 x^4+135 x^5+606 x^6+2585 x^7+10725 x^8+43771 x^9+O\left(x^{10}\right). \label{DF_3series} \end{aligned} \tag{65}\] Asymptotically as \(n \to \infty\), the number of degree 3 vertices, denoted by \(r_3(n)\) is given by \[r_3(n)\sim \frac{13}{2}\frac{4^{n-1}}{\sqrt {\pi n}} . \label{r_3} \tag{66}\]
Let \(P(x,q_4|ab)\) and \(P(x,q_4|a)\) be the gfs for grid graphs with \(k\) parts tracked by \(x\) ending in parts \(ab\) and \(a\) respectively, where \(q_4\) marks the number of degree 4 vertices. We attach part \(b\) to the right of \(a\).
For \(b\ge 2\), \(b < a\) and \(a\ge 3\) we have the following functional equation: \[\begin{aligned} P (x, q_4|ab)=x q_4^{b-1}P(x,q_4|a). \end{aligned} \tag{67}\]
For \(b\ge 2\), \(b = a\) and \(a\ge 3\) we have the following functional equation: \[\begin{aligned} P (x, q_4|ab)=x q_4^{b-2}P(x,q_4|a). \end{aligned} \tag{68}\]
For \(b = a+1\) and \(a\ge 3\) we have the following functional equation: \[\begin{aligned} P (x, q_4|ab)=x q_4^{a-2}P(x,q_4|a). \label{b=a+1} \end{aligned} \tag{69}\]
For \(b\ge 2\) and \(b-1 \le a <3\) \[\begin{aligned} P (x, q_4|ab)=x P(x,q_4|a). \end{aligned} \tag{70}\]
And also \[\begin{aligned} P(x,q_4|1)= x + P (x, q_4|a1)=x+x P(x,q_4|a). \end{aligned} \tag{71}\]
Define \[\begin{aligned} P(x,q_4,z):=\sum\limits_{a \ge 1} P(x,q_4|a)z^a. \end{aligned} \tag{72}\]
Multiplying the previous equations by the appropriate \(z^b\) and summing, we obtain:
\[\begin{aligned} P&(x,q_4,z)\notag\\ &= \sum\limits_{a\ge3}\sum\limits_{b = 2}^{a-1}x q_4^{b-1}P(x,q_4|a)z^b+\sum\limits_{a\ge3}x q_4^{a-2}P(x,q_4|a)z^a\notag\\ &\quad+\underbrace{\frac{x}{q_4^{2}}\sum\limits_{a\ge3} q_4^{a}P(x,q_4|a)z^{a+1}}_{\text{Eq. $\eqref{b=a+1}$}}+ \sum\limits_{a=1}^2\sum\limits_{b = 2}^{a+1}x P(x,q_4|a)z^b+P(x,q_4|1)z\notag\\ &= x \frac{q_4 z^2}{1-q_4 z}(P(x,q_4,1)-P(x,q_4|2)-P(x,q_4|1))\notag\\ &\quad+\frac{x(1-q_4+z -q_4 z-q_4 z^2)}{q_4^2(1-q_4 z)}(P(x,q_4,q_4 z)-P(x,q_4|2)q_4^2 z^2-P(x,q_4|1)q_4 z)\notag\\ &\quad + xP(x,q_4|1)z^2+ xP(x,q_4|2)z^2+ xP(x,q_4|2)z^3+xz+xz P(x,q_4,1). \label{MFE} \end{aligned} \tag{73}\]
Separately solving for \(P(x,q_4|1)\) and \(P(x,q_4|2)\), we obtain \[\begin{aligned} P(x,q_4|1)=x+xP(x,q_4,1), \label{FE1} \end{aligned} \tag{74}\] and \[\begin{aligned} P(x,q_4|2)=(P(x,q_4,1)- P(x,q_4|1)-P(x,q_4|2))xq_4+xP(x,q_4|1)+xP(x,q_4|2), \end{aligned} \tag{75}\] with solution \[\begin{aligned} P(x,q_4|2)=\frac{x(x-q_4 x +P(x,q_4,1)(q_4+x-q_4 x))}{1-(1-q_4)x}. \label{FE2} \end{aligned} \tag{76}\]
We substitute Eqs. (74) and (76) into (73) to obtain
\[\begin{aligned} P(x,q_4,z)=a(z)+ b(z)P(x, q_4, q_4 z) , \label{MR} \end{aligned} \tag{77}\] where \[\begin{aligned} a(z)&=\frac{P(x,q_4,1) x z \left(q_4^2 x z (z+1)-q_4 \left(x (z+1)^2+1\right)+x (z+1)\right)}{q_4 (q_4 z-1)}\notag\\ &\quad+\frac{x z \left(q_4^2 x z (z+1)+q_4^2 z-q_4 \left(x (z+1)^2+1\right)+x (z+1)\right)}{q_4 (q_4 z-1)}, \label{a(z)} \end{aligned} \tag{78}\] and \[\begin{aligned} b(z)=\frac{(1+z-q_4(1+z+z^2))x}{q_4^2(1-q_4 z)}. \label{b(z)} \end{aligned} \tag{79}\]
Adapting Eq. (7), we see that Eq. (77) has solution
\[\begin{aligned} P(x,q_4,z)=\sum\limits_{i \ge 0}a(q_4^i z)\prod_{j=0}^{i-1} b(q_4^j z). \label{Pgsol} \end{aligned} \tag{80}\]
By putting \(z=1\) into Eq. (80), applying Eqs. (78) and (79) and then solving for \(P(x,q_4,1)\), we obtain
\[\begin{aligned} P(x,q_4,1)&=P(x,q_4,1)\sum\limits_{i \ge 0} \frac{x \left(2q_4^2 x -q_4 \left(4x +1\right)+2x \right)}{q_4 (q_4 -1)} \prod_{j=0}^{i-1} b(q_4^j)\notag\\ &\quad+\sum\limits_{i \ge 0}\frac{x \left(2q_4^2 x +q_4^2 -q_4 \left(4x +1\right)+2 x \right)}{q_4 (q_4-1)} \prod_{j=0}^{i-1} b(q_4^j) , \end{aligned} \tag{81}\] where \[\begin{aligned} \prod_{j=0}^{i-1} b(q_4^j)=\prod_{j=0}^{i-1} \frac{x(1+q_4^j-q_4(1+q_4^j+q_4^{2j}))}{q_4^2(1-q_4^{j+1})}. \end{aligned} \tag{82}\]
We have now proved the following theorem:
Theorem 6.1. The generating function \(P(x,q_4,1)\) for the number of grid graphs with invariants \(x\) and \(q_4\) respectively tracking number of parts and number of degree 4 vertices is
\[\begin{aligned} P(x,q_4,1)=\frac{\sum\limits_{i \ge 0}\frac{x \left(2q_4^2 x +q_4^2 -q_4 \left(4x +1\right)+2x \right)}{q_4 (q_4 -1)} \prod_{j=0}^{i-1} b(q_4^j) }{1-\sum\limits_{i \ge 0} \frac{x \left(2q_4^2 x -q_4 \left(4x +1\right)+2x \right)}{q_4 (q_4 -1)} \prod_{j=0}^{i-1} b(q_4^j)}, \end{aligned} \tag{83}\] where \[\begin{aligned} b(q_4^j)= \frac{x(1+q_4^j-q_4(1+q_4^j+q_4^{2j}))}{q_4^2(1-q_4^{j+1})}. \end{aligned} \tag{84}\]
The series expansion for this begins \[\begin{aligned} P(x,q_4,1)&=x+2 x^2+5 x^3+(11+3 q_4) x^4+\left(24+11 q_4+{\bf{4 q_4^2}}+{\bf{3 q_4^3}}\right) x^5\notag\\ &\quad+\left(53+32 q_4+19 q_4^2+13 q_4^3+8 q_4^4+4 q_4^5+3 q_4^6\right) x^6. \end{aligned} \tag{85}\]
Remark 6.2. We illustrate the bold terms above. \({\bf{4 q_4^2}}\) is represented by \[12332,12333,12334,12342,\] each of which have two degree 4 vertices; and \({\bf{ 3q_4^3}}\) is represented by \[12343,12344,12345,\] each of which have three degree 4 vertices.
In [4], it is shown that the total area of bargraphs of Catalan words is given by \[\begin{aligned} \frac{1}{2}\left(4^n-\binom{2n}{n}\right) , \end{aligned} \tag{86}\] and this is also the total number of vertices in grid graphs.
For each \(n\), as already stated earlier we call the number of degree 1 to degree 4 vertices \(r(1), r(2), r(3), r(4)\) respectively. The first three are obtained from Eqs. (33), (50) and (66).
We have not yet calculated \(r(4)\). We do this by subtraction of the other degrees from the total number of vertices to obtain \[\begin{aligned} r(4)\sim \frac{4^n}{2}- \frac{26}{2}\frac{4^{n-1}}{\sqrt {\pi n}}. \end{aligned} \tag{87}\]
To obtain the asymptotic proportions of different degree vertices, we divide the previous numbers by the total number of vertices and obtain the the proportions of degree 1 to degree 4 vertices as
\[\left\{\frac{1}{4 \sqrt{\pi } \sqrt{n}},\frac{1}{\sqrt{\pi } \sqrt{n}},\frac{13}{4 \sqrt{\pi } \sqrt{n}},1-\frac{9}{2 \sqrt{\pi } \sqrt{n}}\right\}. \label{asymp degree proportion} \tag{88}\]
Thus degree 4 vertices dominate for large \(n\) but degree 1, 2 and 3 vertices occur asymptotically in the ratios \({1,4,13}\) to each other. We contrast this to our study of grid graphs of compositions, see [1], where each of the vertices occur as a positive proportion of the total number of vertices. Numerically these proportions were \(\{0.119, 0.464, 0.381, 0.035\}\) which interestingly are very different from the Catalan word case.