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.
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.
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].
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
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
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
The generating function for Eq. (2) is
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
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
We check that
which is the generating function for all words over the alphabet \([k]\) as expected.
The series expansion of \(F(3;y,w,q)\) is
Example 2.2. The term in bold is given by the words
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
By using Eq. (8), changing the order of the double sum and simplifying, we obtain
Now, combining the \(r\) sums and using partial fractions, we simplify this to separate terms suitable for coefficient extractions,
We now extract the coefficients from all but the summed terms of Eq. (10) and we obtain
Next, extracting the coefficients of the last part (i.e., the summed term) of Eq. (10), we obtain
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
In particular the average number of reservoirs in all words of length \(n\) over the alphabet \([k]\) is asymptotic to
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
By using Eq. (14), changing the order of the double sum and simplifying, we obtain
Now, using partial fractions, we simplify this to
Extracting the coefficients from the first four terms of Eq. (16), we obtain
Again, extracting the coefficients of the last part (i.e., the summed term) of Eq. (16), we obtain
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
In particular the average width of reservoirs in all words of length \(n\) over the alphabet \([k]\) is asymptotic to
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
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
By summing over \(m\) for \(1\le m \le \infty\), we obtain the generating function for a single reservoir of any width as
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
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
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
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
And for \(2 \le r < k\) where there are no occurrences of \(j > r\) but at least one occurrence of \(r\), we get
Also,
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
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
We illustrate the seven words constituting the term in bold. These are
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.

In this section, we track the number of reservoirs of depth \(r\) by invariant \(q\). So, this last decomposition has generating function
By summing over \(m\) for \(1\le m \le \infty\), we obtain the generating function for a single reservoir of any width as
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
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
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
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
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
For any fixed alphabet \([k]\), we define \(C_r(k; y,q):=\sum\limits_{i=1}^k C_{i,r}(y,q)\). This yields
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
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
We illustrate the eleven words constituting the term in bold. These all have three reservoirs each of depth \(3\). They are
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
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
where \(y\) marks the number of letters in the subword and now \(x\) marks the capacity.
Thus
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
Therefore the generating function for the total central capacity is
Hence the average central capacity is
as \(n \to \infty.\) We compare this with the total capacity of a word of length \(n\) in [1] which is asymptotic to
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.
Both authors contributed equally to this work and approved the final version of the manuscript.
The authors declare no conflicts of interest.
All data supporting the findings of this study are included in the manuscript.
This research received no funding.