Combinatorial Properties of a Generalized Class of Laguerre Polynomials

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

                 shattuck@math.utk.edu

Abstract

In this paper, we consider various combinatorial aspects of a family of polynomials, denoted by L_{n}^{(α,β)}(x), whose coefficients S_{α,β}(n, k) correspond to a special case of the partial r-Bell polynomials. Among the particular cases of L_{n}^{(α,β)}(x) are the generalized Laguerre polynomials, associated Lah polynomials, and polynomials arising in the study of hyperbolic partial differential equations. Here we provide a combinatorial treatment of L_{n}^{(α,β)}(x) and its coefficients, which were studied previously strictly from an algebraic standpoint. In addition to providing combinatorial proofs of some prior identities, we derive several new relations using the combinatorial interpretations for L_{n}^{(α,β)}(x) and S_{α,β}(n, k). Our proofs make frequent use of sign-changing involutions on various weighted structures. Finally, we introduce a bivariate polynomial generalization arising as a distribution for a pair of statistics and establish some of its basic properties.

1 Introduction

The generalized sequence of polynomials L_{n}^{(α,β)}(x) are defined by Mihoubi and Sahari [17] as coefficients in the exponential generating function formula

∑_{n≥0} L_{n}^{(α,β)}(x)\frac{t^{n}}{n!} = (1 − t)^{α} exp (x ((1 − t)^{β} − 1)) ,  (1)

where α and β are real numbers with β ≠ 0. The special cases of L_{n}^{(α,β)}(x) when (α, β) = (−\frac{1}{2}, −\frac{1}{2}) or (−\frac{3}{2}, −\frac{1}{2}) arise in the theory of hyperbolic partial differential equations, see, [6, pp. 391–398] and [10]. Other important special cases include the generalized Laguerre polynomials (α = −λ − 1, β = −1) and the associated Lah polynomials (α = 0, β = −m), see, e.g., [7] and [1], respectively. It is seen from (1) that L_{n}^{(α,β)}(x) may be expressed as

L_{n}^{(α,β)}(x) = ∑_{k=0}^{n} S_{α,β}(n, k)x^{k},

where

S_{α,β}(n, k) = \frac{1}{k!} ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}(−α − βj)\overline{n},  n, k ≥ 0,  (2)

and x\overline{n} = x(x + 1) ⋯ (x + n − 1) if n ≥ 1, with x\overline{0} = 1, denotes the rising factorial. Note that (2) implies S_{α,β}(n, k) = 0 for k > n ≥ 0, whence the L_{n}^{(α,β)}(x) are indeed polynomials.

Recall that the partial r-Bell polynomials [16] are defined by

∑_{n≥k} B_{n+r,k+r}^{(r)}(a_{ℓ}; b_{ℓ})\frac{t^{n}}{n!} = \frac{1}{k!} (∑_{j≥1} a_{j} \frac{t^{j}}{j!})^{k} (∑_{j≥0} b_{j+1} \frac{t^{j}}{j!})^{r} ,

the r = 0 case of which corresponds to the classical partial Bell polynomials (see, e.g., [2]). It was shown [17] that

S_{rα,β}(n, k) = B_{n+r,k+r}^{(r)} ((−β)\overline{j}, (−α)\overline{j−1}) ,  (3)

where r is a non-negative integer. Note that upon taking α = β = −1 in (3) and replacing r with 2r, one obtains the r-Lah numbers as a special case of S_{α,β}(n, k), which we denote by \left⌊{n \atop k}\right⌋_{r} in accordance with [18]. The r = 0 case of \left⌊{n \atop k}\right⌋_{r}, which is written without a subscript, corresponds to the classical Lah numbers; see, e.g., [11] and \underline{A008297} in [23]. We remark that other polynomial generalizations of the Lah numbers related to S_{α,β}(n, k) have been considered previously [14, 21].

Here, we provide a unified combinatorial treatment of several of the previous algebraic results involving L_{n}^{(α,β)}(x) and S_{α,β}(n, k). To do so, we consider a slight variant, denoted by L_{r}(n, k) = L_{r}^{(α,β)}(n, k), of S_{α,β}(n, k) defined as L_{r}(n, k) = S_{−rα,−β}(n, k). We then let L_{n,r}(x) = L_{n,r}^{(α,β)}(x) be given by

L_{n,r}(x) = ∑_{k=0}^{n} L_{r}(n, k)x^{k},  n ≥ 0.  (4)

We find these forms of S_{α,β}(n, k) and L_{n}^{(α,β)}(x) to be more convenient to deal with combinatorially. The extra parameter r is introduced here since in several of the subsequent identities, we consider integral increments of the parameter α. Also, in the final section, the non-negative integer r is replaced by its polynomial analogue \frac{p^{r}−1}{p−1}, where p is an indeterminate.

The organization of this paper is as follows. In the next section, we find a combinatorial interpretation for L_{r}(n, k) and L_{n,r}(x) in terms of a pair of statistics on a structure closely related to the r-Lah distributions. We make use of this interpretation in the third section in finding some new relations involving L_{r}(n, k) and L_{n,r}(x). In the fourth section, we provide combinatorial proofs of some prior formulas for S_{α,β}(n, k) and L_{n}^{(α,β)}(x), rewritten in terms of L_{r}(n, k) and L_{n,r}(x), which were found previously by algebraic methods. Our proofs entail use of weight-preserving, sign-reversing involutions defined on certain weighted configurations involving various kinds of finite partitions whose blocks are contents-ordered. In the final section, we consider a (p, q)-generalization of L_{r}(n, k) (and hence also of L_{n,r}(x)) by considering two further statistics (marked by p and q) on the underlying structure that is enumerated by L_{r}(n, k) when α = β = 1. Some identities are found of the (p, q)-analogue, which extend earlier ones and the log-concavity is established for a range of p and q values.

2 Combinatorial definition and generating function

In this section, we provide a combinatorial interpretation for the sequences L_{r}(n, k) and L_{n,r}(x) and show how their (exponential) generating function formulas can be obtained using this definition. To do so, we first write a two-term recurrence for L_{r}(n, k). Such a recurrence for L_{r}(n, k) where n, k ≥ 1 (along with initial conditions) may be derived from (2) using L_{r}(n, k) = S_{−rα,−β}(n, k) as follows:

βL_{r}(n − 1, k − 1) + (αr + βk + n − 1)L_{r}(n − 1, k)

= \frac{β}{(k − 1)!} ∑_{j=0}^{k−1}(−1)^{k−1−j}\binom{k − 1}{j}(αr + βj)\overline{n−1}

+ \frac{αr + βk + n − 1}{k!} ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}(αr + βj)\overline{n−1}

= \frac{β}{k!} ∑_{j=0}^{k−1}(−1)^{k−1−j}(k − j)\binom{k}{j}(αr + βj)\overline{n−1} + \frac{(αr + βk)\overline{n}}{k!}

+ \frac{αr + βk + n − 1}{k!} ∑_{j=0}^{k−1}(−1)^{k−j}\binom{k}{j}(αr + βj)\overline{n−1}

= \frac{1}{k!} ∑_{j=0}^{k−1}(−1)^{k−j}\binom{k}{j}(αr + βj)\overline{n−1} (β(j − k) + αr + βk + n − 1) + \frac{(αr + βk)\overline{n}}{k!}

= \frac{1}{k!} ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}(αr + βj)\overline{n} = L_{r}(n, k).

Thus, we have the recurrence

L_{r}(n, k) = βL_{r}(n − 1, k − 1) + (αr + βk + n − 1)L_{r}(n − 1, k),  n, k ≥ 1,  (5)

with initial conditions L_{r}(n, 0) = (αr)\overline{n} and L_{r}(0, k) = δ_{k,0} for all n, k ≥ 0. Note that when α = β = 1 and r is replaced by 2r, it is apparent from (5) that L_{r}(n, k) reduces to the r-Lah number. For a different generalization of the r-Lah numbers, see [4], where the r-Whitney-Lah numbers are introduced, and [9, 20], where they are studied further.

We now find a combinatorial interpretation for L_{r}(n, k) in terms of a bivariate distribution. Given n, k, r ≥ 0, let P_{n,k} = P_{n,k}^{(r)} denote the set of partitions of [n + r] into k + r contents-ordered blocks such that the elements of [r] belong to distinct blocks, with these elements first in their respective blocks. Within λ ∈ P_{n,k}, we refer to blocks containing the elements of [r] as special, with all other blocks being non-special, and at times refer to the elements of [r] themselves as special. Note that by virtue of their association with a distinguished element, special blocks are labeled and in effect allowed to be empty, whereas non-special blocks are unlabeled and always non-empty.

We define a pair of statistics on P_{n,k} as follows. By a left-right minimum (lr min) within a non-special block B = {b_{1}b_{2} ⋯ b_{ℓ}} of λ, we mean an element b_{i} ∈ B such that b_{i} < b_{j} for all j < i. The same definition applies to a left-right minimum in a special block of λ except that one considers only the sequence (possibly empty) of elements obtained by excluding the initial (special) element. Note that the first element of any non-special and the second element of any special block is vacuously an lr min. Let ν_{1}(λ) denote the total number of lr min in all of the special blocks of λ per the definition above and ν_{2}(λ) the number of lr min in its non-special blocks.

Define T_{r}(n, k) = T_{r}^{(α,β)}(n, k) to be the joint distribution on P_{n,k}^{(r)} given by

T_{r}(n, k) = ∑_{λ∈P_{n,k}^{(r)}} α^{ν_{1}(λ)}β^{ν_{2}(λ)},  0 ≤ k ≤ n.  (6)

Note that T_{r}(n, 0) = (αr)\overline{n}, upon considering the placement of the elements of I = [r+1, r+n] within the special blocks, starting with r + 1, and furthermore that T_{r}(n, n) = β^{n}, as each member of I in this case occupies its own (non-special) block and hence is an lr min. We take T_{r}(n, k) to be zero if k > n or k < 0.

We have the following combinatorial interpretation for L_{r}(n, k).

Theorem 1. For all n, k, r ≥ 0, L_{r}(n, k) = T_{r}(n, k); i.e., L_{r}(n, k) is the joint distribution for the statistics ν_{1} and ν_{2} on P_{n,k}^{(r)}.

Proof. The initial conditions of T_{r}(n, k) when n = 0 or k = 0 are seen to agree with those of L_{r}(n, k), so assume n, k ≥ 1. Note that the weight of the members of P_{n,k} in which the element n+r comprises its own block is given by βT_{r}(n−1, k−1). On the other hand, if n+r is placed just after a member of [r] within one of the special blocks or at the beginning of a non-special block, then there are αrT_{r}(n − 1, k) and βkT_{r}(n − 1, k) possibilities, respectively. Finally, members of P_{n,k} in which n + r directly follows some element of [r + 1, r + n − 1] contribute (n − 1)T_{r}(n − 1, k) towards the weight. Combining the previous cases implies T_{r}(n, k) satisfies recurrence (5), and hence T_{r}(n, k) = L_{r}(n, k) for all n, k and r.

Let P_{n} = P_{n}^{(r)} be given by P_{n} = ∪_{k=0}^{n}P_{n,k} for n ≥ 0. Given λ ∈ P_{n}, let μ(λ) denote the number of non-special blocks of λ. Then, from (4), it is seen that L_{n,r}(x) gives the joint distribution of the ν_{1}, ν_{2} and μ statistics on P_{n}, where the μ statistic is marked by the x variable. Note that L_{n,r}(x) reduces when x = α = β = 1 to the n-th row sum of r-Lah numbers, which coincides with \underline{A000262} when r = 0.

The L_{n}^{(α,β)}(x), equivalently the L_{n,r}(x), were defined in [17] as coefficients of a certain exponential generating function (egf), from which various algebraic properties are derived. Alternatively, starting with the combinatorial definition above for L_{n,r}(x), it is possible to derive the corresponding egf formula.

Theorem 2. We have

∑_{n≥0} L_{n,r}(x)\frac{t^{n}}{n!} = (1 − t)^{−αr} exp (x ((1 − t)^{−β} − 1))  (7)

and

∑_{n≥k} L_{r}(n, k)\frac{t^{n}}{n!} = \frac{(1 − t)^{−αr}}{k!} ((1 − t)^{−β} − 1)^{k} .  (8)

Proof. Since (8) follows from (7) and (4), we need only establish (7). To do so, first observe the identity

L_{n+1,r}(x) = (n + αr + βx)L_{n,r}(x) + βx\frac{∂}{∂x}L_{n,r}(x),  n ≥ 0.  (9)

An equivalent form of (9) was shown in [17] algebraically. Using the interpretation given above for L_{n,r}(x), one can give a quick combinatorial proof of (9) as follows. Note that the first term on the right side of (9) counts all ρ ∈ P_{n+1} where the element n + r + 1 either directly follows a member of I, follows a special element or occurs as a singleton block. The second term is seen to count those ρ in which n + r + 1 starts a non-singleton non-special block (and hence itself is an lr min). Observe that since no new block is created in this last case, no factor of x is introduced, which is witnessed with the multiplication of the x-partial derivative by x.

Let f(t, x) = ∑_{n≥0} L_{n,r}(x)\frac{t^{n}}{n!}. Multiplying both sides of (9) by \frac{t^{n}}{n!}, and summing over n ≥ 0, gives

(1 − t)\frac{∂}{∂t}f(t, x) − βx\frac{∂}{∂x}f(t, x) = (αr + βx)f(t, x),  (10)

with initial condition f(0, x) = 1. Solving explicitly the first-order linear partial differential equation (10) then yields

f(t, x) = (1 − t)^{−αr} exp (x ((1 − t)^{−β} − 1)) ,

as desired.

Remark 3. Note that recurrence (5) also follows from equating like powers of x on both sides of (9).

3 New identities for L_{r}(n, k) and L_{n,r}(x)

In this section, we derive some new identities involving L_{r}(n, k) and L_{n,r}(x). Applying recurrence (5) repeatedly yields the following formula for n ≥ k ≥ 1:

L_{r}(n, k) = (αr)\overline{n−k}β^{k} + ∑_{j=0}^{k−1}(αr + β(k − j) + n − j − 1)β^{j}L_{r}(n − j − 1, k − j),  (11)

which may also be shown by considering the largest element n − j + r that either goes in a special block or in a non-singleton non-special block. Multiplying both sides of (11) by x^{k}, and summing over 1 ≤ k ≤ n, gives after simplification the following recurrence:

L_{n,r}(x) = (βx)^{n} + ∑_{j=0}^{n−1}(βx)^{n−j−1} ((αr + j)L_{j,r}(x) + βx\frac{∂}{∂x}L_{j,r}(x)) ,  n ≥ 1.  (12)

From (2), L_{r}(n, k) is given explicitly by

L_{r}(n, k) = \frac{1}{k!} ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}(αr + βj)\overline{n},  n, k ≥ 0.  (13)

Let x\underline{n} = x(x − 1) ⋯ (x − n + 1) for n ≥ 1, with x\underline{0} = 1, denote the falling factorial. We have the following further recurrences for L_{r}(n, k) that can be obtained from (13).

Theorem 4. If n, k ≥ 0 and 0 ≤ s ≤ r, then

L_{r}^{(α,β)}(n, k) = ∑_{j=k}^{n} \binom{n}{j}(α(r − s))\overline{n−j}L_{s}^{(α,β)}(j, k)  (14)

and

L_{r}^{(α,α)}(n, k) = ∑_{j=k}^{n} \binom{j}{k}(r − s)\underline{j−k}L_{s}^{(α,α)}(n, j).  (15)

Proof. By (13), we have

∑_{j=k}^{n} \binom{n}{j}(α(r − s))\overline{n−j}L_{s}^{(α,β)}(j, k)

= ∑_{j=0}^{n} \binom{n}{j}(α(r − s))\overline{n−j} · \frac{1}{k!} ∑_{ℓ=0}^{k}(−1)^{k−ℓ}\binom{k}{ℓ}(αs + βℓ)\overline{j}

= \frac{1}{k!} ∑_{ℓ=0}^{k}(−1)^{k−ℓ}\binom{k}{ℓ} ∑_{j=0}^{n} \binom{n}{j}(α(r − s))\overline{n−j}(αs + βℓ)\overline{j}

= \frac{1}{k!} ∑_{ℓ=0}^{k}(−1)^{k−ℓ}\binom{k}{ℓ}(αr + βℓ)\overline{n} = L_{r}^{(α,β)}(n, k),

where we have used the fact (x + y)\overline{n} = ∑_{j=0}^{n} \binom{n}{j}x\overline{j}y\overline{n−j} in the penultimate equality. For (15), first observe that for a fixed n, k and s where n ≥ k, both sides of (15) may be viewed as polynomials in r of degree n − k. Thus, it suffices to show (15) for all r ≥ n − k + s. Let m = k + r − s. By (13), we then have

∑_{j=k}^{n} \binom{j}{k}(r − s)\underline{j−k}L_{s}^{(α,α)}(n, j) = ∑_{j=k}^{m} \binom{j}{k}(r − s)\underline{j−k} · \frac{1}{j!} ∑_{ℓ=0}^{j}(−1)^{j−ℓ}\binom{j}{ℓ}(α(s + ℓ))\overline{n}

= ∑_{ℓ=0}^{m}(α(s + ℓ))\overline{n} ∑_{j=k}^{m} \frac{(−1)^{j−ℓ}}{j!} \binom{j}{k}\binom{j}{ℓ}(r − s)\underline{j−k}

= \frac{1}{k!} ∑_{ℓ=0}^{m}(α(s + ℓ))\overline{n} ∑_{j=k}^{m}(−1)^{j−ℓ}\binom{r − s}{j − k}\binom{j}{ℓ}

= \frac{1}{k!} ∑_{ℓ=0}^{m}(α(s + ℓ))\overline{n} · (−1)^{r−s+k−ℓ}\binom{k}{ℓ − r + s}

= \frac{1}{k!} ∑_{ℓ=0}^{k}(−1)^{k−ℓ}\binom{k}{ℓ}(α(r + ℓ))\overline{n} = L_{r}^{(α,α)}(n, k),

where we have used [8, Formula 5.24] in the antepenultimate equality

Remark 5. Identities (14) and (15), in the case when α = β = 1 and r and s are even, were shown in [18] by a different method. Furthermore, identity (14) may be given a combinatorial proof by considering the number n−j of elements of I in the final r −s special blocks within a member of P_{n}^{(r)}. Identity (15) may also be obtained combinatorially by first arranging the elements of [n + s] according to a member of P_{n,j}^{(s)} where j ≥ k and then selecting j − k of the non-special blocks whose contents to be transferred to r − s additional special blocks. We leave the details of this argument to the interested reader.

The combinatorial interpretation for L_{r}(n, k) given in Theorem 1 above yields further recurrence formulas for L_{r}(n, k) as follows.

Theorem 6. If n, m, k ≥ 0 and 0 ≤ s ≤ r, then

L_{r}(n + m, k) = ∑_{i=0}^{n} ∑_{j=0}^{m} \binom{n}{i}\binom{m}{j}(α(r − s))\overline{i+j}L_{s}(n + m − i − j, k)  (16)

and

L_{r}(n + m + 1, k) = ∑_{i=0}^{n} ∑_{j=0}^{m}\binom{n}{i}\binom{m}{j}(rα\overline{i+j+1}L_{r−1}(n + m − i − j, k)
+ β\overline{i+j+1}L_{r}(n + m − i − j, k − 1)).  (17)

Proof. To show (16), consider the number i of elements of I and the number j of elements of [r + n + 1, r + n + m] that go in the final r − s special blocks within a member of P_{n+m,k}. There are \binom{n}{i}\binom{m}{j}(α(r − s))\overline{i+j} ways in which to choose and arrange these elements and then L_{s}(n + m − i − j, k) ways to arrange the remaining members of [r + 1, r + n + m], together with the first s special elements. Summing over all possible i and j gives (16).

For (17), we consider the number i of elements of [r + 2, r + n + 1] and the number j of elements of [r + n + 2, r + n + m + 1] that go in the same block as r + 1 within a member of P_{n+m+1,k}. If r + 1 is to go in one of the r special blocks, then there are α\overline{i+j+1} ways in which to order the elements in this block and L_{r−1}(n + m − i − j, k) ways in which to arrange the remaining members of [r + n + m + 1]. If r + 1 goes in a non-special block, then there are β\overline{i+j+1} ways to arrange the elements in this block and L_{r}(n + m − i − j, k − 1) ways in which to arrange the remaining elements. Combining the two previous cases gives the generic term in the sum on the right side of (17), which implies the result.

A similar argument to that given for (16) above implies

L_{n+m,r}(x) = ∑_{i=0}^{n} ∑_{j=0}^{m} \binom{n}{i}\binom{m}{j}(α(r − s))\overline{i+j}L_{n+m−i−j,s}(x), 0 ≤ s ≤ r,

which may also be obtained by multiplying both sides of (16) by x^{k} and summing over all k. A formula comparable to (17) may be given for L_{n+m+1,r}(x) as well. The m = r = 0 case of (17) may be written equivalently as

L_{0}(n + 1, k) = ∑_{i=0}^{n} \binom{n}{i}β\overline{i+1}L_{0}(n − i, k − 1), n, k ≥ 0,

which can also be obtained by considering the number of additional elements in the block containing 1. When β = 1, note that this is a standard recurrence for \left⌊{n \atop k}\right⌋.

Theorem 7. If n, m, j ≥ 0 and 0 ≤ s ≤ r, then

L_{r}(n + 1, m + j + 1) = β ∑_{i=0}^{n−m−j} ∑_{k=m}^{n−i} ∑_{ℓ=j}^{n−i−k}\binom{n + 1}{i}\binom{n − i − k}{ℓ}(αs + β(m + 1) + k + 1)\overline{n−i−k−ℓ} (18)

× (α(r − s))\overline{i}L_{s}(k, m)L_{0}(ℓ, j).

Proof. We enumerate the members of P_{n+1,m+j+1} according to i, k and ℓ defined as follows. Given λ ∈ P_{n+1,m+j+1}, let i denote the number of elements of [r + 1, r + n + 1] going in the final r − s special blocks of λ, and let R denote the subset of elements so selected. Let T = [r+1, r+n+1]−R be given by T = {t_{1}, …, t_{n−i+1}} where t_{1} < ⋯ < t_{n−i+1}, with k such that t_{k+1} is the smallest element of the (m + 1)-st non-special block of λ (where non-special blocks are arranged from left to right in increasing order of smallest elements). Finally, let ℓ denote the number of elements of K = {t_{k+2}, t_{k+3}, …, t_{n−i+1}} that belong to the final j non-special blocks of λ and denote by L the corresponding subset of K. Note that by the definitions, m ≤ k ≤ n − i and j ≤ ℓ ≤ n − i − k, and hence 0 ≤ i ≤ n − m − j, in order for such λ to exist.

To enumerate λ, first note that there are \binom{n+1}{i}(α(r − s))\overline{i} ways in which to choose and position the elements of R. Once this has been done, there are L_{s}(k, m) ways in which to arrange the elements of {t_{1}, …, t_{k}} ∪ [s] such that there are exactly m non-special blocks. We then put t_{k+1} into an additional non-special block by itself (which accounts for the extra factor of β) and insert the n − i − k − ℓ elements of K − L into the first s special and first m + 1 non-special blocks. Note that there are \binom{n−i−k}{ℓ}(αs + β(m + 1) + k + 1)\overline{n−i−k−ℓ} possibilities concerning the selection and placement of the elements of K − L, as there are already k + 1 non-special elements altogether within these blocks. Finally, there are L_{0}(ℓ, j) ways in which to arrange the members of L since none of these elements go in special blocks. Thus, the generic summand on the right side of (18) enumerates all λ ∈ P_{n+1,m+j+1} meeting the restrictions described in the first paragraph. Considering all possible i, k and ℓ then gives (18).

Remark 8. Taking s = r in (18) yields

L_{r}(n+1, m+j +1) = β ∑_{k=m}^{n} ∑_{ℓ=j}^{n−k} \binom{n − k}{ℓ}(αr +β(m+1)+k +1)\overline{n−k−ℓ}L_{r}(k, m)L_{0}(ℓ, j). (19)

Note that when α = β = 1 in (19), one obtains an r-Lah number analogue of formula (7) from [5].

We have the further recurrence relation for L_{n,r}(x) which follows from its combinatorial interpretation.

Theorem 9. If m, n ≥ 0 and 0 ≤ s ≤ r, then

L_{m+n,r}(x) = ∑_{i=0}^{m} ∑_{j=0}^{n} \binom{n}{j}x^{i}(αs + βi + m)\overline{n−j}L_{r}(m, i)L_{j,r−s}(x).  (20)

Proof. Given λ ∈ P_{m+n}, suppose that there are exactly i non-special blocks of λ containing at least one member of R = [r + 1, r + m] where 0 ≤ i ≤ m. Suppose further that within λ there are exactly n − j members of T = [r + m + 1, r + m + n] where 0 ≤ j ≤ n that either (i) occur as an lr min in one of the first s special blocks, (ii) occur as an lr min in one of the non-special blocks containing a member of R, or (iii) directly follow a member of R or some other member of T either within any of the non-special blocks mentioned in (ii) or within any of the special blocks. Note that (i) and (iii) preclude the possibility of an element of T enumerated by n − j from directly following the special element in any one of the final r − s special blocks.

We now enumerate all λ ∈ P_{m+n} subject to the parameters i and j and show that it is given by the generic summand in (20). To do so, first observe that there are x^{i}L_{r}(m, i) ways in which to arrange the elements of [r + m] in their blocks. Let X = {x_{1}, …, x_{n−j}} denote the subset of T whose elements (written in increasing order) each satisfy one of the conditions (i)–(iii) above. Then there are \binom{n}{j} ways in which to select the elements of X and, once this selection has been made, we consider adding x_{1}, x_{2}, …, sequentially, to the blocks already containing the elements of [r + m]. Note that there are αs + βi + m possibilities for the placement of x_{1}, upon considering separately (i)–(iii). In general, for i > 1, it is seen that there are αs + βi + m + i − 1 ways in which to insert x_{i}, since in addition to the possibilities mentioned for x_{1}, the element x_{i} may be placed directly after any member of x_{1}, …, x_{i−1}.

Thus, there are (αs + βi + m)\overline{n−j} ways in which to insert the elements of X into the previous blocks. Further, a member of T − X can go either in a non-special block containing no members of R or in any one of the final r − s special blocks such that no element of R occurs between it and the special element in that block. There are then L_{j,r−s}(x) ways in which to arrange the elements of T − X in their blocks as there is no restriction on the number of additional non-special blocks that are to be occupied. Note that members of T belonging to one of the final r − s special blocks and occurring to the right of the leftmost member of R in the block (if it exists) all belong to X, while those occurring to the left belong to T − X (with all members belonging to T − X if it is the case that the block contains no member of R). Therefore, given λ ∈ P_{m+n}, the elements of T − X, and hence of X, may be retrieved by considering the contents of the final r − s special blocks together with any non-special blocks that fail to contain an element of R. Considering all possible values of i and j thus implies the result.

Remark 10. The case of (20) where α = β = 1 and r, s are both even corresponds to [19, Theorem 3.3], which was shown algebraically by finding two different expansions of (x + 2r)\overline{m+n} and equating like coefficients of x\underline{k}.

Proceeding as in the proof of [22, Theorem 3.1] yields the following further formula, where n, k, r ≥ 0 and x_{i} and y_{i} for i ≥ 0 denote arbitrary sequences:

∑_{j=0}^{n+k} \binom{n + k}{j}x_{j}y_{n+k−j}L_{j,r}(x) = ∑_{p=0}^{k} ∑_{ℓ=0}^{k} ∑_{j=0}^{n} ∑_{i=0}^{j}\binom{n}{j}\binom{k}{ℓ}\binom{j}{i}x_{n+ℓ+i−j}y_{k+j−ℓ−i}
× x^{p}(αr + βp + ℓ)\overline{n−j}L_{r}(ℓ, p)L_{i,0}(x). (21)

We note an important special case of (21). Let U_{n,r}(x) = ∑_{m=0}^{n} \left⌊{n \atop m}\right⌋_{r}x^{m} be the r-Lah polynomial of order n, the r = 0 case of which being denoted simply by U_{n}(x). Taking x_{i} = 1 and y_{i} = δ_{i,0} for all i ≥ 0 in (21), with α = β = 1, gives the formula

U_{n+k,r}(x) = ∑_{p=0}^{k} ∑_{j=0}^{n} \binom{n}{j}x^{p}(k + p + 2r)\overline{n−j}\left⌊{k \atop p}\right⌋_{r}U_{j}(x),  (22)

which is an r-Lah polynomial version of Spivey’s formula [24] for the classical Bell numbers \underline{A000110}.

4 Combinatorial proofs of prior identities

In this section, we provide combinatorial proofs of some prior formulas involving L_{r}(n, k) and L_{n,r}(x) that were shown previously by various algebraic methods.

We first prove a couple of relations involving L_{n,r}(x) and the two kinds of Stirling numbers that occur in a slightly different form as [17, Proposition 5]. Let \left[{n \atop k}\right] denote the (signless) Stirling number of the first kind \underline{A008275} and \left\{{n \atop k}\right\} the Stirling number of the second kind \underline{A008277}. Let B_{n}(x) = ∑_{k=0}^{n} \left\{{n \atop k}\right\}x^{k} be the n-th Bell polynomial (see, e.g., [13] or [15]).

Theorem 11. If n, r ≥ 0, then

L_{n,r}(x) = ∑_{k=0}^{n} ∑_{j=0}^{k} \left[{n \atop k}\right]\binom{k}{j}(αr)^{k−j}β^{j}B_{j}(x)  (23)

and

∑_{k=0}^{n}(−1)^{n−k}\left\{{n \atop k}\right\}L_{k,r}(x) = ∑_{k=0}^{n} \binom{n}{k}(αr)^{n−k}β^{k}B_{k}(x).  (24)

Proof. To show (23), we form members λ ∈ P_{n} as follows. First arrange the elements of I according to a permutation of [n] having exactly k cycles expressed in standard cycle form (i.e., smallest element first within each cycle, with cycles arranged from left to right in increasing order of first elements). Let C_{1}, C_{2}, …, C_{k} denote the cycles so obtained. We then select k − j of the C_{i}, and for each chosen C_{i}, we write the elements contained therein in the same order within one of the special blocks (after the special element). If two or more C_{i} are selected for the same special block, say C_{i_{1}}, C_{i_{2}}, …, where i_{1} > i_{2} > ⋯, then we write all of the element contained in C_{i_{1}} first, followed by those in C_{i_{2}} and so on. Then there are \binom{k}{j}(αr)^{k−j} ways in which to select the k − j cycles and arrange the elements contained therein. Note that the first element of each of the chosen C_{i} corresponds to a special block lr min and hence contributes a factor of α towards the weight. The remaining j cycles are then arranged according to an arbitrary partition of [j] such that the contents of cycles going in the same block are written in descending order of their indices. Thus each cycle starter in this case corresponds to a non-special block lr min, which accounts for the factor of β^{j}. This aside, there are then B_{j}(x) possibilities concerning the relative positions of the cycles within the various (non-special) blocks. Considering all k and j then yields uniquely all possible λ, which implies (23).

To show (24), first let A_{n,k} for 1 ≤ k ≤ n denote the set of ordered pairs (π, ρ), where π is a partition of I with k blocks and ρ is a member of P_{k} using the blocks of π as its non-special elements (together with the members of [r]), where blocks are ordered by the relative sizes of their smallest elements. Define the (signed) weight of (π, ρ) ∈ A_{n,k} as (−1)^{n−k}α^{ν_{1}(ρ)}β^{ν_{2}(ρ)}x^{j}, where j denotes the number of non-special blocks of ρ. Then the left side of (24) is seen to give the sum of the weights of all members of A_{n} = ∪_{k=1}^{n}A_{n,k}, where we may assume n ≥ 1.

Let A′_{n} denote the subset of A_{n} consisting of those (π, ρ) such that π = {r + 1}, {r + 2}, …, {r + n} and within all blocks of ρ, the singletons of π occur in descending order. To define an involution of A_{n} − A′_{n}, consider the largest j ∈ I, which we denote by j^{∗}, such that either (i) the singleton {j} occurs in π, with {j} directly following another block B of π within some block of ρ such that j is greater than the largest element of B, or (ii) j is the largest element of some non-singleton block of π. Replacing option (i) with (ii) by removing the singleton {j^{∗}} from π and adding j^{∗} to the block B, or vice versa if (ii) occurs, is seen to define an involution of A_{n} − A′_{n}. It always preserves the weight (since the number of blocks of ρ does not change and neither does its number of lr min), while it reverses the sign (the number of blocks of π changing by one). Upon considering the number k of singleton blocks of π occurring in the non-special blocks of ρ, the sum of the weights of all members of A′_{n} is seen to be given by the right side of (24), which completes the proof.

The L_{r}(n, k) serve as connection constants between the polynomial bases ((αr + βx)\overline{n})_{n≥0} and (x\underline{n})_{n≥0}, as pointed out in [17, Corollary 4]. Here, we provide a combinatorial explanation as to why, which makes use of a sign-changing involution.

Theorem 12. If n, r ≥ 0, then

(αr + βx)\overline{n} = ∑_{j=0}^{n} L_{r}(n, j)x\underline{j}.  (25)

Proof. Given π ∈ P_{n,j}, let π^{∗} denote a permutation of the non-special blocks of π. Let m(π^{∗}) be the number of left-right minima of π^{∗}, where it is understood that the blocks permuted by π^{∗} (which are construed as the elements in a permutation) are ordered by the relative sizes of their respective smallest elements. Let P̃_{n,j} = {(π, π^{∗}) : π ∈ P_{n,j}}, where it is understood that π^{∗} can range over all possible permutations of the non-special blocks of π for each π. Given π̃ = (π, π^{∗}) ∈ P̃_{n,j}, define the (signed) weight w(π̃) by

w(π̃) = (−1)^{j−m(π^{∗})}α^{ν_{1}(π)}β^{ν_{2}(π)}x^{m(π^{∗})}.

It is seen from the definitions that the right-hand side of (25) gives the sum of the weights of all π̃ ∈ P̃_{n}, where P̃_{n} = ∪_{j=0}^{n}P̃_{n,j}.

To complete the proof, we define a sign-reversing involution on P̃_{n} as follows. In each block permuted by π^{∗} within π̃ = (π, π^{∗}) ∈ P̃_{n,j}, consider the ordering of the elements of I that it contains. Decompose the ordering s_{ℓ} of the elements contained in the ℓ-th block of π^{∗} (from left to right) by

s_{ℓ} = s_{1}^{(ℓ)}α_{1}^{(ℓ)}s_{2}^{(ℓ)}α_{2}^{(ℓ)} ⋯ s_{r_{ℓ}}^{(ℓ)}α_{r_{ℓ}}^{(ℓ)}, 1 ≤ ℓ ≤ j,

where s_{1}^{(ℓ)} > s_{2}^{(ℓ)} > ⋯ > s_{r_{ℓ}}^{(ℓ)} denote the lr min of s_{ℓ} and the α_{i}^{(ℓ)} are possibly empty. We call a sequence s_{ℓ} for some ℓ ∈ [j] disqualifying if (i) r_{ℓ} ≥ 2 (i.e., block ℓ contains at least two lr min), or (ii) r_{ℓ} = 1 where ℓ > 1, with the ℓ-th block of π^{∗} (when viewed from left to right) having larger first element than its predecessor.

Let ℓ′ denote the largest ℓ such that s_{ℓ} is disqualifying. If s_{ℓ′} is disqualifying via (i), then break off the initial segment s_{1}^{(ℓ′)}α_{1}^{(ℓ′)} of s_{ℓ′} and form a separate (contents-ordered) block with it to directly follow the remaining part of the parent block. Otherwise, reverse this operation if (ii) applies. One may verify that this defines a sign-reversing involution on P̃_{n} since j always changes by one, and hence the sign, with the other factors in the definition of w(π̃) unchanged. In particular, note that m(π^{∗}) does not change since blocks are ordered by the size of their smallest elements and thus an lr min is neither introduced nor removed when performing the operations above. The survivors of the involution are those members of P̃_{n} in which the smallest element is first in each non-special block of π, with these blocks arranged in decreasing order of smallest elements from left to right (i.e., π^{∗} corresponds to the permutation j(j − 1) ⋯ 1). Each additional non-special block within such members of P̃_{n} then yields a factor of βx (as it corresponds to an lr min of π^{∗}). Thus, the sum of the weights of the survivors is given by (αr +βx)(αr +βx+1) ⋯ (αr +βx+n−1) = (αr +βx)\overline{n}, since for each i ∈ I, one can either insert i as an lr min in a special block, as a non-special block starter, or as a direct successor of some member of [r + 1, r + i − 1].

The following reciprocity result was shown in [17] using generating functions.

Theorem 13. If n, r ≥ 0, then

L_{n,r}^{(α,β)}(x) = ∑_{k=0}^{n}(−1)^{k}\left⌊{n \atop k}\right⌋L_{k,r}^{(−α,−β)}(x).  (26)

Proof. Let U_{n,k} denote the set of ordered pairs ρ = (ρ_{1}, ρ_{2}), where ρ_{1} is a partition of [n] into k contents-ordered blocks and ρ_{2} ∈ P_{k}, with the weight of ρ taken to be that of ρ_{2}, but with α and β replaced respectively by −α and −β. Let members of U_{n,k} have sign (−1)^{k} and U_{n} = ∪_{k=0}^{n}U_{n,k}. Then the right side of (26) gives the sum of the (signed) weights of all members of U_{n}. To show that the left side of (26) also achieves this, we first regard members ρ of U_{n} as follows. Let ρ′ be obtained from ρ by arranging the blocks of ρ_{1}, ordered by relative size of their smallest elements, according to the partition ρ_{2} (where r extra special elements are added that are distinct from the blocks of ρ_{1}). We let ρ′ have sign and weight equal to that of ρ. Thus, the right side of (26) gives the sum of the weights of all configurations ρ′, the set of which we again denote by U_{n}.

We define an involution on U_{n} as follows. Let us refer to the blocks of ρ′ whose elements are themselves blocks of ρ_{1} as superblocks. In a left-to-right scan of the superblocks of ρ′ ∈ U_{n}, where the special superblocks are written before the non-special, consider the first, denoted by B, which contains within its blocks at least two elements of [n] altogether. Let B denote the rightmost block within B. If B is not a singleton, then break off the final element of B and form a singleton block with it to follow B. If B is a singleton, then we add its element to the block that directly precedes it at the end. Note that this operation always reverses the sign and preserves the weight except in the cases (I) B = {αbβa} or (II) B′ = {αbβ} and B = {a}, where B′ denotes the penultimate block of B, a < b are the two smallest elements of [n] contained within the blocks of B, and α and β are (possibly empty) sequences of elements of [n]. Note in this case that the weight is not preserved since moving a as indicated adds or takes away a factor of either α or β (depending on whether B is special or not) since both B and B′ are lr min (as they correspond to the two ‘smallest’ blocks within B).

If the elements a and b occur according to (I) or (II) above, then let c < d denote the two smallest elements of [n] contained within blocks of B excluding those containing a or b. (If there are less than two such elements of [n] left at this point, then we stop.) We repeat, if possible, the involution above using the elements c and d just as we did a and b, where the block or blocks containing a and b are left undisturbed. If c and d cannot be moved without preserving the weight, then consider the two smallest elements in the remaining blocks and so on. We repeat this process until the operation of breaking or fusing blocks as described can be performed or until all of the blocks of B have been considered (except for possibly an initial singleton block). We then consider the next superblock C from left to right within ρ′ containing at least two elements of [n] within its blocks and repeat. We continue until it is possible to perform the involution on adjacent blocks as described within some superblock or all of the superblocks have been exhausted.

The set of survivors of this involution, which is denoted by U_{n}^{∗}, are those configurations in U_{n} in which each superblock B is comprised of a sequence of blocks where those containing a and b are of the form (I) or (II) above and occur at the end of B, with the remaining blocks of B arranged in the same manner inductively from right to left upon considering the two smallest remaining elements. Note that each block within any superblock of a member of U_{n}^{∗} is seen to be an lr min. Thus since each block receives a weight −α or −β, and the sign is −1 to the number of blocks, one may thus assign a weight of α or β to each block (depending on whether or not the superblock to which it belongs is special). Therefore, to complete the proof, it suffices to define a weight-preserving bijection between U_{n}^{∗} and P_{n}, where the associated weights for either set are α and β.

Let λ ∈ U_{n}^{∗} and we replace the blocks within each superblock B of λ with a sequence of elements in [n]. If B is empty (in which case it is special), then it is left empty. If B contains one block that is a singleton, then simply remove the brackets enclosing the element contained therein. So assume B contains at least two elements of [n] altogether in its blocks. If the last block within B is of the form (I) above, then form the word aαbβ, whereas if it is of form (II), then put bαaβ. Then consider the relative positions of the elements c and d defined above. If c and d occur together in a block as {γdδc}, then write cγdδ directly prior to the current word, whereas if they occur as {γdδ}, {c}, then put dγcδ instead. We continue in this manner working from right to left within the blocks of B, forming a sequence in [n] with distinct letters. If B has an initial singleton block that is left after all other blocks have been used as described, then we simply write its entry at the beginning of the current word.

Thus, the sequence of blocks within B has been replaced by a word w such that its length equals the sum of the cardinalities of the blocks. Note that the number of lr min in w is seen to be the same as the number of blocks within β. This follows from the inductive manner in which w was formed. Note for example that if (I) holds, then only a out of {a, b} corresponds to an lr min in w, whereas if (II) holds, then both a and b do so. Since each block within B is an lr min, it follows that the weight associated with B is the same as the weight of the word w. Forming a word for each of the superblocks of λ as described then results in a member λ̃ ∈ P_{n} having the same weight. Furthermore, one may verify that the mapping λ ↦ λ̃ is a bijection. It follows that the sum of the weights of all members of U_{n}^{∗} is L_{n,r}^{(α,β)}(x), which completes the proof.

Equivalent versions of the following identities involving transformations of the α and β parameters occur in [17] and were shown using generating function techniques. Their elegant form suggests trying to find some sort of a combinatorial explanation as to why.

Theorem 14. If n ≥ 0, r ≥ 1 and β′ ≠ 0, then

(αr + βx)\overline{n} = ∑_{j=0}^{n}(−1)^{j}L_{r}^{(α+ \frac{α′β}{rβ′} , \frac{β}{β′} )}(n, j)(α′ − β′x)\overline{j}  (27)

and

L_{r}^{(α,β)}(n, k) = ∑_{j=k}^{n}(−1)^{j}L_{r}^{(α+ \frac{α′β}{rβ′} , \frac{β}{β′} )}(n, j)L_{1}^{(α′,−β′)}(j, k),  0 ≤ k ≤ n.  (28)

Proof. We first describe a set of configurations, the members of which have sum of weights given by the right-hand side of (27). Given 0 ≤ j ≤ n, let K_{j} denote the set of ordered pairs (π, ρ) such that π ∈ P_{n,j}^{(r+1)} and ρ is a permutation of the non-special blocks of π wherein blocks corresponding to lr min may be marked (where it is understood that blocks of π are ordered by the relative sizes of their smallest elements). Let K = ∪_{j=0}^{n}K_{j} and members of K_{j} have sign (−1)^{j}. We define a weighting of the members of K as follows. Let γ_{1}(π) denote the number of lr min in the first r special blocks of π, where lr min for both special and non-special blocks are defined as before. Let γ_{2}(π) denote the number of lr min in just the (r + 1)-st special block of π and γ_{3}(π) the number of lr min in its non-special blocks. Let δ_{1}(ρ) and δ_{2}(ρ) denote the number of marked and unmarked lr min in ρ, respectively. Note that an lr min of ρ corresponds to a block B of π whose smallest element is less than the smallest element of any block occurring to the left of B within ρ. Define the weight of the ordered pair (π, ρ) ∈ K by

α^{γ_{1}(π)} (\frac{α′β}{β′} )^{γ_{2}(π)} (\frac{β}{β′} )^{γ_{3}(π)} (α′)^{δ_{1}(ρ)}(−β′x)^{δ_{2}(ρ)}.

Then, upon considering the product of terms in (α′ − β′x)\overline{j} and recalling the definition of L_{r}(n, j), it is seen that the right side of (27) gives the sum of the (signed) weights of all members of K.

To define an involution on K, the following definition will be useful. Suppose that the sequence of elements within a non-special block C of π is expressed as s = a_{1}τ_{1}a_{2}τ_{2} ⋯ a_{p}τ_{p}, where a_{1}, …, a_{p} denotes the complete set of lr min of s and τ_{1}, …, τ_{p} are possibly empty. Then we refer to a subsequence of elements of the from a_{i}τ_{i} for some 1 ≤ i ≤ p as a section of C. Similar terminology is applied to the special blocks of π, where it is understood in this case that s does not include the special element and hence can be empty. Let λ = (π, ρ) ∈ K and we pair λ with some λ′ ∈ K of opposite weight. To define the mapping λ ↦ λ′, first suppose that ρ has exactly t lr min which we denote by Q_{1}, …, Q_{t}. Let Q_{i} be the (possibly empty) sequence of blocks of π occurring between Q_{i} and Q_{i+1} if 1 ≤ i ≤ t − 1 and to the right of Q_{t} if i = t.

We first consider the case when Q_{t} is non-empty with the blocks comprising Q_{t} containing at least two sections altogether. Let D denote the last block of Q_{t}. If D contains two or more sections, then we remove the first section and form a separate block of π that is to directly follow D. We reverse this operation if D contains a single section whose first element is greater than the first element of the block directly preceding it. Thus, we may assume that D contains a single section whose first element is less than the first element of its predecessor. In this case, we consider the penultimate block of Q_{t} and apply one of the above operations if possible. If not, continue considering blocks of Q_{t} from right to left until it is the case that a block having two or more sections is encountered or one having a single section whose first element is greater than the first element of its predecessor in Q_{t}. Note that if no such block is ever encountered, then it must be the case that the blocks in Q_{t} each have one section and occur in decreasing order of their smallest elements.

We now extend our involution to the last aforementioned case concerning Q_{t}. Here, we also allow for Q_{t} to consist of a single block containing one section or for Q_{t} to be empty, with Q_{t} containing more than one section if the latter applies. Let E denote the first block of Q_{t}. If the first element of E is greater than the first element of Q_{t}, then we write the elements comprising the section E directly prior to the current sequence of elements in Q_{t}. If the first element of Q_{t} is greater than that of E (or if Q_{t} is empty), then we break off the first section of Q_{t} and form a new block to directly follow. Observe that since the blocks of Q_{t} occur in decreasing order of first elements, these operations are inverses. Note further that in the latter case, the block Q_{t} must contain more than one section since min(Q_{t}) < min(E) if Q_{t} is non-empty. Let λ′ denote the member of K obtained by applying any of the preceding operations. In all cases, the magnitude of the weight of λ and λ′ is the same since moving a section as described does not change the weighting of π with respect to its non-special blocks and neither does it affect the weighting of ρ since no lr min are introduced or removed. On the other hand, since the number j of non-special blocks of π changes by one in all cases, the sign of the weight is always reversed. Finally, one may verify that the mapping λ ↦ λ′ is indeed an involution where defined.

So we may assume henceforth that Q_{t} contains a single section and is the final block of ρ (i.e., Q_{t} is empty). Now let i_{0} denote the largest index i < t, if it exists, such that either Q_{i} is non-empty or Q_{i} is empty, but Q_{i} contains two or more sections. We then apply in this case the previous involution λ ↦ λ′ to the blocks belonging to Q_{i_{0}} ∪ {Q_{i_{0}}}, leaving the remainder of ρ undisturbed. The set of survivors in K of this extended involution are those members (π, ρ) where i_{0} fails to exist, i.e., those in which the non-special blocks of π all contain a single section and are arranged within ρ in decreasing order from left to right. In particular, every block of ρ corresponds to an lr min.

In this case, we let U denote the set consisting of the sections contained either within the (r+1)-st special block of π or within the non-special blocks of π corresponding to any marked lr min of ρ. Assume for now U ≠ ∅. We compare the various sections in U by comparing the sizes of their first elements. If the smallest section F in U belongs to a non-special block, then delete the block containing F from ρ and move F to the (r + 1)-st special block, writing its sequence of elements so that they directly follow any elements already present. If F belongs to the (r + 1)-st special block of π, necessarily as the final section, then we form a new (non-special) block containing only the elements in F, which we mark and insert into ρ so that ρ is still decreasing after the insertion. Note that this uniquely determines the position of F within ρ and implies that these operations are inverses of one another. Furthermore, the magnitude of the weight is preserved since a section within the (r + 1)-st special block of π or within a non-special block of π corresponding to a marked lr min of ρ both contribute a factor of \frac{α′β}{β′} towards the overall weight. On the other hand, the sign is again reversed since a non-special block is either created or removed.

Thus, the set K′ of survivors of all the preceding involutions are those (π, ρ) in which (i) the (r + 1)-st special block of π contains only r + 1, (ii) each non-special block of π contains one section, and (iii) ρ is the decreasing permutation, with no blocks in ρ marked. Within members of K′, each new lr min in one of the first r special blocks of π contributes α and each non-special block of π within ρ contributes −\frac{β}{β′} (−β′x) = βx towards the signed weight. Thus, there are αr + βx possibilities for each section starter. All other members of [r + 2, r + n + 1] fail to be lr min and thus contribute one towards the weight. Upon successively considering each element of [r + 2, r + n + 1] starting with r + 2, it is seen that the sum of the weights of all the members of K′ is given by (αr + βx)\overline{n}, which completes the proof of (27).

To show (28), we extend the proof of (27) and let L_{j} for k ≤ j ≤ n denote the set of ordered pairs (π, τ) such that π is as before and τ is a partition of the non-special blocks of π arranged according to a member of P_{j,k}^{(1)}. Let L = ∪_{j=k}^{n}L_{j} and members of L_{j} have sign (−1)^{j}. Define the weight of (π, τ) ∈ L by

α^{γ_{1}(π)} (\frac{α′β}{β′} )^{γ_{2}(π)} (\frac{β}{β′} )^{γ_{3}(π)} (α′)^{ν_{1}(τ)}(−β′)^{ν_{2}(τ)}.

Here, the statistics γ_{i} are as in the proof of (27) and the ν_{i} are as in the second section above, with the latter now applied to the partition τ whose “elements” are blocks of π. (We refer to the blocks of τ as superblocks.) From the various definitions, it is seen that the sum of the (signed) weights of all members of L is given by the right side of (28).

We now define a sign-reversing, weight-preserving involution on L. We first apply the involution defined above in the third and fourth paragraphs of this proof to the sequence of blocks of π contained in the special and each of the non-special superblocks of τ. Thus, we may assume that all non-special blocks of π contain one section and are arranged in decreasing order within each superblock of τ. Now let V denote the set consisting of sections that belong either to the (r + 1)-st special block of π or to non-special blocks of π going in the special superblock of τ (necessarily in decreasing order). Assume V ≠ ∅ and let H be the smallest section in V. We now apply the same type of involution as we did in conjunction with the set U above, moving the section H from a special to a non-special block, or vice versa. Combining this mapping with the previous, one may verify that this yields the desired involution on L.

The set L′ of survivors of this involution consists of those (π, τ) such that (i) the (r+1)-st special block of π contains only r + 1, (ii) the special superblock of τ contains no blocks of π, and (iii) non-special blocks of π each have a single section and occur in decreasing order within the non-special superblocks of τ. Note that within members of L′, each non-special block of π contributes −\frac{β}{β′} (−β′) = β towards the weight and may be viewed itself as some section of a larger contents-ordered block, upon removing the enclosing parentheses. Thus, combining the k non-special superblocks of τ with the first r special blocks of π, it is seen that the sum of the weights of all members of L′ is given by L_{r}^{(α,β)}(n, k), which completes the proof of (28).

Remark 15. Equivalent forms of (27) and (28) involving S_{α,β}(n, k) occur as [17, Corollary 18] and are given by

(−α − βx)\overline{n} = ∑_{j=0}^{n}(−1)^{j}S_{α− \frac{α′β}{β′} , \frac{β}{β′}} (n, j)(−α′ − β′x)\overline{j}

and

S_{α,β}(n, k) = ∑_{j=k}^{n}(−1)^{j}S_{α− \frac{α′β}{β′} , \frac{β}{β′}} (n, j)S_{α′,β′}(j, k).

Note that the first identity above can be obtained from (27) by replacing α, β and α′ with −α/r, −β and −α′, respectively, and using L_{r}^{(α,β)}(n, k) = S_{−rα,−β}(n, k). The second identity may be obtained similarly from (28).

5 A further polynomial extension

In this concluding section, we derive a (p, q)-analogue of L_{r}(n, k) and L_{n,r}(x) by considering two further statistics on P_{n,k}. Suppose that the special blocks of π ∈ P_{n,k} are labeled 0, 1, …, r − 1 from left to right. For each special block lr min x of π, let p_{x} denote the position number of the block containing x. Define σ_{1}(π) = ∑_{x} p_{x}, where the sum is taken over all possible x in π. Furthermore, suppose that the non-special blocks of π are arranged from left to right in increasing order of minimal elements and then labeled 0, 1, …, k − 1. Similarly, let σ_{2}(π) be the sum of the block position numbers corresponding to the non-special lr min of π. Let L_{r}(n, k) = L_{r}^{(α,β)}(n, k; p, q) for 0 ≤ k ≤ n be given as the distribution

L_{r}(n, k) = ∑_{π∈P_{n,k}^{(r)}} α^{ν_{1}(π)}β^{ν_{2}(π)}p^{σ_{1}(π)}q^{σ_{2}(π)}.

Define L_{n,r}(x) = L_{n,r}^{(α,β)}(x; p, q) by L_{n,r}(x) = ∑_{k=0}^{n} L_{r}(n, k)x^{k}. Note that L_{r}(n, k) and L_{n,r}(x) reduce to L_{r}(n, k) and L_{n,r}(x) when p = q = 1. Letting α = p and β = q, one gets the joint distribution on P_{n,k} for variants of the σ_{1} and σ_{2} statistics obtained by using instead the labelings 1, …, r and 1, …, k for the special and non-special blocks, respectively. We remark that σ_{1} and σ_{2} are related to a family of statistics on set partitions considered originally in [3] and later studied (see, e.g., [25]).

Let m_{q} = 1 + q + ⋯ + q^{m−1} for m ≥ 1, with 0_{q} = 0. By an argument similar to the proof of Theorem 1 above, we have the recurrence

L_{r}(n, k) = βq^{k−1}L_{r}(n − 1, k − 1) + (αr_{p} + βk_{q} + n − 1)L_{r}(n − 1, k),  n, k ≥ 1, (29)

with initial conditions L_{r}(n, 0) = (αr_{p})\overline{n} and L_{r}(0, k) = δ_{k,0} for all n, k ≥ 0.

To find an explicit formula for L_{r}(n, k), we make use of a previous result. Let u(n, k) be an array defined recursively by

u(n, k) = u(n − 1, k − 1) + (a_{n−1} + b_{k})u(n − 1, k),  n, k ≥ 1,  (30)

and satisfying the initial conditions u(n, 0) = ∏_{i=0}^{n−1}(a_{i} + b_{0}) and u(0, k) = δ_{k,0} for n, k ≥ 0, where the a_{i} and b_{i} denote arbitrary sequences and it is assumed that the b_{i} are distinct. Then there is the formula [12, Theorem 1.1]:

u(n, k) = ∑_{j=0}^{k} (\frac{∏_{i=0}^{n−1}(b_{j} + a_{i})}{∏k ; \begin{matrix}i=0 \\ i≠j \end{matrix}(b_{j} − b_{i})}) ,  n, k ≥ 0.  (31)

Dividing both sides of (29) by β^{k}q^{\binom{k}{2}}, and letting

L_{r}^{∗}(n, k) = \frac{L_{r}(n, k)}{β^{k}q^{\binom{k}{2}}},

we have that L_{r}^{∗}(n, k) satisfies recurrence (30) with a_{n} = αr_{p} + n and b_{k} = βk_{q}, where L_{r}^{∗}(n, 0) = (αr_{p})\overline{n} = ∏_{i=0}^{n−1}(a_{i} + b_{0}) and L_{r}^{∗}(0, k) = δ_{k,0} for n, k ≥ 0. Applying (31) gives

L_{r}^{∗}(n, k) = ∑_{j=0}^{k} (\frac{∏_{i=0}^{n−1}(βj_{q} + αr_{p} + i)}{∏k ; \begin{matrix}i=0 \\ i≠j \end{matrix}(βj_{q} − βi_{q})}) = ∑_{j=0}^{k} \frac{∏_{i=0}^{n−1}(αr_{p} + βj_{q} + i)}{(−1)^{k−j}β^{k}q^{\binom{j}{2}+j(k−j)}j_{q}^{!}(k − j)_{q}^{!}} ,

where j_{q}^{!} = 1_{q}2_{q} ⋯ j_{q} denotes the q-factorial. Let \binom{k}{j}_{q} = \frac{k_{q}^{!}}{j_{q}^{!}(k−j)_{q}^{!}} for 0 ≤ j ≤ k denote the q-binomial coefficient. By the preceding, we have the following explicit formula for L_{r}(n, k).

Theorem 16. If n, k, r ≥ 0, then

L_{r}(n, k) = \frac{1}{k_{q}^{!}} ∑_{j=0}^{k}(−1)^{k−j}q^{\binom{k−j}{2}}\binom{k}{j}_{q}(αr_{p} + βj_{q})\overline{n}.  (32)

Note that (32) reduces to (13) when p = q = 1. We now establish the log-concavity of each row within the array L_{r}(n, k). Recall that a sequence d_{n} of non-negative real numbers is said to be log-concave if d_{n}^{2} ≥ d_{n−1}d_{n+1} for all n.

Theorem 17. Let n ≥ 2 be fixed. If α, β, p, r ≥ 0 and 0 ≤ q ≤ 1, then the sequence L_{r}(n, k) for 0 ≤ k ≤ n is log-concave.

Proof. Let M_{r}(n, k) = q^{−\binom{k}{2}}L_{r}(n, k), where we may assume q ≠ 0. Then L_{r}(n, k)^{2} ≥ L_{r}(n, k − 1)L_{r}(n, k + 1) if and only if q^{−1}M_{r}(n, k)^{2} ≥ M_{r}(n, k − 1)M_{r}(n, k + 1). Since 0 < q ≤ 1, it suffices to establish the log-concavity of M_{r}(n, k). To do so, we proceed by induction on n, the n = 2 case following from a direct calculation. Let n ≥ 3 and 1 ≤ k ≤ n − 1. If β = 0, then the result is trivial, so assume further β ≠ 0, in which case M_{r}(n, k) > 0 for 1 ≤ k ≤ n. Then M_{r}(n, k)^{2} ≥ M_{r}(n, k − 1)M_{r}(n, k + 1) if and only if

(βM_{r}(n − 1, k − 1) + (αr_{p} + βk_{q} + n − 1)M_{r}(n − 1, k))^{2}

≥ (βM_{r}(n − 1, k − 2) + (αr_{p} + β(k − 1)_{q} + n − 1)M_{r}(n − 1, k − 1)) · (βM_{r}(n − 1, k)

+ (αr_{p} + β(k + 1)_{q} + n − 1)M_{r}(n − 1, k + 1)).  (33)

Upon expanding both sides and comparing the various terms, it suffices to show

(αr_{p} + βk_{q} + n − 1)^{2} ≥ (αr_{p} + β(k − 1)_{q} + n − 1) (αr_{p} + β(k + 1)_{q} + n − 1)  (34)

and

(αr_{p} + β(2k_{q} − (k − 1)_{q}) + n − 1) M_{r}(n − 1, k − 1)M_{r}(n − 1, k)
≥ (αr_{p} + β(k + 1)_{q} + n − 1) M_{r}(n − 1, k − 2)M_{r}(n − 1, k + 1),  (35)

from which (33) would follow by induction. Note that (34) may be simplified to

2(αr_{p} + n − 1)k_{q} + βk_{q}^{2} ≥ (αr_{p} + n − 1)((k − 1)_{q} + (k + 1)_{q}) + β(k − 1)_{q}(k + 1)_{q}.

The last inequality follows from observing that 2k_{q} ≥ (k − 1)_{q} + (k + 1)_{q} for 0 ≤ q ≤ 1 and k_{q}^{2} ≥ (k − 1)_{q}(k + 1)_{q} for all q ≥ 0. Inequality (35) follows from observing that M_{r}(n−1, k −1)M_{r}(n−1, k) ≥ M_{r}(n−1, k −2)M_{r}(n−1, k +1) since the ratio \frac{M_{r}(n−1,ℓ)}{M_{r}(n−1,ℓ+1)} is increasing by the induction hypothesis and since 2k_{q} − (k − 1)_{q} ≥ (k + 1)_{q}, which completes the proof.

Remark 18. The p = q = r = 1 case of Theorem 17 is equivalent to [17, Corollary 13], which was shown by a different method making use of Newton’s inequality.

Extending prior proofs yields generalizations of several of the identities given above for L_{r}(n, k). For example, extending the combinatorial proof of (16) to account for the σ_{1} and σ_{2} statistics gives

L_{r}(n + m, k) = ∑_{i=0}^{n} ∑_{j=0}^{m} \binom{n}{i}\binom{m}{j} (αp^{s}(r − s)_{p})\overline{i+j} L_{s}(n + m − i − j, k),  0 ≤ s ≤ r, (36)

the m = 0 case of which is

L_{r}(n + m, k) = ∑_{j=k}^{n} \binom{n}{j}(αp^{s}(r − s)_{p})\overline{n−j}L_{s}(j, k).  (37)

Note that (37) may also be shown by an algebraic argument comparable to the one given above for (14), using (32) in place of (13).

The proof given above for (19) may be generalized to give

L_{r}^{(α,β)}(n + 1, m + j + 1; p, q) = βq^{m} ∑_{k=m}^{n} ∑_{ℓ=j}^{n−k}\binom{n − k}{ℓ} (αr_{p} + β(m + 1)_{q} + k + 1)\overline{n−k−ℓ}
× L_{r}^{(α,β)}(k, m; p, q)L_{0}^{(α,βq^{m+1})}(ℓ, j; p, q). (38)

Note that the q^{m} factor at the beginning accounts for the lr min created when m + 1 is initially placed in the (k + 1)-st non-special block. Also, the β parameter must be replaced by βq^{m+1} in the final factor within the summand since each lr min within the final j nonspecial blocks contributes an extra m + 1 (more than it ordinarily would) towards the σ_{2} statistic value.

Finally, extending prior arguments yields the following recurrence for L_{n,r}(x):

L_{m+n,r}^{(α,β)}(x; p, q) = ∑_{i=0}^{m} ∑_{j=0}^{n} \binom{n}{j}x^{i} (αp^{r−s}s_{p} + βi_{q} + m)\overline{n−j} L_{r}^{(α,β)}(m, i; p, q)L_{j,r−s}^{(α,βq^{i})}(x; p, q),

(39)

which provides a (p, q)-analogue of (20).

References

[1] J. C. Ahuja and E. A. Enneking, Concavity property and a recurrence relation for associated Lah numbers, Fibonacci Quart. 17 (1979), 158–161.

[2] E. T. Bell, Exponential polynomials, Ann. of Math. 35 (1934), 258–277.

[3] L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University, 1968, pp. 8–15.

[4] G.-S. Cheon and J.-H. Jung, r-Whitney numbers of Dowling lattices, Discrete Math. 312 (2012), 2337–2348.

[5] R. B. Corcino, R. O. Celeste, and K. J. M. Gonzales, Rook theoretic proofs of some identities related to Spivey’s Bell number formula, Ars Combin. 132 (2017), 11–26.

[6] R. Courant and D. Hilbert, Methoden der Mathematischen Physik 2, Springer, 1937.

[7] G. B. Djordjević, On the generalized Laguerre polynomials, Fibonacci Quart. 39 (2001), 403–408.

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

[9] E. Gyimesi and G. Nyul, New combinatorial interpretations of r-Whitney and r-Whitney-Lah numbers, Discrete Appl. Math. 255 (2019), 222–233.

[10] T. Kim, D. V. Dolgy, D. S. Kim, H. I. Kwon, and J. J. Seo, Differential equations arising from certain Sheffer sequence, J. Comput. Anal. Appl. 23 (2017), 1359–1367.

[11] I. Lah, Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik, Mitteilungsbl. Math. Statist. 7 (1955), 203–212.

[12] T. Mansour, S. Mulay, and M. Shattuck, A general two-term recurrence and its solution, European J. Combin. 33 (2012), 20–26.

[13] T. Mansour and M. Schork, Commutation Relations, Normal Ordering, and Stirling Numbers, Chapman & Hall/CRC, 2015.

[14] T. Mansour, M. Schork, and M. Shattuck, On a new family of generalized Stirling and Bell numbers, Electron. J. Combin. 18 (1) (2011), Paper #P77.

[15] I. Mező and R. B. Corcino, The estimation of the zeros of the Bell and r-Bell polynomials, Appl. Math. Comput. 250 (2015), 727–732.

[16] M. Mihoubi and M. Rahmani, The partial r-Bell polynomials, Afr. Mat. 28 (2017), 1167–1183.

[17] M. Mihoubi and M. Sahari, One some polynomials applied to the theory of hyperbolic differential equations, Online J. Anal. Comb. 15 (2020), Art. #2.

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

[19] G. Nyul and G. Rácz, Sums of r-Lah numbers and r-Lah polynomials, Ars Math. Contemp. 18 (2020), 211–222.

[20] J. L. Ramírez and M. Shattuck, A (p, q)-analogue of the r-Whitney-Lah numbers, J. Integer Sequences 19 (2016), Article 16.5.6.

[21] M. Shattuck, Generalized r-Lah numbers, Proc. Indian Acad. Sci. (Math Sci.) 126 (2016), 461–478.

[22] M. Shattuck, Some combinatorial identities for the r-Dowling polynomials, Notes Number Theory Discrete Math. 25 (2019), 145–154.

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

    at https://oeis.org.

[24] M. Z. Spivey, A generalized recurrence for Bell numbers, J. Integer Sequences 11 (2008), Article 08.2.5.

[25] C. G. Wagner, Partition statistics and q-Bell numbers (q = −1), J. Integer Sequences 7 (2004), Article 04.1.1.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05A05. Keywords: Laguerre polynomial, q-generalization, partial r-Bell polynomial, combinatorial proof.

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

Received November 2 2020; revised version received January 16 2021. Published in Journal of Integer Sequences January 23 2021.

Return to Journal of Integer Sequences home page.