Quadrant Marked Mesh Patterns and the r-Stirling Numbers

Matt Davis Department of Mathematics and Computer Science Muskingum University 163 Stormont St. New Concord, OH 43762 USA

                      mattd@muskingum.edu

Abstract Marked mesh patterns are a very general type of permutation pattern. We examine a particular marked mesh pattern originally defined by Kitaev and Remmel, and show that its generating function is described by the r-Stirling numbers. We examine some ramifications of various properties of the r-Stirling numbers for this generating function, and find (seemingly new) formulas for the r-Stirling numbers in terms of the classical Stirling numbers and harmonic numbers. We also answer some questions posed by Kitaev and Remmel and show a connection to another mesh pattern introduced by Kitaev and Liese.

1 Introduction

The notion of a marked mesh pattern in a permutation is a generalization of classical permutation patterns, and is in fact a common generalization of a number of different variations of permutation patterns that have been of recent interest. Brändén and Claesson introduced mesh patterns [2], and Úlfarsson developed marked mesh patterns [12]. We will give a somewhat loose definition of general marked mesh patterns here before turning to the specific examples studied in this paper.

Let σ be a permutation written in one-line notation: σ = σ_{1}σ_{2} ⋯ σ_{n}. The graph of σ is the set of points of the form (i, σ_{i}) for i from 1 to n. A marked mesh pattern of length k is the graph of a permutation σ in S_{k}, drawn on a grid, with some regions of the grid demarcated and labeled with a symbol ‘= a’, ‘≤ a’, or ‘≥ a’ for some non-negative integer a. This diagram is intended to be a schematic drawing of the graph of a permutation σ in S_{n} (with n > k), where the drawn points are actual points of the graph of σ, but the spaces between may have been compressed. Unmarked regions of the pattern place no restriction on σ, but the marked regions of the graph of σ must contain a number of points satisfying the expression that marks the region. (Since the mark “= 0” is the most commonly used, a shaded region with no other mark is assumed to be marked with “= 0”.)

The main pattern of interest for this paper is shown in Figure 1. We use MMP^{k} to denote this pattern. We precisely define this pattern by saying that σ_{i} matches the pattern MMP^{k} in σ if there are at least k − 1 indices j > i with σ_{j} > σ_{i} and j < m, where σ_{m} = n; and no indices j < i with σ_{j} > σ_{i}. That is, when checking this pattern, we count the points in the graph of σ that appear in the rectangle bounded in the lower left by (i, σ_{i}) and in the upper right by (m, n). For σ_{i} to match MMP^{k}, there must be at least k points in that rectangle (including the point (m, n) itself, but not (i, σ_{i}),) and no points above and to the left of (i, σ_{i}). (This matches the diagram of the pattern because the part of the shaded region along the top of the diagram means that the upper-right point must be (m, n), while the portion of the shaded region on the left gives the restriction on points occurring before σ_{i}. The middle region specifies the minimum number of points between σ_{i} and n in σ.)

[figure: ≥ k−1]

Figure 1: The Pattern MMP^{k}

The graph of σ leads to terminology that will be useful. Draw a horizontal and a vertical line through the point (i, σ_{i}), which will divide the graph of σ into four quadrants. The usual quadrant numbering then lets us more easily describe the position of points relative to (i, σ_{i}). For example, points above and to the left of (i, σ_{i}) are said to be in the second quadrant relative to σ_{i}, or, more succinctly, in σ_{i}’s second quadrant. Kitaev and Remmel [7] began a systematic study of patterns for which the restrictions of the pattern can be described in terms of the quadrants relative to σ_{i}, which they called quadrant marked mesh patterns. (In that paper, the pattern MMP^{k} is denoted by MMP(k ≤ max, ∅, 0, 0).)

The main goal of this paper is to describe the generating function for MMP^{k} in terms of r-Stirling numbers (allowing us to explain some of the results of Kitaev and Remmel [7] more fully) and to examine some related combinatorial questions. Specifically, we will find some new recurrences and descriptions for the r-Stirling numbers, and note a connection to another marked mesh pattern.

2 Preliminaries

For any permutation σ ∈ S_{n}, we define mmp^{k}(σ) to be the number of entries σ_{i} that match MMP^{k} in σ.

mmp^{k}(σ) = |{i | 1 ≤ i ≤ n and i matches MMP^{k} in σ}| .

We will write our permutations in one-line notation. Generally, for σ ∈ S_{n}, we use σ_{1}, σ_{2}, …, σ_{n} throughout to denote the entries of σ. We will also often write σ as

σ = a_{1,1}a_{1,2} ⋯ a_{1,m_{1}}a_{2,1} ⋯ a_{2,m_{2}} ⋯ a_{p,1} ⋯ a_{p,m_{p}},  (1)

where a_{1,1} < a_{2,1} < ⋯ < a_{p,1}, and a_{q,1} > a_{q,m} for any q from 1 to p and m from 1 to m_{q}. We will refer to any of the substrings a_{q,1}a_{q,2} ⋯ a_{q,m_{q}} as a pseudocycle of σ. The entries a_{q,1} are called left-to-right maxima of σ, since if σ is read left-to-right, each entry a_{q,1} is the largest entry read so far. For example, in the permutation 56418732, the three pseudocycles are the substrings 5, 641, and 8732, so we would set a_{1,1} = 5, a_{2,1} = 6, etc. We will also refer to this factorization of σ in Equation (1) as the pseudocycle factorization of σ, and use the notation of (1) when referring to such a factorization throughout.

We note that the permutations in S_{n} with exactly k pseudocycles are counted by the (unsigned) Stirling numbers of the first kind, denoted c(n, k). These numbers are given by

x(x + 1)(x + 2) ⋯ (x + n − 1) = ∑_{i=1}^{n} c(n, k)x^{k}.

We also define the reduction operator red(), which turns a string of k distinct integers into a permutation in S_{k} by setting red(a_{1}a_{2} ⋯ a_{k}) to be the unique permutation σ ∈ S_{k} resulting from arranging 1 through k in the same relative order as the numbers a_{i}. For example, red(3625) = 2413.

3 Generating functions

We now begin our study of the distribution of mmp^{k} on S_{n} with a basic observation relating the number of occurrences of the pattern MMP^{k} in a permutation σ to the pseudocycle structure of σ.

Lemma 1. If σ ∈ S_{n}, then for any k > 1, mmp^{k}(σ) ≤ max(0, n−k). Moreover if mmp^{k}(σ) = j, then in the pseudocycle factorization of σ, the elements that match MMP^{k} in σ are exactly a_{1,1}, a_{2,1}, …, a_{j,1}.

Proof. Use the notation of the pseudocycle factorization in (1) for σ and assume σ has p pseudocycles. Then we note that if σ_{i} matches MMP^{k} in σ, then σ_{i} is a left-to-right maximum, and thus is one of the p entries a_{q,1} for some 1 ≤ q ≤ p. It also implies that there are at least k entries after σ_{i}, so that i ≤ n − k. For the second statement, we note that if a_{i,1} matches MMP^{k} in σ, for i > 1, then there are at least k − 1 elements in the i + 1st through p − 1st pseudocycles that are greater than a_{i,1}. These same k − 1 elements occur between a_{i−1,1} and a_{p,1}, so that a_{i−1,1} also matches MMP^{k} in σ.

The standard generating function for the statistic mmp^{k} is

R_{n}^{k}(x) = ∑_{σ∈S_{n}} x^{mmp^{k}(σ)}.  (2)

There is a recursive formula that allows us to compute R_{n}^{k}(x). Kitaev and Remmel [7] observed that, for any n ≥ 0,

R_{n+1}^{k}(x) = ∑_{i=1}^{n+1}(n + 1 − i)!\binom{n}{i − 1}R_{i−1}^{k−1}(x).

This formula also allows them to give a recursive description of the generating function

R^{k}(t, x) = 1 + ∑_{n≥1} \frac{t^{n}}{n!} ∑_{σ∈S_{n}} x^{mmp^{k}(σ)}.

Specifically, they show that

R^{k}(t, x) = 1 + ∫_{0}^{t} \frac{1}{1 − z} R^{k−1}(z, x)dx.

However, a slight alteration to R_{n}^{k}(x) makes its description more straightforward. Let σ = σ_{1}σ_{2} ⋯ σ_{n}. We say that 0 matches MMP^{k} in σ if n = σ_{i} for some i ≥ k. This is really an extension of the definition of MMP^{k}, since if we were to prepend a 0 to σ and consider it as a permutation σ′ of 0, …, n, then 0 would in fact match MMP^{k} in σ′ as long as n occurs at the kth position or later in σ. In order to specify when we wish to include this expanded notion of matching MMP^{k}, we will define

\overline{mmp}^{k}(σ) = |\{i | 0 ≤ i ≤ n and i matches MMP^{k} in σ\}| .

Conventionally, we will write σ_{0} = 0 when we want to consider this leading 0 as part of the permutation. Notice that \overline{mmp}^{k}(σ) = 0 if and only if n occurs at the k − 1st position or earlier in σ, and we describe this by saying that σ cannot match MMP^{k}. If \overline{mmp}^{k}(σ) = 1, then we say that σ almost matches MMP^{k}. Note that n = σ_{k} is a sufficient but not necessary condition for \overline{mmp}^{k}(σ) = 1. We also point out that if \overline{mmp}^{k}(σ) > 0, then in fact \overline{mmp}^{k}(σ) = mmp^{k}(σ) + 1.

As an example, if σ = 3214 ∈ S_{4}, then mmp^{2}(σ) = 0 and \overline{mmp}^{2}(σ) = 1, so that σ almost matches MMP^{2}. To illustrate that this notion is useful, it can easily be checked that

R_{4}^{2}(x) = 17 + 6x + x^{2}.

However, there are 6 permutations in S_{4} that cannot match MMP^{2}, and 11 that almost match MMP^{2}. Thus, it seems in some ways more natural to write

R_{4}^{2}(x) = 6 + 11 + 6x + x^{2} = c(n, 1) + c(n, 2) + c(n, 3)x + c(n, 4)x^{2}.

More generally, we have the following, which generalizes a result of Kitaev and Remmel [7, Proposition 3].

Theorem 2. For s > 0, the coefficient of x^{s} in R_{n}^{2}(x) is c(n, s + 2). The number of permutations that almost match MMP^{2} is c(n, 2), while the number of permutations that cannot match MMP^{2} is c(n, 1) = (n − 1)!.

Proof. First, we claim that if σ has p > 2 pseudocycles, then mmp^{2}(σ) = p − 2. To see this, write σ in its pseudocycle factorization. As in Lemma 1, if σ_{i} matches MMP^{2} in σ, then σ_{i} is one of the entries a_{q,1} for some 1 ≤ q ≤ p. Conversely, every entry of the form a_{q,1} for 1 ≤ q ≤ p − 2 matches the pattern MMP^{2} in σ, since for such q, the entries a_{q+1,1} and a_{p,1} = n will lie in the first quadrant relative to a_{q,1}. But since a_{p−1,1} is the next-to-last left-to-right maximum, n is the only entry in its first quadrant. Hence, mmp^{2}(σ) = p − 2, as claimed.

For s > 0, this implies that the number of permutations σ that contribute a term of x^{s} to the sum in Equation (2) is precisely the number of permutations with s + 2 pseudocycles, which is counted by c(n, s + 2). The count of permutations that cannot match MMP^{2} is immediate from the definition, and the remaining c(n, 2) permutations must almost match MMP^{2}.

To more easily keep track of \overline{mmp}^{k}, we define a new generating function P_{n}^{k}(x) by setting

P_{n}^{k}(x) = ∑_{π∈S_{n}} x^{\overline{mmp}^{k}(σ)}.

For example,

P_{4}^{2}(x) = 6 + 11x + 6x^{2} + x^{3}.

Of course, R_{n}^{k}(x) is easily recoverable from P_{n}^{k}(x) and vice versa, so we will focus our attention on P_{n}^{k}(x). We also define C_{n,k,j} to be the coefficient of x^{j} in P_{n}^{k}.

For a fixed k, we can generate P_{n}^{k}(x) using the following recursive description.

Theorem 3. For a fixed value of k > 1 and any n ≥ k and j > 0,

C_{n,k,j} = (n − 1)C_{n−1,k,j} + C_{n−1,k,j−1}.

That is,

P_{n}^{k}(x) = (x + n − 1)P_{n−1}^{k}(x).

Also,

C_{n,k,0} = (n − 1)C_{n−1,k,0} and P_{k−1}^{k}(x) = (k − 1)!.

Proof. We first count the set of permutations σ ∈ S_{n} with \overline{mmp}^{k}(σ) = j such that removing the entry 1 and applying red() does not change the value of \overline{mmp}^{k}. That is, we examine the set

X = \{σ ∈ S_{n} | \overline{mmp}^{k}(σ) = j, \overline{mmp}^{k}(σ_{1}σ_{2} ⋯ ˆ1 ⋯ σ_{n}) = j\}.

Given a permutation σ ∈ S_{n−1} with \overline{mmp}^{k}(σ) = j, we construct exactly n − 1 permutations in X. Let σ̃ be the string obtained by adding 1 to each entry of σ. Then we can make n − 1 permutations in S_{n} by inserting 1 into σ̃ in position i = 1, 2, …, n. So, for example, if σ = 1423, then σ̃ = 2534, and the resulting permutations are 21534, 25134, 25314, and 25341.

For any of the permutations σ′ ∈ S_{n} constructed in this way, 1 does not match MMP^{k} in σ′, and in fact removing it from σ′ would not affect any of the entries of σ′ that do match MMP^{k} in σ′, with the possible exception of 0. However, since \overline{mmp}^{k}(σ) = j ≥ 1, then 0 does still match MMP^{k} in σ, and thus removing 1 from σ′ and reducing does not actually change the value of \overline{mmp}^{k}. That is, \overline{mmp}^{k}(σ′) = \overline{mmp}^{k}(σ), and so σ′ ∈ X. This correspondence is exactly 1-to-(n − 1), since it has the inverse correspondence consisting of removing 1 and applying red(). We also claim the correspondence is onto. To see this, let σ′ ∈ X, and let σ be the permutation in S_{n−1} obtained by removing 1 from σ′ and reducing. It is enough to show that the first entry of σ′ cannot be 1, so that σ′ can be obtained from σ using the construction above.

If j > 1, and the first entry of σ′ were 1, then 1 would match MMP^{k} in σ′, and removing it would mean that \overline{mmp}^{k}(σ) < j, contradicting the fact that σ′ ∈ X. If j = 1 and n appears after the kth position in σ′ then the fact that mmp^{k}(σ′) = 0 implies that 1 does not match MMP^{k} in σ, so 1 is not the first entry of σ′. If j = 1 and n is the kth entry of σ, then n − 1 must still be the kth entry of σ, so 1 must occur after n, and is not the first entry of σ′. Thus in any case, 1 is not the first entry of any element of X, and all of the elements of X can be constructed from some σ using the construction above. Then we can conclude that |X| = (n − 1) · C_{n−1,k,j}.

Now, we count the permutations σ ∈ S_{n} with \overline{mmp}^{k}(σ) = j that are not in X, which we do in two parts. First, if j > 1, then we only need to count those permutations with σ_{1} = 1 and \overline{mmp}^{k}(σ) = j. If σ_{1} = 1, then dropping 1 from σ will completely eliminate the first pseudocycle, but will not affect any of the others. Thus red(σ_{2}σ_{3} ⋯ σ_{n}) will match MMP^{k} at exactly j − 1 places - the starting point of each of its first j − 2 pseudocycles and 0. There are exactly C_{n−1,k,j−1} such permutations, and the described correspondence is a bijection, since the inverse map consists of increasing each element of the permutation by 1 and inserting 1 at the start of the string.

If j = 0, the remaining permutations are the σ ∈ S_{n} where σ_{k} = n and 1 appears before n. For each of these, we create a permutation in S_{n−1} that cannot match MMP^{k} as follows - first we swap the positions of n and 1, and then delete 1 and apply red(). This is a bijection, since the inverse map consists of increasing each element of σ′ by 1, inserting 1 in the kth position, and swapping the positions of 1 and n. This completes the proof of the statement C_{n,k,j} = (n − 1)C_{n−1,k,j} + C_{n−1,k,j−1}, and the recursion for P_{n}^{k}(x) follows immediately.

The final statement (including the base case for the recursion and the special case j = 0) is clear from the definition of “cannot match”.

A direct consequence of the second and third statements of this theorem is an easy description of P_{n}^{k}(x).

Corollary 4. For n ≥ k > 0,

P_{n}^{k}(x) = ((k − 1)!) · ∏_{i=k−1}^{n−1}(x + i).

4 The r-Stirling numbers

The recursive relationship in Theorem 3 is the standard recursion for the (unsigned) Stirling numbers of the first kind. In light of Theorem 2, this is not entirely surprising. Of course, for k > 2, the initial conditions for P_{n}^{k}(x) are different from those for c(n, k). The resulting coefficients of P_{n}^{k}(x) are a generalization of the Stirling numbers of the first kind defined originally by Mitrinovic [10], but have appeared in many guises. See Broder [3] and Koutras [8] for some examples. We will use the notation for the r-Stirling numbers of the first kind,

which are defined as follows. We let \begin{cases}n \\ m \end{cases}\}_{r} be the number of permutations in S_{n} with exactly

m left-to-right-maxima such that n, n − 1, …, n − r + 1 are all left-to-right maxima. (We will typically refer to these as just the r-Stirling numbers. While r-Stirling numbers of the second kind exist, we will not use them here.) Theorem 3 immediately implies the following result, but our main goal is an explicit combinatorial correspondence connecting P_{n}(x) and the r-Stirling numbers.

Theorem 5. For n ≥ k ≥ 2 and j ≥ 0, the coefficient C_{n,k,j} is given by

(k − 1)! \begin{cases}n \\ j + k − 1 \end{cases}\}_{k−1}

Proof. First, fix j and assume σ ∈ S_{n} has exactly j + k − 1 left-to-right maxima, including n, n − 1, …, n − k + 2. Say that these left-to-right maxima occur at σ_{i_{1}}, …, σ_{i_{j+k−1}}, where σ_{i_{j+k−1}} = n. From σ, we will construct (k − 1)! permutations counted by C_{n,k,j}, and show that this gives a 1-to-(k − 1)! correspondence. We first note that if j ≥ 1, σ_{i_{j−1}} matches MMP^{k} in σ, since σ_{i_{j}}, …, σ_{i_{j+k−1}} = n are all larger than σ_{i_{j−1}} and occur after it. (If j = 1 we interpret this conventionally to mean σ_{i_{0}} = 0 matches MMP^{k} in σ.) If j = 0, then since σ has k − 1 left-to-right maxima, n must occur in position k − 1 or later in σ.

Now, our argument changes based on whether σ_{i_{j}} matches MMP^{k} in σ. Again, if j = 0, we will conventionally treat σ_{i_{0}} = 0.

Case 1: First assume j > 0. If σ_{i_{j}} does not match MMP^{k} in σ, then we claim that any elements σ_{r} ≥ σ_{i_{j}} that occur between between σ_{i_{j−1}} and n must be one of σ_{i_{j}}, σ_{i_{j+1}}, …, σ_{i_{j+k−2}}. If σ_{r} were such an “extra” element, it could not occur before σ_{i_{j}} since σ_{i_{j}} is a left-to-right maximum, and it could not occur after σ_{i_{j}}, or else σ_{i_{j}} would match MMP^{k} in σ. Then if we rearrange the elements σ_{i_{j}}, σ_{i_{j+1}}, …, σ_{i_{j+k−2}}, but leave all the other entries of σ in the same place, then σ_{i_{j−1}} will still match MMP^{k} in σ. Moreover, no matter how these elements are rearranged, none of them will match MMP^{k} in the resulting permutation, since there are only k − 1 elements between positions i_{j} and i_{j+k−1} that are greater than σ_{i_{j}}, which is the least of all these elements. Then taking all possible rearrangements of σ_{i_{j}} through σ_{i_{j+k−2}} gives us (k − 1)! permutations σ′ with \overline{mmp}^{k}(σ′) = j.

The analogous case for j = 0, where 0 does not match MMP^{k} in σ, is the set of permutations with σ_{k−1} = n. We can rearrange the first k − 1 entries of σ in any order, and all of the resulting permutations cannot match MMP^{k}.

Case 2: Now assume σ_{i_{j}} does match MMP^{k} in σ. (Note that we now make no assumptions on j, so that case 2 includes the possibility that j = 0 and n appears at position k or later.) Since the k − 1 elements n, n − 1, …, n − k + 2 must be among the left-to-right maxima in σ, and σ_{i_{j}} is the kth largest left-to-right maximum, we must have σ_{i_{j+1}} = n − k + 2, σ_{i_{j+2}} = n − k + 3, etc. This implies that the elements that are larger than σ_{i_{j}} that occur between σ_{i_{j}} and n are either in the list σ_{i_{j+1}}, …, σ_{i_{j+k−1}}, or occur between some σ_{i_{r}} and σ_{i_{r+1}}, with r > j. We will create a new permutation σ′ by rearranging σ. The entry σ_{i_{j}} and all entries before it will be left in the same place. However, some of the entries that occur after σ_{i_{j}} but before n will be moved to the end of the string, according to the following algorithm.

For each element σ_{i_{r}}, for r from j + 1 to j + k − 2, we call an entry that lies between σ_{i_{r}} and σ_{i_{r+1}} that is larger than σ_{i_{j}} a “large follower” of σ_{i_{r}}. If σ_{i_{r}} has no large followers, then the string σ_{i_{r}} ⋯ σ_{i_{r+1}−1} will not be directly moved when we rearrange σ. If, however, σ_{i_{r}} has at least one large follower, then we will remove the substring starting at σ_{i_{r}} and ending at the entry before its final large follower, and move that substring to the end of σ. If several entries σ_{i_{r}} have large followers, then we move the strings starting at each σ_{i_{r}} in order based on the last large follower of σ_{i_{r}}, starting with the smallest one. The permutation that results after we have moved all of these strings will be called σ′.

For example, let n = 8, k = 4, and j = 2. (Then we are constructing a permutation in S_{8} that matches MMP^{4} exactly once.) If

σ = 13625748, then σ′ = 13548762.

We have σ_{i_{j}} = 3 which does not match MMP^{k} in σ, and thus we are in case 2. Both 6 and 7 have large followers, and the algorithm tells us to move the substrings 7 and 62 to the end of the string, in that order, since the remaining large followers are 4 and 5 respectively. As another example, if

σ = 13647582, then σ′ = 13458267,

since both 6 and 7 are moved to the end of the string (after the 2), in that order.

Now, we show that the constructed permutation σ′ satisfies \overline{mmp}^{k}(σ′) = j. To do this, it suffices to check that σ_{i_{j}} does not match MMP^{k} in σ′ and σ_{i_{j−1}} does, which will imply that \overline{mmp}^{k}(σ′) = j. But, the given algorithm moves all but one large follower from each substring σ_{i_{r}} ⋯ σ_{i_{r+1}−1} after n so that only one element from that substring that is greater than σ_{i_{j}} remains between σ_{i_{j}} and n. And as noted above, all entries of σ greater than σ_{i_{j}} that occur between σ_{i_{j}} and n are in one of those substrings. Thus σ_{i_{j}} matches MMP^{k−1} but not MMP^{k} in σ′. And since σ_{i_{j−1}} < σ_{i_{j}}, σ_{i_{j−1}} matches MMP^{k} in σ. Then, as in case 1, taking all possible rearrangements of the k − 1 largest elements that occur after σ_{i_{j−1}} and before n gives a total of (k − 1)! permutations σ′′ with \overline{mmp}^{k}(σ′′) = j, constructed from the original σ.

Our work so far has given us a way of constructing (k − 1)! permutations σ′ with

\overline{mmp}^{k}(σ′) = j out of each permutation σ counted by by \begin{cases}n \\ j + k − 1 \end{cases}\}_{k−1}. Now, we must

show that the correspondence we have constructed is exactly one-to-(k − 1)! and onto. To do so, we construct an inverse correspondence.

Let σ ∈ S_{n} be a permutation with \overline{mmp}^{k}(σ) = j. We must construct a permutation σ′ with exactly j + k − 1 left-to-right maxima, including the set X = {n − 1, …, n − k + 2}. By assumption, σ_{i_{j−1}}, the j − 1st left-to-right maximum, is the last element that matches MMP^{k} in σ. Let a_{1}, a_{2}, …, a_{k−1} be the k − 1 largest elements that occur between σ_{i_{j−1}} and n. Then we rearrange the elements a_{2}, a_{3}, …, a_{k−1} in such a way that, if we were to switch the positions of the mth element (in order as the numbers appear in σ) of X that appears after n with the mth smallest of the elements a_{2}, …, a_{k−1}, the elements of X would appear in order.

Finally, for each element r ∈ X that occurs after n, we remove the substring starting at r and ending just before the next occurrence of an entry from X. Each of these substrings is then re-inserted in the string so that the substring starting with the mth element from X after n is inserted just before the mth smallest of the a_{i}. This has the effect that the elements of X now appear in order, after σ_{i_{j}}.

For example, let n = 7, k = 4, and j = 2. Then given the permutation σ = 1324756, we have s = 2, and the a_{i} are the elements 3,2, and 4. We rearrange 2,3, and 4 in σ to get 1423756 since swapping 5 with 2 and 6 with 3 would put 456 in order. Next, we remove the strings 5 and 6 from 1423756 and re-insert them just before 2 and 3 respectively to get σ′ = 1452637. One can easily check that if we apply the original algorithm to σ′, the (k − 1)! permutations we make from σ′ are σ and the permutations we get by rearranging 2,3, and 4 in σ.

Because of the way that we arranged the a_{i}, each of the k−1 elements n−k+2 through n, as well as σ_{i_{j}}, will be left-to-right maxima in the resulting permutation. Also, by assumption, there are exactly j − 1 left-to-right maxima that occur at or before σ_{j−1}. Thus, there are exactly j + k − 1 left-to-right maxima in the resulting permutation. Moreover, this process will reverse the correspondence described above, because of the way (including the order) we chose to move elements with large followers after n in the original algorithm. Thus, the original correspondence is 1-to-(k − 1)!.

This description of the coefficients of P_{n}^{k}(x) allows us to answer an unresolved question about a formula for these coefficients. Kitaev and Remmel [7] observed that a formula for C_{n,4,2} (from entry A001712 in the OEIS [11]) is

6 ∑_{i=2}^{n−3}(−1)^{n+i+1}\binom{i}{2}3^{i−2}s(n − 3, i).

This formula is, in fact, an example of a formula of Mitrinovic [10], which we prove a version of here.

Theorem 6. For k ≥ 2, and 0 ≤ j ≤ n − k + 1, we have

\frac{1}{(k − 1)!}C_{n,k,j} = \begin{cases}n \\ j + k − 1 \end{cases}\}_{k−1} = ∑_{i=j}^{n−k+1} \binom{i}{j}c(n − k + 1, i)(k − 1)^{i−j}.

Thus

C_{n,k,j} = (k − 1)! ∑_{i=j}^{n−k+1} \binom{i}{j}c(n − k + 1, i)(k − 1)^{i−j}.

Proof. We construct a permutation σ counted by \begin{cases}n \\ j + k − 1 \end{cases}\}_{k−1}. First, we know that the

elements n, n − 1, …, n − k + 2 must be left-to-right maxima, and so must occur in order in σ. We choose a way to insert the entries 1 through n − k + 1 to complete σ. For any i from j to n − k + 1, choose one of the c(n − k + 1, i) permutations of 1, …, n − k + 1 (in one-line notation) with exactly i pseudocycles. We choose j of these pseudocycles to be inserted before n − k + 2, and insert them in increasing order of their first entry, so that those first entries are left-to-right maxima of σ. The other i − j pseudocycles will then be inserted somewhere after n − k + 2: between n − k + 2 and n − k + 3, between n − k + 3 and n − k + 4, etc., up to between n − 1 and n, or after n. That gives k − 1 possible places that a given pseudocycle could be inserted. If multiple pseudocycles are inserted in the same place, we arrange the pseudocycles in increasing order of their first entries. There are exactly \binom{i}{j}c(n − k + 1, i)(k − 1)^{i−j} ways to construct σ in this way, and every such σ can be constructed uniquely in this way. The formula for C_{n,k,j} follows immediately from the first part.

Example 7. Let n = 7, k = 4, and j = 2. Then the theorem gives us

119 = \begin{cases}7 \\ 5 \end{cases}\}_{3} = 6 · 1 · 9 + 3 · 6 · 3 + 1 · 11 · 1.

The first term counts permutations using the permutation 1234 (consisting of 4 different pseudocycles) inserted around 5,6, and 7. The second term includes permutations where 1,2,3, and 4 are arranged in a permutation with three pseudocycles, while the last terms fit 1,2,3,4 into two pseudocycles.

The second part of this theorem is somewhat difficult to see directly. Theoretically, we can apply the correspondence described in Theorem 5 to the proof of this theorem to understand it. However, the manner of counting is different for permutations in Case 1 of the proof of Theorem 5 as opposed to Case 2. For example, if n = 6, k = 4, and j = 2, the term \binom{3}{2} · c(3, 3) · 3^{1} counts the permutations 123564, 124365, 124563, 134256, 134526, 134562, 234156,234516, and 234561. The middle 3 and last 3 of these are easily counted - we choose two numbers out of 1,2,3 to start the permutation and then choose for the remaining one to be placed after 4,5, or 6. However, the first 3 (which correspond to Case 1 in Theorem 5) are counted by choosing 1 and 2 to start the permutation and then choosing which of 3,4, or 5 is placed after 6. Now the factor 3 chooses an element, rather than a position for that element. These two cases make the counting argument much clearer for the r-Stirling numbers proper than for the coefficients C_{n,k,j}.

5 A recurrence for fixed n

Now, we examine some more consequences of this description of the coefficients of P_{n}^{k}(x).

Broder [3, Theorem 3] shows that the numbers \begin{cases}n \\ m \end{cases}\}_{r} satisfy the following recursion in r.

\begin{cases}n \\ m \end{cases}\}_{r} = \frac{1}{r − 1} (\begin{cases}n \\ m − 1 \end{cases}\}_{r−1} − \begin{cases}n \\ m − 1 \end{cases}\}_{r}) .

We prove an equivalent result directly for the coefficients of P_{n}^{k}(x). First, we make an observation.

Lemma 8. Let σ be a permutation. For j ≥ 0,

if \overline{mmp}^{k}(σ) = j + 1, then \overline{mmp}^{k+1}(σ) = j + 1 or j.

Proof. The condition of matching MMP^{k+1} is strictly stronger than matching MMP^{k}, so \overline{mmp}^{k+1}(σ) ≤ \overline{mmp}^{k}(σ). This implies the result for j = 0, so we now assume j ≥ 1. Let σ = a_{1}a_{2} ⋯ a_{n}, and let a_{i_{1}}, a_{i_{2}}, …, a_{i_{j}} be the j elements (besides 0) which match MMP^{k} in σ, written so that i_{1} < i_{2} < ⋯ < i_{j}. Since a_{i_{j}} matches MMP^{k} in σ, we know that a_{i_{j−1}} < a_{i_{j}}, and that there are at least k entries of σ larger than a_{i_{j}} that occur after a_{i_{j}} but (weakly) before n. Then those k entries and a_{i_{j}} are a set of k + 1 elements that are larger than a_{i_{j−1}} and occur after it in σ, but weakly before n. Thus a_{i_{j−1}} matches MMP^{k+1} in σ. Then Lemma 1 implies that a_{i_{1}}, …, a_{i_{j−2}} match MMP^{k+1}, and \overline{mmp}^{k+1}(σ) ≥ j.

Theorem 9. Let k > 1 and j > 0. Then

(k − 1) · |\{σ ∈ S_{n} | \overline{mmp}^{k}(σ) = j and \overline{mmp}^{k+1}(σ) = j − 1\}|
= |\{σ ∈ S_{n} | \overline{mmp}^{k}(σ) = j − 1 and \overline{mmp}^{k+1}(σ) = j − 1\}| .

As a result, C_{n,k+1,j−1} is given by

k · |\{σ ∈ S_{n} | \overline{mmp}^{k}(σ) = j and \overline{mmp}^{k+1}(σ) = j − 1\}| .

Proof. We give an explicit k − 1-to-one correspondence between the two sets in question. Write σ in its pseudocycle factorization, with a_{1,1} < a_{2,1} < ⋯ < a_{p,1} the left-to-right maxima of σ. Moreover, assume that \overline{mmp}^{k}(σ) = j and \overline{mmp}^{k+1}(σ) = j − 1. Then, by Lemma 1, a_{j−1,1} matches MMP^{k} but not MMP^{k+1}. (If j = 1, then a_{0,1} is again considered to be the “virtual” entry 0 at the start of σ.) Then, there are exactly k − 1 entries of σ that are larger than a_{j−1,1} that occur after a_{j−1,1} but strictly before a_{p,1} = n. Say that these entries are indexed a_{i_{1}}, a_{i_{2}}, …, a_{i_{k−1}}, with a_{j−1,1} < a_{i_{1}} < a_{i_{2}} < ⋯ < a_{i_{k−1}}. Note that the a_{i_{q}} and a_{j−1,1} are the k largest elements that occur in the j − 1st through p − 1st pseudocycles of σ, since the a_{i_{q}} are the only elements larger than a_{j−1,1} that occur in those pseudocycles.

Then, for q from 1 to k−1, define π_{q} to be the permutation identical to σ, except with the positions of a_{j−1,1} and a_{i_{q}} switched. We claim that \overline{mmp}^{k}(π_{q}) = j − 1 = \overline{mmp}^{k+1}(π_{q}). First, we note that the entries a_{1,1}, a_{2,1}, …, a_{j−2,1} still match MMP^{k+1} in π_{q}, since for any r from 1 to j −2, the set of numbers between a_{r,1} and a_{p,1} in π_{q} is the same as in σ. However, a_{i_{q}} does not match MMP^{k} in π_{q} since the only entries of π_{q} that are larger than a_{i_{q}} that occur after the j − 2nd pseudocycle but before the last pseudocycle are a_{i_{q+1}}, …, a_{i_{k−1}}. However, there are only k −1−q < k −1 such elements. Moreover, since a_{j−1,1} began the j −1st pseudocycle of σ, it was greater than all the entries of σ before it. Since a_{i_{q}} > a_{j,1}, we know that a_{i_{q}} is now the first entry of the j − 1st pseudocycle of π_{q}. Thus, \overline{mmp}^{k}(π_{q}) = j − 1 = \overline{mmp}^{k+1}(σ).

To finish the proof, we construct the correspondence in the opposite direction. Let π be any permutation with \overline{mmp}^{k}(π) = j −1 and \overline{mmp}^{k+1}(π) = j −1. Write π in the pseudocycle notation of (1). Then, by assumption and Lemma 1, a_{j−2,1} matches MMP^{k+1} and MMP^{k} in π, but a_{j−1,1} matches neither. Thus, there are at least k entries of π larger than a_{j−2,1} that occur after a_{j−2,1} but strictly before a_{p,1} = n, but at most k − 1 of those occur after a_{j−1,1}. Since none of those entries larger than a_{j−2,1} can occur in the j − 2nd pseudocycle, there must be exactly k of these (a_{j−1,1} and k − 1 others that occur after a_{j−1,1}) which we call a_{i_{1}}, a_{i_{2}}, …, a_{i_{k}}. Assume that a_{i_{1}} < a_{i_{2}} < ⋯ < a_{i_{k}}. Let q be the index so that a_{j,1} = a_{i_{q}}. Notice that q ≠ 1, since if it were, then a_{j,1} would match MMP^{k} in π. Then, let σ be the permutation identical to π, except with the positions of a_{i_{1}} and a_{i_{q}} switched. Then by construction, π is exactly the permutation π_{q} constructed from σ as in the previous paragraph.

24  +50x  +35x^{2}  +10x^{3}  +x^{4}
↓_{24} ↙_{24} ↓_{26} ↙_{26} ↓_{9} ↙_{9} ↓_{1} ↙_{1}
48 +52x +18x^{2} +2x^{3}
↓_{48} ↙_{24} ↓_{28} ↙_{14} ↓_{4} ↙_{2}
72 +42x +6x^{2}
↓_{72} ↙_{24} ↓_{18} ↙_{6}
96  +24x
↓_{96} ↙_{24}

120

Figure 2: A Recursive Calculation of P_{5}^{k}(x) for k ≤ 5.

This shows that the correspondence above is exactly (k − 1)-to-one, and its image is the entire set \{σ ∈ S_{n} | \overline{mmp}^{k}(σ) = j − 1 and \overline{mmp}^{k+1}(σ) = j − 1\}.

The second part of the result then follows from the first part and Lemma 8.

This result can be seen in Table 2, displaying the generating functions P_{5}^{k}(x), beginning with k = 2 in the first row. The arrows between the polynomials demonstrate the number of permutations in the sets described by the theorem. For example, the arrow from 10x^{3} in the first row to 18x^{2} in the second row depicts the 9 permutations σ with \overline{mmp}^{2}(σ) = 3 and \overline{mmp}^{3}(σ) = 2. We can determine the labels on the arrows from right-to-left, since the first diagonal arrow on the right in each row must be labeled with the coefficient of the highest degree term, each diagonal arrow determines the vertical arrow pointing to the same term (by the theorem), and the total labels on the two arrows coming from any given term must add up to the coefficient of that term.

We define the notation

m_{n,k,i,j} = |{σ ∈ S_{n} | mmp^{k}(σ) = i and mmp^{k+1}(σ) = j}|

for the marks on the arrows in diagrams like this one.

As a result, we can easily deduce the following recurrence relation satisfied by the coefficients of P_{n}^{k}(x). It essentially describes the process of determining one row of the above table from the previous row.

Corollary 10. For k ≥ 2 and 0 ≤ j ≤ n − k,

C_{n,k+1,j} = ∑_{i=j+1}^{n−k+1} k(1 − k)^{i−j−1}C_{n,k,i}.

Proof. We prove the corollary inductively. By Lemma 8, if \overline{mmp}^{k}(σ) = n − k + 1, then \overline{mmp}^{k+1}(σ) = n − k. Thus the theorem implies that C_{n,k+1,n−k} = k · C_{n,k,n−k+1}. That is, the corollary holds for j = n − k. Then, assume that the formula in the corollary holds for some j > 1. This implies (using the second part of the theorem) that

∑_{i=j+1}^{n−k+1}(k)(1 − k)^{i−j−1}C_{n,k,i} = C_{n,k+1,j} = k · m_{n,k,j+1,j}.  (3)

Then, by Lemma 8 and the theorem,

C_{n,k+1,j−1} = m_{n,k,j−1,j−1} + m_{n,k,j,j−1} = k · m_{n,k,j,j−1}  (4)

and

m_{n,k,j,j−1} = C_{n,k,j} − m_{n,k,j,j} = C_{n,k,j} − (k − 1)m_{n,k,j+1,j}.  (5)

Thus, by (3), (4), and (5),

C_{n,k+1,j−1} = k(C_{n,k,j} + (1 − k)m_{n,k,j+1,j})

= kC_{n,k,j} + (1 − k) · ∑_{i=j+1}^{n−k+1}(k)(1 − k)^{i−j−1}C_{n,k,i}

= ∑_{i=j}^{n−k+1}(k)(1 − k)^{i−j}C_{n,k,i}.

That is, the theorem is true for j − 1, and by induction, it is true for all j ≥ 0.

Corollary 11. For k ≥ 2 and 0 ≤ j ≤ n − k,

\begin{cases}n \\ j + k \end{cases}\}_{k} = ∑_{i=j+1}^{n−k+1}(1 − k)^{i−j−1} \begin{cases}n \\ i + k − 1 \end{cases}\}_{k−1} .

Proof. Simply substituting the formula for C_{n,k,j} given in Theorem 5 into the previous corollary and canceling k! from both sides gives this result.

This corollary is a special case of a theorem of Broder [3, Theorem 19], but is included since it is such an easy consequence of Theorem 9. However, our main goal for the results of this section (and pictures like Figure 2) is to describe a (seemingly new) connection between the r-Stirling numbers and the classical Stirling numbers.

6 The classical Stirling numbers

The recursive description of the coefficients of P_{n}^{k}(x) gives us another way to compute an explicit formula for any coefficient C_{n,k,j}. For example, we can compute a formula for the coefficients of P_{n}^{3}(x) as follows. We assume that n is large, and begin by writing the entries

c(n, 1)  c(n, 2)x  c(n, 3)x^{2}  ⋯
↓_{c(n,1)} ↙  ↓_{c(n,2)−c(n,1)}  ↙  ↓_{c(n,3)−c(n,2)+c(n,1)}  ⋯
2c(n, 1)  2(c(n, 2) − c(n, 1))x  2(c(n, 3) − c(n, 2) + c(n, 1))x^{2} ⋯

Figure 3: Table to compute C_{n,3,j} in terms of c(n, k).

c(n, 1), c(n, 2), etc. in the first row. We can then mark the arrows in the diagram left-to-right - the first vertical arrow (And thus the first diagonal arrow) is marked with c(n, 1). Thus the second pair of arrows are both marked with c(n, 2) − c(n, 1). Continuing in this fashion, we can fill out the entire second row of the diagram.

The alternating sum of Stirling numbers of the first kind that appear in this diagram is in fact plus or minus the sum of signed Stirling numbers of the first kind, whichever makes the total sum positive. Thus, the computations depicted in the diagram prove the following corollary.

Corollary 12. For any n > 1,

P_{n}^{3}(x) = ∑_{j=0}^{n−2} 2 |∑_{i=1}^{j+1} s(n, i)| x^{j}.

Kitaev and Remmel pointed out a special case of this theorem [7, Proposition 4]. As another example, we find a formula for the number of permutations that almost match MMP^{k}. To do so, we fill out only the first two columns of the diagram above. The first vertical and diagonal arrows are determined, and from the first diagonal arrow and the second entry in each row, we can compute the mark on the second vertical arrow. Thus we can compute the entire table one column at a time, since each entry in the kth row of the table is \frac{k}{k−1} times the mark on the vertical arrow pointing to it.

c(n, 1)  c(n, 2)x  c(n, 3)x^{2}
↓_{c(n,1)} ↙  ↓_{c(n,2)−c(n,1)}  ↙  ↓_{c(n,3)−c(n,2)+c(n,1)}
2c(n, 1)  (2c(n, 2) − 2c(n, 1)) x  (2c(n, 3) − 2c(n, 2) + 2c(n, 1)) x^{2}
↓_{2c(n,1)} ↙  ↓_{2c(n,2)−3c(n,1)}  ↙  ↓_{2c(n,3)−3c(n,2)+ \frac{7}{2} c(n,1)}
3c(n, 1)  (3c(n, 2) − \frac{9}{2}c(n, 1)) x  (3c(n, 3) − \frac{9}{2}c(n, 2) + \frac{21}{4}c(n, 1)) x^{2}
↓_{3c(n,1)} ↙  ↓_{3c(n,2)− \frac{11}{2} c(n,1)}  ↙  ↓_{3c(n,3)− \frac{11}{2} c(n,2)+ \frac{170}{24} c(n,1)}
4c(n, 1)  (4c(n, 2) − \frac{44}{6}c(n, 1)) x  (4c(n, 3) − \frac{44}{6}c(n, 2) + \frac{340}{36}c(n, 1)) x^{2}
↓_{4c(n,1)} ↙  ↓_{4c(n,2)− \frac{50}{6} c(n,1)x}  ↙  ↓_{4c(n,3)− \frac{50}{6} c(n,2)+ \frac{415}{36} c(n,1)}
5c(n, 1)  (5c(n, 2) − \frac{250}{24}c(n, 1)) x  (5c(n, 3) − \frac{250}{24}c(n, 2) + \frac{2075}{144}c(n, 1)) x^{2}
Figure 4: Table to compute C_{n,k,1} and C_{n,k,2} in terms of c(n, k)

We can see from this computation that the number of permutations that almost match MMP^{k} is of the form (k − 1)c(n, 2) − Ac(n, 1) for some positive constant A, which can be found recursively, or by using boundary conditions to solve for A = \frac{c(k,2)−(k−2)!}{(k−2)!}. (The numerator of the coefficient of c(n, 1) in this formula is A052881 in the OEIS [11].)

In light of Theorem 5, this formula expresses \begin{cases}n \\ r + 1 \end{cases}\}_{r} as a linear combination of the

classical Stirling numbers. But this procedure could be continued, so that we have the following.

Fact 13. For any j ≥ 0 and k ≥ 2, there are constants a_{m,r,1}, a_{m,r,2}, …, a_{m,r,m−r} so that, for all n > j + k − 2, we have

\begin{cases}n \\ m \end{cases}\}_{r} = ∑_{i=1}^{m−r} a_{m,r,i}c(n, i).

We will describe these coefficients more precisely in Theorem 14 below. Note that the r-Stirling numbers were previously known to be linear combinations of classical Stirling

numbers of the first kind. Koutras [8, Equation 1.8] (for example) describes \begin{cases}n \\ m \end{cases}\}_{r} as a

linear combination of c(k, k), c(k + 1, k), …, c(n, k) rather than c(n, 1), c(n, 2), …, c(n, k),

as we have here. Broder [3, Equation 43] also describes \begin{cases}n \\ m \end{cases}\}_{r} as a linear combination of

Stirling numbers, but as an integer linear combination of c(n, m), c(n, m + 1), …, c(n, n), so that the formulas described in this fact are new. (In fact, Broder’s formula can be recovered by drawing a table like Figure 4 that starts from the right-hand side rather than the left.)

7 Harmonic sums

The Stirling numbers (and thus the r-Stirling numbers) have a number of connections to harmonic numbers, which we now explore. We define the nth harmonic number to be H_{n}^{(1)} = ∑_{i=1}^{n} \frac{1}{i}. We recursively define the iterated harmonic sum for j > 1 by

H_{n}^{(j)} = ∑_{i=1}^{n} \frac{H_{i}^{(j−1)}}{i} .

Conventionally, we will set H_{n}^{(0)} = 1 for any n > 0.

We will be most interested in the sequences nH_{n−1}^{(j)}. For example, nH_{n−1}^{(1)} is the sequence

2, 9/2, 44/6, 250/24, …

which are exactly the coefficients of c(n, 1) that appear in the second column of Figure 4. We can also check that nH_{n−1}^{(2)} is

2, 21/4, 340/36, …

which appear in the third column of Figure 4. This leads us to the following theorem.

Theorem 14. For j > 0, and k > 2, the coefficients of P_{n}^{k}(x) satisfy

C_{n,k,j} = ∑_{i=1}^{j+1}(k − 1)H_{k−2}^{(j+1−i)}(−1)^{j+1−i}c(n, i).

Proof. We proceed inductively. For k = 3, the statement is exactly the same as Corollary 12. Now, we assume the result for a fixed value of k, and prove the result for C_{n,k+1,j} by induction on j. Again, the result for j = 0 is obvious since C_{n,k+1,0} = k(n − 1)! = kc(n, 1), as the theorem claims. Now, we assume the result for C_{n,k+1,j} for some fixed j, and prove the result for j + 1.

By assumption, C_{n,k+1,j} = ∑_{i=1}^{j+1} kH_{k−1}^{(j+1−i)}(−1)^{j+1−i}c(n, i). Then, we imagine the tables as drawn in Figure 4, focusing on C_{n,k,j+1}, C_{n,k+1,j}, and C_{n,k+1,j+1}. Recall the notation m_{n,k,j,j′} for the mark on the arrow pointing from C_{n,k,j} to C_{n,k+1,j′}. By Theorem 9, m_{n,k,j+1,j} = ∑_{i=1}^{j+1} H_{k−1}^{(j+1−i)}(−1)^{j+1−i}c(n, i). Then, we compute

m_{n,k,j+1,j+1} = C_{n,k,j+1} − ∑_{i=1}^{j+1} H_{k−1}^{(j+1−i)}(−1)^{j+1−i}c(n, i)

= ∑_{i=1}^{j+2}(k − 1)H_{k−2}^{(j+2−i)}(−1)^{j+2−i}c(n, i) − ∑_{i=1}^{j+1} H_{k−1}^{(j+1−i)}(−1)^{j+1−i}c(n, i)

= (k − 1)c(n, j + 2) + ∑_{i=1}^{j+1}(−1)^{j+2−i}c(n, i) ((k − 1)H_{k−2}^{(j+2−i)} + H_{k−1}^{(j+1−i)})

= (k − 1) (c(n, j + 2) + ∑_{i=1}^{j+1}(−1)^{j+2−i}c(n, i) (H_{k−2}^{(j+2−i)} + \frac{1}{k − 1}H_{k−1}^{(j+1−i)}))

= (k − 1) (c(n, j + 2) + ∑_{i=1}^{j+1}(−1)^{j+2−i}c(n, i)H_{k−1}^{(j+2−i)}) .

But again by Theorem 9, C_{n,k+1,j+1} is

\frac{k}{k − 1}m_{n,k,j+1,j+1} = ∑_{i=1}^{j+2}(−1)^{j+2−i}k · c(n, i)H_{k−1}^{(j+2−i)},

as desired.

Loeb [9] defines a generalization of the Stirling numbers s(n, k) for arbitrary values of n, and examines these numbers when n is a negative integer. Briefly, s(n, k) can be defined for all integers n and k ≥ 0 using the recursive relation s(n + 1, k) = s(n, k − 1) − ns(n, k) and the initial conditions s(n, 0) = δ_{n0}.

For our purposes, we will only use the following theorem.

Theorem 15. ([9, Theorem 2]) Using Loeb’s [9] definition of s(−n, k), we have

(−1)^{k}n!s(−n, k) = H_{n}^{(k)}.

Substituting this formula for H_{m}^{(k)} into Theorem 14 gives us an appealing formula for the coefficients C_{n,k,j} and the r-Stirling numbers in terms of c(n, k) and s(−n, k).

Corollary 16. For j > 0 and k > 2, we have

C_{n,k,j} = ∑_{i=1}^{j+1}(k − 1)!s(2 − k, j + 1 − i)c(n, i)

and

\begin{cases}n \\ j + r \end{cases}\}_{r} = ∑_{i=1}^{j+1} s(1 − r, j + 1 − i)c(n, i).

Interestingly, this is not the only connection between r-Stirling numbers and iterated harmonic sums. We define another set of iterated harmonic sums as follows. Set

H_{n,j}^{1} = ∑_{1≤i_{1}<i_{2}<···<i_{j}≤n} \frac{1}{i_{1}i_{2} ⋯ i_{j}} ,

and then for k > 1, recursively define

H_{n,j}^{k} = ∑_{i=1}^{n} H_{i,j}^{k−1}.

(Notice the slight change in notation to distinguish this notion from H_{n}^{(j)}.) Of course, H_{n,j}^{k} = 0 for any n < j.

First, we note that the generating function for the Stirling numbers of the first kind,

(x + 1)(x + 2) ⋯ (x + n − 1) = ∑_{j=0}^{n−1} c(n, j + 1)x^{j}

easily implies that

c(n, j + 1) = ∑_{1≤i_{1}<i_{2}<···<i_{n−j−1}≤n−1} i_{1}i_{2} ⋯ i_{n−j−1} = e_{n−j−1}(1, 2, …, n − 1).

(Here, e_{k} is the usual elementary symmetric function.) We can re-write this formula for j > 0 as

c(n, j + 1) = (n − 1)! ∑_{1≤i_{1}<i_{2}<···<i_{j}≤n−1} \frac{1}{i_{1}i_{2} ⋯ i_{j}} = (n − 1)!H_{n−1,j}^{1}.  (6)

Similarly, the r-Stirling numbers have generating function

(x + r)(x + r + 1) ⋯ (x + n − 1) = ∑_{j=0}^{n−r} \begin{cases}n \\ j + r \end{cases}\}_{r} x^{j},

so that

\begin{cases}n \\ j + r \end{cases}\}_{r} = ∑_{r≤i_{1}<i_{2}<···<i_{n−j−r}≤n−1} i_{1}i_{2} ⋯ i_{n−j−r} = e_{n−j−r}(r, r + 1, …, n − 1),

which is equivalent to

\begin{cases}n \\ j + r \end{cases}\}_{r} = \frac{(n − 1)!}{(r − 1)!} ∑_{r≤i_{1}<i_{2}<···<i_{j}≤n−1} \frac{1}{i_{1}i_{2} ⋯ i_{j}} .

A combinatorial interpretation is of this formula is described by Broder [3, Theorem 7].

However, there is another way to generalize equation (6). We begin with another recurrence we can use to describe the r-Stirling numbers, which is due to Broder [3, Lemma 11].

Proposition 17. For r > 1 and n ≥ m ≥ r, the r-Stirling numbers satisfy

\begin{cases}n \\ m \end{cases}\}_{r} = ∑_{i=0}^{n−m} \frac{(n − r)!}{(m + i − r)!} \begin{cases}m + i − 1 \\ m − 1 \end{cases}\}_{r−1} .

Proof. We count the permutations counted by \begin{cases}n \\ m \end{cases}\}_{r} according to the position of n. Consider

a permutation σ in S_{n} with m left-to-right maxima that include n, n−1, …, n−r+1. Since n is the mth largest left-to-right maximum, it must occur at position m or later in σ. Now, for i from 0 to n−m, we notice that if n is in position m+i, then the n−i−m entries that occur after n in σ will not be left-to-right maxima, so they must be chosen from 1, 2, …, n − r. There are then \frac{(n−r)!}{(m+i−r)!} ways to choose and place these elements. We also note that exactly m − 1 more left-to-right maxima must occur before n, including n − 1, n − 2, …, n − r + 1. This implies that red(σ_{1}σ_{2} ⋯ σ_{m+i−1}) is a permutation in S_{m+i−1} with exactly m − 1 left-to-right maxima, including m + i − 1, m + i − 2, …, m + i − r + 1, of which there are exactly

\begin{cases}m + i − 1 \\ m − 1 \end{cases}\}_{r−1}.

Then another formula for the r-Stirling numbers is given by the following.

Theorem 18. For r ≥ 1, m > r and n ≥ r,

\begin{cases}n \\ m \end{cases}\}_{r} = (n − r)!H_{n−r,m−r}^{r}.

Proof. The result is clear if r = 1, since then the formula coincides with that given in (6). We proceed by induction on r. Recall that

(n − r)!H_{n−r,m−r}^{r} = (n − r)! ∑_{i=1}^{n−r} H_{i,m−r}^{r−1} = (n − r)! ∑_{i=m−r}^{n−r} H_{i,m−r}^{r−1}

= (n − r)! ∑_{i=0}^{n−m} H_{m+i−r,m−r}^{r−1}

We claim that, for i from 0 to n−m, the term (n−r)!H_{m+i−r,m−r}^{r−1} counts the permutations σ

with n in position m + i. By the proof of Proposition 17, there are \frac{(n−r)!}{(m+i−r)!} \begin{cases}m + i − 1 \\ m − 1 \end{cases}\}_{r−1}

such permutations. However, inductively, we may assume that

\begin{cases}m + i − 1 \\ m − 1 \end{cases}\}_{r−1} = (m + i − r)!H_{m+i−r,m−r}^{r−1}.

Then the total number of permutations we have just counted is

\frac{(n − r)!}{(m + i − r)!} · (m + i − r)!H_{m+i−r,m−r}^{r−1} = (n − r)!H_{m+i−r,m−r}^{r−1}.

Then summing over all i from 0 to n − m gives the desired result.

Although this particular description of this formula for the r-Stirling numbers seems to be new, the formula itself is not entirely new. We could trace back the nested sums

H_{n−r,m−r}^{r} to express \begin{cases}n \\ m \end{cases}\}_{r} as an integer linear combination of the original harmonic sums

H_{i,m−1}^{1} = \frac{1}{i!} \begin{cases}1 + i \\ m \end{cases}\}_{1}. That formula appears to be a special case of a theorem of Broder [3,

Theorem 12, the case p = 1].

Adamchik [1] makes some other connections between the classical Stirling numbers and generalized harmonic numbers.

8 Border patterns

Finally, we note that the r-Stirling numbers \begin{cases}n \\ r + 2 \end{cases}\}_{r} are also related to another permutation

pattern. Kitaev and Liese [6] introduce the border mesh pattern p in Figure 5.

This pattern is called a border pattern since the squares around the outside edge of the pattern are all marked “= 0”. We say that a permutation σ = σ_{1} ⋯ σ_{n} matches the pattern p if σ_{1} > 1, σ_{n} = n, and there is an entry a so that σ_{1} < a < n, and a occurs after 1 in σ.

[figure]

Figure 5: The pattern p

(The first dot in the picture is σ_{1}, the second must be 1, and the fourth must be n. The third dot in the picture is a.) When we count occurrences of p, we will count every set of 4 entries of σ that meet the description of the pattern. Since σ_{1}, 1, and n must be involved in the pattern, this is equivalent to counting the number of possibilities for a - i.e., the number of entries between 1 and n that are larger than σ_{1}.

Theorem 19. For any k ≥ 1, the number of permutations in S_{n} that match p exactly k times is exactly the number of permutations in S_{n−1} that match MMP^{k+1} exactly once, but almost match MMP^{k+2}.

Proof. Again, we can give a bijective proof. First, we note that if σ = σ_{1} ⋯ σ_{n} ∈ S_{n} matches p exactly k times, then σ = σ_{1}A1Bn, where A and B are strings, and B contains exactly k elements larger than σ_{1}. Then we form σ′ = σ_{1}BnA, and let ϕ = (σ_{1} − 1)B′(n − 1)A′, where A′ and B′ are obtained from A and B, respectively, by subtracting 1 from each number in the string. Then ϕ ∈ S_{n−1} since σ′ contained 2, …, n.

Since the string B contains exactly k elements greater than σ_{1}, B′ will contain exactly k elements greater than σ_{1} − 1. Hence ϕ will match MMP^{k+1} but not MMP^{k+2}. This map will be a bijection since its inverse can be constructed easily.

References

[1] V. Adamchik, On Stirling numbers and Euler sums, J. Comput. Appl. Math. 79 (1997), 119–130.

[2] P. Brändén and A. Claesson, Mesh patterns and the expansion of permutation statistics as sums of permutation patterns, Electron. J. Combin. 18 (2011), Article #P5.

[3] A. Z. Broder, The r-Stirling numbers, Discrete Math. 49 (1984), 241–259.

[4] L. Carlitz, Weighted Stirling numbers of the first and second kind I, Fibonacci Quart. 18 (1980), 147–162.

[5] L. Carlitz, Weighted Stirling numbers of the first and second kind II, Fibonacci Quart. 18 (1980), 242–257.

[6] S. Kitaev and J. Liese, Harmonic numbers, Catalan’s triangle and mesh patterns, Discrete Math. 313 (2013) 1515–1531.

[7] S. Kitaev and J. Remmel, Quadrant marked mesh patterns, J. Integer Seq. 15 (2012), Paper 12.4.7.

[8] M. Koutras, Non-central Stirling numbers and some applications, Discrete Math. 42 (1982), 73–89.

[9] A. Loeb, A generalization of the Stirling numbers. Discrete Math. 103 (1992), 259–269.

[10] D. Mitrinovic, Sur une classe de nombres reliés aux nombres de Stirling, C. R. Math. Acad. Sci. Paris. 252 (1961), 2354–2356.

[11] N. J. A. Sloane, Online Encyclopedia of Integer Sequences, http://oeis.org.

[12] H. Úlfarsson, A unification of permutation patterns related to Schubert varieties, Pure Math. Appl. 22 (2011), 273–296.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05E15. Keywords: permutation pattern, marked mesh pattern, permutation statistic, r-Stirling number, harmonic number.

(Concerned with sequences \underline{A001712} and \underline{A052881}.)

Received November 30 2014; revised versions received April 12 2015; August 31 2015. Published in Journal of Integer Sequences, September 8 2015.

Return to Journal of Integer Sequences home page.