Combinatorial Proofs of Some Stirling Number Convolution Formulas

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

                       mshattuc@utk.edu

Abstract

Recently, some new convolution formulas extending the orthogonality of the Stirling numbers of the first and second kind were shown by algebraic techniques. The formulas involve sums of products of the two Stirling numbers wherein the inner arguments vary while differing by a prescribed amount and the outer arguments are fixed. Here, we provide combinatorial proofs of these formulas using direct enumeration and signchanging involutions. Our arguments may be extended to establish generalizations of the foregoing results in terms of the r-Stirling numbers.

1 Introduction

Perhaps two of the most prevalent number sequences in enumerative combinatorics are the Stirling numbers of the first and second kind, which will be denoted here by \left[{n \atop k}\right] and \left\{{n \atop k}\right\} respectively in accordance with [7]. See sequences \underline{A008275} and \underline{A008277} in the On-Line Encyclopedia of Integer Sequences [12] and references contained therein. Recall that \left[{n \atop k}\right] counts the permutations of [n] = {1, …, n} having k cycles (and is often referred to as the signless Stirling number of the first kind), whereas \left\{{n \atop k}\right\} enumerates the partitions of [n] with k blocks. Both kinds of Stirling numbers satisfy a variety of identities; see, for example, the texts [4, Chap. V], [5, §6.1], and [10] as well as the recent papers [2, 3, 6, 11].

We will need the following further notation. Define the generalized harmonic number σ_{λ}(m; n) by

σ_{λ}(m; n) = ∑_{m≤i_{1}<···<i_{λ}≤n} ∏_{j=1}^{λ} \frac{1}{i_{j}} ,  λ > 0,

with σ_{0}(m; n) = 1. Denote the Lah number (see [12, \underline{A008297}]) by \left⌊{n \atop k}\right⌋, which counts the partitions of [n] into k contents-ordered blocks (i.e., blocks in which the order of the elements contained therein matters). Recall that \left⌊{n \atop k}\right⌋ is given explicitly by \left⌊{n \atop k}\right⌋ = \frac{n!}{k!} \binom{n−1}{k−1} for 1 ≤ k ≤ n, which is also seen to hold for k = 0 and all n ≥ 0 if one adopts the convention \binom{i}{−1} = δ_{i,−1} for integers i ≥ −1.

Chu [3] considered the following general sums where λ denotes an arbitrary integer:

Φ_{m,n}(λ) = ∑_{k=m}^{n−λ} \left[{n \atop k + λ}\right]\left\{{k \atop m}\right\}  (1)

and

Ψ_{m,n}(λ) = ∑_{k=m}^{n−λ} \left[{n \atop k + λ}\right]\left\{{k \atop m}\right\}(−1)^{n−k}.  (2)

Note that the evaluations of (1) and (2) when λ = 0 correspond to the well-known identities

∑_{k=m}^{n} \left[{n \atop k}\right]\left\{{k \atop m}\right\} = \left⌊{n \atop m}\right⌋

and

∑_{k=m}^{n} \left[{n \atop k}\right]\left\{{k \atop m}\right\}(−1)^{n−k} = δ_{m,n},

see, e.g., [5, §6.1]. Further, the evaluation of (2) when λ = 1 is known and gives

∑_{k=m}^{n−1} \left[{n \atop k + 1}\right]\left\{{k \atop m}\right\}(−1)^{n−k} = (−1)^{n−m} \frac{(n − 1)!}{m!},

which corresponds to [5, Identity 6.25].

The following general identities for Φ_{m,n}(λ) and Ψ_{m,n}(λ) were established in [3] by algebraic methods using a connection coefficient approach:

Φ_{m,n}(λ) = ∑_{j=m}^{n−λ} \frac{(n − 1)!}{m!}\binom{j − 1}{m − 1}σ_{λ−1}(j + 1; n − 1), λ > 0,  (3)

Φ_{m,n}(λ) = ∑_{i=0}^{−λ} ∑_{j=0}^{i} \frac{(−1)^{λ+j}}{n^{λ+i}} \binom{−λ}{i}\left\{{i \atop j}\right\}\left⌊{j + n \atop m}\right⌋, λ < 0,  (4)

Ψ_{m,n}(λ) = (−1)^{n−m} \frac{(n − 1)!}{m!}σ_{λ−1}(m + 1; n − 1), λ > 0,  (5)
Ψ_{m,n}(λ) = ∑_{i=0}^{−λ} \frac{(−1)^{λ}}{n^{λ+i}} \binom{−λ}{i}\left\{{i \atop m − n}\right\}, λ < 0.  (6)

Throughout, one may assume n, m ≥ 0 with λ ∈ ℤ, where it is seen that the lower index of summation in the definitions of Φ_{m,n}(λ) and Ψ_{m,n}(λ) may be replaced by k = max{m, −λ}. Note also that both Φ_{m,n}(λ) and Ψ_{m,n}(λ) are zero if n < m + λ; hence, one may assume further n ≥ m + λ to avoid trivialities.

In the next section, we provide combinatorial proofs of (3)–(6). We make use of direct enumeration to show (3), together with sign-changing involutions to prove (4)–(6). Our proofs may be extended to afford combinatorial explanations of some related recurrences from [3] for Φ_{m,n}(λ) and Ψ_{m,n}(λ). In the third section, we generalize (3)–(6) to the r-Stirling numbers of the first and second kind, which are denoted by \left[{n \atop k}\right]_{r} and \left\{{n \atop k}\right\}_{r}. See [1, 8], where these numbers were introduced, and [9] for a list of useful properties.

Recall that \left[{n \atop k}\right]_{r} enumerates the permutations of [n + r] having k + r cycles in which the elements of [r] lie in distinct cycles, while \left\{{n \atop k}\right\}_{r} counts partitions of [n + r] with k + r blocks in which the elements of [r] belong to distinct blocks. Note that \left[{n \atop k}\right]_{r} and \left\{{n \atop k}\right\}_{r} reduce respectively to \left[{n \atop k}\right] and \left\{{n \atop k}\right\} when r = 0. Using the combinatorial interpretation for the r-Stirling numbers, one may extend the arguments of the subsequent section and find formulas for the sums obtained by replacing \left[{n \atop k+λ}\right] and \left\{{k \atop m}\right\} in (1) and (2) with \left[{n \atop k+λ}\right]_{r} and \left\{{k \atop m}\right\}_{s} respectively for arbitrary non-negative r and s. Our formulas will be seen to reduce to those given in (3)–(6) above in the case r = s = 0.

2 Combinatorial proofs

In this section, we provide combinatorial explanations of formulas (3)–(6) above.

Proof of (3). We construct a set of configurations comprising the elements of [n] and provide two different enumerations of this set. Given λ > 0 and m ≤ k ≤ n − λ, first arrange the members of [n] according to a permutation having k + λ cycles C_{1}, …, C_{k+λ}, where the smallest element is first in each cycle and cycles are ordered according to the size of their respective first elements. We then arrange the first k cycles C_{1}, …, C_{k} according to a partition having m blocks, where cycles within a block are written in decreasing order of their first elements. Note that one may then erase the pair of parentheses enclosing each cycle so that now cycle starters correspond to left-right minima within m contents-ordered blocks. The remaining λ cycles C_{k+1}, …, C_{k+λ} are set aside. Let A_{k} = A_{k}^{(m,n,λ)} denote the set of configurations of [n] that arise in this manner for m ≤ k ≤ n − λ. Define A = A^{(m,n,λ)} by A = ∪_{k=m}^{n−λ}A_{k}. Then it is seen that Φ_{m}(λ) gives the cardinality of A.

We now enumerate members of A by considering the smallest element j + 1 belonging to cycle C_{k+1}. To do so, we arrange the elements of [j] according to an arbitrary permutation (written using the one-line notation) and insert m − 1 internal dividers in any of \binom{j−1}{m−1} ways. Then elements between consecutive dividers (or preceding the first or following the last divider) constitute the elements within one of m (nonempty) contents-ordered blocks. Since the ordering of the blocks themselves is immaterial, we divide by m!, and hence there are \frac{j!}{m!} \binom{j−1}{m−1} = \left⌊{j \atop m}\right⌋ ways in which to arrange the members of [j]. Further, the number of ways in which to insert the elements of [j + 2, n] so that exactly λ − 1 additional cycles are created is given by

\frac{(n − 1)!}{j!} ∑_{j+1≤i_{1}<···<i_{λ−1}≤n−1} ∏_{j=1}^{λ−1} \frac{1}{i_{j}} = \frac{(n − 1)!}{j!}σ_{λ−1}(j + 1; n − 1)

if λ > 1 (which also holds if λ = 1 since σ_{0}(j + 1; n − 1) = 1). To see this, note that i_{1} + 1, …, i_{λ−1} + 1, where i_{ℓ} is as in the preceding multi-sum, would correspond to the starters of cycles C_{k+2}, …, C_{k+λ}, respectively. Hence, each factor i_{ℓ} for 1 ≤ ℓ ≤ λ − 1 is “missed” in the product (j + 1)(j + 2) ⋯ (n − 1) = \frac{(n−1)!}{j!}. Thus, for each j ∈ [m, n − λ], there are \left⌊{j \atop m}\right⌋ · \frac{(n−1)!}{j!}σ_{λ−1}(j + 1; n − 1) = \frac{(n−1)!}{m!} \binom{j−1}{m−1}σ_{λ−1}(j + 1; n − 1) members of A_{j} and considering all possible j completes the proof.

Proof of (4). Let n, m ≥ 0 be fixed with λ < 0. Given 0 ≤ j ≤ i ≤ −λ, let B_{i,j} denote the set of configurations obtained as follows. Choose exactly i of the elements of I = [n+1, n−λ] and arrange them according to an ordinary partition with j blocks. We then arrange these j blocks B_{1}, …, B_{j}, together with the members of [n], according to a Lah distribution having m blocks. Then insert the −λ − i unchosen elements of I into this Lah distribution so that at the time of insertion each element is placed so that it directly precedes some member of [n] (and not any of the blocks B_{ℓ} for ℓ ∈ [j]). Further, if S = {s_{1} > ⋯ > s_{−λ−i}} denotes the set of elements to be inserted, then s_{1} is to be added first directly prior to some member of [n] within one of the m blocks. The element s_{2} is to be added in the same way, where if s_{2} is placed in the same slot as s_{1} was, then s_{2} is to follow s_{1} (this ensures that s_{2} is also inserted directly prior to some element of [n]). The remaining elements s_{3}, …, s_{−λ−i} are then to be added sequentially in this same manner. Then the absolute value of the generic summand in the formula on the right-hand side of (4) is seen to give |B_{i,j}| for all i and j. Define the sign of a member of B_{i,j} to be (−1)^{λ+j} and let B = ∪_{i=0}^{−λ} ∪_{j=0}^{i} B_{i,j}. Then the right side of (4) gives the sum of the signs of all members of B.

To complete the proof, we define a sign-changing involution on B. To do so, we will need the following further definitions. First, we will refer to the blocks of π ∈ B whose members themselves are either individual elements of [n − λ] or blocks whose elements belong to I as super-blocks. We will refer to an internal block consisting of members of I within a superblock as a sub-block. Note that each member of B_{i,j} contains exactly j sub-blocks in all and each member of B has exactly m super-blocks, the contents of which we now describe in further detail. By a free element within a super-block B, we mean a member of I not belonging to any of the sub-blocks lying within B. Given a ∈ [n], let L_{a} denote the (ordered) set consisting of free elements and/or sub-blocks occurring to the left of a if a is the leftmost member of [n] lying within its super-block or between a and the next member of [n] to its left if not. If b is the rightmost member of [n] in its super-block, then let M_{b} denote the collection of sub-blocks occurring to the right of b. Note that since free elements are to precede directly elements of [n], no free elements can occur to the right of b since it is rightmost and thus M_{b} consists solely of sub-blocks. Finally, let N_{c} for c ∈ I denote the contents of a super-block of π that contains no elements of [n] and whose smallest element lying within one of the sub-blocks is c. Note that N_{c}, like M_{b}, can contain no free elements. Further, within a nonempty L_{a}, the sub-blocks are followed by any free elements (in decreasing order). Given b ∈ [n] or c ∈ I, let M_{b} be empty if b is not the rightmost element of [n] in its super-block and let N_{c} be empty if c does not correspond to the smallest element lying within a sub-block of a super-block containing no elements of [n].

Let p denote the smallest index j ∈ [n − λ] such that at least one of the following holds:

(i) j ∈ [n], with L_{j} nonempty,
(ii) j ∈ [n] and M_{j} is nonempty, with M_{j} ≠ {a_{1}}, …, {a_{k}} for some k ≥ 1,
(iii) j ∈ I and N_{j} is nonempty, with N_{j} ≠ {a_{1}}, …, {a_{k}} for some k ≥ 1,

where a_{1} < ⋯ < a_{k} in (ii) and (iii). If both (i) and (ii) apply to the smallest j as described, then consider only (i).

We now can define the involution on B. Given p as specified above, let K_{1}, …, K_{r} denote the individual sub-blocks (in order, from left to right) contained within L_{p}, M_{p} or N_{p}, whichever is applicable. Let u be the smallest element in K_{1} ∪ ⋯ ∪ K_{r}. If K_{1} ≠ {u}, then either add u to the block directly preceding it if K_{j} = {u} for some j ∈ [2, r] or remove u from the non-singleton to which it currently belongs and add it back as a singleton to follow this block. Note that this operation always reverses the sign. If K_{1} = {u}, then consider K_{2}, …, K_{r} and look to move the smallest element of K_{2} ∪ ⋯ ∪ K_{r} as before, if possible. We continue until some element within K_{1} ∪ ⋯ ∪ K_{r} has been moved, or we have that these blocks consist of singletons arranged in increasing order (which can only occur in scenario (i) above). If p applies to a situation in (i) in which r ≥ 1 and K_{i} = {a_{i}} for i ∈ [r] with a_{1} < ⋯ < a_{r} (followed by any free elements), or in which r = 0 and L_{p} = b_{1} ⋯ b_{s}, where the b_{i} are free elements with b_{1} > ⋯ > b_{s} and s ≥ 1, then we change the status of m = max{a_{1}, …, a_{r}, b_{1}, …, b_{s}}. Note that m occurs either as K_{r} = {m} or as b_{1} = m; thus, we may either erase the brackets enclosing m and designate m a free element if the former, or vice versa, if the latter. This operation again reverses the sign and completes the pairing of all possible π for which L_{i} is nonempty for some i.

Let B^{∗} ⊆ B denote the set of survivors of the involution above. Then B^{∗} comprises those configurations in which L_{i} is empty for all i ∈ [n], with M_{j} and N_{j} consisting of singletons (possibly none) arranged in ascending order for all j. Then each member of B^{∗} has positive sign and |B^{∗}| = ∑_{k=m}^{n−λ} \left[{n \atop k+λ}\right]\left\{{k \atop m}\right\}. To realize this, first note that any left-right minima belonging to [n] within a super-block of ρ ∈ B^{∗} may be viewed as a cycle starter (in some permutation of [n]). If we denote the number of these cycles by k + λ, then it is seen that there are k objects altogether (k + λ cycles and −λ singleton sub-blocks) to be arranged in the m super-blocks of ρ, wherein the members of I (written as singleton blocks) within a super-block must occur in ascending order following any elements of [n] which are arranged in cycles written in decreasing order. Thus, given any permutation of [n] with k +λ cycles, there are \left\{{k \atop m}\right\} ways in which to arrange the cycles as described together with the −λ elements of I so as to form a member of B^{∗}. Considering all possible k implies |B^{∗}| is as stated and completes the proof.

Proof of (5). Given λ > 0 and m ≤ k ≤ n − λ, let C_{k} = C_{k}^{(m,n,λ)} denote the set of configurations that are obtained by first arranging the elements of [n] according to a permutation having k + λ cycles expressed in standard form and then forming a partition with m blocks using the first k of these cycles. Here, cycles are assumed to be ordered by the size of their respective smallest (= first) elements. Define the sign of each member of C_{k} to be (−1)^{n−k}. Let C = C^{(m,n,λ)} be given by C = ∪_{k=m}^{n−λ}C_{k}. Then Ψ_{m,n}(λ) gives the sum of the signs of all members of C.

We define an involution on C as follows. Given π ∈ C, identify the block B of π containing the smallest element of [n] within its cycles out of all the blocks of π that contain at least two elements of [ℓ] within their respective cycles, where ℓ + 1 denotes the first element of the λ-th largest cycle of π (i.e., if π ∈ C_{k} for some k, then ℓ + 1 is the first element of the (k +1)-st cycle). Let a and b where a < b denote the two smallest elements of [ℓ] lying within the cycles of B. If a and b occur in the same cycle as (a ⋯ b ⋯), then we break this cycle at b to get (a ⋯) and (b ⋯), and vice versa, if a and b occur in different cycles of B.

This operation defines a sign-changing involution on all of C except for those members in which B fails to exist, i.e., for members of C_{m} in which the (m + 1)-st cycle has first element m + 1. Note that the elements of [m] in these members of C_{m} all belong to different cycles, with each of these cycles constituting a singleton block within the partition of cycles. Upon erasing the outer brackets enclosing these singleton blocks, it is seen that the set of survivors of the involution above are synonymous with permutations of [n] having λ + m cycles altogether wherein the elements of [m + 1] belong to distinct cycles, and hence it is enumerated by the (m + 1)-Stirling number of the first kind \left[{n−m−1 \atop λ−1}\right]_{m+1}. Furthermore, each survivor has sign (−1)^{n−m}. Upon considering the elements i_{j} + 1, where j ∈ [λ − 1] and i_{j} < i_{j+1} for all j, that start the final λ − 1 cycles, we have

\left[{n − m − 1 \atop λ − 1}\right]_{m+1} = \frac{(n − 1)!}{m!} ∑_{m+1≤i_{1}<···<i_{λ−1}≤n−1} ∏_{j=1}^{λ−1} \frac{1}{i_{j}} ,

which implies Ψ_{m,n}(λ) = (−1)^{n−m} \frac{(n−1)!}{m!}σ_{λ−1}(m + 1; n − 1) as desired.

Proof of (6). Given λ < 0 and max{m, −λ} ≤ k ≤ n − λ, let D_{k} = D_{k}^{(m,n,λ)} denote the set of configurations of [n − λ] obtained by first arranging the elements of [n] according to a permutation having k + λ cycles and then placing these cycles in an m-block partition, together with the elements of I = [n + 1, n − λ] (which do not go in cycles). Define the sign of a member of D_{k} by (−1)^{n−k} and denote the union of all D_{k} by D. Identify the block B of π ∈ D that contains the smallest element of [n] out of all the blocks of π that contain at least two elements of [n] within their cycles. Applying to π the involution from the proof of (5) above using the block B, we may consider only those members of D whose cycles all have length one, with at most one cycle per block of the partition.

Thus, if m < n, we have Ψ_{m,n}(λ) = 0, since there would be no survivors of the involution, which agrees with (6) in this case since \left\{{i \atop m−n}\right\} = 0 for all i ≥ 0 as m − n < 0. If m = n, then each block of a survivor contains a single 1-cycle (i) for some i ∈ [n], with n^{−λ} choices concerning the placement of the elements of I within the blocks of the m-partition. Note that the sign of each survivor is (−1)^{n−k} = (−1)^{λ} since k = n − λ in order for every cycle to have length one. Thus, we get (−n)^{−λ} in this case which agrees with the formula when m = n. If m > n, first note that all cycles must again have length one with these cycles going in n distinct blocks of the partition within a survivor of the involution. Then we select \binom{−λ}{i} members of [n + 1, n − λ] to comprise m − n additional blocks, which can be effected in \left\{{i \atop m−n}\right\} ways. Finally, the remaining members of I go in the blocks already containing the 1-cycles, which can be achieved in n^{−λ−i} = \frac{1}{n^{λ+i}} ways. Considering all possible i, where 0 ≤ i ≤ −λ, implies the formula in the case m > n and completes the proof of (6).

We conclude this section by providing combinatorial proofs of some related recurrences for Φ_{m,n}(λ) and Ψ_{m,n}(λ) which were shown in [3] by other methods. Counting members of the set A from the proof of (3) in another way yields the following recurrence for Φ_{m,n}(λ):

Φ_{m,n}(λ) = ∑_{i=m+λ−1}^{n−1} \frac{(n − 1)!}{i!}Φ_{m,i}(λ − 1), λ > 0.  (7)

Proof. One may assume n ≥ m + λ, for otherwise both sides of (7) are zero. Consider the smallest element i+1 of the last cycle within a member of A^{(m,n,λ)}, where m+λ−1 ≤ i ≤ n−1. Then the elements of [i] are arranged according to some member of A^{(m,i,λ−1)} with i+1 going in a new cycle by itself. Elements of [i + 2, n] are then inserted sequentially so that each x ∈ [i + 2, n] directly follows some element of [x − 1] occurring in either one of the m (contents-ordered) blocks or in one of the λ cycles that are set aside. Note that no x can be placed at the very beginning of one of the m blocks since this would create implicitly a new cycle with first element x contradicting that i + 1 was the smallest element of the last cycle. Thus, there are (i + 1)(i + 2) ⋯ (n − 1) = \frac{(n−1)!}{i!} ways in which to insert the elements of [i + 2, n] and considering all possible i implies (7).

The argument used to show (5) can be extended to prove the following recurrence relations from [3] for Ψ_{m,n}(λ) where λ > 0:

Ψ_{m,n}(λ) = ∑_{i=m+1}^{n−λ+1}(−1)^{i−m} \frac{(i − 1)!}{m!}Ψ_{i,n}(λ − 1)  (8)

= ∑_{i=m+λ−1}^{n−1}(−1)^{n−i} \frac{(n − 1)!}{i!}Ψ_{m,i}(λ − 1).  (9)

Proof. Note that one may assume λ > 1 in (8) and (9), as they are seen to hold when λ = 1 since Ψ_{m,n}(1) = (−1)^{n−m} \frac{(n−1)!}{m!} and Ψ_{i,n}(0) = δ_{i,n}. By the proof of (5), we have Ψ_{m,n}(λ) = (−1)^{n−m}\left[{n−m−1 \atop λ−1}\right]_{m+1}. Upon replacing m by m − 1 and λ by λ + 1 in (8) and (9), one may then show equivalently

\left[{n − m \atop λ}\right]_{m} = ∑_{i=m}^{n−λ} \frac{(i − 1)!}{(m − 1)!}\left[{n − i − 1 \atop λ − 1}\right]_{i+1}  (10)

= ∑_{i=m+λ−1}^{n−1} \frac{(n − 1)!}{i!}\left[{i − m \atop λ − 1}\right]_{m}.  (11)

Before proceeding with the proof of (10), let us introduce a couple of definitions which we will also make use of in the next section. Permutations enumerated by the r-Stirling number \left[{n \atop k}\right]_{r} are called r-permutations and we will refer to a cycle containing a member of [r] within an r-permutation as special, with all other cycles being non-special. The same descriptors will also be used for the elements themselves of the sets [r] and of [r + 1, n + r], respectively. Analogous terminology can be applied to the r-partitions enumerated by \left\{{n \atop k}\right\}_{r}. Assume that the smallest element is first in all cycles. To show (10), we argue that the right side counts the permutations enumerated by \left[{n−m \atop λ}\right]_{m} according to the smallest element i + 1 of the first non-special cycle where m ≤ i ≤ n − λ. Note that there are \frac{(i−1)!}{(m−1)!} choices regarding the placement of the elements of [i] since the elements of [m] belong to different cycles, with i + 1 going in a new cycle by itself. At this point, we may regard each of the i + 1 elements already inserted as special (each starting its own respective cycle) when placing the elements of [i + 2, n]. Note that λ − 1 additional non-special cycles must be created when these elements are placed since already one non-special cycle has been started. Thus, there are \left[{n−i−1 \atop λ−1}\right]_{i+1} possibilities concerning the placement of the elements of [i + 2, n] and considering all i completes the proof of (10). A similar proof applies to (11), where instead one considers the element i + 1 starting the last non-special cycle for some i ∈ [m + λ − 1, n − 1].

3 Generalization

Given r, s ≥ 0, let

Φ_{m,n}^{(r,s)}(λ) = ∑_{k=m}^{n−λ} \left[{n \atop k + λ}\right]_{r}\left\{{k \atop m}\right\}_{s}  (12)

and

Ψ_{m,n}^{(r,s)}(λ) = ∑_{k=m}^{n−λ} \left[{n \atop k + λ}\right]_{r}\left\{{k \atop m}\right\}_{s}(−1)^{n−k}.  (13)

In this section, we find formulas for (12) and (13) which generalize those above corresponding to the case r = s = 0. Let x\overline{m} = x(x + 1) ⋯ (x + m − 1) for a positive integer m, with x\overline{0} = 1. We first consider Φ_{m,n}^{(r,s)}(λ).

Theorem 1. We have

Φ_{m,n}^{(r,s)}(λ) = ∑_{ℓ=m+λ}^{n} ∑_{j=m}^{ℓ−λ} \frac{(ℓ − 1)!r\overline{n−ℓ}}{m!} \binom{n}{ℓ}\binom{j + s − 1}{m + s − 1}σ_{λ−1}(j + 1; ℓ − 1), λ > 0, (14)

and

Φ_{m,n}^{(r,s)}(λ) = ∑_{ℓ=0}^{n} ∑_{i=0}^{−λ} ∑_{j=0}^{i} \frac{(−1)^{λ+j}(ℓ + j)!r\overline{n−ℓ}}{ℓ^{λ+i}m!} \binom{n}{ℓ}\binom{−λ}{i}\left\{{i \atop j}\right\}\binom{ℓ + j + s − 1}{m + s − 1}, λ < 0. (15)

Proof. To show (14), we first generalize the sets A_{k} and A from the proof of (3) above. Define A_{k}^{(r,s)} to be the extension of A_{k} obtained by replacing [n] with [n + r] and allowing some of the elements of J = [r + 1, n + r] to go in special cycles starting with elements of [r] and then allowing some of the first k non-special cycles to go in s special blocks when forming a partition of cycles according the some s-partition enumerated by \left\{{k \atop m}\right\}_{s}. Let A^{(r,s)} = ∪_{k=m}^{n−λ}A_{k}^{(r,s)}, which extends the prior set A. Note that Φ_{m,n}^{(r,s)} gives |A^{(r,s)}|. To count the members of A^{(r,s)} in another way, first suppose n−ℓ elements of J are to go in the special cycles. Then there are \binom{n}{ℓ}r\overline{n−ℓ} ways in which to choose and arrange these elements. Let U = {u_{1} < ⋯ < u_{ℓ}} denote the subset of J consisting of the unchosen members. Proceeding at this point in a manner analogous to the proof of (3) above, suppose u_{j+1} is the smallest element of the (k + 1)-st non-special cycle within a member of A_{k}^{(r,s)} for some k. Then members of V = {u_{1}, …, u_{j}} form the cycles which constitute the non-special elements in a partition enumerated by \left\{{k \atop m}\right\}_{s}. Since a special block within such a partition need not contain a non-special cycle, it follows that there are \frac{j!}{m!} \binom{j+s−1}{m+s−1} ways in which to arrange the elements of V. Then u_{j+1} starts a new cycle and the remaining elements of U − V can be inserted into the current structure in \frac{(ℓ−1)!}{j!}σ_{λ−1}(j + 1; ℓ − 1) ways. Considering all possible ℓ and j then gives (14).

To show (15), we consider sets B_{i,j,ℓ}^{(r,s)} of configurations π that are obtained as follows. First, pick n − ℓ elements of J which are to be placed in r special cycles starting with elements of [r]. Next, form an ordinary j-block partition utilizing exactly i elements chosen from K = [n+r+1, n+r−λ]. Using the elements of U, where U is as in the prior paragraph, together with the j blocks, we form a partition having m + s contents-ordered blocks where the first s blocks are labeled and allowed to be empty and the last m blocks are unlabeled and nonempty. Finally, to obtain a configuration π, the −λ − i unchosen members of K are added to this partition in decreasing order of size in such a way that each one is inserted directly preceding an element of U. Let B^{(r,s)} denote the union of all possible B_{i,j,ℓ}^{(r,s)} and define the sign of π ∈ B_{i,j,ℓ}^{(r,s)} by (−1)^{λ+j}. Then one may verify that the right side of (15) gives the sum of the signs of all members of B^{(r,s)}. Apply now the involution used in the proof of (4) above (considering also the contents of the s labeled blocks above, if needed). Then the set L of survivors is as before, but with elements of U in place of [n] and where s additional labeled super-blocks may contain sub-blocks and/or members of U. Let p denote the number of left-right minima corresponding to elements of U within all the super-blocks of a member of L. Then there are \left\{{k \atop m}\right\}_{s} ways in which to arrange the elements of U and K within such a member of L, where k = p − λ. Further, taking into account the placement of the elements of J − U as well, there are \left[{n \atop p}\right]_{r} ways to arrange the elements of J. Note that each member of L has positive sign as i = j = −λ is required. Considering all possible p, it is seen that the cardinality of L is given by Φ_{m,n}^{(r,s)}, which completes the proof.

Taking r = 0 or s = 0, for example, in (14) gives identities for λ > 0 such as

∑_{k=m}^{n−λ} \left[{n \atop k + λ}\right]\left\{{k \atop m}\right\}_{r} = ∑_{j=m}^{n−λ} \frac{(n − 1)!}{m!}\binom{j + r − 1}{m + r − 1}σ_{λ−1}(j + 1; n − 1)

and

∑_{k=m}^{n−λ} \left[{n \atop k + λ}\right]_{r}\left\{{k \atop m}\right\} = ∑_{ℓ=m+λ}^{n} ∑_{j=m}^{ℓ−λ} \frac{(ℓ − 1)!r\overline{n−ℓ}}{m!} \binom{n}{ℓ}\binom{j − 1}{m − 1}σ_{λ−1}(j + 1; ℓ − 1).

Note that letting r = 0 in either of these formulas recovers (3). Taking λ = −1 in (15) yields

∑_{k=m}^{n+1} \left[{n \atop k − 1}\right]_{r}\left\{{k \atop m}\right\}_{s} = ∑_{ℓ=0}^{n} \frac{ℓ!r\overline{n−ℓ}}{m!} \binom{n}{ℓ} ((ℓ + 1)\binom{ℓ + s}{m + s − 1} − ℓ\binom{ℓ + s − 1}{m + s − 1}) .

There are the following comparable formulas for Ψ_{m,n}^{(r,s)}(λ).

Theorem 2. We have

Ψ_{m,n}^{(r,s)}(λ) = ∑_{i=0}^{u} ∑_{j=0}^{u−i} \frac{(−1)^{n−m−j}(n − i − 1)!r\overline{i}}{m!} \binom{n}{i}\binom{s}{j}σ_{λ−1}(m+j+1; n−i−1), λ > 0, (16)

and

Ψ_{m,n}^{(r,s)}(λ) = ∑_{i=0}^{n} ∑_{j=0}^{n−i} ∑_{ℓ=0}^{−λ} \frac{(−1)^{λ+i}j!r\overline{i}}{(v_{i,j} + s)^{λ+ℓ}} \binom{n}{i}\binom{s}{j}\binom{n − i}{j}\binom{−λ}{ℓ}\left\{{ℓ \atop m − v_{i,j}}\right\}, λ < 0, (17)

where u := n − m − λ and v_{i,j} := n − i − j.

Proof. To show (16), let C_{k}^{(r,s)} be obtained by first forming r-permutations of [n + r] having k + λ non-special cycles and then arranging the first k non-special cycles according to an spartition having m non-special blocks. Let members of C_{k}^{(r,s)} have sign (−1)^{n−k} and C^{(r,s)} = ∪_{k=m}^{n−λ}C_{k}^{(r,s)}. Then Ψ_{m,n}^{(r,s)} gives the sum of the signs of all members of C^{(r,s)}. Applying the involution used in the proof of (5) above (considering also any cycles placed in the s special blocks, if necessary) implies that the set M of survivors consists of those members of C^{(r,s)} in which k = m + j for some 0 ≤ j ≤ s wherein the k + 1 smallest members of J belonging to non-special cycles each start their own cycle, with the first k of these cycles lying in different blocks of the s-partition. If i denotes the number of members of J going in special cycles within a member of M, then we have j ≤ u−i and there are \frac{(n−i−1)!}{(m+j)!}σ_{λ−1}(m+j +1; n−i−1) ways in which to arrange those members of J lying in non-special cycles but not starting one of the first k + 1 non-special cycles. Further, there are \binom{m+j}{j}\binom{s}{j}j! ways to choose and then arrange the cycle starters of the cycles that go in the special blocks within a member of M. Upon considering all possible values of i and j, the right side of (16) is seen to give the sum of the signs of members of M.

To show (17), we form the set D_{k}^{(r,s)} consisting of configurations obtained by first arranging the elements of [n + r] according to an r-permutation having k + λ non-special cycles and then arranging these non-special cycles, together with the elements of K, according to an s-partition of size k + s having m + s blocks. Define the sign of members of D_{k}^{(r,s)} as (−1)^{n−k} and let D^{(r,s)} be the union of all D_{k}^{(r,s)}. Let i again denote the number of elements of J going in one of the r special cycles and j be the number of special blocks that contain at least one non-special cycle in the s-partition. Upon applying the prior involution, to determine the sum of the signs of all members of D^{(r,s)}, we may assume that the non-special cycles all have length one and occur in different blocks of the s-partition. Note that if m < v_{i,j}, then it is seen that there are no survivors of the involution corresponding to such i and j, and indeed the summands for such i and j in the sum on the right side of (17) are all seen to be zero. If m = v_{i,j}, then there are (m + s)^{−λ} ways in which to add the elements of K within a surviving configuration, which is accounted for by the terms in the sum where ℓ = 0. Finally, if m > v_{i,j}, then ℓ members of K for some 1 ≤ ℓ ≤ −λ must occupy the remaining unfilled non-special blocks, which implies the remaining terms in the sum account for survivors where m > v_{i,j}. Combining this case with the prior cases implies the right side of (17) gives the sum of the signs of all survivors, which completes the proof.

Letting, for example, r = 0 or s = 0 in (16) gives for λ > 0 the identities

∑_{k=m}^{n−λ} \left[{n \atop k + λ}\right]\left\{{k \atop m}\right\}_{r}(−1)^{n−k} = ∑_{j=0}^{u} \frac{(−1)^{n−m−j}(n − 1)!}{m!}\binom{r}{j}σ_{λ−1}(m + j + 1; n − 1)

and

∑_{k=m}^{n−λ} \left[{n \atop k + λ}\right]_{r}\left\{{k \atop m}\right\}(−1)^{n−k} = (−1)^{n−m} ∑_{i=0}^{u} \frac{(n − i − 1)!r\overline{i}}{m!} \binom{n}{i}σ_{λ−1}(m + 1; n − i − 1).

References

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

[2] Y. Cai, q-Stirling identities revisited, Electron. J. Combin. 25 (2018), Paper #P1.37.

[3] W. Chu, Disjoint convolution sums of Stirling numbers, Math. Commun. 26 (2021), 239–251.

[4] L. Comtet, Advanced Combinatorics, Dordrecht-Holland, 1974.

[5] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, second edition, Addison-Wesley, 1994.

[6] D. Guo, Summation formulae involving Stirling and Lah numbers, Forum Math. 32 (2020), 1407–1414.

[7] D. E. Knuth, Two notes on notation, Amer. Math. Monthly 99 (1992), 403–422.

[8] R. Merris, The p-Stirling numbers, Turkish J. Math. 24 (2000), 379–399.

[9] G. Nyul and G. Rácz, The r-Lah numbers, Discrete Math. 338 (2015), 1660–1666.

[10] J. Quaintance and H. W. Gould, Combinatorial Identities for Stirling Numbers, World Scientific, 2016.

[11] M. Shattuck, Combinatorial identities for Stirling numbers of the first kind via involution, Integers 12 (2012), Paper #A59.

[12] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2022. Available

    at https://oeis.org.

2020 Mathematics Subject Classification: Primary: 05A19; Secondary: 05A05. Keywords: combinatorial identity, Stirling number, Lah number, combinatorial proof.

(Concerned with sequences \underline{A008275}, \underline{A008277}, and \underline{A008297}.)

Received August 25 2021; revised version received January 9 2022. Published in Journal of Integer Sequences, January 29 2022.

Return to Journal of Integer Sequences home page.