Enumeration of Partitions by Long Rises, Levels, and Descents

Toufik Mansour Department of Mathematics Haifa University 31905 Haifa Israel

                     toufik@math.haifa.ac.il

Augustine O. Munagi

The John Knopfmacher Centre for Applicable Analysis and Number Theory

School of Mathematics University of the Witwatersrand Johannesburg 2050 South Africa

                     munagi@maths.wits.ac.za

Abstract

When the partitions of [n] = {1, 2, …, n} are identified with the restricted growth functions on [n], under a known bijection, certain enumeration problems for classical word statistics are formulated for set partitions. In this paper we undertake the enumeration of partitions of [n] with respect to the number of occurrences of rises, levels and descents, of arbitrary integral length not exceeding n. This approach extends previously known cases. We obtain ordinary generating functions for the number of partitions with a specified number of occurrences of the three statistics. We also derive explicit formulas for the number of occurrences of each statistic among all partitions, besides other combinatorial results.

1 Introduction

This paper is concerned with an aspect of the general enumeration problem for subword patterns which continues to attract intense research activity. Much of the impetus came from Carlitz and collaborators, in the 1970’s, with several papers on rises, levels and descents in selected classes of words which include permutations and compositions (see, for example, [3, 4, 6, 5]). Recently, Burstein and Mansour [2] studied the set of k-ary words containing a specified number of subword partterns. Heubach and Mansour [9] found generating functions for the number compositions of n according to the number of rises, descents and levels. Later the authors [8] obtained enumerative results for compositions of n according to the number of occurrences of a subword of length three. Elizalde and Noy [7] studied the permutations of length n according to the number occurrences of a fixed word of length three or four. More recently, Mansour and Sirhan [11, Theorem 2.1] found the following generating function for the number of k-ary n-words according to the number of t-levels:

W_{t}(x, y; k) = (1 − \frac{k(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy))}{1 + x + ⋯ + x^{t−2} + x^{t−1}/(1 − xy)})^{−1} .  (1.1)

In this paper we specialize to set partitions, and extend several of the above results. More precisely, we find the generating functions for the number of partitions of [n] according to the number occurrences of t-levels, t-rises and t-descents, defined below.

A partition of [n] = {1, 2, …, n} is a decomposition of [n] into non-overlapping subsets or blocks B_{1}, B_{2}, …, B_{k}, 1 ≤ k ≤ n, which are listed in the increasing order of their least elements. We will represent a partition π = B_{1}, B_{2}, …, B_{k} in the canonical sequential form π = π_{1}π_{2} ⋯ π_{n} such that j ∈ B_{π_{j}}, 1 ≤ j ≤ n. Thus a sequence π = π_{1}π_{2} ⋯ π_{n} over the alphabet [k] represents a partition of [n] with k blocks if and only if it is a restricted growth function on [n] satisfying {π_{1}, π_{2}, ⋯, π_{n}} = [k] (see [14] for details). For instance, 12312424 is the canonical sequential form of the partition {1, 4}, {2, 5, 7}, {3}, {6, 8} of [8].

Partitions will be identified with their corresponding canonical sequences throughout, and this platform will be employed in the study of three word-statistics. We undertake the enumeration of partitions according to the number of occurrences of rises, levels and descents by considering t letters at a time, t > 1. This generalizes the work done in an earlier paper [10] which dealt with the case t = 2.

Let π = π_{1}π_{2} ⋯ π_{n} be any partition represented by its canonical sequence. Given an integer t > 1 we say that π has a t-rise at i if π_{i} < π_{i+1} < ⋯ < π_{i+t−1}, and a t-level if π_{i} = π_{i+1} = ⋯ = π_{i+t−1}. Similarly for a t-descent. For example, if t = 3, then the partition 1211123421 of [10] has two 3-rises (at i = 5 and i = 6), one 3-level (at i = 3) and one 3-descent (at i = 8).

The set of partitions of [n] will be denoted by 𝔓_{n} and the subset of partitions with k blocks by 𝔓_{n,k}. The cardinality of 𝔓_{n,k} is the Stirling number of the second kind S(n, k), in the notation of [12].

Our first main result is the ordinary generating function for the number of partitions of [n] with a given number of t-levels (Theorem 2.1). This is followed shortly by a “generic” generating function for the number of partitions of [n] with a given number of t-rises (Theorem 3.3). It is generic in the sense that it yields an explicit ordinary generating function when t is specified. We illustrate the derivations with t = 2 and t = 3.

Expectedly, an analogous (but simpler) generating function (than that of t-rises) is obtained for the number of t-descents (Theorem 4.1).

Fundamental to our results is the observation that a partition π of [n] with k blocks, can be decomposed uniquely as

π = π′kw,  (1.2)

where π′ is a partition of [n] with k − 1 blocks and w is a k-ary word, i.e., a word over the alphabet [k].

Between, the main theorems we provide examples with a few special cases and obtain some combinatorial results requiring direct proof.

2 Enumeration of partitions by t-levels

Let L_{t}(x, y) be the ordinary generating function for the number of partitions of [n] according to the number of t-levels, that is,

L_{t}(x, y) = ∑_{n≥0} ∑_{π∈𝔓_{n}} x^{n}y^{#t−levels in π}.

In order to evaluate L_{t}(x, y), we modify the above notation to the case of partitions of [n] with k blocks, that is, we denote the ordinary generating function for the number of partitions of [n] with k blocks and t-levels by

L_{t}(x, y; k) = ∑_{n≥0} ∑_{π∈𝔓_{n,k}} x^{n}y^{#t−levels in π}.

Note that a refinement of (1.1) can be obtained by using [11, Section 2.1] and (1.1) to prove that the generating function W_{t}(x, y; k, a) for the number of k-ary words σ of length n with σ_{1} = a according to the number of t-levels is given by

\begin{aligned}W_{t}(x, y; k, a) & = \frac{x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy)}{1 + x + ⋯ + x^{t−2} + x^{t−1}/(1 − xy)}W_{t}(x, y; k) \\ & = \frac{x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy)}{1 − (k − 1)(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy))}. \end{aligned}  (2.1)

We now obtain an explicit expression for L_{t}(x, y; k) by means of (2.1) and (1.2). Note that (1.2) implies L_{t}(x, y; k) = L_{t}(x, y; k − 1)W_{t}(x, y; k, k) for all k ≥ 1 with initial condition L_{t}(x, y; 0) = 1. Hence, by (2.1) we obtain, for all k ≥ 1,

L_{t}(x, y; k) = L_{t}(x, y; k − 1)\frac{x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy)}{1 − (k − 1)(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy))},

which implies that

L_{t}(x, y; k) = \frac{(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy))^{k}}{∏_{j=0}^{k−1}(1 − j(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy)))}.

Since L_{t}(x, y) = 1 + ∑_{k≥1} L_{t}(x, y; k) we obtain the following result.

Theorem 2.1. The ordinary generating function for the number of partitions of [n] with k blocks according to the number of t-levels is given by

L_{t}(x, y; k) = \frac{(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy))^{k}}{∏_{j=0}^{k−1}(1 − j(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy)))}.

Moreover, the ordinary generating function for the number of partitions of [n] according to the number of t-levels is given by

L_{t}(x, y) = 1 + ∑_{k≥1} \frac{(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy))^{k}}{∏_{j=0}^{k−1}(1 − j(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}/(1 − xy)))}.

As a corollary of the above theorem we obtain the following result.

Corollary 2.2. The number of t-levels in all the partitions of [n] with k blocks is given by

k ∑_{i=0}^{n+1−t} S(i, k) + ∑_{j=2}^{k}(j − 1) ∑_{i=0}^{n−t} j^{n−t−i}S(i, k).

Proof. Differentiating the generating function in the statement of Theorem 2.1, and then substituting y = 1, we have

∑_{n≥0} ∑_{π∈𝔓_{n,k}}(#t − levels in π)x^{n} = \frac{kx^{k−1+t}}{(1 − x) ∏_{j=1}^{k}(1 − jx)} + \frac{x^{k+t}}{(1 − x) ∏_{j=1}^{k}(1 − jx)} ∑_{j=2}^{k} \frac{j − 1}{1 − jx},

which is equivalent to (use the fact that \frac{x^{k}}{∏_{j=0}^{k}(1−jx)} = ∑_{n≥0} S(n, k)x^{n}):

∑_{n≥0} ∑_{π∈𝔓_{n,k}}(#2 − rises in π)x^{n}

= kx^{t−1} ∑_{n≥0} S(n, k)x^{n} ∑_{n≥0} x^{n} + x^{t} ∑_{n≥0} S(n, k)x^{n} ∑_{j=2}^{k}(j − 1) ∑_{n≥0} j^{n}x^{n}.

Thus, by collecting the x^{n} coefficient we obtain the desired result.

2.1 Some Special Cases

It follows from Theorem 2.1 that the ordinary generating function for the number of partitions of [n] with k blocks without t-levels is given by

L_{t}(x, 0; k) = \frac{(x + x^{2} + ⋯ + x^{t−2} + x^{t−1})^{k}}{∏_{j=0}^{k−1}(1 − j(x + x^{2} + ⋯ + x^{t−2} + x^{t−1}))}.

In particular, we obtain for verification,

L_{2}(x, 0; k) = \frac{x^{k}}{(1 − x)(1 − 2x) ⋯ (1 − (k − 1)x)} = ∑_{n} S(n − 1, k − 1)x^{n}.

That is (see [10] for a bijective proof), the number of k-partitions of [n] without levels is given by S(n − 1, k − 1). In a similar manner, it can be shown that

L_{3}(x, 0; k) = L_{2}(x + x^{2}, 0; k) = ∑_{n} ∑_{r=0}^{⌊n/2⌋} \binom{n − r}{r}S(n − 1 − r, k − 1)x^{n}.

That is, the number of k-partitions of [n] without 3-levels is given by

∑_{r=0}^{⌊n/2⌋} \binom{n − r}{r}S(n − 1 − r, k − 1).

And so forth.

Direct special cases of Theorem 2.1 can also be explicitly stated. For instance,

L_{2}(x, y; k) = \frac{(x/(1 − xy))^{k}}{∏_{j=0}^{k−1}(1 − j(x/(1 − xy)))} = ∑_{n} ∑_{r} \binom{n − 1}{r}S(n − 1 − r, k − 1)x^{n}y^{r}.

So the number of partitions of [n] with k blocks and r occurrences of 2-levels is given by \binom{n−1}{r}S(n − 1 − r, k − 1). Similarly we have

L_{3}(x, y; k) = \frac{(x + x^{2}/(1 − xy))^{k}}{∏_{j=0}^{k−1}(1 − j(x + x^{2}/(1 − xy)))}.

It is a routine exercise to show that the coefficient of x^{n}y^{r} in the expansion of L_{3}(x, y; k), and hence the number of k-partitions of [n] with r occurrences of 3-levels, is given by

∑_{v=1}^{r} ∑_{j=v}^{⌊(n−r)/2⌋} \binom{r − 1}{v − 1}\binom{j}{r}\binom{n − r − j}{j}S(n − r − j − 1, k − 1).

Analogous formulas for higher values of t are clearly possible. Table 1 shows the numbers of 2-levels and 3-levels in the partitions of [n] for n = 0, 1, …, 10. The sequence numbers in the encyclopedia of integer sequences are given in the last column, except where a sequence is “new”, that is, not presently in [13].

3 Enumeration of partitions by t-rises

In this section we consider the generating function for the number of partitions of [n] according to the number of t-rises,

R_{t}(x, y) = ∑_{n≥0} ∑_{π∈𝔓_{n}} x^{n}y^{#t−rises in π}.

2-levels\n 0 1 2 3 4 5 6 7  8  9 Sequence in [13]
0  1 1 1 2 5 15 52 203 877 4140  \underline{A000110}
1  0 0 1 2 6 20 75 312 1421 7016  \underline{A052889}
2  0 0 0 1 3 12 50 225 1092 5684  \underline{A105479}
3  0 0 0 0 1 4 20 100 525 2912  \underline{A105480}
4  0 0 0 0 0 1 5 30 175 1050  \underline{A105481}
3-levels\n 0 1 2 3 4 5 6 7  8  9 Sequence in [13]
0  1 1 2 4 12 41 159 685 3233 16534  “new”
1  0 0 0 1 2 8 32 141 672 3451  \underline{A105483}
2  0 0 0 0 1 2 9 38 177 882  \underline{A105484}
3  0 0 0 0 0 1 2 10 44 215  \underline{A105485}
4  0 0 0 0 0 0 1 2 11  50  \underline{A105486}

Table 1: Number of partitions of [n] with 2-levels and 3-levels

as well as the generating function for the number of partitions of [n] with k blocks according to the number of t-rises,

R_{t}(x, y; k) = ∑_{n≥0} ∑_{π∈𝔓_{n,k}} x^{n}y^{#t−rises in π}.

For rises the decomposition (1.2) gives

R_{t}(x, y; k) = xR_{t}^{(1)}(x, y; k − 1)U_{t}(x, y; k) = ∑_{n≥0} ∑_{π∈𝔓_{n,k−1}} x^{n}y^{#t−rises in (πk)}U_{t}(x, y; k), (3.1)

where U_{t}(x, y; k) is the ordinary generating function for the number of k-ary words of length n according to the number of t-rises, that is, U_{t}(x, y; k) = ∑_{n≥0} ∑_{w} x^{n}y^{#t−rises in w} such that the internal sum is over all k-ary words w of length n.

Lemma 3.1. The ordinary generating function U_{t}^{(s)}(x, y; k) for the number of (k + s)-ary words w(k + 1)(k + 2) ⋯ (k + s), w is k-ary word, of length n + s according to number of t-rises is given by

U_{t}^{(s)}(x, y; k) = \frac{U_{t}^{(s)}(x, y; k − 1) + xU_{t}^{(s+1)}(x, y; k − 1) − xU_{t}^{(1)}(x, y; k − 1)}{1 − xU_{t}^{(1)}(x, y; k − 1)}

for all s = 0, 1, …, t − 1,

U_{t}^{(t)}(x, y; k) = yU_{t}^{(t−1)}(x, y; k) and U_{t}^{(0)}(x, y; k) = U_{t}(x, y; k),

with the initial condition U_{t}^{(s)}(x, y; k) = \frac{1}{1−kx} for all s + k ≤ t − 1.

Proof. The equalities

U_{t}^{(t)}(x, y; k) = yU_{t}^{(t−1)}(x, y; k), U_{t}^{(0)}(x, y; k) = U_{t}(x, y; k), and U_{t}^{(s)}(x, y; k) = \frac{1}{1 − kx},

with s + k ≤ t − 1, hold from the definitions. Assume 0 ≤ s ≤ t − 1. We derive a functional equation for U_{t}^{(s)}(x, y; k). Let w be any k-ary word w contains the letter k exactly m times, and let us consider the following cases:

• The case m = 0. The contribution in this case is U_{t}^{(s)}(x, y; k − 1).

• The case m > 0. In this case w can be decomposed as w = w^{(1)}kw^{(2)}k ⋯ w^{(m)}kw^{(m+1)}. By considering the two cases, with w^{(m+1)} being either empty or nonempty, we obtain that the contribution of this case equals

x^{m}(U_{t}^{(1)}(x, y; k − 1))^{m−1}U_{t}^{(s+1)}(x, y; k − 1) + x^{m}(U_{t}^{(1)}(x, y; k − 1))^{m}(U_{t}^{(s)}(x, y; k − 1) − 1).

Summing over all possible values of m ≥ 0 we obtain that

U_{t}^{(s)}(x, y; k) = U_{t}^{(s)}(x, y; k − 1) + ∑_{m≥1} x^{m}(U_{t}^{(1)}(x, y; k − 1))^{m−1}U_{t}^{(s+1)}(x, y; k − 1)
+ ∑_{m≥1} x^{m}(U_{t}^{(1)}(x, y; k − 1))^{m}(U_{t}^{(s)}(x, y, k − 1) − 1)
= U_{t}^{(s)}(x, y; k − 1) + \frac{xU_{t}^{(s+1)}(x,y;k−1)+xU_{t}^{(1)}(x,y;k−1)(U_{t}^{(s)}(x;y,k−1)−1)}{1−xU_{t}^{(1)}(x,y;k−1)}
= \frac{U_{t}^{(s)}(x,y;k−1)+xU_{t}^{(s+1)}(x,y;k−1)−xU_{t}^{(1)}(x,y;k−1)}{1−xU_{t}^{(1)}(x,y;k−1)},

as claimed.

Lemma 3.2. The ordinary generating function R_{t}^{(s)}(x, y; k) for the number of partitions π(k + 1)(k + 2) ⋯ (k + s), π a partition of [n] with k blocks, of length n + s according to number of t-rises is given by

R_{t}^{(s)}(x, y; k) = xR_{t}^{(s+1)}(x, y; k − 1) + xR_{t}^{(1)}(x, y; k − 1)(U_{t}^{(s)}(x, y; k) − 1),

for all s = 1, 2, …, t − 1,

R_{t}^{(t)}(x, y; k) = yR_{t}^{(t−1)}(x, y; k),

with the initial condition R_{t}^{(s)}(x, y; k) = \frac{x^{k}}{(1−x)(1−2x)···(1−kx)} for all s + k ≤ t − 1.

Proof. The equality R_{t}^{(t)}(x, y; k) = yR_{t}^{(t−1)}(x, y; k) and R_{t}^{(s)}(x, y; k) = \frac{x^{k}}{(1−x)(1−2x)···(1−kx)} with s + k ≤ t − 1 hold from the definitions. Assume 0 ≤ s ≤ t − 1. Let us write an equation for R_{t}^{(s)}(x, y; k). Let π be any partition with k blocks, then π(k + 1) ⋯ (k + s) can be written as π′kπ′′(k + 1) ⋯ (k + s), where π′ is a partition with k − 1 blocks and π′′ is a k-ary word. By considering the cases that π′′ is empty or nonempty, we obtain that

R_{t}^{(s)}(x, y; k) = xR_{t}^{(s+1)}(x, y; k − 1) + xR_{t}^{(1)}(x, y; k − 1)(U_{t}^{(s)}(x, y; k) − 1),

as requested.

Now we solve the system of recurrence relations in the statement of Lemma 3.1. It is not hard to see by induction on s that there exists a solution of the following form

U_{t}^{(s)}(k) = U_{t}^{(s)}(x, y; k) = \frac{U_{t}^{′(s)}(x, y; k)}{U_{t}^{′′(1)}(x, y; k)},

where

\{ \begin{matrix}U_{t}^{′(s)}(k) = U_{t}^{′(s)}(k − 1) + xU_{t}^{′(s+1)}(k − 1) − xU_{t}^{′(1)}(k − 1), \\ Ut^{′′}(k) = Ut^{′′}(k − 1) − xU_{t}^{′(1)}(k − 1). \end{matrix}  (3.2)

Hence, for all k ≥ 0

U_{t}^{(s)}(k) = \frac{U_{t}^{′(s)}(k)}{1 − x ∑_{j=0}^{k−1} U_{t}^{′(1)}(j)}.  (3.3)

In order to get an explicit formula for U_{t}^{′(s)}(k), we rewrite the recurrence relations in Lemmas 3.1-3.2 and (3.2) in terms of matrices. Define

U′_{t}(k) = ( U_{t}^{′(1)}(k) ; U_{t}^{′(2)}(k) ; ⋮ ; U_{t}^{′(t−1)}(k) ) and R_{t}(k) = ( R_{t}^{(1)}(k) ; R_{t}^{(2)}(k) ; ⋮ ; R_{t}^{(t−1)}(k) ) .

Then Lemmas 3.1-3.2 and (3.2) can be reformulated as follows.

Theorem 3.3. Let t ≥ 1. Then

U′_{t}(k) = A^{k} · 1 and R_{t}(k) = x^{k} (∏_{j=1}^{k} B_{j}) · 1,

where 1 = (1, 1, ⋯, 1)^{T} is a vector with t − 1 coordinates,

A = I + x ( −1 1 0 ⋯ 0 ; −1 0 1 ⋯ 0 ; ⋮ ; −1 0 0  1 ; −1 0 0  y ) , B_{j} = ( U_{t}^{(1)}(j) − 1 1 0 ⋯ 0 ; U_{t}^{(2)}(j) − 1 0 1 ⋯ 0 ; ⋮ ; U_{t}^{(t−2)}(j) − 1 0 0 ⋯ 1 ; U_{t}^{(t−1)}(j) − 1 0 0 ⋯ y ) ,

and I the unit matrix of order t − 1 with U_{t}^{(s)}(j) = \frac{U_{t}^{′(s)}(j)}{1−x ∑_{i=0}^{k−1} U_{t}^{′(1)}(i)} for all j = 1, 2, …, k.

Proof. Rewriting Lemma 3.1 together with (3.2) in terms of matrices, we obtain that U′_{t}(k) = A · U′_{t}(k − 1), for all k ≥ 1. Rewriting Lemma 3.2 in matrices forms, we obtain that R_{t}(k) = B_{k} · R_{t}(k − 1), for all k ≥ 1. Thus, R_{t}(k) = x^{k} (∏_{j=1}^{k} B_{j}) · R_{t}(0). Using the initial

condition U′_{t}(0) = R_{t}(0) = 1, we arrive at U′_{t}(k) = A^{k} · 1 and R_{t}(k) = x^{k} (∏_{j=1}^{k} B_{j}) · 1, as claimed.

3.1 The case t = 2

Now let us consider the case t = 2. Theorem 3.3 for t = 2 gives U_{2}^{′(1)}(x, y; k) = (1 − x + xy)^{k} for all k ≥ 0. Thus, by (3.3) we have that

U_{2}^{(1)}(x, y; k) = \frac{(1 − x + xy)^{k}}{1 − x ∑_{j=0}^{k−1}(1 − x + xy)^{j}} ,

which is equivalent to

U_{2}^{(1)}(x, y; k) = \frac{(1 − x + xy)^{k}}{1 − \frac{1−(1−x+xy)^{k}}{1−y}} = \frac{(1 − y)(1 − x + xy)^{k}}{(1 − x + xy)^{k} − y} .  (3.4)

This implies that (see Lemma 3.1 for s = 0)

U_{2}(x, y; k) = \frac{U_{2}(x, y; k − 1)}{1 − \frac{x(1−y)(1−x+xy)^{k−1}}{(1−x+xy)^{k−1}−y}}

and U_{2}(x, y; 1) = \frac{1}{1−x}, thus we obtain that

U_{2}(x, y; k) = \frac{1}{∏_{j=0}^{k−1} (1 − \frac{x(1−y)(1−x+xy)^{j}}{(1−x+xy)^{j}−y} )}.  (3.5)

On the other hand, Theorem 3.3 for t = 2 gives R_{2}^{(1)} = x^{k} ∏_{j=1}^{k}(U_{t}^{(1)}(x, y; j) − 1 + y), and by (3.4) we get that

R_{2}^{(1)}(x, y; k) = \frac{x^{k}y^{k}(1 − y)^{k}}{∏_{j=1}^{k}(1 − x + xy)^{j} − y} .

Thus using (3.1) with (3.5) we obtain the following result.

Theorem 3.4. The ordinary generating function for the number of partitions of [n] with k blocks according to the number of 2-rises is given by

\frac{x^{k}y^{k−1}(1 − y)^{k}}{∏_{j=1}^{k} ((1 − x + xy)^{j} − y)}.

From the above theorem we deduce the number of the 2-rises in all the partitions of [n] with k blocks, as follows:

Corollary 3.5. The number of 2-rises in all the partitions of [n] with k blocks is given by

(k − 1)S(n, k) + ∑_{j=2}^{k} \binom{j}{2} ∑_{i=k}^{n−2} j^{n−2−i}S(i, k).

Proof. Differentiating the generating function in the statement of Theorem 3.4 and then substituting y = 1 we get that

∑_{n≥0} ∑_{π∈𝔓_{n,k}}(#2 − rises in π)x^{n} = \frac{x^{k}}{∏_{j=1}^{k} 1 − jx} (k − 1 + x^{2} ∑_{j=2}^{k} \frac{\binom{j}{2}}{1 − jx}) ,

which is equivalent (use the fact that \frac{x^{k}}{∏_{j=0}^{k} 1−jx} = ∑_{n≥0} S_{n,k}x^{n}) to

∑_{n≥0} ∑_{π∈𝔓_{n,k}}(#2 − rises in π)x^{n} = (k − 1) ∑_{n≥0} S(n, k)x^{n} + ∑_{n≥2} x^{n} ∑_{j=2}^{k} \binom{j}{2} ∑_{i=0}^{n−2} j^{n−2−i}S(i, k).

Thus, by collecting the x^{n} coefficient we obtain the desired result.

3.2 The case t = 3

Theorem 3.3 for t = 3 gives

U3^{′}(k) = ( \begin{matrix}1 − x & x \\ −x & 1 + xy \end{matrix} )^{k} ( \begin{matrix}1 \\ 1 \end{matrix} ) .

Using the decomposition

A = ( \begin{matrix}1 − x & x \\ −x & 1 + xy \end{matrix} ) = PDP^{−1}, P = ( \begin{matrix}1 & 1 \\ \frac{λ_{1}−1}{x} + 1 & \frac{λ_{2}−1}{x} + 1 \end{matrix} ) , D = ( \begin{matrix}λ_{1} & 0 \\ 0 & λ_{2} \end{matrix} )

with

λ_{1} = 1 + \frac{x}{2}(y − 1 + \sqrt{(y − 1)(y + 3)}) and λ_{2} = 1 + \frac{x}{2}(y − 1 − \sqrt{(y − 1)(y + 3)}), (3.6)

we obtain that

U3^{′}(k) = \frac{1}{\sqrt{(y − 1)(y + 3)}} ( \begin{matrix}\frac{λ_{1}−1}{x}λ_{2}^{k} − \frac{λ_{2}−1}{x}λ_{1}^{k} \\ \frac{λ_{1}−1}{x}λ_{1}^{k} − \frac{λ_{2}−1}{x}λ_{2}^{k} \end{matrix} ) ,

which implies that

\{ \begin{matrix}U_{3}^{′(1)}(k) = \frac{1}{x\sqrt{(y−1)(y+3)}} ((λ_{1} − 1)λ_{2}^{k} − (λ_{2} − 1)λ_{1}^{k}) , \\ U_{3}^{′(2)}(k) = \frac{1}{x\sqrt{(y−1)(y+3)}} ((λ_{1} − 1)λ_{1}^{k} − (λ_{2} − 1)λ_{2}^{k}) . \end{matrix}

Using (3.3) we obtain that

U_{3}^{(1)}(k) = \frac{U_{t}^{′(1)}(k)}{1 − x ∑_{j=0}^{k−1} U_{t}^{′(1)}(j)} = \frac{(1 − λ_{2})λ_{1}^{k} − (1 − λ_{1})λ_{2}^{k}}{x (\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{k} − \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{k})} ,  (3.7)

and

U_{3}^{(2)}(k) = \frac{U_{t}^{′(2)}(k)}{1 − x ∑_{j=0}^{k−1} U_{t}^{′(1)}(j)} = \frac{(1 − λ_{2})λ_{2}^{k} − (1 − λ_{1})λ_{1}^{k}}{x (\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{k} − \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{k})} ,  (3.8)

Thus, Lemma 3.1 for s = 0 gives that

U_{3}(x, y; k) = \frac{1}{∏_{j=0}^{k−1}(1 − xU_{3}^{(1)}(x, y; j))},

which is equivalent to

U_{3}(x, y; k) = \frac{1}{∏_{j=0}^{k−1}(1 − \frac{(1−λ_{2})λ_{1}^{j}−(1−λ_{1})λ_{2}^{j}}{\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{j}− \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{j}})} = ∏_{j=0}^{k−1} \frac{\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{j} − \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{j}}{\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{j+1} − \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{j+1}} .

Thus, Theorem 3.3 for t = 3 gives the following result.

Theorem 3.6. The ordinary generating function R_{3}(x, y; k) for the number of partitions of [n] with k blocks according to the number 3-rises is given by

xR_{3}^{(1)}(x, y; k − 1)U_{3}(x, y; k) = xR_{3}^{(1)}(x, y; k − 1) ∏_{j=0}^{k−1} \frac{\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{j} − \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{j}}{\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{j+1} − \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{j+1}} ,

where

( \begin{matrix}R_{3}^{(1)}(x, y; k) \\ R_{3}^{(2)}(x, y; k) \end{matrix} ) = x^{k} (∏_{j=1}^{k} B_{j}) · 1

with B_{j} = ( \begin{matrix}U_{3}^{(1)}(x, y; j) − 1 & 1 \\ U_{3}^{(2)}(x, y; j) − 1 & y \end{matrix} ).

In order to find an explicit formula for R_{3}(x, y; k) we need the following notation and two further lemmas. The set of all the solutions of the equation i_{1} + i_{2} + ⋯ + i_{m} = n with i_{1}, i_{2}, …, i_{m} ∈ {1, 2} is denoted by 𝔉_{n,m}. Define 𝔉_{n} = ∪_{m=1}^{n}𝔉_{n,m}.

Lemma 3.7. Let {a_{n}}_{n≥0} be any sequence that satisfies a_{n+2} = α_{n+1}a_{n+1} + β_{n+1}a_{n} with a_{0} = 0 and a_{1} = α_{0}. Then

a_{n} = α_{0} ∑_{(i_{1},i_{2},...,i_{m})∈𝔉_{n−1}} (∏_{i_{j}=1} α_{i_{1}+i_{2}+···+i_{j}} ∏_{i_{j}=2} β_{i_{1}+i_{2}+···+i_{j}} ) .

Proof. The proof can be obtained by induction on n. It is trivial to check the lemma for n = 0, 1. Let n ≥ 0, then by the induction hypothesis for n + 1 and n we obtain that

a_{n+2} = α_{n+1}α_{0} ∑_{𝔉_{n}} (∏_{i_{j}=1} α_{i_{1}+i_{2}+···+i_{j}} ∏_{i_{j}=2} β_{i_{1}+i_{2}+···+i_{j}})
+β_{n+1}α_{0} ∑_{𝔉_{n−1}} (∏_{i_{j}=1} α_{i_{1}+i_{2}+···+i_{j}} ∏_{i_{j}=2} β_{i_{1}+i_{2}+···+i_{j}})
= α_{0} ∑_{𝔉_{n+1}} (∏_{i_{j}=1} α_{i_{1}+i_{2}+···+i_{j}} ∏_{i_{j}=2} β_{i_{1}+i_{2}+···+i_{j}}) ,

which completes the proof.

Lemma 3.8. Let {Q_{n}}_{n≥1} be any sequence of matrices of order two, where Q_{n} is defined by

( \begin{matrix}α_{n} & 1 \\ β_{n} & y \end{matrix} ). Then

∏_{j=1}^{n} Q_{j} = Q_{1}Q_{j} ⋯ Q_{n} = ( \begin{matrix}a_{n} & b_{n} \\ c_{n} & d_{n} \end{matrix} ) ,

where

\begin{matrix}b_{n} = ∑_{(i_{1},i_{2},...,i_{m})∈𝔉_{n−1}} (∏_{i_{j}=1}(α_{i_{1}+i_{2}+···+i_{j}} + y) ∏_{i_{j}=2}(β_{i_{1}+i_{2}+···+i_{j}} − α_{i_{1}+i_{2}+···+i_{j}}y)) , \\ d_{n} = ∑_{(i_{1},i_{2},...,i_{m})∈𝔉_{n}} (∏_{i_{j}=1}(α_{i_{1}+i_{2}+···+i_{j}−1} + y) ∏_{i_{j}=2}(β_{i_{1}+i_{2}+···+i_{j}−1} − α_{i_{1}+i_{2}+···+i_{j}−1}y)) , \end{matrix}

a_{n} = b_{n+1} − yb_{n} and c_{n} = d_{n+1} − yd_{n}.

Proof. Define P_{n} = ∏_{j=1}^{n} Q_{j} = ( \begin{matrix}a_{n} & b_{n} \\ c_{n} & d_{n} \end{matrix} ). From the definitions, the sequences \{a_{n}\}_{n≥0}, {b_{n}}_{n≥0}, {c_{n}}_{n≥0} and {d_{n}}_{n≥0} satisfy

\{ \begin{matrix}a_{n+1} & = α_{n+1}a_{n} + β_{n+1}b_{n}, \\ b_{n+1} & = a_{n} + yb_{n}, \\ c_{n+1} & = α_{n+1}c_{n} + β_{n+1}d_{n}, \\ d_{n+1} & = c_{n} + yd_{n}. \end{matrix}

This implies that

b_{n+2} = (α_{n+1} + y)b_{n+1} + (β_{n+1} − α_{n+1}y)b_{n}.

The initial conditions b_{0} = 0 and b_{1} = 1 hold from the definitions. Thus, Lemma 3.7 gives

b_{n} = ∑_{(i_{1},i_{2},...,i_{m})∈𝔉_{n−1}} (∏_{i_{j}=1}(α_{i_{1}+i_{2}+···+i_{j}} + y) ∏_{i_{j}=2}(β_{i_{1}+i_{2}+···+i_{j}} − α_{i_{1}+i_{2}+···+i_{j}}y)) .

Similarly, we have

d_{n+2} = (α_{n+1} + y)d_{n+1} + (β_{n+1} − α_{n+1}y)d_{n}

with the initial conditions d_{0} = 1 and d_{1} = y, which implies by Lemma 3.7 that

d_{n} = ∑_{(i_{1},i_{2},...,i_{m})∈𝔉_{n}} (∏_{i_{j}=1}(α_{i_{1}+i_{2}+···+i_{j}−1} + y) ∏_{i_{j}=2}(β_{i_{1}+i_{2}+···+i_{j}−1} − α_{i_{1}+i_{2}+···+i_{j}−1}y)) .

The rest holds from the recurrence relations of the sequences {c_{n}}_{n≥0} and {a_{n}}_{n≥0}. Theorem 3.6 and Lemma 3.8 give the following result.

Theorem 3.9. The ordinary generating function R_{3}(x, y; k) for the number of partitions of [n] with k blocks according to the number of 3-rises is given by

x^{k}(Y (x, y; k) − (1 − y)Y (x, y; k − 1)) ∏_{j=0}^{k−1} \frac{\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{j} − \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{j}}{\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{j+1} − \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{j+1}} ,

where λ_{i}, i = 1, 2, is defined in (3.6), and

Y (x, y; k) = ∑_{(i_{1},i_{2},...,i_{m})∈𝔉_{k−1}} (∏_{i_{j}=1}(α_{i_{1}+i_{2}+···+i_{j}} + y) ∏_{i_{j}=2}(β_{i_{1}+i_{2}+···+i_{j}} − α_{i_{1}+i_{2}+···+i_{j}}y)) ,

α_{j} = U_{3}^{(1)}(x, y; j) − 1 and β_{j} = U_{3}^{(2)}(x, y; j) − 1, see (3.7) and (3.8).

Some enumerative results for t-rises, t = 2, 3, are given in Table 2. We remark that all the row sequences in Table 2 are not presently in [13].

2-rises\n 0 1 2 3 4 5 6 7  8  9  10
0  1 1 1 1 1 1 1 1  1  1  1
1  0 0 1 3 6 10 15 21 28 36  45
2  0 0 0 1 7 26 71 161 322 588 1002
3  0 0 0 0 1 14 89 380 1268 3571 8878
4  0 0 0 0 0 1 26 267 1709 8136 31532
3-rises\n 0 1 2 3 4 5 6 7  8  9  10
0  1 1 2 4 10 27 82 268 950 3595 14512
1  0 0 0 1 4 19 79 350 1558 7256 34851
2  0 0 0 0 1 5 35 191 1114 6260 36246
3  0 0 0 0 0 1 6 60 410 3045 20914
4  0 0 0 0 0 0 1 7 99 821 7613

Table 2: Number of partitions of [n] with 2-rises and 3-rises

4 Enumeration of partitions by t-descents

In this section we obtain the generating function for the number of partitions of [n] with k blocks according to number of t-descents, that is,

D_{t}(x, y; k) = ∑_{n≥0} ∑_{π∈𝔓_{n,k}} x^{n}y^{#t−descents in π}.

For descents the decomposition (1.2) immediately implies

D_{t}(x, y; k) = D_{t}(x, y; k − 1)V_{t}(x, y; k),

where V_{t}(x, y; k) is the ordinary generating function for the number k-ary words kπ of length n according to the number of t-descents. Each k-ary word kπ can be decomposed as kπ = kπ^{(1)}kπ^{(2)} ⋯ kπ^{(m)} with m ≥ 1. Thus the occurrence of t-descents are exactly the occurrences of t-rises in the reversal word of kπ. Thus, by the definition of U_{t}^{(s)}(x, y; k) we obtain that

V_{t}(x, y; k) = \frac{xU_{t}^{(1)}(x, y; k − 1)}{1 − xU_{t}^{(1)}(x, y; k − 1)}.

Hence, we can state the following result.

Theorem 4.1. Let t ≥ 1. Then the ordinary generating function for the number of partitions of [n] with k blocks according to the number of t-descents is given by

D_{t}(x, y; k) = x^{k} ∏_{j=0}^{k−1} \frac{U_{t}^{(1)}(x, y; j)}{1 − xU_{t}^{(1)}(x, y; j)}.

4.1 The case t = 2

Using Theorem 4.1 for t = 2 together with (3.4) we obtain the following result.

Corollary 4.2. The ordinary generating function for the number of partitions of [n] with k blocks according to the number of 2-descents is given by

x^{k} ∏_{j=0}^{k−1} \frac{(1 − y)(1 − x + xy)^{j}}{(1 − x + xy)^{j+1} − y} .

Again, from the above corollary we can obtain the number of 2-descents in all the partitions of [n] with k blocks, as follows.

Corollary 4.3. The number of 2-descents in all the partitions of [n] with k blocks is given by

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

Proof. Differentiating the generating function in the statement of Corollary 4.2 and then substituting y = 1 we get that

∑_{n≥0} ∑_{π∈𝔓_{n,k}}(#2-descents in π)x^{n} = \frac{x^{k+1}}{∏_{j=1}^{k}(1 − jx)} ∑_{j=2}^{k} \frac{(j − 1) − \binom{j}{2}x}{1 − jx},

2-descents\n 0 1 2 3 4 5 6 7  8  9  10
0  1 1 2 4 8 16 32 64 128 256 512
1  0 0 0 1 7 32 121 411 1304 3949 11567
2  0 0 0 0 0 4 49 360 2062 10163 45298
3  0 0 0 0 0 0 1 42 624 6042 45810
4  0 0 0 0 0 0 0 0 22 730 12170
3-descents\n 0 1 2 3 4 5 6 7  8  9  10
0  1 1 2 5 15 51 192 789 3504 16689 84717
1  0 0 0 0 0 1 11 87 616 4199 28465
2  0 0 0 0 0 0 0 1 20 257 2729
3  0 0 0 0 0 0 0 0  0  2  64

Table 3: Number partitions of [n] with 2-descents and 3-descents

which is equivalent (use the fact that \frac{x^{k}}{∏_{j=0}^{k}(1−jx)} = ∑_{n≥0} S(n, k)x^{n}) to

∑_{n≥0} ∑_{π∈𝔓_{n,k}}(#2-descents in π)x^{n} = x ∑_{n≥0} S(n, k)x^{n} (\frac{1}{2}\binom{k}{2} + \frac{1}{2} ∑_{j=2}^{k}(j − 1) ∑_{n≥0} j^{n}x^{n}) .

Thus, by collecting the x^{n} coefficient we obtain the desired result.

4.2 The case t = 3

Theorem 4.1 for t = 2 together with (3.7) we obtain the following result.

Corollary 4.4. The ordinary generating function for the number of partitions of [n] with k blocks according to the number of 3-descents is given by

x^{k} ∏_{j=0}^{k−1} \frac{(1 − λ_{2})λ_{1}^{j} − (1 − λ_{1})λ_{2}^{j}}{\frac{1−λ_{2}}{1−λ_{1}} λ_{1}^{j+1} − \frac{1−λ_{1}}{1−λ_{2}} λ_{2}^{j+1}} ,

where λ_{1} = 1 + \frac{x}{2}(y − 1 + \sqrt{(y − 1)(y + 3)}) and λ_{2} = 1 + \frac{x}{2}(y − 1 − \sqrt{(y − 1)(y + 3)}).

Some specific enumeration of t-descents, t = 2, 3, are given in Table 3. The row sequences in Table 3 are not yet in the database in [13].

5 Concluding remarks

Special cases of the results obtained in previous sections include the generating functions for the numbers of k-ary words according to both t-rises and t-descents, which complete the solution of a class of enumeration problems described by Burstein and Mansour (see [2]).

Combinatorial proofs are solicited for the formulas enumerating the occurrences of levels, rises and descents, among all partitions of [n], obtained in Corollaries 2.2, 3.5 and 4.3 respectively.

There are several ways in which one could extend our research. For example, one can study the following problems.

• It would be interesting to find explicit formulas for the generating functions R_{t}(x, y; k) and D_{t}(x, y; k) which evaluate directly for each integer t ≥ 2, (in the spirit of the “nice” result L_{t}(x, y; k)).

• Consider two words, σ ∈ [k]^{n} and τ ∈ [ℓ]^{m}. In other words, σ is an k-ary word of length n and τ is an ℓ-ary word of length m. Assume additionally that τ contains all letters 1 through ℓ. We say that σ contains an occurrence of τ, or simply that σ contains τ, if σ has a subword order-isomorphic to τ, i.e., if there exists 1 ≤ i ≤ n − m such that, for any relation ϕ ∈ {<, =, >} and indices 1 ≤ a, b ≤ m, σ_{i+a}ϕσ_{i+b} if and only if τ_{a}ϕτ_{b}. In this situation, the word τ is called a subword pattern. One may be interested in generalizing our results to study the number of partitions that avoid a subword pattern τ.

References

[1] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1998.

[2] A. Burstein and T. Mansour, Counting occurrences of some subword patterns, Discr. Math. Theor. Comp. Sci. 6 (2003), 1–12.

[3] L. Carlitz, Enumeration of up-down sequences, Discrete Math. 4 (1973), 273–286.

[4] L. Carlitz, Enumeration of compositions by rises, falls and levels, Math. Nachr. 77 (1977), 361–371.

[5] L. Carlitz, T. Vaughan, Enumeration of sequences of given specification according to rises, falls and maxima, Discrete Math. 8 (1974), 147–167.

[6] L. Carlitz, R. Scoville, Enumeration of permutations by rises, falls, rising maxima and falling maxima, Acta Math. Sci. Hungar. 25 (1974), 269–277.

[7] S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110–125.

[8] S. Heubach and T. Mansour, Enumeration of 3-letter patterns in compositions, Integers Conference, Celebration of the 70th Birthday of Ron Graham, University of West Georgia Carrollton, 2005.

[9] S. Heubach and T., Counting rises, levels, and drops in compositions, Integers 5 (2005), Article A11.

[10] T. Mansour and A. O. Munagi, Enumeration of partitions by rises, levels and descents, Proceedings of the Fifth Conference on Permutation Patterns, 2007, to appear.

[11] T. Mansour and B. Sirhan, Counting ℓ-letter subwords in compositions, Discrete Math. Theor. Comput. Sci. 8 (2006), 285–298.

[12] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958.

[13] N. J. A. Sloane, The On-Line Encylopedia of Integer Sequences, 2008.

[14] D. Stanton and D. White, Constructive Combinatorics, Springer, 1986.

2000 Mathematics Subject Classification: Primary 05A05; Secondary 05A15. Keywords: set partition, generating function, recurrence relation, t-rise, t-level, t-descent.

(Concerned with sequences \underline{A000110}, \underline{A052889}, \underline{A105479}, \underline{A105480}, \underline{A105481}, \underline{A105483}, \underline{A105484}, \underline{A105485}, and \underline{A105486}.)

Received July 5 2008; revised version received January 2 2009. Published in Journal of Integer Sequences, January 3 2009.

Return to Journal of Integer Sequences home page.