Abstract

In this paper, we consider statistics on compositions of a positive integer represented geometrically as bargraphs that avoid certain classes of consecutive patterns. A unit square exterior to a bargraph that lies along a horizontal line between any two squares contained within its subtended area is called a water cell since it is a place where a liquid would collect if poured along the top part of the bargraph from above. The total number of water cells in the bargraph representation of a k-ary word then gives what is referred to as the capacity of w. Here, we determine the distribution of the capacity statistic on certain pattern-restricted compositions, regarded as k-ary words. Several general classes of patterns are considered, including and where a is arbitrary. As a consequence of our results, we obtain all of the distinct distributions for the capacity statistic on avoidance classes of compositions corresponding to 3-letter patterns having at most two distinct letters. Finally, in the case of some further enumerative results are given when a=2, including algebraic and bijective proofs for the total capacity of all Carlitz partitions of a given size having a fixed number of blocks.

2010 Mathematics Subject Classification. Primary 05A15; Secondary 05A18.

1. Introduction

Bargraphs have been studied recently from several standpoints and have found various refined enumerations. Recall that a bargraph is a first quadrant self-avoiding random walk starting at the origin and ending upon its first return to the -axis in which there are three types of steps--an up step , a down step and a horizontal step Bargraphs are also known as wall polyominoes ¹ and skylines ², and have proven to be effective in visualizing compositions ³ and other discrete structures ⁴. Prellberg and Brak ⁵ and Feretíc ⁶ were among the first to study statistics on bargraphs and found a generating function with two variables and marking the number of horizontal and up steps, respectively. Blecher et al. later considered such statistics as levels ⁷, peaks ⁸, descents ³ and area ³. Generating function formulas related to bargraphs have also arisen in statistical physics ⁹, where they are used to model various kinds of polymers.

Four points that lie along a bargraph or within the area it subtends in the first quadrant determine what is called a cell of . If contains horizontal steps, then it can be identified as a sequence of columns such that the -th column from the left contains exactly cells. A composition of is a sequence of positive integers, called parts, whose sum is . Let denote the set of compositions of having parts. Then members of may be represented as bargraphs having horizontal steps and that subtend a first quadrant area of , where the -th column height (from the left) of a bargraph corresponds to the size of the -th part of a composition.

Here, we consider counting certain classes of compositions with respect to a parameter defined on their bargraph representations. Let us call a unit square in the first quadrant a water cell of the bargraph if lies outside of the area subtended by but along a horizontal line connecting two cells of . Thus, if one were to pour a large amount of a liquid along an impermeable boundary modeled by from above and assume the usual rules of water flow, then a water cell is a square that would be immersed by virtue of its location. That is, two columns of strictly greater height are present one to the left and another to the right of the column of above which lies, with the height of (above the -axis) less than or equal the minimum of these two greater heights. The total number of water cells within a bargraph whose sequence of column heights is given by the -ary word has been termed the capacity of (also applied to the word ), see ¹⁰. For example, if and is a -ary word of length whose bargraph representation is shown below, then the capacity of is .

Let be a member of and let where be a word of length containing all the letters in for some . An occurrence of is a string of which is order isomorphic to , i.e., if and only if for all , and likewise with the inequalities reversed. Then is said to avoid if it contains no occurrences of . In this context, is usually referred to as a subword or consecutive pattern. For example, the composition avoids the subword pattern 212, but contains three occurrences of 112, namely, 113, 112 and 223. Let denote the subset of whose members avoid the subword . Here, we wish to enumerate members of represented geometrically as bargraphs according to the capacity statistic for various . Specifically, we will compute the generating function (g.f.) for the distribution of the capacity statistic (marked by ) on . When , one obtains avoidance results for compositions with respect to consecutive patterns (see, e.g., ¹¹), and hence our results may be viewed as generalizations of the avoidance case for these patterns. For a different generalization of the avoidance case wherein the number of occurrences of a given pattern is considered, see ¹² and also ¹³ for comparable work on finite set partitions.

This paper is organized as follows. In the next section, we compute the g.f. which counts -avoiding members of according to the joint distribution of the number of runs of parts and the capacity. Note that avoiding is the same as avoiding of length for all possible , i.e., there are no runs of length or more of the same part . Some further enumerative results are given in the case wherein there are no two consecutive parts the same (which coincides with what are known as Carlitz compositions). Among our results is a bijective proof for the total capacity of all Carlitz set partitions represented sequentially having a fixed number of blocks. In the third section, we compute the g.f. counting members of according to the number of water cells in the cases when , , or 121, where is arbitrary. As a consequence of the preceding results and symmetry, one obtains all of the distinct distributions for the capacity statistic on the set of -avoiding compositions of a given size in the case when has length three and at most two distinct letters.

2. Distribution of Water Cells in Compositions Avoiding 1^m

We will refer to compositions having parts in [k] as -ary. Let for a subword pattern denote the subset of whose members are -ary. Note that taking in gives , and hence one may consider the former when computing the distribution of a statistic on the latter. A run within a composition is a string of parts of the same kind. Let count -ary -avoiding compositions of having parts (marked by and , respectively) according to the number of runs and the capacity (marked by and ). That is,

where and denote the number of runs and the capacity of a composition

We first compute the case when which we will need to establish the general formula. Let

Lemma 1. If , then

(1)

Proof. Let denote the restriction of to those compositions starting with .

Then considering the length of the initial run of implies

which gives

Summing both sides of the last equation over , and noting , yields (1).

Let be the restriction of to those compositions that start with . We have the following product formula for .

Lemma 2. If , then

(2)

where .

Proof. First suppose enumerated by is of the form , where and is -ary (possibly empty) and not starting with . To determine this case, let denote the restriction of to compositions starting with a single . Then is synonymous with a composition enumerated by where there is an extra weight of (which has the effect of changing the initial run of of length to a run of ). Thus, we get a contribution towards of

in this case. Note that . To realize this, note that both sides of the equality give the difference of the g.f. that counts -ary compositions avoiding and starting with a single letter with the g.f. that counts compositions of the form , where is a composition enumerated by but not .

If counted by is of the form , where is -ary, then considering all possible gives

Finally, if , where is -ary and nonempty, then each part of size in contributes towards the capacity for all since there is a both to the left and right. Thus, has weight , while contributes . Accounting for the initial run of yields

where is determined by (1). Combining the three previous cases then implies for the recurrence

which may be rewritten as

Iterating this last equation implies

where is as defined, which gives (2).

Theorem 3. If , then

(3)

where is given by (2) above.

Proof. Let be the same as except that we count the k-ary compositions according to the capacity of Upon writing enumerated by and containing at least one as where is -ary, we have

which implies

We now determine . If the last part of counted by is , then the contribution is , upon writing compositions in reverse order. Otherwise, the final part of belongs to or is empty, in either case the may be regarded as the initial in a composition enumerated by , where we divide by since this letter actually does not contribute to the weight of . This case is then accounted for by and thus

Substituting the last expression into (4) implies (3).

Remark: Note that the generating function counts all -avoiding -ary words (where the length is marked by ) according to the number of runs and the capacity. A similar comment will apply to the pattern-avoiding compositions considered in the subsequent section.

Taking in (3) recovers an earlier formula for the g.f. enumerating -avoiding compositions according to the number of parts.

Corollary 4 (Mansour and Sirhan ¹²). If , then

Proof. We first simplify . Taking in (2) implies that the numerator of is given by

while the -th factor in the denominator may be written as

Therefore, we have

by telescoping. Thus, by (3), we have

by telescoping, as desired.

Carlitz compositions (see, e.g., [ ¹¹, Section 3.2.2]) are those with no two consecutive parts the same and are enumerated by the case of Theorem 3 above. Note that the number of runs (marked by ) in a Carlitz composition is always equal the number of parts (marked by ), hence one may take . Let for . Letting in Theorem 3 and simplifying gives the following explicit formula.

Corollary 5. The generating function that counts Carlitz compositions with parts in [k] where according to the capacity is given by , where

(5)

Recall that a partition of a set is a collection of non-empty, mutually disjoint subsets, called blocks, whose union is the set. A partition of [n] having blocks is said to be in standard form if its blocks are labeled so that . A partition in standard form can be expressed equivalently by the canonical sequential form wherein for all (see, e.g., ¹⁴). This sequence is onto [k] and satisfies the restricted growth property ¹⁵, For example, if and is a partition of ¹², then . One can represent the restricted growth sequence associated with a partition of [n] as a bargraph whose sequence of column heights satisfy the restricted growth property. At times, the sequential form as well as the associated bargraph will be used interchangeably with .

A Carlitz (set) partition (see, e.g., ¹⁶) is one in which no two consecutive elements belong to the same block of ; i.e., there are no two adjacent letters the same in , see the example above. We will denote the set of Carlitz partitions of [n] having blocks by . Define the capacity of as the number of water cells in the bargraph representation of . For example, if is as given above, then the capacity is , as illustrated in Figure 2.

Given , let denote the g.f. enumerating members of according to the capacity.

Theorem 6. The generating function that counts Carlitz partitions of [n] having blocks where according to the capacity is given by

(6)

Proof. The canonical sequential form of may be represented as , where is -ary such that has no equal adjacent letters letters for each . In the notation from the previous section, this implies

(7)

By (2) and (1) when , we have

and

from which formula (6) follows from (7).

Substituting into (6) gives

where denotes the Stirling number of the second kind. This reaffirms the well-known fact (see, for example, ¹⁶) that there are members of .

We now determine an expression for the sum of the capacities of all members of . To do so, we compute the derivative with respect to of at . We handle the two factors occurring in the product expression in (6) separately. First observe that

and thus

Also, we have

with , so that

Therefore, by (7), we get

which yields the following result.

Theorem 7. The generating function for the number of water cells in all Carlitz partitions of [n] having blocks is given by

(8)

Let denote the generalized Fibonacci sequence (see, e.g., [ ¹⁷, Section 3.1]) defined by the recurrence for , with and . Note that

Then extracting the coefficient of in 8) gives the following explicit formula for the total capacity.

Corollary 8. The number of water cells in all Carlitz partitions of [n] having blocks where is given by

Combinatorial proof of Corollary 8.

We first describe a class of words enumerated by for and that will be needed in our combinatorial interpretation. Given a -ary word , a (circular) succession is an occurrence of two consecutive letters (where corresponds to if ). Consider underlining non-overlapping successions in starting from the left in a greedy manner. That is, we underline the first succession encountered starting from the left having no letters in common with previously underlined successions. For example, for the -ary word where and , we have .

Definition 9. Let denote the set of all -ary words where such that (I) no two adjacent letters of w are the same, and (II) when non-overlapping successions are underlined in a greedy manner starting from the left, the last letter of is not part of an underlined succession.

Note that by symmetry the cardinality of would not change if the requirement is replaced by for any fixed . We will refer to -ary words satisfying properties (I) and (II) above as being restricted. For example, if and , then the j-ary word is restricted, whereas and are not since the last two letters, 34 and 51, respectively, form successions that would be underlined in these words. In what follows, a set of restricted words will often be assumed to start with a specific letter. Let .

Lemma 10. If and then

Proof. First note that there is word of length one and words of length two since the second letter cannot be or . If , then there are members of in which there are two or more letters to the right of the rightmost underlined succession, as seen upon appending a letter from to a member of ending in for some There are possibilities if the penultimate letter and its predecessor form an underlined succession, upon appending where to a member of ending in . Combining this case with the previous implies for all .

Let denote the set of “marked” Carlitz partitions obtained from members of by marking any one of the water cells. Note that , which we compute below, equals the total number of water cells in all the members of Given represented sequentially, we will refer to the subsequence as the -ary section of (and also when discussing the corresponding portion of the bargraph representation of , which we denote by ). We first count members of where the marked water cell lies above a column in the -ary section for some . To do so, given and , consider the set of triples , where is a two-element subset of [j], and is a restricted -ary word of length with first letter Note that by the previous lemma.

Given , we form as follows. If and the last letter of does not equal , then let

that is, we append just prior to the first occurrence of , and then mark the water cell at height directly above the column of corresponding to the initial letter of . This operation is seen to yield (uniquely) all members of in which the marked cell has height above a column of height in the -ary section of such that the subword of starting with the letter corresponding to the column of the marked cell of and ending with the final letter of the -ary section of is restricted and of length . On the other hand, if the last letter of equals , then we delete this letter from and add it back to the end of as where denotes the final letter of (with representing if ). Note that implies is nonempty in this case. Let denote minus its last letter and let . We then form the partition

which is seen to satisfy all the same properties as before except that the subword starting with the letter corresponding to the marked cell and ending just prior to the first occurrence of is no longer restricted and has length . The correspondence then defines a bijection between and all members of in which the marked water cell occurs in a column belonging to the -ary section where there are exactly positions between it and the first column of height . Considering all possible and implies that there are

members of in which the marked cell lies above a column within a -ary section for some .

Similar reasoning applies to members in which the marked cell lies above a column in the -ary section, which gives However, this would be assuming that there is a terminal letter that follows . Thus, we must subtract the number of those cells which do no yield de facto members of when marked. By a non-water cell, we will mean one of height at most that lies above some column in the -ary section of which is not itself a water cell. Let be obtained from by marking one of the non-water cells. Then we must subtract from the current total to obtain the desired . We now show

from which Corollary 8 follows. Suppose that the marked non-water cell in has height . First assume . Given , let denote the set of triples , where , and is a restricted -ary word of length having first letter . Then the bijection defined above on applies here and shows that gives the cardinality of all members of in which the marked cell has height with exactly columns to the right of the one containing this cell. Therefore, summing over and gives all possible members of in which the marked cell has height at least three.

We now consider the case and count members of where the marked cell has height two. In order to have height two, the column in which this cell lies must correspond to the final letter of a partition, for otherwise it would actually be a water cell. Thus, counting the remaining members of is equivalent to counting members of ending in 1. Since for , the remaining case when in the expression to be shown above for is given by , and thus it suffices to show that this is the cardinality of the subset of whose members end in 1. To do so, we first let for denote the set of words of length obtained by appending exactly 1's to members (represented sequentially) and circling the final letter of if it ends in a 1 and let . Define the sign of members of by . Note that the sum of the signs of members of is given by . Define an involution on by either circling the first 1 in the terminal sequence of 1's if it is not circled or erasing the circle enclosing the first 1 if it is. Note that this pairs members of of opposite sign and is not defined in the case when and ends in a single (uncircled) . Such words are seen to be equivalent to members of ending in 1, which establishes the desired formula for this subset of and completes the proof.

Remark: It is also possible to find an expression for the exponential generating function for the total capacity of all members of . Let and . Then transferring from the ordinary to the exponential generating function gives the following formula:

3. Capacity of other Pattern-restricted Compositions

In this section, we enumerate various avoidance classes of compositions according to the number of water cells in their bargraph representations. As corollaries to our results, we obtain the distribution for this statistic on the 112, 121, 122 and 212 avoidance classes. Note that this covers all patterns of length three having two distinct letters since the capacity statistic is preserved by the reversal operation. On the other hand, while the patterns 112 and 122 (and also 121 and 212) are equivalent when enumerating compositions avoiding either pattern according to the number of parts, this is not the case when the capacity is considered since it is unclear how this statistic behaves with respect to the reverse-complement operation.

We will use the following notation. Let be a subword pattern of length (where here will actually denote a particular member of an infinite class of patterns containing one representative for each ). Given , let denote the g.f. counting -avoiding -ary compositions of having parts (marked by and respectively) according to the capacity (marked by ), i.e.,

Let be the same as except now we are counting -ary compositions according to the capacity of , where it is assumed that avoids . Similarly, define as the g.f. counting -ary according to the capacity of , where it is assumed that avoids .

If is -ary and contains at least one letter , then one may write , where is -ary and is -ary. Suppose is such that its largest letter occurs in the final position (and possibly elsewhere as well). Then the preceding decomposition of may be expressed in terms of generating functions as

(9)

In the following subsections, we use , and as they are defined above for the particular pattern in question. Also, we will frequently regard a composition as a -ary word, referring to its parts as letters by a slight abuse of notation.

Let be of length . Let

for and . In this case for , we have the following recursive formulas for and .

Lemma 11. If , then

(10)

and

(11)

Proof. To show (10), we must account for the -ary factor within in the decomposition stated above and enumerated by . Note first that may assume the form , where is any composition enumerated by and denotes the reversal operation, with the capacity of and equal. Note further that it is also possible for to be of the form , where and is -ary (the reversal in this case would not be accounted for by since the last letters of would form an occurrence of ). Considering all , such are seen to have weight

Combining the previous cases implies that contributes , from which formula (10) follows from (9).

For (11), first note that the prior reasoning shows also that the contribution of towards , in the case when is -ary, is given by . If ends in , then this letter is extraneous concerning the avoidance of (and thus may be deleted) and we get a contribution of . So assume , where is -ary and possibly empty and is -ary and nonempty. In this case, any letter of size in produces water cells since there is a letter both to its left and to its right in . The distribution for the number of water cells in may then be obtained by the transformation . Thus, the factor contributes

where the second subtracted term accounts for strings of the same letter of length exactly (which would produce an occurrence of in ). Therefore, compositions of the given form contribute towards Combining all of the previous cases, and rewriting the resulting equation, yields (11).

Iterating (11) gives

By [ ¹², Theorem 2.4], we have

which implies

Thus, we can state the following result.

Theorem 12. If , then the generating function is given by

where

and .

Taking in the prior theorem implies that generating function for $212$-avoiding compositions is given by

where

Let be of length . Then in this case the following recurrences are satisfied by and .

Lemma 13. If , then

(12)

and

(13)

Proof. To show (12), first note that if enumerated by consists of a (possibly empty) sequence of the letter , then the contribution is . So assume has the form , where and is nonempty with final letter in . First suppose contains at least one letter . Let , where is -ary and is -ary. Then and are accounted for by and , respectively, since any letter in is seen to have water cells above it. Considering all possible implies contributes

in this case.

Now suppose is -ary. Let count -avoiding -ary compositions according to the number of water cells in . Then in this case contributes towards . We now determine . Note that in addition to counting all compositions enumerated by , the g.f. also enumerates of the form , where does not end in and is nonempty. Let be the g.f. that counts nonempty -avoiding k-ary compositions whose final letter belongs to according to the capacity of . Then any composition enumerated by and not consisting of a string of 's may be obtained by appending up to 's to the end of having the stated form, which implies

i.e.,

Thus, we have

Combining all of the previous cases then implies

where is as given. The last equality may be rewritten as (12).

To show (13), first note that accounts for -ary compositions and for starting with . So assume , where is -ary and nonempty, is -ary and does not start with (possibly empty), and . Note that nonempty implies and that contributes , by subtraction. Thus in this case is accounted for by

Combining the previous cases leads to (13).

By [ ¹², Theorem 2.3], we have

Define

From (12), we get

Thus, by induction on with , we have

Moreover, (13) shows that , which implies

Hence, by (9), we can state the following result.

Theorem 14. If , then the generating function is given by

where .

Let be of length . We refine in this case as follows. Let denote the restriction of to those compositions whose last part is . We have the following formula for .

Lemma 15. If and , then

(14)

Proof. One may clearly add to any -avoiding -ary composition ending in without introducing an occurrence of . On the other hand if , then the final run of the letter in cannot have length greater than . Thus in this case is accounted for by by subtraction, as appending letters to a composition enumerated by results in one ending in at least letters where Combining the previous cases and considering the penultimate letter within a composition enumerated by gives

(15)

where the term represents the composition consisting of a single part .

Replacing with in (15), and subtracting, gives

which may be rewritten as

(16)

Iterating (16), and noting

leads to (14).

By using (14) and the fact

we get for the formulas

(17)

(18)

where (17) was shown in [ ¹²,Theorem 2.2].

Lemma 16. If , then

(19)

and

(20)

Proof. To show (19), first suppose enumerated by is -ary, which gives . However, we must subtract the possibility of ending in a string of the letter of length at least . Thus, we get in the case that is -ary. If ends in , then we clearly get . So assume , where is -ary and is -ary and nonempty. If ends in , then the final string of 's must have length at most in order for to avoid . Thus, by subtraction, such would contribute Considering all possible , and using (14), then gives a contribution of

where the factor accounts for . Combining this with the previous cases leads to (19).

For (20), first note that accounts for all enumerated by of the form , where and is -ary. So assume , where is -ary, nonempty and not consisting of a string of 's and is -ary. Then the last letter of belonging to must not occur as a string of length or more (for otherwise, would contain ). Considering all possible , and using (14), gives a contribution from of

where the factor accounts for a possibly empty terminal string of the letter . Then gives , which now fully accounts for the second term on the right-hand side of (20) (when divided by ) and completes the proof.

By Lemma 16 and (17), we have

and

which, by , leads to

(21)

(22)

Hence, by (9), we can state the following result.

Theorem 17. If then the generating function is given by

where and are given by (21) and (22).

While we were unable to find an expression for the g.f. that counts water cells in -avoiding compositions for patterns of general length, we did find a recursive procedure for generating the distribution of water cells in the 121 case, which we describe in this subsection. Let denote the set of 121-avoiding k-ary words of length n. Given , let be the joint distribution polynomial on for the statistics recording the sum of the letters and the capacity (marked by and , respectively). Note that gives the distribution for the capacity statistic on -ary 121-avoiding compositions of n with parts.

To determine , we will need the following further definitions. Let be the same as except now we consider the capacity of kw for . Let where denote the restriction of to words whose first letter is . By the definitions, we have

with for (where for all ). Considering whether or not enumerated by contains , and if so, the position of the leftmost occurrence of , leads to the formula

(23)

with and for .

We now determine a recurrence for the array. To aid in doing so, let for be the joint distribution on of the form for the sum of the letters of and the number of water cells in kwk (again, marked by p and q, respectively). Note that the sum of the letters in equals the difference of nk with the number of water cells in kwk, so is actually a distribution of a single statistic, but we will keep track of both variables since this array is used to find a recurrence as follows for the where this is not the case.

Proposition 18. If and , then

(24)

where , and .

Proof. Let be a word enumerated by . Then there are possibilities for , by definition, if is -ary, so assume contains at least one . If is of the form , then there are possibilities. If and appears only once and as the final letter, then there are words , upon considering the penultimate letter. So assume , where w' is -ary of length for some and w'' is -ary. Let denote the last letter of w' and the first letter of w''. Then there are possibilities for the w'k and for $w''$. Considering all , and gives the remaining words and implies (24).

Let for denote the restriction of to of the form Note that for , by the definitions, with . We have the following recurrence formula for .

Proposition 19. If and and , then

(25)

and

(26)

where if and

otherwise.

Proof. The initial conditions when follow from the definitions, so assume . First assume and consider the third letter of enumerated by . If and then both the and may be deleted which gives the first term on the right side of (25). If , then only the may be deleted which gives the second term in (25). If then is extraneous concerning the avoidance of 121 and thus may be deleted, which implies (26).

Note that recurrences (25) and (26) determine the array which in turn gives the For example, one can use these recurrences to compute for all and up to some fixed number. Once the are known, then the array is determined by (24), which gives and hence by (23).

References