Counting Peaks and Valleys in a Partition of a Set

Toufik Mansour Department of Mathematics University of Haifa 31905 Haifa Israel

                toufik@math.haifa.ac.il

Mark Shattuck Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

                 shattuck@math.utk.edu

Abstract

A partition π of the set [n] = {1, 2, …, n} is a collection {B_{1}, B_{2}, …, B_{k}} of nonempty disjoint subsets of [n] (called blocks) whose union equals [n]. In this paper, we find an explicit formula for the generating function for the number of partitions of [n] with exactly k blocks according to the number of peaks (valleys) in terms of Chebyshev polynomials of the second kind. Furthermore, we calculate explicit formulas for the total number of peaks and valleys in all the partitions of [n] with exactly k blocks, providing both algebraic and combinatorial proofs.

1 Introduction

A partition Π of the set [n] = {1, 2, …, n} is a collection {B_{1}, B_{2}, …, B_{k}} of nonempty disjoint subsets of [n], called blocks, whose union equals [n]. We assume that blocks are listed in increasing order of their minimal elements, that is, min B_{1} < min B_{2} < ⋯ < min B_{k}. The set of all partitions of [n] with k blocks is denoted by P (n, k). The cardinality of P (n, k) is the well-known Stirling number of the second kind [13], which is usually denoted by S_{n,k}. Any partition Π can be written in the canonical sequential form π_{1}π_{2} ⋯ π_{n}, where i ∈ B_{π_{i}} for all i (see, e.g., [7]). Throughout, we will identify each partition with its canonical sequential form. For example, if Π = {1, 4}, {2, 5, 7}, {3}, {6} is a partition of [7], then its canonical sequential form is π = 1231242 and in such a case we write Π = π.

Several authors have studied different subword patterns on the set of partitions of [n]. For example, Mansour and Munagi [9] studied the number of partitions of [n] according to the number levels, rises, and descents. Recall that a level (respectively, rise, descent) of a word π = π_{1}π_{2} ⋯ π_{n} is an index i such that π_{i} = π_{i+1} (respectively, π_{i} < π_{i+1}, π_{i} > π_{i+1}). A general question concerns counting the elements in a subset of P (n, k) which have no occurrences of a particular pattern. On this subject, the reader is referred to the works of Sagan [12], Mansour and Severini [10], Chen et al. [1], and Jelínek and Mansour [4], as well as to the references therein.

Let [k]^{n} denote the set of all words of length n over the alphabet [k]. Given π = π_{1}π_{2} ⋯ π_{n} ∈ [k]^{n}, a peak (respectively, valley) is an entry π_{j}, 1 ≤ j ≤ n − 2, of π such that π_{j} < π_{j+1} > π_{j+2} (respectively, π_{j} > π_{j+1} < π_{j+2}); that is, a peak is a rise followed immediately by a descent and a valley is a descent followed immediately by a rise. In this case, we say that a peak or valley occurs at j in π. We denote the number of peaks (respectively, valleys) in π by peak(π) (respectively, valley(π)).

That there are 2^{n−1} permutations of [n] without peaks (valleys) was shown [5] and later extended [6] by Kitaev. Comparable results on words are given by Heubach and Mansour [2], where they find an explicit formula for the generating function for the number of elements of [k]^{n} according to the number of peaks (valleys) (see [3] for further results). See also the paper by Mansour [8] for analogous results on Dyck paths.

The aim of this paper is to find an explicit formula for the generating function for the number of partitions of [n] with exactly k blocks, expressed canonically, according to the number of peaks (valleys), where k is fixed. The case of peaks (respectively, valleys) is treated in Section 2 (respectively, Section 3). Our main approach is to first compute the generating functions for the number of peaks (or valleys) for words over [k] of length n and then relate this to the corresponding generating functions for partitions of [n] with exactly k blocks via the restricted growth function of the partition. All the explicit solutions obtained in Sections 2 and 3 involve Chebyshev polynomials of the second kind, see [11]. We also derive explicit formulas for the total number of peaks and valleys in all the partitions of [n] with exactly k blocks, providing both algebraic and combinatorial proofs.

2 Counting peaks

Let W_{k}(x, q) be the generating function for the number of words of length n over the alphabet [k] according to the number of peaks, that is,

W_{k}(x, q) = ∑_{n≥0} (x^{n} ∑_{π∈[k]^{n}} q^{peak(π)}) .

Lemma 2.1. The generating function W_{k}(x, q) satisfies the recurrence relation

W_{k}(x, q) = \frac{x(q − 1) + (1 − x(q − 1))W_{k−1}(x, q)}{1 − x(1 − q)(1 − x) − x(x + q(1 − x))W_{k−1}(x, q)},

with the initial condition W_{0}(x, q) = 1.

Proof. Let us write an equation for W_{k}(x, q). Since each word in [k]^{n} may or may not contain the letter k, we have

W_{k}(x, q) = W_{k−1}(x, q) + W_{k}^{∗}(x, q),

where W_{k}^{∗}(x, q) is the generating function for the number of words π of length n over the alphabet [k] according to the number of peaks such that π contains the letter k. Such words π may be decomposed as either k, π′k, kπ′′, π′kπ′′′, or π′kkπ′′′′, where π′ is a nonempty word over the alphabet [k − 1], π′′ is a nonempty word over the alphabet [k], π′′′ is a nonempty word over the alphabet [k] which starts with a letter a < k, and π′′′′ is a word over the alphabet [k]. The corresponding generating functions for the number of words of these forms are given by x, x(W_{k−1}(x, q) − 1), x(W_{k}(x, q) − 1), x^{2}(W_{k−1}(x, q) − 1)W_{k}(x, q) and xq(W_{k−1}(x, q) − 1)(W_{k}(x, q) − xW_{k}(x, q) − 1), respectively. Summing these five generating functions, we obtain

W_{k}^{∗}(x, q) = x(q − 1) − x(q − 1)W_{k−1}(x, q) + x((1 − q)(1 − x)
+ (x + q(1 − x))W_{k−1}(x, q))W_{k}(x, q),

which implies

W_{k}(x, q) = x(q − 1) + (1 − x(q − 1))W_{k−1}(x, q) + x((1 − q)(1 − x)
+ (x + q(1 − x))W_{k−1}(x, q))W_{k}(x, q),

which is equivalent to

W_{k}(x, q) = \frac{x(q − 1) + (1 − x(q − 1))W_{k−1}(x, q)}{1 − x(1 − q)(1 − x) − x(x + q(1 − x))W_{k−1}(x, q)},

as claimed.

In order to write the explicit formula for the generating function W_{k}(x, q), we need the following lemma.

Lemma 2.2. Let a_{n} be any sequence defined by the recurrence relation a_{n} = \frac{A+Ba_{n−1}}{C+Da_{n−1}} with the initial condition a_{0} = 1 such that α = BC − AD ≠ 0. Then for all n ≥ 0,

a_{n} = \frac{A (\frac{A+B}{\sqrt{α}} U_{n−1}(\frac{B+C}{2\sqrt{α}}) − U_{n−2}(\frac{B+C}{2\sqrt{α}}))}{\sqrt{α} (\frac{A+B}{\sqrt{α}} U_{n}(\frac{B+C}{2\sqrt{α}}) − U_{n−1}(\frac{B+C}{2\sqrt{α}})) − B (\frac{A+B}{\sqrt{α}} U_{n−1}(\frac{B+C}{2\sqrt{α}}) − U_{n−2}(\frac{B+C}{2\sqrt{α}}))},

where U_{m} is the m-th Chebyshev polynomial of the second kind.

Proof. We proceed by induction on n. Since U_{0}(t) = 1, U_{−1}(t) = 0 and U_{−2}(t) = −1, the lemma holds for n = 0. Let

g_{n} = \frac{A + B}{\sqrt{α}} U_{n−1}(\frac{B + C}{2\sqrt{α}}) − U_{n−2}(\frac{B + C}{2\sqrt{α}}).

Assume the lemma holds for n and let us prove it for n + 1:

a_{n+1} = \frac{A + Ba_{n}}{C + Da_{n}} = \frac{A + B \frac{Ag_{n}}{\sqrt{α}g_{n+1}−Bg_{n}}}{C + D\frac{Ag_{n}}{\sqrt{α}g_{n+1}−Bg_{n}}}

= \frac{A\sqrt{α}g_{n+1}}{C\sqrt{α}g_{n+1} − (BC − DA)g_{n}} = \frac{Ag_{n+1}}{Cg_{n+1} − \sqrt{α}g_{n}} .

Using the fact that the Chebyshev polynomials of the second kind satisfy the recurrence relation

U_{m}(t) = 2tU_{m−1}(t) − U_{m−2}(t),  (1)

we get g_{n} = \frac{B+C}{\sqrt{α}} g_{n+1} − g_{n+2}, which implies

a_{n+1} = \frac{Ag_{n+1}}{Cg_{n+1} − (B + C)g_{n+1} + \sqrt{α}g_{n+2}} = \frac{Ag_{n+1}}{\sqrt{α}g_{n+2} − Bg_{n+1}}

and completes the induction step.

Combining Lemmas 2.1 and 2.2, we obtain the following result.

Theorem 2.3. The generating function W_{k}(x, q) for the number of words of length n over the alphabet [k] according to the number of peaks is given by

W_{k}(x, q) = \frac{x(q − 1) (U_{k−1}(t) − U_{k−2}(t))}{U_{k}(t) − U_{k−1}(t) − (1 − x(q − 1)) (U_{k−1}(t) − U_{k−2}(t))},

where t = 1 + \frac{x^{2}}{2} (1 − q) and U_{m} is the m-th Chebyshev polynomial of the second kind.

Remark 2.4. The mapping on [k]^{n} given by

π_{1}π_{2} ⋯ π_{n} ↦ (k + 1 − π_{1})(k + 1 − π_{2}) ⋯ (k + 1 − π_{n})

implies that the generating function for the number of words of length n over the alphabet [k] according to the number of valleys is also given by W_{k}(x, q).

Theorem 2.3 for q = 0 gives

W_{k}(x, 0) = \frac{−x (U_{k−1}(t) − U_{k−2}(t))}{U_{k}(t) − U_{k−1}(t) − (1 + x) (U_{k−1}(t) − U_{k−2}(t))},

which, by (1), implies the following corollary.

Corollary 2.5. The generating function W_{k}(x, 0) for the number of words of length n over the alphabet [k] without peaks is given by

W_{k}(x, 0) = \frac{U_{k−1}(t) − U_{k−2}(t)}{(1 − x)U_{k−1}(t) − U_{k−2}(t)},

where t = 1 + \frac{x^{2}}{2} and U_{m} is the m-th Chebyshev polynomial of the second kind.

Now we consider the number of peaks (valleys) in all the words of length n over the alphabet [k]. Theorem 2.3 gives

lim_{q→1} W_{k}(x, q) = lim_{q→1} \frac{x (U_{k−1}(1) − U_{k−2}(1))}{\frac{d}{dq}(U_{k}(t) − 2U_{k−1}(t) + U_{k−2}(t)) |_{q=1} +x (U_{k−1}(1) − U_{k−2}(1))}.

Since U_{k}(1) = k + 1 and \frac{d}{dq}U_{k}(1 + \frac{x^{2}}{2} (1 − q)) |_{q=1}= −x^{2}\binom{k+2}{3}, we get

lim_{q→1} W_{k}(x, q) = lim_{q→1} \frac{x}{−kx^{2} + x} = \frac{1}{1 − kx},

which agrees with the generating function for the number of words of length n over the alphabet [k]. To find the q-partial derivative of W_{k}(x, q) at q = 1 using Theorem 2.3, first let

f(q) = x(q − 1)(U_{k−1}(t) − U_{k−2}(t))

and

g(q) = (U_{k}(t) − U_{k−1}(t)) − (1 − x(q − 1))(U_{k−1}(t) − U_{k−2}(t)),

where t = 1+ \frac{x^{2}}{2} (1−q). It is readily verified that f(1) = g(1) = 0, f′(1) = x, g′(1) = x−kx^{2}, f′′(1) = −2x^{3}\binom{k}{2}, and g′′(1) = 2x^{4}\binom{k+1}{3} − 2x^{3}\binom{k}{2}, where primes denote differentiation with respect to q. Then applying L’Hôpital’s rule twice to

lim_{q→1}(\frac{f′(q)g(q) − f(q)g′(q)}{g^{2}(q)})

yields

\frac{d}{dq} W_{k}(x, q) |_{q=1}= \frac{(k\binom{k}{2} − \binom{k+1}{3}) x^{3}}{(1 − kx)^{2}} = \frac{(2\binom{k}{3} + \binom{k}{2}) x^{3}}{(1 − kx)^{2}} ,

which implies the following result.

Corollary 2.6. The number of peaks (valleys) in all the words of length n over the alphabet [k] is given by

(n − 2)k^{n−3} (2\binom{k}{3} + \binom{k}{2}) .

Now we turn our attention to finding an explicit formula for the generating function P P_{k}(x, q) for the number of partitions of [n] with exactly k blocks according to the number of peaks, that is,

P P_{k}(x, q) = ∑_{n≥0} x^{n} ∑_{π∈P (n,k)} q^{peak(π)}.

Lemma 2.7. For all k ≥ 1,

P P_{k}(x, q) = x^{k} ∏_{j=1}^{k}(1 + x(1 − q)W_{j}(x, q) + q(W_{j}(x, q) − 1)).

Proof. If π is any partition of [n] with exactly k blocks, then π may be written as π = π′kπ′′, where π′ is a partition of [n′] with exactly k − 1 blocks and π′′ is a word of length n′′ over the alphabet [k] such that n′ + n′′ + 1 = n. Since π′′ is either empty, starts with the letter k, or starts with a letter less than k, we get

P P_{k}(x, q) = xP P_{k−1}(x, q)(1 + xW_{k}(x, q) + q(W_{k}(x, q) − xW_{k}(x, q) − 1)).

The desired result now follows by induction on k, upon noting the initial condition P P_{0}( x, q) = 1.

Combining Lemma 2.7 and Theorem 2.3 yields the following result.

Theorem 2.8. For all k ≥ 1, the generating function for the number of partitions of [n] with exactly k blocks according to the number of peaks is given by

P P_{k}(x, q) = x^{k}(1 − q)^{k} ∏_{j=1}^{k} \frac{1 + x + x^{2}(1 − q) − \frac{U_{j}(t)−U_{j−1}(t)}{U_{j−1}(t)−U_{j−2}(t)}}{1 + x(1 − q) − \frac{U_{j}(t)−U_{j−1}(t)}{U_{j−1}(t)−U_{j−2}(t)}} ,

where t = 1 + \frac{x^{2}}{2} (1 − q) and U_{m} is the m-th Chebyshev polynomial of the second kind.

The above theorem for q = 0 implies that the generating function for the number of partitions of [n] with exactly k blocks without peaks is given by

P P_{k}(x, 0) = x^{k} ∏_{j=1}^{k} (1 + \frac{x^{2}}{1 + x − \frac{U_{j}(t′)−U_{j−1}(t′)}{U_{j−1}(t′)−U_{j−2}(t′)}} ) ,

which, by (1), is equivalent to

P P_{k}(x, 0) = x^{k} ∏_{j=1}^{k} \frac{U_{j−1}(t′) − (1 + x)U_{j−2}(t′)}{(1 − x)U_{j−1}(t′) − U_{j−2}(t′)},

where t′ = 1 + \frac{x^{2}}{2} and U_{m} is the m-th Chebyshev polynomial of the second kind. Table 1 below presents the number of partitions of [n] with exactly k blocks without peaks.

Corollary 2.9. The generating function for the number of partitions of [n] without peaks is given by

1 + ∑_{k≥1} P P_{k}(x, 0) = ∑_{k≥0} x^{k} ∏_{j=1}^{k} \frac{U_{j−1}(t′) − (1 + x)U_{j−2}(t′)}{(1 − x)U_{j−1}(t′) − U_{j−2}(t′)},

where t′ = 1 + \frac{x^{2}}{2} and U_{m} is the m-th Chebyshev polynomial of the second kind.

\begin{matrix}k\n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 0 & 1 & 2 & 4 & 8 & 15 & 27 & 48 & 85 & 150 & 264 & 464 \\ 3 & 0 & 0 & 1 & 3 & 9 & 27 & 75 & 197 & 503 & 1263 & 3132 & 7695 \\ 4 & 0 & 0 & 0 & 1 & 4 & 16 & 64 & 236 & 818 & 2736 & 8934 & 28622 \\ 5 & 0 & 0 & 0 & 0 & 1 & 5 & 25 & 125 & 575 & 2479 & 10275 & 41409 \end{matrix}

Table 1: The number of partitions of [n] with exactly k blocks without peaks, for n = 1, 2, …, 12 and k = 1, 2, …, 5

Now we turn our attention to finding a formula for the total number of peaks in all the partitions of [n] with exactly k blocks. Theorem 2.8 gives

P P_{k}(x, 1) = x^{k} ∏_{j=1}^{k} lim_{q→1} \frac{(1 − q) (1 + x + x^{2}(1 − q) − \frac{U_{j}(t)−U_{j−1}(t)}{U_{j−1}(t)−U_{j−2}(t)})}{1 + x(1 − q) − \frac{U_{j}(t)−U_{j−1}(t)}{U_{j−1}(t)−U_{j−2}(t)}}

= x^{k} ∏_{j=1}^{k} \frac{− (1 + x − \frac{U_{j}(1)−U_{j−1}(1)}{U_{j−1}(1)−U_{j−2}(1)})}{−x − \frac{d}{dq} (\frac{U_{j}(t)−U_{j−1}(t)}{U_{j−1}(t)−U_{j−2}(t)}) |_{q=1}} .

Using U_{k}(1) = k + 1 and \frac{d}{dq}U_{k}(1 + \frac{x^{2}}{2} (1 − q)) |_{q=1}= −x^{2}\binom{k+2}{3}, we obtain

P P_{k}(x, 1) = x^{k} ∏_{j=1}^{k} \frac{−x}{−x + jx^{2}} = \frac{x^{k}}{∏_{j=1}^{k}(1 − jx)},

which is in accord with the generating function for the number of partitions of [n] with exactly k blocks; see, e.g., [13]. Also, Theorem 2.8 gives

\frac{d}{dq} P P_{k}(x, q) |_{q=1}= P P_{k}(x, 1) ∑_{j=1}^{k} lim_{q→1} ( \frac{\frac{d}{dq}h_{j}(q)}{h_{j}(q)}) ,

where h_{j}(q) = \frac{(1−q)(1+x+x^{2}(1−q)−u_{j})}{1+x(1−q)−u_{j}} and u_{j} = \frac{U_{j}(t)−U_{j−1}(t)}{U_{j−1}(t)−U_{j−2}(t)}, with t = 1+ \frac{x^{2}}{2} (1−q). Let u′_{j}(q) =

\frac{d}{dq}u_{j}(q) and u′′_{j}(q) = \frac{d^{2}}{dq^{2}} u_{j}(q). Since u_{j}(1) = 1, lim_{q→1} h_{j}(q) = \frac{1}{1−jx} and lim_{q→1} u′_{j}(q) = −jx^{2}, we have

lim_{q→1} \frac{d}{dq} h_{j}(q) = \frac{x(j − 1)}{1 − jx} − x lim_{q→1} \frac{1 − u_{j}(q) − (1 − q)u′_{j}(q)}{(1 + x(1 − q) − u_{j}(q))^{2}}

= \frac{x(j − 1)}{1 − jx} − \frac{1}{2(1 − jx)} lim_{q→1} \frac{(1 − q)u′′_{j}(q)}{1 + x(1 − q) − u_{j}(q)}

= \frac{x(j − 1)}{1 − jx} − \frac{1}{2(1 − jx)} \frac{u′′_{j}(1)}{(x − jx^{2})}.

It is not hard to check that lim_{q→1} u′′_{j}(q) = −2\binom{j+1}{3}x^{4} − 2\binom{j}{3}x^{4}, which implies

lim_{q→1} \frac{d}{dq} h_{j}(q) = \frac{x(j − 1)}{1 − jx} + \frac{x^{3}\binom{j+1}{3} + x^{3}\binom{j}{3}}{(1 − jx)^{2}}.

Hence, we have

\frac{d}{dq} P P_{k}(x, q) |_{q=1}= P P_{k}(x, 1) ∑_{j=1}^{k} (\frac{x^{3}\binom{j+1}{3} + x^{3}\binom{j}{3}}{(1 − jx)} + x(j − 1)) .

Since P P_{k}(x, 1) = ∑_{n≥1} S(n, k)x^{n} and ∑_{j=1}^{k} x(j − 1) = x\binom{k}{2}, we get the following result, upon writing \binom{j+1}{3} + \binom{j}{3} as j\binom{j}{2} − \binom{j+1}{3}.

Corollary 2.10. The number of peaks in all the partitions of [n] with k blocks is given by

\binom{k}{2}S_{n−1,k} + ∑_{j=2}^{k} (j\binom{j}{2} − \binom{j + 1}{3}) f_{n,j},

where f_{n,j} = ∑_{i=3}^{n−k} j^{i−3}S_{n−i,k} and S_{i,j} is the Stirling number of the second kind.

3 Counting valleys

In this section, we find an explicit formula for the generating function V P_{k}(x, q) for the number of partitions of [n] with exactly k blocks according to the number of valleys, that is,

V P_{k}(x, q) = ∑_{n≥0} (x^{n} ∑_{π∈P (n,k)} q^{valley(π)}) .

In order to achieve this, let W′_{k}(x, q) (respectively, W′′_{k}(x, q)) be the generating function for the number of words π of length n over the alphabet [k] (respectively, [k − 1]) according to the number of valleys in kπ(k + 1) (respectively, kπk).

Lemma 3.1. For all k ≥ 2,

W′_{k}(x, q) = \frac{W′′_{k}(x, q)}{1 − xW′′_{k}(x, q)}

and

W′′_{k}(x, q) = W′′_{k−1}(x, q) + x(W′′_{k−1}(x, q)W′_{k−1}(x, q) − 1) + xq,

with W′_{1}(x, q) = \frac{1}{1−x} and W′′_{1}(x, q) = 1.

Proof. The initial conditions W′_{1}(x, q) = \frac{1}{1−x} and W′′_{1}(x, q) = 1 hold directly from the definitions. Each word kπ(k + 1) such that π is a word over the alphabet [k] can be written as either kπ(k + 1), where π is a word over the alphabet [k − 1], or as kπ′kπ′′(k + 1), where π′ is a word over the alphabet [k − 1] and π′′ is a word over the alphabet [k]. Note that the number of valleys in the word kπ(k + 1) equals the number of valleys in kπk for any word π over the alphabet [k − 1]. Therefore, for all k ≥ 2,

W′_{k}(x, q) = W′′_{k}(x, q) + xW′′_{k}(x, q)W′_{k}(x, q),

which implies

W′_{k}(x, q) = \frac{W′′_{k}(x, q)}{1 − xW′′_{k}(x, q)}.

Similarly, each word kπk such that π is a word over the alphabet [k − 1] can be written either as kπk such that π is a word over the alphabet [k − 2] or as kπ′(k − 1)π′′k such that π′ is a word over the alphabet [k − 2] and π′′ is a word over the alphabet [k − 1]. Note that the number of valleys in the word kπ(k − 1) equals the number of valleys in (k − 1)π(k − 1) for any word π over the alphabet [k − 2]. Therefore, for all k ≥ 2,

W′′_{k}(x, q) = W′′_{k−1}(x, q) + x(W′′_{k−1}(x, q)W′_{k−1}(x, q) − 1) + xq,

where xq accounts for the word k(k − 1)k, which yields the result above.

Lemma 3.2. For all k ≥ 1,

W′′_{k}(x, q) = \frac{x(q − 1)A_{k}}{A_{k+1} − (1 − x^{2}(q − 1))A_{k}} ,

where A_{k} = (1 + x(1 − x)(q − 1))U_{k−2}(t) − U_{k−3}(t), t = 1 + \frac{x^{2}}{2} (1 − q), and U_{m} is the m-th Chebyshev polynomial of the second kind.

Proof. Lemma 3.1 gives

W′′_{k}(x, q) = x(q − 1) + \frac{W′′_{k−1}(x, q)}{1 − xW′′_{k−1}(x, q)},  (2)

with initial condition W′′_{1}(x, q) = 1. Assume that W′′_{k}(x, q) = \frac{A′_{k}}{B′_{k}} for all k ≥ 1. Then we have

\frac{A′_{k}}{B′_{k}} = x(q − 1) + \frac{A′_{k−1}}{B′_{k−1} − xA′_{k−1}} ,

which implies A′_{k} = x(q − 1)B′_{k−1} + (1 − x^{2}(q − 1))A′_{k−1} and B′_{k} = B′_{k−1} − xA′_{k−1}, with A′_{1} = B′_{1} = 1, A′_{2} = 1 + x(1 − x)(q − 1), and B′_{2} = 1 − x. Therefore,

A′_{k} = 2tA′_{k−1} − A′_{k−2}, A′_{1} = 1, A′_{2} = 1 + x(1 − x)(q − 1).  (3)

Hence, by (1) and induction on k, we have A′_{k} = A_{k}. From the recurrence A′_{k} = x(q − 1)B′_{k−1} + (1 − x^{2}(q − 1))A′_{k−1}, we get

B′_{k} = \frac{1}{x(q − 1)} (A′_{k+1} − (1 − x^{2}(q − 1))A′_{k}) ,

which completes the proof.

Lemma 3.1 and (2) imply W′_{k}(x, q) = W′′_{k+1}(x, q) − x(q − 1). Thus, by Lemma 3.2, we get

W′_{k}(x, q) = \frac{x(q − 1)(2tA_{k+1} − A_{k+2})}{A_{k+2} − (1 − x^{2}(q − 1))A_{k+1}} ,

which, by (3), implies the following result.

Lemma 3.3. For all k ≥ 1,

W′_{k}(x, q) = \frac{x(q − 1)A_{k}}{A_{k+2} − (1 − x^{2}(q − 1))A_{k+1}} ,

where A_{k} = (1 + x(1 − x)(q − 1))U_{k−2}(t) − U_{k−3}(t), t = 1 + \frac{x^{2}}{2} (1 − q), and U_{m} is the m-th Chebyshev polynomial of the second kind.

¿From the fact that each partition π of [n] with exactly k blocks may be expressed uniquely as π = 1π^{(1)}2π^{(2)} ⋯ kπ^{(k)} such that π^{(j)} is a word over the alphabet [j], it follows that the generating function V P_{k}(x, q) is given by

V P_{k}(x, q) = x^{k}V_{k}(x, q) ∏_{j=1}^{k−1} W′_{j}(x, q),  (4)

where V_{k}(x, q) is the generating function for the number of words π over the alphabet [k] according to the number of valleys in kπ.

Lemma 3.4. For all k ≥ 1,

V_{k}(x, q) = ∏_{j=1}^{k} \frac{1}{1 − xW′′_{j}(x, q)}.

Proof. Since each word kπ, where π is a word over the alphabet [k], can be written either as kπ, where π is a word over the alphabet [k − 1], or as kπ′kπ′′, where π′ is a word over the alphabet [k − 1] and π′′ is a word over the alphabet [k], we get

V_{k}(x, q) = V′_{k}(x, q) + xW′′_{k}(x, q)V_{k}(x, q),  (5)

where V′_{k}(x, q) is the generating function for the number of words π over the alphabet [k − 1] according to the number of valleys in kπ. Similarly, each word kπ, where π is a word over the alphabet [k −1], can be written either as kπ, where π is a word over the alphabet [k −2], or as kπ′(k − 1)π′′, where π′ is a word over the alphabet [k − 2] and π′′ is a word over the alphabet [k − 1]. Also, the number of valleys in kπ (kπ(k − 1)) equals the number of valleys in (k − 1)π ((k − 1)π(k − 1)) for any word π over the alphabet [k − 2]. Therefore,

V′_{k}(x, q) = V′_{k−1}(x, q) + xW′′_{k−1}(x, q)V_{k−1}(x, q).  (6)

Hence, by (5) and (6), we get V_{k}(x, q)−V_{k−1}(x, q) = xW′′_{k}(x, q)V_{k}(x, q) for all k ≥ 1. Applying this recurrence relation k times, we have V_{k}(x, q) = ∏_{j=1}^{k} \frac{1}{1−xW′′_{j}(x,q)}, as claimed.

Now we can state the main result of this section. Theorem 3.5. The generating function V P_{k}(x, q) for the number of partitions of [n] with exactly k blocks is given by

V P_{k}(x, q) = \frac{x^{k}}{(1 − x)U_{k−1}(t) − U_{k−2}(t)} ∏_{j=1}^{k−1} \frac{U_{j−1}(t) − (1 − x(q − 1))U_{j−2}(t)}{(1 − x)U_{j−1}(t) − U_{j−2}(t)},

where t = 1 + \frac{x^{2}}{2} (1 − q) and U_{m} is the m-th Chebyshev polynomial of the second kind. Proof. Lemma 3.4 and (4) yield

V P_{k}(x, q) = x^{k} ∏_{j=1}^{k} \frac{1}{1 − xW′′_{j}(x, q)} ∏_{j=1}^{k−1} W′_{j}(x, q).

Thus, by Lemmas 3.2 and 3.3, we have

V P_{k}(x, q) = \frac{x^{k}(A_{k+1} − (1 − x^{2}(q − 1))A_{k})}{A_{k+1} − A_{k}}·

· ∏_{j=1}^{k−1} (\frac{x(q − 1)A_{j}}{A_{j+1} − A_{j}} · \frac{A_{j+1} − (1 − x^{2}(q − 1))A_{j}}{A_{j+2} − (1 − x^{2}(q − 1))A_{j+1}} )

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

where A_{k} = (1 + x(1 − x)(q − 1))U_{k−2}(t) − U_{k−3}(t). Using the initial conditions A_{1} = 1, A_{2} = 1 + x(1 − x)(q − 1) and the fact that

A_{j+1} − A_{j} = x(q − 1)((1 − x)U_{j−1}(t) − U_{j−2}(t)),

we get

V P_{k}(x, q) = \frac{x^{k+1}(q − 1)}{A_{k+1} − A_{k}} ∏_{j=1}^{k−1} \frac{x(q − 1)A_{j}}{A_{j+1} − A_{j}}

= \frac{x^{k}}{(1 − x)U_{k−1}(t) − U_{k−2}(t)} ∏_{j=1}^{k−1} \frac{(1 + x(1 − x)(q − 1))U_{j−2}(t) − U_{j−3}(t)}{(1 − x)U_{j−1}(t) − U_{j−2}(t)},

which, by the recurrence U_{m}(t) = 2tU_{m−1}(t) − U_{m−2}(t), is equivalent to

V P_{k}(x, q) = \frac{x^{k}}{(1 − x)U_{k−1}(t) − U_{k−2}(t)} ∏_{j=1}^{k−1} \frac{U_{j−1}(t) − (1 − x(q − 1))U_{j−2}(t)}{(1 − x)U_{j−1}(t) − U_{j−2}(t)},

as claimed.

\begin{matrix}k\n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 0 & 1 & 3 & 6 & 11 & 20 & 36 & 64 & 113 & 199 & 350 & 615 \\ 3 & 0 & 0 & 1 & 5 & 16 & 45 & 121 & 315 & 799 & 1992 & 4913 & 12029 \\ 4 & 0 & 0 & 0 & 1 & 7 & 31 & 119 & 430 & 1484 & 4935 & 15984 & 50838 \\ 5 & 0 & 0 & 0 & 0 & 1 & 9 & 51 & 249 & 1136 & 4914 & 20343 & 81510 \end{matrix}

Table 2: The number of partitions of [n] with exactly k blocks without valleys, for n = 1, 2, …, 12 and k = 1, 2, …, 5

The generating function for the number of partitions of [n] without valleys is given by

1 + ∑_{k≥1} V P_{k}(x, 0)

= ∑_{k≥0} (\frac{x^{k}}{(1 − x)U_{k−1}(t′) − U_{k−2}(t′)} ∏_{j=1}^{k−1} \frac{U_{j−1}(t′) − (1 + x)U_{j−2}(t′)}{(1 − x)U_{j−1}(t′) − U_{j−2}(t′)}) ,

where t′ = 1 + \frac{x^{2}}{2} and U_{m} is the m-th Chebyshev polynomial of the second kind. Table 2 presents the number of partitions of [n] with exactly k blocks without valleys.

Theorem 3.5, together with the fact U_{j}(1) = j + 1, yields

V P_{k}(x, 1) = \frac{x^{k}}{(1 − x)U_{k−1}(1) − U_{k−2}(1)} ∏_{j=1}^{k−1} \frac{U_{j−1}(1) − U_{j−2}(1)}{(1 − x)U_{j−1}(1) − U_{j−2}(1)}

= \frac{x^{k}}{∏_{j=1}^{k}(1 − jx)},

which is the generating function for the number of partitions of [n] with exactly k blocks; see, e.g., [13]. Also, Theorem 3.5 gives

\frac{\frac{d}{dq}V P_{k}(x, q) |_{q=1}}{V P_{k}(x, 1)}

= ∑_{j=1}^{k−1} \frac{lim_{q→1} \frac{d}{dq} \frac{U_{j−1}(t)−(1−x(q−1))U_{j−2}(t)}{(1−x)U_{j−1}(t)−U_{j−2}(t)}}{\frac{1}{1−jx}}

− \frac{(1 − x)U′_{k−1}(1) − U′_{k−2}(1)}{1 − kx}

= ∑_{j=1}^{k−1} \frac{(U′_{j−1}(1) + xU_{j−2}(1) − U′_{j−2}(1))(1 − jx) − ((1 − x)U′_{j−1}(1) − U′_{j−2}(1))}{1 − jx}

− \frac{(1 − x)U′_{k−1}(1) − U′_{k−2}(1)}{1 − kx},

which, by the fact that U′_{j}(1) := \frac{d}{dq}U_{j}(t) |_{q=1}= −x^{2}\binom{j+2}{3}, implies that the generating function for the number of valleys in all the partitions of [n] with exactly k blocks is given by

\frac{d}{dq} V P_{k}(x, q) |_{q=1}

= \frac{x^{k}}{∏_{j=1}^{k}(1 − jx)} (∑_{j=1}^{k−1} (x(j − 1) − x^{2}\binom{j}{2}) + ∑_{j=1}^{k} \frac{x^{2}\binom{j}{2} − x^{3}\binom{j+1}{3}}{1 − jx})

= \frac{x^{k}}{∏_{j=1}^{k}(1 − jx)} (x\binom{k − 1}{2} − x^{2}\binom{k}{3} + ∑_{j=1}^{k} \frac{x^{2}\binom{j}{2} − x^{3}\binom{j+1}{3}}{1 − jx}) .

This yields the following explicit formula.

Corollary 3.6. The number of valleys in all the partitions of [n] with exactly k blocks is given by

\binom{k − 1}{2}S_{n−1,k} − \binom{k}{3}S_{n−2,k} + ∑_{j=2}^{k} (\binom{j}{2}f′_{n,j} − \binom{j + 1}{3}f_{n,j}) ,

where f_{n,j} = ∑_{i=3}^{n−k} j^{i−3}S_{n−i,k}, f′_{n,j} = ∑_{i=2}^{n−k} j^{i−2}S_{n−i,k}, and S_{i,j} is the Stirling number of the second kind.

4 Combinatorial proofs

In this section, we provide direct combinatorial proofs of Corollaries 2.6, 3.6, and 2.10. We start with Corollary 2.6.

Proof of Corollary 2.6.

Proof. To show that there are (n − 2)k^{n−3} (2\binom{k}{3} + \binom{k}{2}) total peaks (valleys), it is enough to show for each i, 1 ⩽ i ⩽ n−2, that there are a total of k^{n−3} (2\binom{k}{3} + \binom{k}{2}) peaks at i within all the words w_{1}w_{2} ⋯ w_{n} in [k]^{n}. There are 2\binom{k}{3}k^{n−3} such peaks at i for which w_{i} ≠ w_{i+2} within all the members of [k]^{n}. To see this, note that for any three distinct numbers a < b < c in [k], there are 2k^{n−3} words of length n in the alphabet [k] whose (i + 1)^{st} letter is c and whose i^{th} and (i + 2)^{nd} letters comprise the set {a, b}. Upon letting a = b in the preceding, one sees that there are a total of \binom{k}{2}k^{n−3} peaks at i for which w_{i} = w_{i+2}.

Let π = π_{1}π_{2} ⋯ π_{n} be any partition represented by its canonical sequence. Recall that a rise (descent) is said to occur at i if π_{i} < π_{i+1} (π_{i} > π_{i+1}). We will call a rise or a descent at i non-trivial if neither i nor i + 1 are the smallest elements of their respective blocks. The following lemma provides an explicit formula for the total number of non-trivial rises in all of the members of P (n, k).

Lemma 4.1. The number of non-trivial rises (descents) in all of the partitions of [n] with exactly k blocks is given by

∑_{j=2}^{k} \binom{j}{2}f′_{n,j},

where f′_{n,j} = ∑_{i=2}^{n−k} j^{i−2}S_{n−i,k}.

Proof. Given i and j, where 2 ⩽ i ⩽ n − k and 2 ⩽ j ⩽ k, consider all the members of P (n, k) which may be decomposed uniquely as

π = π′jαβ,  (7)

where π′ is a partition with j − 1 blocks, α is a word of length i in the alphabet [j] whose last two letters form a rise, and β is possibly empty. For example, if i = 5, j = 3, and π = 122323113342 ∈ P (12, 4), then π′ = 122, α = 23113, and β = 342. The total number of non-trivial rises can then be obtained by finding the number of partitions which may be expressed as in (7) for each i and j and then summing over all possible values of i and j. And there are \binom{j}{2}j^{i−2}S_{n−i,k} members of P (n, k) which may be expressed as in (7) since there are j^{i−2} choices for the first i − 2 letters of α, \binom{j}{2} choices for the final two letters in α (as the last letter must exceed its predecessor), and S_{n−i,k} choices for the remaining letters π′jβ which necessarily constitute a partition of an (n − i)-set into k blocks.

If π is a partition of [n] and i ∈ [n], then we will say that i is minimal if i is the smallest element of a block within π, i.e., if the i^{th} slot of the canonical representation of π corresponds to the left-most occurrence of a letter. We now provide direct combinatorial proofs of Corollaries 3.6 and 2.10.

Proof of Corollary 3.6.

Proof. By Lemma 4.1, the first sum ∑_{j=2}^{k} \binom{j}{2}f′_{n,j} counts the total number of non-trivial rises within all of the members of P (n, k). From these, we subtract all non-trivial rises at r, r ≥ 2, where r − 1 either goes in the same block as r (∑_{j=2}^{k} \binom{j}{2}f_{n,j} total such rises) or goes in a block to the left of r (∑_{j=2}^{k} \binom{j}{3}f_{n,j} total such rises). Thus, the second sum ∑_{j=2}^{k} \binom{j+1}{3}f_{n,j} counts all non-trivial rises at r in which r − 1 fails to appear in a block to the right of r, upon noting \binom{j}{2} + \binom{j}{3} = \binom{j+1}{3}. Therefore, the difference between the two sums counts all valleys at m in which m + 2 is not minimal.

We’ll call valleys at m where m + 2 is minimal trivial. So to complete the proof, we must show that the total number of trivial valleys at m, m ≥ 1, is given by \binom{k−1}{2}S_{n−1,k} −\binom{k}{3}S_{n−2,k}, which we rewrite as 2\binom{k}{3}S_{n−2,k}+\binom{k−1}{2}S_{n−2,k−1} using the fact that S_{n−1,k} = kS_{n−2,k}+S_{n−2,k−1}. First, there are \binom{k}{3}S_{n−2,k} trivial valleys at m, where m is not minimal. To see this, pick three numbers a < b < c in [k] and let t denote the smallest element of the c^{th} block of λ ∈ P (n−2, k). Increase all members of [t, n−2] = {t, t+1, …, n−2} by two within λ, leaving all numbers within their current blocks. Then add t to block b and t+1 to block a to obtain a member of P (n, k) in which a trivial valley occurs at t, where t is not minimal. For example, if n = 10, k = 5, a = 1, b = 3, and c = 4, with λ = {1, 4}, {2, 3}, {5}, {6, 8}, {7} belonging to P (8, 5), then t = 6 and the resulting member λ′ = {1, 4, 7}, {2, 3}, {5, 6}, {8, 10}, {9} of P (10, 5) has a trivial valley at 6.

There are also \binom{k}{3}S_{n−2,k} trivial valleys at m, where m is minimal and not occurring as a singleton block. To see this, pick numbers a < b < c in [k] and let t denote the smallest element of the b^{th} block of λ ∈ P (n − 2, k). Increase all members of [t, n − 2] by two within λ and add t to block c and t + 1 to block a. The resulting member of P (n, k) will have a trivial valley at t with the singleton block \{t\} not occurring. Finally, there are \binom{k−1}{2}S_{n−2,k−1} trivial valleys at m in which the block {m} occurs. To see this, pick a < b in [k −1] and let t denote the smallest element of the b^{th} block of λ ∈ P (n − 2, k − 1). Increase all members of [t, n − 2] by two within λ. Then add t + 1 to block a as well as the singleton block {t}. The resulting member of P (n, k) will have a trivial valley at t with the singleton block {t} occurring. For example, if n = 9, k = 4, a = 1, and b = 3, with λ = {1, 4}, {2, 3, 6}, {5, 7} ∈ P (7, 3), then t = 5 and the resulting member λ′ = {1, 4, 6}, {2, 3, 8}, {5}, {7, 9} of P (9, 4) has a trivial valley at 5.

Proof of Corollary 2.10.

Proof. By reasoning similar to that used in the proof of Lemma 4.1, there are a total of ∑_{j=2}^{k} j\binom{j}{2}f_{n,j} non-trivial descents at r + 1 in which r is not minimal in all the members of P (n, k). Reasoning as in the proof of Corollary 3.6 above, we see that there are a total of ∑_{j=2}^{k} \binom{j+1}{3}f_{n,j} non-trivial descents at r + 1 in which either r either goes in the same block as r + 1 or goes in a block to the right of r + 1, where r itself is not minimal. Thus, the difference between the two sums counts all peaks at r where r + 1 is not minimal.

So to complete the proof, we’ll show that the total number of peaks at r, where r + 1 is minimal, is given by \binom{k}{2}S_{n−1,k}. To see this, we first observe that peaks at r where r + 1 is minimal are synonymous with descents at r + 1 where r + 1 is minimal. To show that \binom{k}{2}S_{n−1,k} counts all descents at i for some i where i is the smallest member of its block in some member of P (n, k), first choose two numbers a < b in [k]. Given λ ∈ P (n − 1, k), let t denote the smallest member of block b. Increase all members of [t + 1, n − 1] in λ by one (leaving them within their blocks) and then add t + 1 to block a. This produces a descent between the first element of block b and an element of block a within some member of P (n, k). For example, if n = 7, k = 4, a = 1, and b = 3, then λ = {1, 5}, {2}, {3, 4}, {6} ∈ P (6, 4) would give rise to the descent between 3 and 4 in {1, 4, 6}, {2}, {3, 5}, {7} ∈ P (7, 4).

References

[1] W. C. Chen, E. P. Deng, R. X. Du, R. P. Stanley, and C. H. Yan, Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc. 359(4) (2007), 1555–1575.

[2] 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.

[3] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, CRC Press, Boca Raton, 2009.

[4] V. Jelínek and T. Mansour, On pattern-avoiding partitions, Electron. J. Combin. 15 (2008), #R39.

[5] S. Kitaev, Multi-avoidance of generalized patterns, Discrete Math. 260 (2003), 89–100.

[6] S. Kitaev, Partially ordered generalized patterns, Discrete Math. 298 (2005), 212–229.

[7] M. Klazar, On abab-free and abba-free set partitions, European J. Combin. 17 (1996), 53–68.

[8] T. Mansour, Counting peaks at height k in a Dyck path, J. Integer Seq. 5 (2002), Article 2.1.1.

[9] T. Mansour and A. Munagi, Enumeration of partitions by long rises, levels and descents, J. Integer Seq. 12 (2009), Article 9.1.8.

[10] T. Mansour and S. Severini, Enumeration of (k, 2)-noncrossing partitions, Discrete Math. 308 (2008), 4570–4577.

[11] T. Rivlin, Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory, John Wiley, New York, 1990.

[12] B. E. Sagan, Pattern avoidance in set partitions, to appear in Ars Combin.

[13] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, Cambridge, UK, 1996.

2010 Mathematics Subject Classification: 05A18, 05A15, 42C05 Keywords: set partition, generating function, recurrence relation, peak, valley

(Concerned with sequences \underline{A000110}, \underline{A008277}.)

Received April 19 2010; revised version received June 18 2010. Published in Journal of Integer Sequences, June 22 2010.

Return to Journal of Integer Sequences home page.