Counting Rectangles of Size r × s in Nondecreasing and Smirnov Words

Sela Fried Department of Computer Science Israel Academic College in Ramat Gan Pinhas Rutenberg 87 Ramat Gan 52275 Israel

                  friedsela@gmail.com

Abstract

The rectangle capacity, a word statistic that Mansour and the author recently introduced, counts, for two fixed positive integers r and s, the number of occurrences of a rectangle of size r × s in the bargraph representation of a word. In this work we find the bivariate generating function for the distribution on nondecreasing words of the number of rectangles of size r × s and the generating function for their total number over all nondecreasing words. We also obtain the analog results for Smirnov words, which are words that have no consecutive equal letters. This complements our recent results concerned with general words (i.e., not restricted) and Catalan words.

1 Introduction

Let n and k be two positive integers and set [k] = {1, 2, …, k}. A word over k of length n is any element of the set [k]^{n}. Words have a visual representation in terms of bargraphs (see Figure 1), giving rise to many natural statistics on words, such as their water capacity, number of lit cells, and perimeter (see [12] for a comprehensive review of the subject).

In this work we continue the study of a new statistic, which Mansour and the author introduced in [8], called rectangle capacity. This statistic, for two fixed positive integers r and s, counts the number of occurrences of a rectangle of size r×s in the bargraph representation of a word (see Figure 2). Rectangle capacity is a special case of a much more general statistic, defined by Mansour and Shabani [11]: for two bargraphs B and C, a vertex (x, y) of B is said to be a C-vertex if C lies entirely in B, when positioned starting at (x, y). In their work, Mansour and Shabani studied the number of C-vertices in several special cases. Two of these correspond to rectangle capacity of size 1 × s and r × 1.

Rectangle capacity has also been studied in the context of set partitions by Cakić et al. [3], for r × s = 1 × 2 and by Archibald et al. [1], for r × s = 2 × 2. Notice that the rectangle capacity of size 1 × 1 coincides with the area of the bargraph, a statistic that is naturally well studied (e.g., [4, 12]).

In our work [8] we studied general words (i.e., not restricted) and Catalan words. The purpose of this work is to explore additional families of words, namely nondecreasing words and Smirnov words. By the former we mean words w_{1} ⋯ w_{n} ∈ [k]^{n} such that w_{i+1} ≥ w_{i}, for each 1 ≤ i ≤ n − 1, and, by the latter, words w_{1} ⋯ w_{n} ∈ [k]^{n} such that w_{i+1} ≠ w_{i}, for each 1 ≤ i ≤ n − 1 (cf. [5, Example 23, p. 193]).

Smirnov words proved to be applicable to different kinds of problems such as waiting time distributions of runs in [7] and diagonal coinvariant rings in [10]. Furthermore, Smirnov words are connected to q-Eulerian polynomials (e.g., [6]). Several results concerned with statistics on nondecreasing words appear in [9, Section 4.3].

Figure 1: The bargraph representation of the word 345134.

Figure 2: There are four occurrences of a rectangle of size 3×2 in the bargraph representation of the word 345134.

Before we begin, let us fix three positive integers r, s, and k and let n be a nonnegative integer. For a positive integer m, we denote by [m] the set {1, 2, …, m}.

2 Main results

2.1 Nondecreasing words

We denote by W_{n,k}^{↗} the set of nondecreasing words over k of length n, i.e.

W_{n,k}^{↗} = {w_{1} ⋯ w_{n} ∈ [k]^{n} : w_{i} ≤ w_{i+1} for every i ∈ [n − 1]} .

It is well known that

|W_{n,k}^{↗}| = \binom{n + k − 1}{k − 1}.

We distinguish between two cases, namely r = 1 and r ≥ 2.

2.1.1 Rectangle capacity of size 1 × s

Denote by a_{n,k} = a_{n,k}(t) the distribution on W_{n,k}^{↗} of the number of 1 × s rectangles and let A_{k}(x, t) denote the generating function of the numbers a_{n,k}. We shall need the following restrictions of W_{n,k}^{↗}: Let

W_{n,k}^{↗,(0)} = {w_{1} ⋯ w_{n} ∈ W_{n,k}^{↗} : w_{j} > 1 for every j ∈ [n]}

and, for i ∈ [n], we define

W_{n,k}^{↗,(i)} = {w_{1} ⋯ w_{n} ∈ W_{n,k}^{↗} : w_{i} = 1 and w_{j} > 1 for every i < j ≤ n} .

For 0 ≤ i ≤ n, let a_{n,k}^{(i)} be the restriction of a_{n,k} to W_{n,k}^{↗,(i)}. Notice that if w_{1} ⋯ w_{n} ∈ W_{n,k}^{↗,(i)}, then w_{1} = ⋯ = w_{i} = 1.

Theorem 1. We have

A_{k}(x, t) = ∑_{i=0}^{k−1} \frac{α_{k−i}(t^{i}x, t)}{t^{i(s−1)} ∏_{j=1}^{i}(1 − t^{j}x)},  (1)

where

α_{m}(x, t) = ∑_{n=0}^{s−2} \binom{n + m − 1}{m − 1}x^{n} + \frac{x^{s−1}}{1 − tx}\binom{s + m − 3}{m − 1} − \frac{1}{t^{s−1}(1 − tx)} ∑_{n=0}^{s−2} \binom{n + m − 2}{m − 2}(tx)^{n}.

Proof. The set W_{n,1}^{↗} consists solely of the word 1 ⋯ 1, containing n − s + 1 rectangles of size 1 × s. Thus, a_{n,1} = t^{max{0,n−s+1}} and it is easily verified that the corresponding generating function is given by

A_{1}(x, t) = α_{1}(x, t) = \frac{1 − x^{s−1}}{1 − x} + \frac{x^{s−1}}{1 − tx}.

Assume now that k ≥ 2. For n ≥ s we have

a_{n,k} = a_{n,k}^{(0)} + ∑_{i=1}^{n} a_{n,k}^{(i)}

= t^{n−s+1}a_{n,k−1} + t^{n−s+1} ∑_{i=1}^{n} a_{n−i,k−1}.

Multiplying both sides of this equation by x^{n}, summing over n ≥ s and adding ∑_{n=0}^{s−1} a_{n,k}x^{n} to both sides, we obtain

A_{k}(x, t) = ∑_{n=0}^{s−1} \binom{n + k − 1}{k − 1}x^{n} − \binom{s + k − 3}{k − 2}x^{s−1}

+ \frac{1}{t^{s−1}(1 − tx)} (A_{k−1}(tx, t) + ∑_{n=0}^{s−2} \binom{n + k − 2}{k − 2}((tx)^{s} − (tx)^{n})) ,

from which (1) follows by induction.

Corollary 2. The generating function for the total number f_{k}(n) of 1 × s rectangles over all words belonging to W_{n,k}^{↗} is given by

\frac{x^{s} ∑_{i=0}^{k−1}(−1)^{i}\binom{i+s−2}{i}\binom{k+s}{s+i+1}x^{i}}{(1 − x)^{k+1}} .

Thus, for n ≥ s,

f_{k}(n) = ∑_{i=0}^{min\{k−1,n−s\}}(−1)^{i}\binom{i + s − 2}{i}\binom{k + s}{s + i + 1}\binom{n − s − i + k}{k}.

Proof. Let 0 ≤ i ≤ k − 1. We have

\frac{∂}{∂t} \frac{α_{k−i}(t^{i}x, t)}{t^{i(s−1)} ∏_{j=1}^{i}(1 − t^{j}x)}

= \frac{(\frac{∂}{∂t}α_{k−i}(t^{i}x, t)) t^{i(s−1)} ∏_{j=1}^{i}(1 − t^{j}x) − α_{k−i}(t^{i}x, t) (\frac{∂}{∂t}t^{i(s−1)} ∏_{j=1}^{i}(1 − t^{j}x))}{(t^{i(s−1)} ∏_{j=1}^{i}(1 − t^{j}x))^{2}}.

We have

[t^{i(s−1)} ∏_{j=1}^{i}(1 − t^{j}x)]_{|t=1} = (1 − x)^{i},

[\frac{∂}{∂t}t^{i(s−1)} ∏_{j=1}^{i}(1 − t^{j}x)]_{|t=1} = i(1 − x)^{i−1} ((s − 1)(1 − x) − \frac{x(i + 1)}{2}) .

It is not hard to see that

[α_{k−i}(t^{i}x, t)]_{|t=1} = \begin{cases}0, & if i < k − 1; \\ \frac{1}{1−x}, & otherwise. \end{cases}

[\frac{∂}{∂t}α_{k−i}(t^{i}x, t)]_{|t=1} = \begin{cases}∑_{n=0}^{s−2}(s − 1 − n)\binom{n+k−1−i}{k−1−i}x^{n}, & if i < k − 1; \\ \frac{x(x^{s−1}+k−1)}{(1−x)^{2}}, & otherwise. \end{cases}

It follows that

[\frac{∂}{∂t}A_{k}(x, t)]_{|t=1}

= ∑_{i=0}^{k−1} [\frac{∂}{∂t} \frac{α_{k−i}(t^{i}x, t)}{t^{i(s−1)} ∏_{j=1}^{i}(1 − t^{j}x)}]_{|t=1}

= ∑_{i=0}^{k−2} \frac{∑_{n=0}^{s−2}(s − 1 − n)\binom{n+k−1−i}{k−1−i}x^{n}}{(1 − x)^{i}} + \frac{x (x^{s−1} + \frac{(k−1)(2s+k)}{2}) − (k − 1)(s − 1)}{(1 − x)^{k+1}},

from which the assertion follows.

Example 3. For k = 2 we have

f_{2}(n) = \frac{3n^{2} + (7 − 4s)n + (s − 1)(s − 4)}{2}

and Table 1 lists the corresponding sequences that we found in the On-Line Encyclopedia of Integer Sequences (OEIS) [14]. For k = 3 we have

f_{3}(n) = \frac{2n^{3} − 3(s − 3)n^{2} + (s^{2} − 10s + 13)n + 2(s − 1)(s − 3)}{2}

and it seems that no corresponding sequence is registered in the OEIS.

2.1.2 Rectangle capacity of size r × s, where r ≥ 2

Denote by b_{n,k} = b_{n,k}(t) the distribution on W_{n,k}^{↗} of the number of r × s rectangles and by B_{k}(x, t) the generating function of the numbers b_{n,k}. We shall need the following restriction of W_{n,k}^{↗}: for m ∈ [k], let

W_{n,k}^{↗,(≥m)} = {w_{1} ⋯ w_{n} ∈ W_{n,k}^{↗} : w_{j} ≥ m for each j ∈ [n]} ,

and let b_{n,k}^{(≥m)} be the restriction of b_{n,k} to W_{n,k}^{↗,(≥m)}. Let B_{k}^{(≥m)}(x, t) be the generating function of the numbers b_{n,k}^{(≥m)}.

s  f_{2}(n)  OEIS
1  (3n^{2} − 3n)/2  \underline{A045943}
2 (3n^{2} − n − 2)/2 \underline{A115067}
3 (3n^{2} − 5n − 2)/2 \underline{A140090}
4 (3n^{2} − 9n)/2 \underline{A140091}
5 (3n^{2} − 13n + 4)/2 \underline{A059845}
6 (3n^{2} − 17n + 10)/2 \underline{A140672}
7 (3n^{2} − 21n + 18)/2 \underline{A140673}
8 (3n^{2} − 25n + 28)/2 \underline{A140674}
9 (3n^{2} − 29n + 40)/2 \underline{A140675}
10 (3n^{2} − 33n + 54)/2 \underline{A151542}
11 (3n^{2} − 37n + 70)/2 \underline{A370238}

Table 1: The total number f_{2}(n) of 1 × s rectangles over all words of length n, for several values of s.

Lemma 4. Assume that k ≥ r − 1. Then

B_{k}^{(≥r−1)}(x, t) = ∑_{i=0}^{k−r+1} \frac{α_{k−i}^{(≥r−1)}(t^{i}x, t)}{t^{i(s−1)} ∏_{j=0}^{i−1}(1 − t^{j}x)},  (2)

where

α_{m}^{(≥r−1)}(x, t)

= ∑_{n=0}^{s−1} \binom{n + m − r + 1}{m − r + 1}x^{n} + \frac{x^{s}}{1 − x}\binom{s + m − r}{s − 1} − \frac{1}{t^{s−1}(1 − x)} ∑_{n=0}^{s−1} \binom{n + m − r}{m − r}(tx)^{n}.

Proof. The set W_{n,r−1}^{↗,(≥r−1)} consists solely of the word (r−1) ⋯ (r−1), containing no rectangles of size r × s. Thus, b_{n,r−1}^{(≥r−1)} = 1 and the corresponding generating function is given by B_{r−1}^{(≥r−1)}(x, t) = 1/(1 − x). Assume now that k ≥ r. For n ≥ s we have

b_{n,k}^{(≥r−1)} = b_{n,k}^{(≥r)} + ∑_{i=1}^{n} b_{i,r−1}^{(≥r−1)}b_{n−i,k}^{(≥r)}

= t^{n−s+1}b_{n,k−1}^{(≥r−1)} + ∑_{i=1}^{n−s} t^{n−i−s+1}b_{n−i,k−1}^{(≥r−1)} + ∑_{i=n−s+1}^{n} b_{n−i,k−1}^{(≥r−1)}.

Multiplying both sides of this equation by x^{n}, summing over n ≥ s and adding ∑_{n=0}^{s−1} b_{n,k}^{(≥r−1)}x^{n} to both sides, we obtain the equation

B_{k}^{(≥r−1)}(x, t) = \frac{1}{t^{s−1}(1 − x)}B_{k−1}^{(≥r−1)}(tx, t) + ∑_{n=0}^{s−1} \binom{n + k − r + 1}{k − r + 1}x^{n}

− \frac{1}{t^{s−1}(1 − x)} ∑_{n=0}^{s−1} \binom{n + k − r}{k − r}(tx)^{n} + \frac{x^{s}}{1 − x} ∑_{n=0}^{s−1} \binom{n + k − r}{k − r},

from which the statement immediately follows by induction. Theorem 5. Assume that k ≥ r. Then

B_{k}(x, t) = \frac{1}{(1 − x)^{r−1}} ∑_{i=1}^{k−r+1} \frac{α_{k−i}^{(≥r−1)}(t^{i}x, t)}{t^{i(s−1)} ∏_{j=1}^{i−1}(1 − t^{j}x)} + β_{k}(x, t),

where

β_{k}(x, t) = ∑_{i=0}^{s−1} \binom{i + k − 1}{k − 1}x^{i} + \frac{1}{(1 − x)^{r−1}} ∑_{i=0}^{s−1} \binom{i + k − r}{k − r}x^{i}

− ∑_{i=0}^{s−1} \binom{i + k − r}{k − r}x^{i} ∑_{n=0}^{s−1−i} \binom{n + r − 2}{r − 2}x^{n} − \frac{1}{t^{s−1}(1 − x)^{r−1}} ∑_{i=0}^{s−1} \binom{i + k − r}{k − r}(tx)^{i}.

Proof. For n ≥ s we have

b_{n,k} = b_{n,k}^{(≥r)} + ∑_{i=1}^{n} b_{i,r−1}b_{n−i,k}^{(≥r)}

= t^{n−s+1}b_{n,k−1}^{(≥r−1)} + ∑_{i=1}^{n−s} t^{n−i−s+1}b_{i,r−1}b_{n−i,k−1}^{(≥r−1)} + ∑_{i=n−s+1}^{n} b_{i,r−1}b_{n−i,k−1}^{(≥r−1)}.

Multiplying both sides of this equation by x^{n}, summing over n ≥ s and adding ∑_{n=0}^{s−1} b_{n,k}x^{n} to both sides, we obtain the equation

B_{k}(x, t)

= \frac{1}{t^{s−1}(1 − x)^{r−1}} B_{k−1}^{(≥r−1)}(tx, t) + ∑_{i=0}^{s−1} \binom{i + k − 1}{k − 1}x^{i} + \frac{1}{(1 − x)^{r−1}} ∑_{i=0}^{s−1} \binom{i + k − r}{k − r}x^{i}

− ∑_{i=0}^{s−1} \binom{i + k − r}{k − r}x^{i} ∑_{n=0}^{s−1−i} \binom{n + r − 2}{r − 2}x^{n} − \frac{1}{t^{s−1}(1 − x)^{r−1}} ∑_{i=0}^{s−1} \binom{i + k − r}{k − r}(tx)^{i},

from which, together with (2), the statement immediately follows.

Corollary 6. The generating function for the total number g_{k}(n) of r × s rectangles over all words belonging to W_{n,k}^{↗} is given by

\frac{x^{s} ∑_{i=0}^{k−r+1}(−1)^{i}\binom{i+s−2}{i}\binom{k−r+1+s}{s+i+1}x^{i}}{(1 − x)^{k+1}} .

Thus, for n ≥ s,

g_{k}(n) = ∑_{i=0}^{min\{k−r+1,n−s\}}(−1)^{i}\binom{i + s − 2}{i}\binom{k − r + 1 + s}{s + i + 1}\binom{n − s − i + k}{k}.

Proof. Let i ∈ [k − r + 1]. We have

\frac{∂}{∂t} \frac{α_{k−i}^{(≥r−1)}(t^{i}x, t)}{t^{i(s−1)} ∏_{j=1}^{i−1}(1 − t^{j}x)}

= \frac{(\frac{∂}{∂t}α_{k−i}^{(≥r−1)}(t^{i}x, t)) t^{i(s−1)} ∏_{j=1}^{i−1}(1 − t^{j}x) − α_{k−i}^{(≥r−1)}(t^{i}x, t) (\frac{∂}{∂t}t^{i(s−1)} ∏_{j=1}^{i−1}(1 − t^{j}x))}{(t^{i(s−1)} ∏_{j=1}^{i−1}(1 − t^{j}x))^{2}}.

We have

[t^{i(s−1)} ∏_{j=1}^{i−1}(1 − t^{j}x)]_{|t=1} = (1 − x)^{i−1},

[\frac{∂}{∂t}t^{i(s−1)} ∏_{j=1}^{i−1}(1 − t^{j}x)]_{|t=1} = i(1 − x)^{i−2} ((s − 1)(1 − x) − \frac{x(i − 1)}{2}) .

It is not hard to see that

[α_{k−i}^{(≥r−1)}(t^{i}x, t)]_{|t=1} = \begin{cases}0, & if i < k − r + 1; \\ \frac{1}{1−x}, & otherwise. \end{cases}

[\frac{∂}{∂t}α_{k−i}^{(≥r−1)}(t^{i}x, t)]_{|t=1} = \begin{cases}\frac{1}{1−x} ∑_{n=0}^{s−2}(s − 1 − n)\binom{n+k−r−i}{k−r−i}x^{n}, & if i < k − r + 1; \\ \frac{x(k−r+1)}{(1−x)^{2}}, & otherwise. \end{cases}

[\frac{∂}{∂t}β_{k}(x, t)]_{|t=1} = \frac{1}{(1 − x)^{r−1}} ∑_{n=0}^{s−2}(s − 1 − n)\binom{n + k − r}{k − r}x^{n}.

It follows that

[\frac{∂}{∂t}A_{k}(x, t)]_{|t=1}

= \frac{1}{(1 − x)^{r−1}} ∑_{i=1}^{k−r+1} [\frac{∂}{∂t} \frac{α_{k−i}^{(≥r−1)}(t^{i}x, t)}{t^{i(s−1)} ∏_{j=1}^{i−1}(1 − t^{j}x)}]_{|t=1} + [\frac{∂}{∂t}β_{k}(x, t)]_{|t=1}

= \frac{1}{(1 − x)^{r−1}} (∑_{i=1}^{k−r} \frac{∑_{n=0}^{s−2}(s − 1 − n)\binom{n+k−r−i}{k−r−i}x^{n}}{(1 − x)^{i}} + (k − r + 1)\frac{x(k − r + 2) − 2(s − 1)(1 − x)}{2(1 − x)^{k−r+2}})

+ \frac{1}{(1 − x)^{r−1}} ∑_{n=0}^{s−2}(s − 1 − n)\binom{n + k − r}{k − r}x^{n}

= \frac{1}{(1 − x)^{r−1}} ∑_{i=0}^{k−r} \frac{∑_{n=0}^{s−2}(s − 1 − n)\binom{n+k−r−i}{k−r−i}x^{n}}{(1 − x)^{i}} + (k − r + 1)\frac{x(k − r + 2) − 2(s − 1)(1 − x)}{2(1 − x)^{k+1}}

from which the assertion follows.

Example 7. For r = k = 2 and arbitrary s we have

g_{2}(n) = \binom{n − s + 2}{2}.

For r = s = 2 and arbitrary k we have

g_{k}(n) = \frac{n − 1}{n + 1}\binom{k}{2}\binom{n − 1 + k}{k},

which, for k = 3, 4 corresponds to \underline{A077414} and \underline{A105938} in the OEIS, respectively. For s = 1 and arbitrary k and r we have

g_{k}(n) = \binom{k − r + 2}{2}\binom{n − 1 + k}{k}

and Table 2 lists the corresponding sequences that we found in OEIS.

2.2 Smirnov words

We denote by S_{n,k} the set of Smirnov words (e.g., [5, Example 23 on p. 193]), i.e.,

S_{n,k} = {w_{1} ⋯ w_{n} ∈ [k]^{n} : w_{i} ≠ w_{i+1} for every i ∈ [n − 1]} .

Since there are no Smirnov words for k = 1, we assume that k ≥ 2. We distinguish between two cases, namely r = 1 and r ≥ 2.

k r OEIS
3 2 \underline{A027480}
4 2 \underline{A033487}
5 2 \underline{A266732}
6 2 \underline{A240440}
7 2 \underline{A266733}
4 3 \underline{A050534}
5 3 \underline{A253945}
6 3 \underline{A271040}

Table 2: The total number g_{k}(n) of r × 1 rectangles over all words of length n, for several values of k and r.

2.2.1 Rectangle capacity of size 1 × s

Denote by c_{n,k} = c_{n,k}(t) the distribution on S_{n,k} of the number of 1 × s rectangles and by C_{k}(x, t) the generating function of the numbers c_{n,k}. We shall need the following restrictions of S_{n,k}: Let

S_{n,k}^{(0)} = {w_{1} ⋯ w_{n} ∈ S_{n,k} : w_{j} > 1 for every j ∈ [n]}

and, for i ∈ [n], we define

S_{n,k}^{(i)} = {w_{1} ⋯ w_{n} ∈ S_{n,k} : w_{i} = 1 and w_{j} > 1 for every j ∈ [i − 1]} .

For 0 ≤ i ≤ n, let c_{n,k}^{(i)} be the restriction of c_{n,k} to S_{n,k}^{(i)}. Clearly,

|S_{n,k}| = \begin{cases}1, & if n = 0; \\ k(k − 1)^{n−1}, & otherwise. \end{cases}

|S_{n,k}^{(1)}| = \begin{cases}1, & if n = 0; \\ (k − 1)^{n−1}, & otherwise. \end{cases}

Theorem 8. We have

C_{2}(x, t) = \frac{2(t − 1)x^{s}}{(1 − tx)(1 − x)} + \frac{1 + x}{1 − x}  (3)

and, for k ≥ 3,

C_{k}(x, t) = \frac{(1 + tx) (γ_{k}(x, t) + δ_{k}(x, t)C_{k−1}(tx, t))}{1 + tx − txC_{k−1}(tx, t)},  (4)

where

γ_{k}(x, t) = \frac{1 + x − k(k − 1)^{s−1}x^{s}}{1 − (k − 1)x} − \frac{1 + tx − k(k − 1)^{s−1}(tx)^{s}}{t^{s−1}(1 − (k − 1)tx)} ,

δ_{k}(x, t) = \frac{1 − (k − 2)tx − (k − 1)^{s−1}(tx)^{s}}{t^{s−1}(1 − (k − 1)tx)} − \frac{tx}{1 + tx} \frac{(1 + x)(1 − ((k − 1)x)^{s−1})}{1 − (k − 1)x}.

Proof. For n ≥ 1, the set S_{n,2} consists of two words, namely 1212 ⋯ and 2121 ⋯, containing exactly n−s+1 1×s rectangles, each. It is easily verified that the corresponding generating function is given by (3). Assume now that k ≥ 3. For n ≥ s we have

c_{n,k} = c_{n,k}^{(0)} + ∑_{i=1}^{n} c_{n,k}^{(i)}

= c_{n,k−1} + ∑_{i=1}^{n−s+1} t^{i−1}c_{i−1,k−1}c_{n−i+1,k}^{(1)} + ∑_{i=n−s+2}^{n} t^{n−s+1}c_{i−1,k−1}c_{n−i+1,k}^{(1)},  (5)
c_{n,k}^{(1)} = t (c_{n−1,k} − c_{n−1,k}^{(1)}) .  (6)

Multiplying both sides of (6) by x^{n}, summing over n ≥ s and adding ∑_{n=0}^{s−1} c_{n,k}^{(1)}x^{n} to both sides, we obtain

C_{k}^{(1)}(x, t) = \frac{1}{1 + tx} (∑_{n=0}^{s−1} c_{n,k}^{(1)}x^{n} + tx (C_{k}(x, t) − ∑_{n=0}^{s−2} c_{n,k}x^{n}) + tx ∑_{n=0}^{s−2} c_{n,k}^{(1)}x^{n}) . (7)

Multiplying both sides of (5) by x^{n}, summing over n ≥ s and adding ∑_{n=0}^{s−1} c_{n,k}x^{n} to both sides, we obtain

C_{k}(x, t) = ∑_{n=0}^{s−1} c_{n,k}x^{n} + \frac{1}{t^{s−1}} (C_{k−1}(tx, t) − ∑_{n=0}^{s−1} c_{n,k−1}(tx)^{n})

+ C_{k−1}(tx, t) (C_{k}^{(1)}(x, t) − ∑_{n=0}^{s−1} c_{n,k}^{(1)}x^{n})

+ \frac{1}{t^{s−1}} ∑_{i=2}^{s} c_{s−i+1,k}^{(1)}(tx)^{s−i+1} (C_{k−1}(tx, t) − ∑_{n=0}^{i−2} c_{n,k−1}(tx)^{n}) .  (8)

Substituting (7) into (8), we obtain (4).

Corollary 9. The generating function for the total number h_{k}(n) of 1 × s rectangles over all words belonging to S_{n,k} is given by

\frac{x^{s} ∑_{i=1}^{k−1} i^{s−1}(i + 1)}{(1 − (k − 1)x)^{2}}.  (9)

Thus, for n ≥ s,

h_{k}(n) = (k − 1)^{n−s}(n − s + 1) ∑_{i=1}^{k−1} i^{s−1}(i + 1).

Proof. We have

[\frac{∂}{∂t}C_{2}(x, t)]_{|t=1} = \frac{2x^{s}}{(1 − tx)^{2}} .

Thus, (9) holds for k = 2. Assume now that k ≥ 3 and that (9) holds for k − 1. It is not hard to see that

[γ_{k}(x, t)]_{|t=1} = 0,
[\frac{∂}{∂t}γ_{k}(x, t)]_{|t=1} = \frac{x(s − 1) + s}{1 − (k − 1)x} − \frac{1 + x − k(k − 1)^{s−1}x^{s}}{(1 − (k − 1)x)^{2}} ,
[δ_{k}(x, t)]_{|t=1} = 1,
[\frac{∂}{∂t}δ_{k}(x, t)]_{|t=1} = 1 − s − \frac{x}{1 + x} [\frac{∂}{∂t}γ_{k}(x, t)]_{|t=1} ,
[C_{k}(x, t)]_{|t=1} = \frac{1 + x}{1 − (k − 1)x},
[\frac{∂}{∂x}C_{k}(x, t)]_{|t=1} = \frac{k}{(1 − (k − 1)x)^{2}} ,
[\frac{∂}{∂t}C_{k}(tx, t)]_{|t=1} = x [\frac{∂}{∂x}C_{k}(x, t)]_{|t=1} + [\frac{∂}{∂t}C_{k}(x, t)]_{|t=1} .

Differentiating (4) with respect to t and substituting t = 1, we obtain

[\frac{∂}{∂t}C_{k}(x, t)]_{|t=1} = [\frac{(1 + tx) (γ_{k}(x, t) + δ_{k}(x, t)C_{k−1}(tx, t))}{1 + tx − txC_{k−1}(tx, t)}]_{|t=1}

= \frac{(s − 1)(k − 1)x^{2} + (2 + (k − 2)s)x − s + 1}{(1 − (k − 1)x)^{2}}

+ \frac{(1 − (k − 2)x)^{2}}{(1 − (k − 1)x)^{2}} [\frac{∂}{∂t}C_{k−1}(x, t)]_{|t=1} + [\frac{∂}{∂t}γ_{k}(x, t)]_{|t=1}

= \frac{k(k − 1)^{s−1}x^{s}}{(1 − (k − 1)x)^{2}} + \frac{x^{s} ∑_{i=1}^{k−2} i^{s−1}(i + 1)}{(1 − (k − 1)x)^{2}}

= \frac{x^{s} ∑_{i=1}^{k−1} i^{s−1}(i + 1)}{(1 − (k − 1)x)^{2}}.

Example 10. For k = 2 and arbitrary s we have

h_{2}(n) = 2(n − s + 1).

For k = 3 and arbitrary s we have

h_{3}(n) = 2^{n−s}(n − s + 1)(2 + 3 · 2^{s−1}),

which, for s = 2, 3 corresponds to \underline{A241204} and \underline{A281200} in the OEIS, respectively.

2.2.2 Rectangle capacity of size r × s, where r ≥ 2

Denote by d_{n,k} = d_{n,k}(t) the distribution on S_{n,k} of the number of r × s rectangles and by D_{k}(x, t) the generating function of the numbers d_{n,k}. We shall need the following restrictions of S_{n,k}: for m ∈ [k] let

S_{n,k}^{(≥m)} = {w_{1} ⋯ w_{n} ∈ S_{n,k} : w_{i} ≥ m for every i ∈ [n]} ,
S̄_{n,k}^{(≥m)} = {w_{1} ⋯ w_{n} ∈ S_{n,k}^{(≥m)} : w_{1} ≠ m} .
S̄_{n,k} = {w_{1} ⋯ w_{n} ∈ S_{n,k} : w_{1} ≠ r − 1} .

Denote by d_{n,k}^{(≥m)} (resp., d̄_{n,k}^{(≥m)}, d̄_{n,k}) the restriction of d_{n,k} to S_{n,k}^{(≥m)} (resp., to S̄_{n,k}^{(≥m)}, S̄_{n,k}). Let D_{k}^{(≥m)}(x, t) (resp., D̄_{k}^{(≥m)}(x, t), D̄_{k}(x, t)) denote the generating function of the numbers d_{n,k}^{(≥m)} (resp., d̄_{n,k}^{(≥m)}, d̄_{n,k}). Clearly,

|S_{n,k}^{(≥m)}| = \begin{cases}1, & if n = 0; \\ (k − m + 1)(k − m)^{n−1}, & otherwise. \end{cases}
|S̄_{n,k}^{(≥m)}| = (k − m)^{n}.

Lemma 11. We have

D_{r}^{(≥r−1)}(x, t) = \frac{1 + x}{1 − x}  (10)

and, for k ≥ r + 1,

D_{k}^{(≥r−1)}(x, t) = (1 + x)\frac{\frac{1}{t^{s−1}} D_{k−1}^{(≥r−1)}(tx, t) + σ_{k}(x, t)}{−\frac{x}{t^{s−1}} D_{k−1}^{(≥r−1)}(tx, t) + ρ_{k}(x, t)},

where

σ_{k}(x, t) = \frac{1 + x − (k − r + 1)(k − r)^{s−1}x^{s}}{1 − (k − r)x} − \frac{1 + tx − (k − r + 1)(k − r)^{s−1}(tx)^{s}}{t^{s−1}(1 − (k − r)tx)} ,
ρ_{k}(x, t) = 1 − (k − r + 1)x^{2} \frac{1 − ((k − r)x)^{s−1}}{1 − (k − r)x} + x\frac{1 + tx − (k − r + 1)(k − r)^{s−1}(tx)^{s}}{t^{s−1}(1 − (k − r)tx)} .

Proof. For n ≥ 1, the set S_{n,r}^{(≥r−1)} consists of two words, namely r(r − 1)r(r − 1) ⋯ and (r − 1)r(r − 1)r(r − 1) ⋯, containing no r × s rectangles. Thus, (10) holds true in this case. Assume now that k ≥ r + 1. For n ≥ s we have

d_{n,k}^{(≥r−1)} = d_{n,k}^{(≥r)} + ∑_{i=1}^{n} d_{i−1,k}^{(≥r)}d̄_{n−i,k}^{(≥r−1)}

= t^{n−s+1}d_{n,k−1}^{(≥r−1)} + ∑_{i=1}^{s} d_{i−1,k−1}^{(≥r−1)}d̄_{n−i,k}^{(≥r−1)} + ∑_{i=s+1}^{n} t^{i−s}d_{i−1,k−1}^{(≥r−1)}d̄_{n−i,k}^{(≥r−1)},  (11)

d̄_{n,k}^{(≥r−1)} = d_{n,k}^{(≥r)} + ∑_{i=2}^{n} d_{i−1,k}^{(≥r)}d̄_{n−i,k}^{(≥r−1)}

= t^{n−s+1}d_{n,k−1}^{(≥r−1)} + ∑_{i=2}^{s} d_{i−1,k−1}^{(≥r−1)}d̄_{n−i,k}^{(≥r−1)} + ∑_{i=s+1}^{n} t^{i−s}d_{i−1,k−1}^{(≥r−1)}d̄_{n−i,k}^{(≥r−1)}.  (12)

Multiplying both sides of (11) by x^{n}, summing over n ≥ s and adding ∑_{n=0}^{s−1} d_{n,k}^{(≥r−1)}x^{n} to both sides, we obtain the equation

D_{k}^{(≥r−1)}(x, t)

= ∑_{n=0}^{s−1} d_{n,k}^{(≥r−1)}x^{n} + \frac{1}{t^{s−1}} (D_{k−1}^{(≥r−1)}(tx, t) − ∑_{n=0}^{s−1} d_{n,k−1}^{(≥r−1)}(tx)^{n}) − ∑_{i=1}^{s} d_{i−1,k−1}^{(≥r−1)}x^{i} ∑_{n=0}^{s−i−1} d̄_{n,k}^{(≥r−1)}x^{n}

+ D̄_{k}^{(≥r−1)}(x, t) (∑_{i=1}^{s} d_{i−1,k−1}^{(≥r−1)}x^{i} + \frac{x}{t^{s−1}} (D_{k−1}^{(≥r−1)}(tx, t) − ∑_{n=0}^{s−1} d_{n,k−1}^{(≥r−1)}(tx)^{n})) .  (13)

Multiplying both sides of (12) by x^{n}, summing over n ≥ s and adding ∑_{n=0}^{s−1} d̄_{n,k}^{(≥r−1)}x^{n} to both sides, we obtain the equation

D̄_{k}^{(≥r−1)}(x, t) (1 − \frac{x}{t^{s−1}} D_{k−1}^{(≥r−1)}(tx, t) − ∑_{i=2}^{s} d_{i−1,k−1}^{(≥r−1)}x^{i} + \frac{x}{t^{s−1}} ∑_{n=0}^{s−1} d_{n,k−1}^{(≥r−1)}(tx)^{n})

= \frac{1}{t^{s−1}} D_{k−1}^{(≥r−1)}(tx, t) + ∑_{n=0}^{s−1} d̄_{n,k}^{(≥r−1)}x^{n} − \frac{1}{t^{s−1}} ∑_{n=0}^{s−1} d_{n,k−1}^{(≥r−1)}(tx)^{n}

− ∑_{i=2}^{s} d_{i−1,k−1}^{(≥r−1)}x^{i} ∑_{n=0}^{s−i−1} d̄_{n,k}^{(≥r−1)}x^{n}.

Substituting this into (13), the assertion follows.

Theorem 12. We have

D_{r}(x, t) = \frac{1 + x}{1 − x}

and, for k ≥ r + 1,

D_{k}(x, t) = (1 + x)\frac{\frac{1}{t^{s−1}} D_{k−1}^{(≥r−1)}(tx, t) + σ_{k}(x, t)}{−\frac{(r−1)x}{t^{s−1}}D_{k−1}^{(≥r−1)}(tx, t) − (r − 2)(1 + x) + (r − 1)ρ_{k}(x, t)}.  (14)

Proof. We have

d_{n,k} = d_{n,k}^{(≥r)} + (r − 1) ∑_{i=1}^{n} d_{i−1,k}^{(≥r)}d̄_{n−i,k}

= t^{n−s+1}d_{n,k−1}^{(≥r−1)} + (r − 1) ∑_{i=1}^{s} d_{i−1,k−1}^{(≥r−1)}d̄_{n−i,k} + (r − 1) ∑_{i=s+1}^{n} t^{i−s}d_{i−1,k−1}^{(≥r−1)}d̄_{n−i,k}, (15)

d̄_{n,k} = d_{n,k}^{(≥r)} + (r − 1) ∑_{i=2}^{n} d_{i−1,k}^{(≥r)}d̄_{n−i,k} + (r − 2)d̄_{n−1,k}

= t^{n−s+1}d_{n,k−1}^{(≥r−1)} + (r − 1) ∑_{i=2}^{s} d_{i−1,k−1}^{(≥r−1)}d̄_{n−i,k}

+ (r − 1) ∑_{i=s+1}^{n} t^{i−s}d_{i−1,k−1}^{(≥r−1)}d̄_{n−i,k} + (r − 2)d̄_{n−1,k}.  (16)

Multiplying both sides of (15) by x^{n}, summing over n ≥ s and adding ∑_{n=0}^{s−1} d_{n,k}x^{n} to both sides, we obtain

D_{k}(x, t)

= ∑_{n=0}^{s−1} d_{n,k}x^{n} + \frac{1}{t^{s−1}} (D_{k−1}^{(≥r−1)}(tx, t) − ∑_{n=0}^{s−1} d_{n,k−1}^{(≥r−1)}(tx)^{n}) − (r − 1) ∑_{i=1}^{s} d_{i−1,k−1}^{(≥r−1)}x^{i} ∑_{n=0}^{s−i−1} d̄_{n,k}x^{n}

+ D̄_{k}(x, t) ((r − 1) ∑_{i=1}^{s} d_{i−1,k−1}^{(≥r−1)}x^{i} + \frac{(r − 1)x}{t^{s−1}} (D_{k−1}^{(≥r−1)}(tx, t) − ∑_{n=0}^{s−1} d_{n,k−1}^{(≥r−1)}(tx)^{n})) . (17)

Multiplying both sides of (16) by x^{n}, summing over n ≥ s and adding ∑_{n=0}^{s−1} d̄_{n,k}x^{n} to both sides, we obtain

D̄_{k}(x, t)

= ∑_{n=0}^{s−1} d̄_{n,k}x^{n} + \frac{1}{t^{s−1}} (D_{k−1}^{(≥r−1)}(tx, t) − ∑_{n=0}^{s−1} d_{n,k−1}^{(≥r−1)}(tx)^{n})

+ (r − 1) ∑_{i=2}^{s} d_{i−1,k−1}^{(≥r−1)}x^{i} (D̄_{k}(x, t) − ∑_{n=0}^{s−i−1} d̄_{n,k}x^{n})

+ \frac{(r − 1)x}{t^{s−1}} D̄_{k}(x, t) (D_{k−1}^{(≥r−1)}(tx, t) − ∑_{n=0}^{s−1} d_{n,k−1}^{(≥r−1)}(tx)^{n}) + (r − 2)x (D̄_{k}(x, t) − ∑_{n=0}^{s−2} d̄_{n,k}x^{n}) .

Solving for D̄_{k}(x, t) and substituting it into (17), the assertion follows.

Corollary 13. The generating function for the total number i_{k}(n) of r × s rectangles over all words belonging to S_{n,k} is given by

\frac{x^{s} ∑_{i=1}^{k−r} i^{s−1}(i + 1)}{(1 − (k − 1)x)^{2}}.

Thus, for n ≥ s,

i_{k}(n) = (k − 1)^{n−s}(n − s + 1) ∑_{i=1}^{k−r} i^{s−1}(i + 1).

Proof. It is not hard to see that

[D_{k}^{(≥r−1)}(x, t)]_{|t=1} = \frac{1 + x}{1 − (k − r + 1)x},
[\frac{∂}{∂x}D_{k}^{(≥r−1)}(x, t)]_{|t=1} = \frac{k − r + 2}{(1 − (k − r + 1) x)^{2}} ,

[\frac{∂}{∂t}D_{k}^{(≥r−1)}(x, t)]_{|t=1} = \frac{x^{s} ∑_{n=0}^{k−r} n^{s−1}(n + 1)}{(1 − (k − r + 1)x)^{2}}.

We omit the rest of the details, which are very similar to those in the proof of Corollary 9.

3 Discussion

We mentioned in the introduction the works of Cakić et al. [3] and Archibald et al [1], who studied rectangle capacity of size 1 × 2 and 2 × 2 in set partitions, respectively. Another family of restricted words, which draws much attention in recent years, is inversion sequences (e.g., [2] and [13]). To the best of our knowledge, this family was not studied at all in terms of rectangle capacity. Thus, a possible direction for future work would be generalizing previous results on rectangle capacity in set partitions and initiating the study thereof in inversion sequences.

4 Acknowledgments

We thank the anonymous referee for the careful reading of the manuscript and for the helpful suggestions.

References

[1] M. Archibald, A. Blecher, C. Brennan, A. Knopfmacher, and T. Mansour, Two by two squares in set partitions, Math. Slovaca 70 (2020), 29–40.

[2] M. Archibald, A. Blecher, and A. Knopfmacher, Parameters in inversion sequences, Math. Slovaca 73 (2023), 551–564.

[3] N. Cakić, T. Mansour, and A. Sh. Shabani, Counting 1 × 2 rectangles in set partitions, J. Difference Equ. Appl. 25 (2019), 708–715.

[4] D. Callan, T. Mansour, and J. L. Ramírez, Statistics on bargraphs of Catalan words, J. Autom. Lang. Comb. 26 (2021), 177–196.

[5] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[6] B. Ellzey and M. L, Wachs, On enumerators of Smirnov words by descents and cyclic descents, J. Comb. 11 (2020), 413–456.

[7] U. Freiberg, C. Heuberger, and H. Prodinger, Application of Smirnov words to waiting time distributions of runs, Electron. J. Combin. 24, 2017.

[8] S. Fried and T. Mansour, Counting r × s rectangles in (Catalan) words, arxiv preprint arXiv:2405.06962 [math.CO], 2024. Available at https://arxiv.org/abs/2405.06962.

[9] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Courier Corporation, 2004.

[10] A. Iraci, P. Nadeau, and A. V. Wyngaerd, Smirnov words and the Delta conjectures, Adv. Math. 452 (2024), article 109793.

[11] T. Mansour and A. S. Shabani, Bargraphs in bargraphs, Turkish J. Math. 42 (2018), 2763–2773.

[12] T. Mansour and A. S. Shabani, Enumerations on Bargraphs, Discrete Math. Lett. 2 (2019), 65–94.

[13] T. Mansour and M. Shattuck, Statistics on bargraphs of inversion sequences of permutations, Discrete Math. Lett. 4 (2020), 42–49.

[14] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, OEIS Foundation Inc.,

https://oeis.org.

2020 Mathematics Subject Classification: Primary 05A05; Secondary 05A15. Keywords: rectangle capacity, bargraph, generating function, nondecreasing word, Smirnov word.

(Concerned with sequences \underline{A027480}, \underline{A033487}, \underline{A045943}, \underline{A050534}, \underline{A059845}, \underline{A077414}, \underline{A105938}, \underline{A115067}, \underline{A140090}, \underline{A140091}, \underline{A140672}, \underline{A140673}, \underline{A140674}, \underline{A140675}, \underline{A151542}, \underline{A240440}, \underline{A241204}, \underline{A253945}, \underline{A266732}, \underline{A266733}, \underline{A271040}, \underline{A281200}, and \underline{A370238}.)

Received June 27 2024; revised version received October 1 2024. Published in Journal of Integer Sequences, November 26 2024.

Return to Journal of Integer Sequences home page.