Reservoirs in words over the alphabet \([k]\)

Aubrey Blecher1, Arnold Knopfmacher1
1The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics University of the Witwatersrand, Private Bag 3, Wits 2050, Johannesburg, South Africa

Abstract

We represent words \(w_1 w_2\dots w_ n\) over the alphabet \([k]\) as bargraphs where the \(j\)th column of the bargraph is of height \(w_j\). The capacity of a word is the amount of water the bargraph would retain under the usual laws of physics when the water is allowed to escape left or right. A reservoir is a single body of water after all water has been allowed to escape under the same physical laws. For all words with \(n\) parts, generating functions are found which track the number of reservoirs, their total width, relationship to capacity and depth where the latter is defined as largest capacity of each single letter in the reservoir.

Keywords: Catalan words, Dyck paths, generating functions, asymptotics

1. Introduction

Given an arbitrary word made up of letters from the alphabet \([k]=\{1,2,\cdots,k\}\), we define its capacity as the amount of water the word would retain if it was considered as a full container with the water allowed to escape left and right, subject to the usual rules of physics.

We further define the capacity of any given letter (or part) in the word as the amount of water retained above that letter after the water has been allowed to escape left and right. In the current paper, we consider the separate reservoirs in words rather than the general notion of the full capacity of the word. Roughly speaking, a reservoir is a single connected body of water. Formally, a reservoir in a word is a subword \(a_1,a_2,\cdots,a_i\) of the original word where \({\text{capacity}}(a_1)={\text{capacity}}(a_i)=0\) and for \(2 \le r \le i-1\), \({\text{capacity}}(a_r) > 0\). In addition, if \(a_1=a_i=k\), then this is called a central reservoir. This notion of a reservoir was originally defined in an equivalent way in [8] and is illustrated in the Figure 1 below. The notion is general enough to include reservoirs in word structures such as compositions, Dyck and Motzkin paths, permutations, set partitions (in the form of restricted growth functions) and Catalan words. These cases are dealt with in further articles.

Fig. 1. The water capacity of two words (brown colour) of length 8 over the alphabet [5]. Each has two reservoirs (with capacity in blue colour)

The main technique used in this paper is a sequence decomposition of all possible words with any number of parts over the alphabet \([k]\). We design the sequence decomposition in such a way as to enable the tracking of the number of reservoirs and their widths in the resulting generating function. It is perhaps worth noting that the sequence construction method is analagous to the (Temperley) method of adding a slice as discussed in [4]. In the Temperley method, only one part at a time is added to a pre-existing combinatorial structure in which the initial (or end) part is known. In the sequence construction method, the pre-existing structure has an initial and last part of size \(k\), say, and what is added both before and after this structure are any number of parts with only the size of the initial or end part fixed at \(k-1\). This analogy between the two methods is intriguing to the authors and is demonstrated in this paper. The sequence construction is applied to capacity which is a global concept (i.e., its definition involves the word as a whole) as opposed to the Temperley method which is local in conception in the sense that it is based on a part-by-part methodology. The nature of the problem studied influences which method is appropriate.

For further research on capacity in the bargraphs of combinatorial structures, see [1, 2, 3, 6, 7]. In particular there is a very nice treatment of bargraphs of words over a finite alphabet to be found in the recent book [5].

2. The generating function for the total number of reservoirs and the total width of these reservoirs

We use a sequence construction to obtain this generating function and we use the following notation to represent the sequence.

Here, \(k^*\) or \(k^+\) reflect a maximal sequence of adjacent \(k\)s possibly empty in the first case and non-empty in the second. \(w_{[k]}\) represents all non-empty words on the alphabet \([k]\) with generating function \(\frac{ky}{1-ky}\). We assume first that our word over the alphabet \(k\) has at least one part \(k\). We call the sequence for the subword starting at the leftmost \(k\) and ending at the rightmost \(k\), the central sequence. This may be represented as

\[\begin{aligned} k^+\left((w_{[k-1]}k^+)^+ +\epsilon\right). \end{aligned}\tag{1}\]

The subword to the right of the central sequence has at least one or no occurrences of \(k-1\). If there is such an occurrence, we focus on the last of these. This can be represented as the last of of a non-empty maximal sequence of adjacent such \(k-1\)s with sequence representation \((k-1)^+\). To its left, a maximal word on the alphabet \([k-2]\), namely, \(w_{[k-2]}\) or nothing. Including the last \(k-1\) grouping or the case of no \(k-1\)s, this part of the sequence has representation

\[\begin{aligned} (k-1)^*\left(w_{[k-2]}(k-1)^+\right)^+ + (k-1)^+ +\epsilon. \end{aligned}\tag{2}\]

Similarly for the subword (in reverse order) to the left of the central sequence.

We continue in this way, both to the right and left, next considering the occurrences of \(k-2\), then \(k-3\) and so on. Finally, we are down only to \(1\)s both on the right and left. The sequence for these is \((1^*)^2\), with generating function \((\frac{1}{1-y})^2.\)

For the above Equations, we mark the number of reservoirs with invariant \(q\) and the width of each reservoir with invariant \(w\). The generating function for decomposition (1) is

\[\begin{aligned} &\frac{y}{1-y}\left(\frac{\frac{(k-1)yw}{1-(k-1)yw}\frac{yq}{1-y}}{1-\frac{(k-1)yw}{1-(k-1)yw}\frac{yq}{1-y}}+1\right)=\frac{y(1-(k-1)yw)}{1-y-(k-1)yw-(k-1)(q-1)y^2 w}. \end{aligned}\tag{3}\]

The generating function for Eq. (2) is

\[\begin{aligned} &\left(\frac{1}{1-y}\right)\left(\frac{\frac{(k-2)yw}{1-(k-2)yw}\frac{yq}{1-y}}{1-\frac{(k-2)yw}{1-(k-2)yw}\frac{yq}{1-y}}+1\right)=\left(\frac{1-(k-2)yw}{1-y-(k-2)yw-(k-2)(q-1)y^2 w}\right). \end{aligned}\tag{4}\]

By putting the full sequence together and allowing the non-central reservoir to occur on either side of the central reservoir (hence the exponent \(2\)), we obtain the generating function \(F_k(y,w,q)\) as

\[\begin{aligned} &F_k(y,w,q):=\\ &\frac{y(1-(k-1)yw)}{1-y-(k-1)yw-(k-1)(q-1)y^2 w}\frac{1}{(1-y)^2}\prod_{i=1}^{k-2} \left(\frac{1-iyw}{1-y-iyw-i(q-1)y^2 w}\right)^2. \end{aligned}\tag{5}\]

Thus we have proved the following theorem.

Theorem 2.1. The generating function for all words according to number of reservoirs tracked by \(q\) and total width of these reservoirs tracked by \(w\) is given by

\[\begin{aligned} F(k;y,w,q):=\frac{1}{1-y}+\sum\limits_{r=2}^k F_r(y,w,q). \end{aligned}\tag{6}\]

We check that

\[F(k;y,1,1)=\frac{1}{1-ky},\]

which is the generating function for all words over the alphabet \([k]\) as expected.

The series expansion of \(F(3;y,w,q)\) is

\[\begin{aligned} &1+3 y+9 y^2+(22+5 q w) y^3+\left(46+28 q w+\mathbf{7 q w^2}\right) y^4\\ &~+\left(86+94 q w+40 q w^2+12 q^2 w^2+11 q w^3\right) y^5+O\left(y^6\right). \end{aligned}\tag{7}\]

Example 2.2. The term in bold is given by the words

\[3113,3123,3213,3223,2113,3112,2112.\]

By differentiating Eq. (6) with respect to \(q\) , we obtain the following corollary.

Corollary 2.3. The generating function \(DF_q(k;y,1,1):=\frac{\partial F(k;y,1,q)}{\partial q}\Big{|}_{q=1}\) for the total number of reservoirs in all words over the alphabet \([k]\) is given by

\[\begin{aligned} DF_q(k;y,1,1)=y^3 \sum\limits_{r=2}^k \frac{1}{(1-r y) (1-(r-1) y)}\left(\frac{r-1}{1-r y}+\sum\limits_{j=1}^{r-2} \frac{2 j}{1-(j+1) y}\right). \end{aligned}\tag{8}\]

By using Eq. (8), changing the order of the double sum and simplifying, we obtain

\[\begin{aligned} DF_q(k;y,1,1)=&y^3 \sum\limits_{r=2}^k \frac{r-1}{(1-r y) (1-(r-1) y) (1-r y)}\\ &+y^3 \sum\limits_{r=2}^k \frac{(2 r)}{1-(r+1) y} \left(\frac{r+1}{-1+(r+1) y}-\frac{k}{-1+k y}\right)\\ &~-\frac{2 (-2+k) y^3}{(1-2 y)^2 (-1+k y)}-\frac{2 k y^3}{(-1+k y) (-1+y+k y)^2}. \end{aligned}\tag{9}\]

Now, combining the \(r\) sums and using partial fractions, we simplify this to separate terms suitable for coefficient extractions,

\[\begin{aligned} DF_q(k;y,1,1)=&-\frac{1-3 k^2+6 k^3}{(-1+k)^2 k^2 (1+k)^2}+\frac{-1+k}{k^2 (-1+k y)^2}+\frac{-2+k+3 k^2}{k^2 (-1+k y)}\\ &~-\frac{1}{-1-2 y+k y}+\frac{-2+k}{(-1+k)^2 (-1-y+k y)^2}+\frac{-3+k}{(-1+k)^2 (-1-y+k y)}\\ &~-\frac{2 k}{(1+k)^2 (-1+y+k y)^2}-\frac{2 \left(3 k+k^2\right)}{(1+k)^2 (-1+y+k y)}-\frac{-2+k+k^3}{2 k (1+k)^2}\\ &~-\frac{1}{2 (-1+2 y)^2}+\frac{3-k}{(-2+k) (-1+2 y)}-\frac{2 \left(1-2 k+k^2\right)}{(-2+k) k (-1+k y)}\\ &~+\frac{2 k}{(1+k)^2 (-1+y+k y)^2}+\frac{2 \left(3 k+k^2\right)}{(1+k)^2 (-1+y+k y)}\\ &~+y^3 \left(-\frac{1}{-1+y}+\frac{(k-2)^3}{-1+(k-2) y}-\frac{4 k}{(k-2) (-1+2 y)}\right.\\ &~\left.+\frac{2 k (k-1) (k-2)}{-1+(k-1) y}+\frac{4}{(-1+2 y)^2}-\frac{2 (k-1) (k-2)}{(-1+(k-1) y)^2}\right)+\\ &~+y^3 \left(\sum\limits_{r=2}^{k-2} -\frac{2 k^2 r}{(-1+k-r) (-1+k y)}-\sum\limits_{r=2}^{k-2} \frac{r (r-1)}{(-1+r y)^2}\right.\\ &~\left.+\sum _{r=2}^{k-2} \frac{r-2 r^2}{-1+r y}+\sum\limits_{r=2}^{k-2} \frac{2 k r (r-1)}{(k-r) (-1+r y)}\right). \end{aligned}\tag{10}\]

We now extract the coefficients from all but the summed terms of Eq. (10) and we obtain

\[\begin{aligned} g_0(k,n):=&1+(k-1)^{-2+n} \left(-9+9 k-2 k^2\right)+\frac{k^{-2+n} \left(-4+6 k+k^2-k^3\right)}{k-2}\\ &~-(-2+k) (k-1)^{-2+n} (1+n)+(k-1) k^{-2+n} (1+n). \end{aligned}\tag{11}\]

Next, extracting the coefficients of the last part (i.e., the summed term) of Eq. (10), we obtain

\[\begin{aligned} & f_0(k,n):=\sum\limits_{r=2}^{k-2} \left(\frac{2 k^{-1+n} r}{k-r-1}-(1+n) (-1+r) r^{-2+n}+\frac{r^{-2+n} ((4-5 r) r+k (-2+3 r))}{k-r}\right). \end{aligned}\tag{12}\]

By summing these coefficients we obtain the following corollary.

Corollary 2.4. The total number of reservoirs in all words of length \(n\) over the alphabet \([k]\) is given by

\[\begin{aligned} g_0(k,n)+f_0(k,n). \end{aligned}\tag{13}\]

In particular the average number of reservoirs in all words of length \(n\) over the alphabet \([k]\) is asymptotic to

\[{(k-1)}k^{-2}n.\]

Again, by differentiating Eq. (6), this time with respect to \(w\) , we obtain

Corollary 2.5. The generating function \(DF_w(k;y,1,1):=\frac{\partial F(k;y,1,q)}{\partial w}\Big{|}_{w=1}\) for the total number of reservoirs in all words over the alphabet \([k]\) is given by

\[\begin{aligned} DF_w(k;y,1,1)=&\sum\limits_{r=2}^k \frac{y}{(1-r y) (1-(r-1) y)}\left(\frac{(r-1) y^2}{(1-r y) (1-(r-1) y)}\right.\\ &~\left.+\sum\limits_{j=1}^{r-2} \frac{2 j y^2}{(1-j y) (1-(j+1) y)}\right). \end{aligned}\tag{14}\]

By using Eq. (14), changing the order of the double sum and simplifying, we obtain

\[\begin{aligned} DF_w(k;y,1,1)=&\sum\limits_{r=2}^k \frac{y}{(1-r y) (1-(r-1) y)}\left(\frac{(r-1) y^2}{(1-r y) (1-(r-1) y)}\right.\\ &~\left.-\frac{2}{1-y}+\frac{2}{1-(r-1) y}\right)-\sum _{r=2}^{k} \frac{2 y^2}{1-r y}\left(\frac{r}{-1+r y}-\frac{k}{-1+k y}\right). \end{aligned}\tag{15}\]

Now, using partial fractions, we simplify this to

\[\begin{aligned} DF_w(k;y,1,1)= &-\frac{1}{(-1+y)^2}+\frac{1}{(-1+k y)^2}+\frac{y \left(2-7 y-(-7+k) y^2+(-4+3 k) y^3\right)}{(1-2 y)^2 (-1+y)^2 (-1+k y)}\\ &~+\frac{y \left(-2+(-1+2 k) y+y^2\right)}{(-1+y) (-1+(-1+k) y) (-1+k y)^2}\\ &~+\sum _{r=3}^{k-1} \left(\frac{2}{(-2+r) (-1+r) (-1+y)}+\frac{2}{(k-r) (-1+k y)}\right.\\ &~\left.-\frac{r}{(-2+r) (-1+(-1+r) y)}+\frac{1}{r (-1+r y)^2}\right.\\ &~\left.+\frac{k-3 r-2 k r+4 r^2-k r^2+r^3}{(-1+r) r (-k+r) (-1+r y)}\right). \end{aligned}\tag{16}\]

Extracting the coefficients from the first four terms of Eq. (16), we obtain

\[\begin{aligned} g_1(k,n):=&1+\frac{2^{-1+n} (18-7 k)}{-2+k}+\frac{(-3+k) k}{(-2+k) (-1+k)}+\frac{(-1+k)^n k}{-2+k}+\\ &+\frac{k^{-1+n} \left(2+k-k^3\right)}{(-2+k) (-1+k)}+n+2^{-1+n} (1+n)+(-1+k) k^{-1+n} (1+n). \end{aligned}\tag{17}\]

Again, extracting the coefficients of the last part (i.e., the summed term) of Eq. (16), we obtain

\[\begin{aligned} f_1(k,n):=&\sum\limits_{r=3}^{k-1} \left(-\frac{2 k^n}{k-r}+\frac{(-1+r)^n r}{-2+r}+(1+n) r^{-1+n}-\frac{2}{2-3 r+r^2}\right.\\ &~\left.+\frac{r^{-1+n} \left(-k \left(-1+2 r+r^2\right)+r \left(-3+4 r+r^2\right)\right)}{(k-r) (-1+r)}\right). \end{aligned}\tag{18}\]

By summing these coefficients we obtain the following corollary.

Corollary 2.6. The total width of reservoirs in all words of length \(n\) over the alphabet \([k]\) is given by

\[\begin{aligned} g_1(k,n)+f_1(k,n). \end{aligned}\tag{19}\]

In particular the average width of reservoirs in all words of length \(n\) over the alphabet \([k]\) is asymptotic to

\[\frac{k-1}{k}n.\]

3. The number of reservoirs of depth 1

A reservoir is of depth \(r\) iff it has at least one part of capacity \(r\) and all other interior parts are of capacity \(\le r\). For example, reading from left to right in Figure 1, the reservoirs are of depth \(1,2,1,3\). The rest of this section deals with reservoirs of depth \(1\). The generating function we wish to obtain tracks the number of reservoirs of depth \(1\) with invariant \(q\).

Lets fix \(m\) as the distance between any \(k\) and the next \(k\). Between these \(k\)’s there is any word on the alphabet \([k-1]\), with \(m\) parts. So lets consider a sequence construction for this word including the initial and last \(k\). This can be represented by the sequence

\[\begin{aligned} k w_{[k-1],m} k-k (1^{‘}) k+k(1^{‘}) k, \end{aligned}\tag{20}\]

where \(w_{[k-1],m}\) represents a word over the alphabet \([k-1]\) having m letters and where \(1^{‘}\) represents the letter \(k-1\) repeated \(m\) times. We track reservoirs of depth 1 by invariant \(q\). This latter has generating function

\[\begin{aligned} y^2 (k-1)^m y^m -y^2 y^m +y^2 y^m q. \end{aligned}\tag{21}\]

By summing over \(m\) for \(1\le m \le \infty\), we obtain the generating function for a single reservoir of any width as

\[\begin{aligned} y^2\left(\frac{(k-1)y}{1-(k-1)y}-\frac{y}{1-y} + \frac{yq}{1-y}\right). \end{aligned}\tag{22}\]

A sequence of such reservoirs separated by an arbitrary number of non-isolated \(k\)s and having any number of non isolated \(k\)s at the beginning an end of the sequence has generating function

\[\begin{aligned} \frac{y}{1-y}\frac{\left(\frac{(k-1)y}{1-(k-1)y}-\frac{y}{1-y} + \frac{yq}{1-y}\right)\frac{y}{1-y}}{1-\left(\frac{(k-1)y}{1-(k-1)y}-\frac{y}{1-y} + \frac{yq}{1-y}\right)\frac{y}{1-y}}+\frac{y}{1-y}, \end{aligned}\tag{23}\]

where the last term covers the case of one or more \(k\)s with no reservoirs. Next, we consider reservoirs on the right of the central reservoirs. By extending the reasoning we used for the central reservoirs, assuming that there is at least one such \(k-1\), we count this as being the rightmost such and obtain the generating function for this part of the sequence as

\[\begin{aligned} \frac{1}{1-y}\frac{\left(\frac{(k-2)y}{1-(k-2)y}-\frac{y}{1-y} + \frac{yq}{1-y}\right)\frac{y}{1-y}}{1-\left(\frac{(k-2)y}{1-(k-2)y}-\frac{y}{1-y} + \frac{yq}{1-y}\right)\frac{y}{1-y}}+\frac{1}{1-y}, \end{aligned}\tag{24}\]

where the last term covers the case of no reservoirs as well as no occurrences of \(k-1\). If there is no such \(k-1\) on the left the empty case yields 1. So, combining cases on the left (or the right), with the previous case of one or more occurrences of \(k\), we get the generating function for the combined subword as

\[\begin{aligned} \left(1-y\right)^2&\left(\frac{ (1-(k-2) y)}{1+2 y^3-q y^2 (1+2 y)-k y \left(1-y+(1-q) y^2\right)}\right)^2\\ &~\times\frac{(1-y) y (1-(k-1) y)}{1-(1+k) y+(1+k-q) y^2+(k-1) (q-1) y^3}. \end{aligned}\tag{25}\]

Iterating this process for \(k-2, k-3, …, 1\) if there is at least one occurrence of \(k \ge 2\) in our word, we get the capacity and reservoir generating function to be

\[\begin{aligned} C_{k}(y,q):=&\frac{(1-y)^{2k-5} y (1-(k-1) y)}{1-(1+k) y+(1+k-q) y^2+(k-1) (q-1) y^3}\\ &~\times\prod_{i=1}^{k-2} \left(\frac{ (1-i y)}{1-(2+i) y+(2+i-q) y^2 -i(1-q)y^3} \right)^2 \end{aligned}\tag{26}\]

And for \(2 \le r < k\) where there are no occurrences of \(j > r\) but at least one occurrence of \(r\), we get

\[\begin{aligned} C_{r}(y,q):=&\frac{(1-y)^{2r-5} y (1-(r-1) y)}{1-(1+r) y+(1+r-q) y^2+(r-1) (q-1) y^3}\\ &~\times\prod_{i=1}^{r-2} \left(\frac{ (1-i y)}{1-(2+i) y+(2+i-q) y^2 -i(1-q)y^3} \right)^2. \end{aligned}\tag{27}\]

Also,

\[\begin{aligned} C_1(y,q)=\frac{1}{1-y}. \end{aligned}\tag{28}\]

We define \(C(k; y,q):=\sum\limits_{r=1}^k C_r(y,q).\) Thus we have the following theorem

Theorem 3.1. The reservoir generating function \(C(k; y,q)\) for all words on \(k\) letters where \(y\) marks the length, and \(q\) the number of reservoirs of depth \(1\) is given by

\[\begin{aligned} C(k; y,q)=&\frac{1}{1-y}+\sum\limits_{r=2}^k \frac{(1-y)^{2r-5} y (1-(r-1) y)}{1-(1+r) y+(1+r-q) y^2+(r-1) (q-1) y^3}\\ &~\times\prod_{i=1}^{r-2} \left(\frac{ (1-i y)}{1-(2+i) y+(2+i-q) y^2 -i(1-q)y^3} \right)^2. \end{aligned}\tag{29}\]

Example 3.2. From this theorem, we obtain the series expansion for \(C(k; y,q)\) in the case of \(k=3\). This is given by

\[\begin{aligned} C(3; y,q)=& 1+3 y+9 y^2+(23+4 q) y^3+(55+26 q) y^4+\left(133+103 q+\mathbf{7 q^2}\right) y^5\\ &~+\left(337+331 q+61 q^2\right) y^6+O\left(y^7\right). \end{aligned}\tag{30}\]

We illustrate the seven words constituting the term in bold. These are

\[\{32323,21323,32312,21212,31212,21213,21312\}.\]

4. The number of reservoirs of depth \(r\)

We use a conceptually different decomposition in this section from that of the last. To reiterate, a reservoir is of depth \(r\) iff it has at least one part of depth \(r\) and all other interior parts are of depth \(\le r\). The generating function we wish to obtain tracks the number of reservoirs of depth \(r\) with invariant \(q\).

As in the previous section, we fix \(m\) as the distance between any \(k\) and the next \(k\). Fix \(r\) such that \(1\le r \le k-1\). Between these \(k\)’s there is any word on the alphabet \([k-1]\), with \(m\) parts. We split these as per the following decomposition where we use the same notation as in Eq. (22), i.e., \(w_{[k-r],m}\) represents a word over the alphabet \([k-r]\) having m letters. However, we are conceiving these latter words as being upside-down words with their bases at height \(y=k\). See Figure 2 below. So in the following decomposition, parameter \(r\) actually measures the depth of each reservoir.

\[\begin{aligned} k \left(w_{[k-1],m} – w_{[r],m} + w_{[r],m} – w_{[r-1],m} \right) k. \end{aligned}\tag{31}\]
Fig. 2. A word of length \(m+2\) over the alphabet \([k]\) and bounded on both sides by \(k\). There is one reservoir of depth \(r\)

In this section, we track the number of reservoirs of depth \(r\) by invariant \(q\). So, this last decomposition has generating function

\[\begin{aligned} y^2\left((k-1)^m y^m-(r^m-(r-1)^m) y^m+q(r^m-(r-1)^m)y^m\right) . \end{aligned}\tag{32}\]

By summing over \(m\) for \(1\le m \le \infty\), we obtain the generating function for a single reservoir of any width as

\[\begin{aligned} &g_{r,k}(y,q):=\\ &\frac{k y-2 y+q y-2 y^2+2 k y^2+q y^2-k q y^2+2 r y^2-2 k r y^2+r y^3-k r y^3-r^2 y^3+k r^2 y^3}{(1+y-k y) (1-r y) (1+y-r y)}. \end{aligned}\tag{33}\]

A sequence of such reservoirs separated by an arbitrary number of non-isolated \(k\)s and having any number of non isolated \(k\)s at the beginning an end of the sequence has generating function

\[\begin{aligned} \frac{y}{1-y}\left(\frac{g_{r,k}(y,q)\frac{y}{1-y}}{1-g_{r,k}(y,q)\frac{y}{1-y}}+1\right)=\frac{y}{1-y}\left(\frac{1}{1-g_{r,k}(y,q)\frac{y}{1-y}}\right), \end{aligned}\tag{34}\]

where the last term covers the case of one or more \(k\)s with no reservoirs. Next, we consider reservoirs on the right of the central reservoirs. We use the same reasoning as we used for the central reservoirs and assume that there is at least one such \(k-1\) which we count as being the rightmost such. The generating function for this part of the sequence is

\[\begin{aligned} \frac{1}{1-y}\left(\frac{1}{1-g_{r,k-1}(y,q)\frac{y}{1-y}}\right), \end{aligned}\tag{35}\]

where the last term covers the case of no reservoirs as well as no occurrences of \(k-1\). If there is no such \(k-1\) on the left the empty case yields 1. So, combining cases on the left (or the right), with the previous case of one or more occurrences of \(k\), we get the generating function for the combined subword as

\[\begin{aligned} \frac{y}{1-y}\left(\frac{1}{1-g_{r,k}(y,q)\frac{y}{1-y}}\right) \left(\frac{1}{1-y}\frac{1}{1-g_{r,k-1}(y,q)\frac{y}{1-y}}\right)^2. \end{aligned}\tag{36}\]

We set \(r \le k-1\). Now we iterate this process for \(k-2, k-3, …, r+1\). If there is at least one occurrence of \(k \ge 2\) in our word, we get the capacity and reservoir generating function to be

\[\begin{aligned} C_{k,r}(y,q):=&\frac{y}{1-y}\left(\frac{1}{1-g_{r,k}(y,q)\frac{y}{1-y}}\right)\times\prod_{i=r+1}^{k-1} \left(\frac{1}{1-y}\frac{1}{1-g_{r,i}(y,q)\frac{y}{1-y}}\right)^2 \left(\frac{1}{1-ry}\right)^2, \end{aligned}\tag{37}\]

where the last bracket above accounts for all cases \(1 \le i\le r\). The above equation requires that the term \(g_{r,i}(y,q)\) is meaningful which requires that \(r < i\). If \(r\ge i\), all cases are accounted for collectively by

\[\begin{aligned} \sum\limits_{i=1}^r C_{i,r}(y,q)=\frac{1}{1-ry}. \end{aligned}\tag{38}\]

For any fixed alphabet \([k]\), we define \(C_r(k; y,q):=\sum\limits_{i=1}^k C_{i,r}(y,q)\). This yields

\[\begin{aligned} C_r(k; y,q)=&\sum\limits_{i=1}^r C_{i,r}(y,q)+\sum\limits_{i=r+1}^k \frac{y}{1-y}\left(\frac{1}{1-g_{r,k}(y,q)\frac{y}{1-y}}\right)\times\\ &~\times\prod_{i=r+1}^{k-1} \left(\frac{1}{1-y}\frac{1}{1-g_{r,i}(y,q)\frac{y}{1-y}}\right)^2 \left(\frac{1}{1-ry}\right)^2. \end{aligned}\tag{39}\]

Applying Eqs. (38) and (37) respectively to the successive terms of the previous equation, we have the following theorem.

Theorem 4.1. The reservoir generating function \(C_r(k; y,q)\) for all words on \(k\) letters where \(y\) marks the length, and \(q\) the number of reservoirs of depth \(r\) is given by

\[\begin{aligned} C_r(k; y,q)=&\frac{1}{1-ry}+~\sum\limits_{i=r+1}^k \frac{y}{1-y}\left(\frac{1}{1-g_{r,k}(y,q)\frac{y}{1-y}}\right)\times\\ &~\times\prod_{i=r+1}^{k-1} \left(\frac{1}{1-y}\frac{1}{1-g_{r,i}(y,q)\frac{y}{1-y}}\right)^2 \left(\frac{1}{1-ry}\right)^2, \end{aligned}\tag{40}\]

where \(g_{r,k}\) is defined in Eq. (33).

Example 4.2. From this theorem, we obtain the series expansion for \(C_3(k; y,q)\) in the case of \(k=5\). This is given by

\[\begin{aligned} &C_3(5; y,q)=1+5 y+25 y^2+(4 q+121) y^3+(58 q+567) y^4+\left(7 q^2+523 q+2595\right) y^5\\ &~~~+\left(145 q^2+3767 q+11713\right) y^6+\left(\mathbf{11 q^3}+1750 q^2+23779 q+52585\right) y^7+O\left(y^8\right). \end{aligned}\tag{41}\]

We illustrate the eleven words constituting the term in bold. These all have three reservoirs each of depth \(3\). They are

\[\begin{aligned} &4141414,4141415,4141514,4141525,4151414,4152514,4152525,\\ &5141414,5251414,5252514,5252525. \end{aligned}\]

5. The capacity of the central reservoirs

Recall that \(k\) is the size of the alphabet and \(n\) is the length of a word. At the end of this section, we show that asymptotically as \(n \to \infty\), the capacity of the central reservoirs is equal to the total capacity of the word.

As per the introduction, the central reservoirs are those bounded by the leftmost and righmost letter \(k\). If there is only one \(k\) or if the two \(k\)’s are adjacent, or if there are no \(k\)s, we say that the central reservoir has capacity \(0\).

First we consider the case where there are at least two maxima, \(k\) in the word. Every letter between these two is of height \(\le k\), and all others are of height \(<k\).

We know that words on the alphabet \([k]\) have generating function

\[\sum\limits_{m\ge 0}y^m\left(\sum\limits_{a=1}^k x^a\right)^m = \frac{1}{1-y\sum\limits_{a=1}^k x^a},\]

where \(y\) tracks the length of the word and \(x\) tracks the area of the word.

For the words illustrated in Figure 1, the generating function for the capacity is therefore given by the exponent of \(x\) in

\[y^2 \sum\limits_{m\ge 0}\left(\sum\limits_{a=1}^k x^{k-a}\right)^m y^m,\]

where \(y\) marks the number of letters in the subword and now \(x\) marks the capacity.

Thus

\[y^2 \sum\limits_{m\ge 0}\left(\sum\limits_{a=1}^k x^{k-a}\right)^m y^m =\frac{y^2}{1-\sum\limits_{a=1}^k x^{k-a} y}= \frac{(1-x)y^2}{1-x-y+x^{k} y}.\]

For the case where there is only one occurrence of \(k\) in the word, the central capacity generating function is \(y\). To the left of the leftmost \(k\) is a possibly empty arbitrary word over the alphabet \([k-1]\) with generating function \(\frac{1}{1-(k-1)y}\) and similarly to the right of the rightmost \(k\). The full generating function for the central capacity is

\[F_{c}(x,y):=\left(\frac{1}{1-(k-1)y}\right)^2 \left(\frac{(1-x)y^2}{1-x-y+x^{k} y}+y\right).\]

Therefore the generating function for the total central capacity is

\[\begin{aligned} \frac{\partial}{\partial x}F_{c}(x,y)\Big|_{x=1}= \frac{k(k-1)y^3}{2(1-(k-1)y)^2(1-ky)^2}. \end{aligned}\tag{42}\]
\[\begin{aligned} [y^n]\frac{\partial}{\partial x}F_{c}(x,y)\Big|_{x=1} &~=\frac{1}{2} n \left(k^{n+1}-k^n+k(k-1)^n\right) + k \left((k-1)^n-k^n\right) (k-1). \end{aligned}\tag{43}\]

Hence the average central capacity is

\[\frac{1}{2} n \left(k-1+k\left(1-\frac{1}{k}\right)^n\right) + k \left(\left(1-\frac{1}{k}\right)^n-1\right) (k-1)\sim\frac{1}{2} n \left(k-1\right) – k (k-1),\]

as \(n \to \infty.\) We compare this with the total capacity of a word of length \(n\) in [1] which is asymptotic to

\[\frac{k-1}{2}n-4k(H_{k}-1),\]

where \(H_k\) is the \(k\)th harmonic number. Therefore, we have proved the following proposition.

Proposition 5.1. As \(n \to \infty\), the average value of the capacity of the central reservoirs of a word of length \(n\) over any alphabet \(k\) is asymptotically the same as the full capacity of that word.

Author Contributions

Both authors contributed equally to this work and approved the final version of the manuscript.

Conflicts of Interest

The authors declare no conflicts of interest.

Data Availability

All data supporting the findings of this study are included in the manuscript.

Funding Information

This research received no funding.

References:

  1. A. Blecher, C. Brennan, and A. Knopfmacher. Capacity of words. Journal of Combinatorial Mathematics and Combinatorial Computing, 107:249–258, 2018.
  2. A. Blecher, C. Brennan, and A. Knopfmacher. The water capacity of integer compositions. Online Journal of Analytic Combinatorics, (13):1–14, 2018. https://doi.org/10.61091/ojac-1306. Paper 6.
  3. A. Blecher, C. Brennan, A. Knopfmacher, and M. Shattuck. Capacity of permutations. Annales Mathematicae et Informaticae, 50:39–56, 2019. https://doi.org/10.33039/ami.2019.03.004.
  4. M. Bousquet-Mélou and R. Brak. Exactly solved models. In A. J. Guttmann, editor, Polygons, Polyominoes and Polycubes. Volume 775, Lecture Notes in Physics, chapter 3, pages 43–78. Springer, Dordrecht, 2009. https://doi.org/10.1007/978-1-4020-9927-4_3.
  5. T. Mansour and A. S. Shabani. Combinatorics of Bargraphs. Research Monographs. Press STEM, Prishtina, 2026.
  6. T. Mansour and M. Shattuck. Counting water cells in bargraphs of compositions and set partitions. Applicable Analysis and Discrete Mathematics, 12(2):413–438, 2018. https://doi.org/10.2298/AADM170428010M.
  7. T. Mansour and M. Shattuck. Counting water cells in pattern restricted compositions. Turkish Journal of Analysis and Number Theory, 7(4):98–112, 2019. https://doi.org/10.12691/tjant-7-4-2.
  8. T. Mansour and M. Shattuck. Enumeration of Catalan and smooth words according to capacity. Integers, 25, 2025. https://doi.org/10.5281/zenodo.14679307. Article A5.