Identities for Generalized Whitney and Stirling Numbers

Mark Shattuck Institute for Computational Science and Faculty of Mathematics and Statistics Ton Duc Thang University Ho Chi Minh City Vietnam

               mark.shattuck@tdt.edu.vn

Abstract

In this paper, we prove by algebraic methods two further formulas satisfied by the r-Whitney numbers of the second kind, which have been an object of recent study. We establish a version of one of the formulas for a polynomial generalization of the r-Whitney numbers. As special cases, we obtain apparently new identities for the Stirling numbers of the second kind and the Bell numbers. Moreover, one may obtain analogous formulas for Lah numbers and Stirling numbers of the first kind.

1 Introduction

The r-Whitney numbers of the second kind, which will be denoted by W (n, k) = W (n, k; r, m), were studied by Cheon and Jung [5], where several algebraic properties are found (also see [11]). The W (n, k) are connection constants in the polynomial identities

(mx + r)^{n} = ∑_{k=0}^{n} W (n, k)m^{k}(x)_{k}, n ≥ 0,

where (x)_{k} = x(x − 1) ⋯ (x − k + 1) if k ≥ 1, with (x)_{0} = 1. The parameter r is usually taken to be a non-negative integer and the parameter m a positive integer, but both may also be regarded as indeterminates. Equivalently, the W (n, k) are defined by the recurrence

W (n, k) = W (n − 1, k − 1) + (r + mk)W (n − 1, k), n, k ≥ 1,

with initial values W (n, 0) = r^{n} and W (0, k) = δ_{k,0} for n, k ≥ 0. The r-Dowling numbers D(n) = D(n; r, m) [5] are defined as D(n) = ∑_{k=0}^{n} W (n, k) for n ≥ 0.

The r = 1 case of the r-Whitney and r-Dowling numbers are known simply as Whitney and Dowling numbers; see, e.g., [1, 2, 12] for various properties. When r = 0 and m = 1, the r-Whitney and r-Dowling numbers reduce, respectively, to the Stirling numbers of the second kind and to the Bell numbers (see sequences \underline{A008277} and \underline{A000110} in OEIS [14]), which we will denote here by S(n, k) and B(n). See [9] and references contained therein for various generalizations of S(n, k) and B(n). When m = 1, the W (n, k) and D(n) reduce to the r-Stirling numbers [3] of the second kind and to the r-Bell numbers [10].

In the next two sections of this paper, we prove two new identities for the r-Whitney and r-Dowling numbers. We use generating function techniques to establish our results. As special cases, we will obtain recurrence formulas for the Stirling and Bell numbers, which are also given combinatorial proofs. For one of the identities, we in fact prove a polynomial generalization involving a recently introduced (p, q)-analogue [8] of W (n, k); also see [7] for a related q-analogue. This result (Theorem 3 below) is seen to generalize the well-known Stirling number recurrence [16, Identity 1.11] given by

S(n + 1, k + 1) = ∑_{i=0}^{n} \binom{n}{i}S(i, k), n, k ≥ 0,

upon suitably selecting the parameters. The comparable formula for the r-Dowling numbers (Corollary 4 below) is seen to generalize the Bell number recurrence [15, p. 34] given by

B(n + 1) = ∑_{i=0}^{n} \binom{n}{i}B(i), n ≥ 0.

We conclude by noting analogues of our results that hold for the Stirling numbers of the first kind and Lah numbers.

2 Generalized r-Whitney formula

In this section, we prove a formula for a polynomial generalization of the r-Whitney numbers. Given an indeterminate q, let [n]_{q} = 1 + q + ⋯ + q^{n−1} if n ≥ 1, with [0]_{q} = 0. Let W_{p,q}(n, k) = W_{p,q}(n, k; r, m) denote the sequence of polynomials defined recursively by

W_{p,q}(n, k) = W_{p,q}(n − 1, k − 1) + ([r]_{p} + m[k]_{q})W_{p,q}(n − 1, k), n, k ≥ 1,

with W_{p,q}(n, 0) = [r]_{p}^{n} and W_{p,q}(0, k) = δ_{k,0} for n, k ≥ 0, see [8]. Note that W_{p,q}(n, k) reduces to W (n, k) when p = q = 1. The column generating function for W_{p,q}(n, k) is given by

∑_{n≥k} W_{p,q}(n, k)x^{n} = \frac{x^{k}}{∏_{i=0}^{k}(1 − ([r]_{p} + m[i]_{q})x)},  k ≥ 0.  (1)

We denote the special case of W_{p,q}(n, k) when r = 0 and m = p = 1 by S_{q}(n, k). The S_{q}(n, k) sequence is a polynomial generalization of the Stirling numbers which was introduced by Carlitz [4] and has since been studied (see, e.g., [16]). In what follows, we will make use of the well-known generating function formulas

∑_{n≥k} S_{q}(n, k)x^{n} = \frac{x^{k}}{∏_{i=1}^{k}(1 − [i]_{q}x)},  k ≥ 0,  (2)

and

∑_{n≥k} \binom{n}{k}x^{n} = \frac{x^{k}}{(1 − x)^{k+1}} ,  k ≥ 0.  (3)

Before proving our main result, we will need a couple of lemmas.

Lemma 1. If n > k ≥ 0, then

W_{p,q}(n, k + 1) − [r]_{p}W_{p,q}(n − 1, k + 1) = ∑_{j=k}^{n−1} \binom{n − 1}{j}(mq)^{j−k}(m + [r]_{p})^{n−j−1}S_{q}(j, k). (4)

Proof. Computing the generating function for the right-hand side of (4), we have

∑_{n≥k+1} x^{n} ∑_{j=k}^{n−1}\binom{n − 1}{j}(mq)^{j−k}(m + [r]_{p})^{n−j−1}S_{q}(j, k)

= ∑_{j≥k} S_{q}(j, k)(mq)^{j−k}(m + [r]_{p})^{−j}x ∑_{n≥j+1} \binom{n − 1}{j}(m + [r]_{p})^{n−1}x^{n−1}

= ∑_{j≥k} S_{q}(j, k)(mq)^{j−k}(m + [r]_{p})^{−j}x · \frac{(m + [r]_{p})^{j}x^{j}}{(1 − (m + [r]_{p})x)^{j+1}}

= \frac{(mq)^{−k}x}{1 − (m + [r]_{p})x} ∑_{j≥k} S_{q}(j, k) (\frac{mqx}{1 − (m + [r]_{p})x})^{j}

= \frac{(mq)^{−k}x}{1 − (m + [r]_{p})x} · \frac{(mqx)^{k}}{(1 − (m + [r]_{p})x)^{k} ∏_{i=1}^{k} (1 − \frac{mq[i]_{q}x}{1−(m+[r]_{p})x})}

= \frac{x^{k+1}}{∏_{i=1}^{k+1}(1 − ([r]_{p} + m[i]_{q})x)},

by formulas (3) and (2) and since m + mq[i]_{q} = m[i + 1]_{q} for i ≥ 0. By (1), the left-hand side of (4) is seen to have this same generating function, which completes the proof.

Lemma 2. If d > k + 1, then

∑_{n=k+1}^{d−1}(W_{p,q}(n, k + 1) − [r]_{p}W_{p,q}(n − 1, k + 1))x^{n}

= \frac{m^{d−k−1}}{q^{k}} ∑_{ℓ=k}^{d−1} ∑_{j=k}^{ℓ−1} ∑_{i=j}^{ℓ−1} \binom{d − 1}{ℓ}\binom{i}{j}m^{j−ℓ}q^{j}[r]_{p}^{i−j}S_{q}(j, k)x^{i+d−ℓ}(1 − mx)^{ℓ−i−1}. (5)

Proof. The right-hand side of (5) is seen to be a polynomial in x whose powers lie in the set {k + 1, k + 2, …, d − 1}. If k + 1 ≤ n ≤ d − 1, then the coefficient of x^{n} on the right side of (5) is given by

\frac{(−1)^{d−n}m^{n−k−1}}{q^{k}} ∑_{ℓ=k}^{d−1} ∑_{j=k}^{ℓ−1} ∑_{i=j}^{ℓ−1}(−1)^{ℓ−i}\binom{d − 1}{ℓ}\binom{i}{j}\binom{ℓ − i − 1}{d − n − 1}m^{j−i}q^{j}[r]_{p}^{i−j}S_{q}(j, k)

= \frac{(−1)^{d−n}m^{n−k−1}}{q^{k}} ∑_{j=k}^{d−2} ∑_{i=j}^{d−2}(−1)^{i}\binom{i}{j}m^{j−i}q^{j}[r]_{p}^{i−j}S_{q}(j, k) ∑_{ℓ=i+1}^{d−1}(−1)^{ℓ}\binom{d − 1}{ℓ}\binom{ℓ − i − 1}{d − n − 1}.

Note that the innermost sum in the last expression is the coefficient of x^{d−i−2} in the convolution product

(−1)^{d−1}(1 − x)^{d−1} · \frac{x^{d−n−1}}{(1 − x)^{d−n}} ,

and is thus given by

(−1)^{d−1}[x^{n−i−1}](1 − x)^{n−1} = (−1)^{d−1}\binom{n − 1}{n − 1 − i}(−1)^{n−i−1} = (−1)^{d+n−i}\binom{n − 1}{i}.

Plugging this into the last expression implies that the aforementioned coefficient of x^{n} is given by

∑_{j=k}^{d−2}(mq)^{j−k}S_{q}(j, k) ∑_{i=j}^{d−2} \binom{i}{j}\binom{n − 1}{i}m^{n−i−1}[r]_{p}^{i−j}

= ∑_{j=k}^{d−2} \binom{n − 1}{j}(mq)^{j−k}S_{q}(j, k) ∑_{i=j}^{d−2} \binom{n − j − 1}{i − j}m^{n−i−1}[r]_{p}^{i−j}

= ∑_{j=k}^{n−1} \binom{n − 1}{j}(mq)^{j−k}S_{q}(j, k) ∑_{i=0}^{n−j−1} \binom{n − j − 1}{i}m^{n−j−1−i}[r]_{p}^{i}

= ∑_{j=k}^{n−1} \binom{n − 1}{j}(mq)^{j−k}(m + [r]_{p})^{n−j−1}S_{q}(j, k)

= W_{p,q}(n, k + 1) − [r]_{p}W_{p,q}(n − 1, k + 1),

by the binomial theorem and Lemma 1, which completes the proof.

Theorem 3. If n, k ≥ 0 and d ≥ 1, then

W_{p,q}(n + d, k + 1) − [r]_{p}W (n + d − 1, k + 1)
= \frac{m^{n+d−k−1}}{q^{k}} ∑_{ℓ=0}^{d−1} ∑_{i=0}^{n} ∑_{j=0}^{i+ℓ} \binom{d − 1}{ℓ}\binom{n}{i}\binom{i + ℓ}{j}m^{−j}q^{i+ℓ−j}[r]_{p}^{j}S_{q}(i + ℓ − j, k). (6)

Proof. We first assume d > k + 1. Then by (1), we have

∑_{n≥0}(W_{p,q}(n + d, k + 1) − [r]_{p}W_{p,q}(n + d − 1, k + 1))x^{n+d}

= \frac{x^{k+1}}{∏_{i=1}^{k+1}(1 − ([r]_{p} + m[i]_{q})x)} − ∑_{n=k+1}^{d−1}(W_{p,q}(n, k + 1) − [r]_{p}W_{p,q}(n − 1, k + 1))x^{n}. (7)

We now compute the generating function of the quantity on the right-hand side of (6). Consider replacing j by i + ℓ − j in the innermost sum. Furthermore, note that if ℓ < k, then the innermost sum is empty unless i ≥ k − ℓ (since j ≥ k is required), whereas if ℓ ≥ k, then this sum is non-empty for all i ≥ 0. We rearrange the terms in the sum as follows:

∑_{ℓ=0}^{d−1} ∑_{i=0}^{n} ∑_{j=k}^{i+ℓ} = ∑_{ℓ=0}^{k−1} ∑_{i=0}^{n} ∑_{j=k}^{i+ℓ} + ∑_{ℓ=k}^{d−1} ∑_{i=0}^{n} ∑_{j=k}^{i+ℓ} = ∑_{ℓ=0}^{k−1} ∑_{j=k}^{ℓ+n} ∑_{i=j−ℓ}^{n} + ∑_{ℓ=k}^{d−1} ∑_{j=k}^{ℓ+n} ∑_{i=j−ℓ}^{n} − ∑_{ℓ=k}^{d−1} ∑_{j=k}^{ℓ−1} ∑_{i=j−ℓ}^{−1}

= ∑_{ℓ=0}^{d−1} ∑_{j=k}^{ℓ+n} ∑_{i=j−ℓ}^{n} − ∑_{ℓ=k}^{d−1} ∑_{j=k}^{ℓ−1} ∑_{i=j−ℓ}^{−1} := S_{1} − S_{2}.

If i < 0, then let \binom{n}{i} = (−1)^{n−i}\binom{−i−1}{−n−1} if i ≤ n < 0, with \binom{n}{i} = 0 otherwise. Note that with this definition that (3) continues to hold for k < 0. While S_{1} contains terms where i < 0 in the \binom{n}{i} factor, the sum sought contains no such terms of this form; hence, these terms are subtracted in S_{2}. We compute the generating function for S_{1} and S_{2} separately, first considering S_{1}:

\frac{1}{m^{k+1}q^{k}} ∑_{n≥−d}(mx)^{n+d} ∑_{ℓ=0}^{d−1} ∑_{j=k}^{ℓ+n} ∑_{i=j−ℓ}^{n} \binom{d − 1}{ℓ}\binom{n}{i}\binom{i + ℓ}{j}m^{j−i−ℓ}q^{j}[r]_{p}^{i+ℓ−j}S_{q}(j, k)

= \frac{m^{d−k−1}}{q^{k}} ∑_{ℓ=0}^{d−1} ∑_{j≥k} ∑_{i≥j−ℓ} \binom{d − 1}{ℓ}\binom{i + ℓ}{j}m^{j−i−ℓ}q^{j}[r]_{p}^{i+ℓ−j}S_{q}(j, k)\frac{m^{i}x^{i+d}}{(1 − mx)^{i+1}}

= \frac{m^{d−k−1}}{q^{k}} ∑_{ℓ=0}^{d−1} ∑_{j≥k} \binom{d − 1}{ℓ}m^{j−ℓ}q^{j}[r]_{p}^{ℓ−j}S_{q}(j, k) ∑_{i≥j−ℓ} \binom{i + ℓ}{j}\frac{[r]_{p}^{i}x^{i+d}}{(1 − mx)^{i+1}}

= \frac{m^{d−k−1}}{q^{k}} ∑_{ℓ=0}^{d−1} ∑_{j≥k} \binom{d − 1}{ℓ}m^{j−ℓ}q^{j}[r]_{p}^{ℓ−j}S_{q}(j, k)x^{d−ℓ} (\frac{[r]_{p}}{1 − mx})^{−ℓ} \frac{([r]_{p}x)^{j}}{(1 − (m + [r]_{p})x)^{j+1}}

= \frac{m^{d−k−1}}{q^{k}} ∑_{ℓ=0}^{d−1} \binom{d − 1}{ℓ}x^{d−ℓ} (\frac{1 − mx}{m})^{ℓ} ∑_{j≥k} S_{q}(j, k)\frac{(mqx)^{j}}{(1 − (m + [r]_{p})x)^{j+1}}

= \frac{m^{d−k−1}}{q^{k}} ∑_{ℓ=0}^{d−1} \binom{d − 1}{ℓ}x^{d−ℓ} (\frac{1 − mx}{m})^{ℓ} \frac{(mqx)^{k}}{(1 − (m + [r]_{p})x)^{k+1} ∏_{i=1}^{k} (1 − \frac{mq[i]_{q}x}{1−(m+[r]_{p})x})}

= \frac{m^{d−1}x^{k}}{∏_{i=1}^{k+1}(1 − ([r]_{p} + m[i]_{q})x)} ∑_{ℓ=0}^{d−1} \binom{d − 1}{ℓ}x^{d−ℓ} (\frac{1 − mx}{m})^{ℓ}

= \frac{x^{k+1}}{∏_{i=1}^{k+1}(1 − ([r]_{p} + m[i]_{q})x)},

which is the first term on the right-hand side of (7).

The generating function for S_{2} is given by

\frac{1}{m^{k+1}q^{k}} ∑_{n≥−d}(mx)^{n+d} ∑_{ℓ=k}^{d−1} ∑_{j=k}^{ℓ−1} ∑_{i=j−ℓ}^{−1} \binom{d − 1}{ℓ}\binom{n}{i}\binom{i + ℓ}{j}m^{j−i−ℓ}q^{j}[r]_{p}^{i+ℓ−j}S_{q}(j, k)

= \frac{m^{d−k−1}}{q^{k}} ∑_{ℓ=k}^{d−1} ∑_{j=k}^{ℓ−1} ∑_{i=j}^{ℓ−1} \binom{d − 1}{ℓ}\binom{i}{j}m^{j−ℓ}q^{j}[r]_{p}^{i−j}S_{q}(j, k)x^{i+d−ℓ}(1 − mx)^{ℓ−i−1},

upon replacing i by i − ℓ in the innermost sum. By Lemma 2, this last expression equals

∑_{n=k+1}^{d−1}(W_{p,q}(n, k + 1) − [r]_{p}W_{p,q}(n − 1, k + 1))x^{n},

which by (7) shows that the right side of (6) has the same generating function as the left. This implies (6) in the case when d > k + 1. If d ≤ k + 1, then a similar argument may be given where both S_{2} and the sum on the right side of (7) are empty, which completes the proof.

We note some special cases of the prior result.

Corollary 4. If n, k ≥ 0 and d ≥ 1, then

W (n + d, k + 1) − rW (n + d − 1, k + 1) = ∑_{ℓ=0}^{d−1} ∑_{i=0}^{n} \binom{d − 1}{ℓ}\binom{n}{i}m^{n+d−i−ℓ−1}W (i + ℓ, k) (8)

and

D(n + d) − rD(n + d − 1) = ∑_{ℓ=0}^{d−1} ∑_{i=0}^{n} \binom{d − 1}{ℓ}\binom{n}{i}m^{n+d−i−ℓ−1}D(i + ℓ).  (9)

Proof. Formula (8) follows from substituting p = q = 1 in (6) and using the fact

W (i + ℓ, k) = ∑_{j=0}^{i+ℓ} \binom{i + ℓ}{j}m^{i+ℓ−j−k}r^{j}S(i + ℓ − j, k),

see [5, Section 3]. Summing (8) over k ≥ 0, and noting that W (n + d, 0) = rW (n + d − 1, 0), gives formula (9).

Taking r = 0 and m = 1 in (6) gives the following recurrence for S_{q}(n, k).

Corollary 5. If n, k ≥ 0 and d ≥ 1, then

S_{q}(n + d, k + 1) = ∑_{ℓ=0}^{d−1} ∑_{i=0}^{n} \binom{d − 1}{ℓ}\binom{n}{i}q^{i+ℓ−k}S_{q}(i + ℓ, k).  (10)

Taking q = 1 in (10) gives the following formula for S(n, k):

S(n + d, k + 1) = ∑_{ℓ=0}^{d−1} ∑_{i=0}^{n} \binom{d − 1}{ℓ}\binom{n}{i}S(i + ℓ, k),  d ≥ 1.  (11)

Summing (11) over k ≥ 0 yields the following Bell number formula:

B(n + d) = ∑_{ℓ=0}^{d−1} ∑_{i=0}^{n} \binom{d − 1}{ℓ}\binom{n}{i}B(i + ℓ),  d ≥ 1.  (12)

Remark 6. The d = 1 cases of (11) and (12) correspond to the well-known recurrences for the Stirling and Bell numbers, respectively. The d = 2 cases of (11) and (12) may be written as

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

and

B(n + 2) = 2B(n + 1) + ∑_{i=1}^{n} \binom{n}{i − 1}B(i),  n ≥ 0,  (14)

the latter of which is previously known [13].

We conclude this section by giving bijective proofs of the last four identities.

Combinatorial proof of formulas (11)–(14).

Let P_{n,k} denote the set of all partitions of [n] = {1, 2, …, n} containing exactly k blocks and let P_{n} = ∪_{k=0}^{n}P_{n,k}. To show (11), suppose that the number of elements of [2, d] = {2, 3, …, d} lying in the block containing 1 of π ∈ P_{n+d,k+1} is d − ℓ − 1, while the number of elements of [d+1, d+n] lying in this block is n−i, where 0 ≤ ℓ ≤ d−1 and 0 ≤ i ≤ n. Then there are \binom{d−1}{d−1−ℓ}\binom{n}{n−i} choices regarding the block of π containing 1, with the remaining i + ℓ elements of [n+d] to be partitioned in any one of S(i+ℓ, k) ways. Summing over all possible i and ℓ gives (11). A similar proof applies to (12), upon allowing partitions to contain any number of blocks.

To show (13), first note that there are S(n + 1, k + 1) members of P_{n+2,k+1} in which the elements 1 and 2 belong to the same block and S(n + 1, k) members in which 1 belongs to its own block. Next observe that there are \binom{n}{n−i+1}S(i, k) = \binom{n}{i−1}S(i, k) members of P_{n+2,k+1} for 1 ≤ i ≤ n in which there are exactly n − i + 1 elements of [3, n + 2] belonging to the block containing 1, with 1 and 2 belonging to different blocks (note that the remaining n − (n − i + 1) = i − 1 elements of [3, n + 2], together with 2, would constitute a partition having k blocks). Summing over i yields all members of P_{n+2,k+1} in which 1 and 2 belong to different blocks, with 1 not forming its own block. Combining this with the previous cases gives (13). Similar reasoning applies to (14). Note that there are 2B(n + 1) members of P_{n+2} in which 1 either belongs to its own block or to the same block as 2 and that there are \binom{n}{n−i+1}B(i) members of P_{n+2} for 1 ≤ i ≤ n in which 1 and 2 belong to different blocks with the cardinality of the block containing 1 equal n − i + 2.

3 A further formula for r-Whitney numbers

In this section, we prove a further identity satisfied by the r-Whitney numbers of the second kind.

Theorem 7. If n ≥ 1 and k ≥ 2, then

W (n+1, k)−rW (n, k) = ∑_{j=0}^{n−1} (\binom{n}{j} + \frac{r}{m} − 1) m^{n−j}W (j, k−1)+∑_{j=1}^{n} \binom{n}{j}m^{n−j}W (j−1, k−2)

(15)

and

D(n + 1) − rD(n) = m^{n} + ∑_{j=0}^{n−1} (\binom{n}{j} + \frac{r}{m} − 1) m^{n−j}D(j) + ∑_{j=1}^{n} \binom{n}{j}m^{n−j}D(j − 1). (16)

Proof. By (1) when p = q = 1, we have

∑_{n≥1}(W (n + 1, k) − rW (n, k))x^{n} = \frac{x^{k−1}}{∏_{i=1}^{k}(1 − (r + mi)x)}.

Computing the generating function of the right-hand side of (15) gives

∑_{n≥1} x^{n} ∑_{j=0}^{n−1} (\binom{n}{j} + \frac{r}{m} − 1) m^{n−j}W (j, k − 1) + ∑_{n≥1} x^{n} ∑_{j=1}^{n} \binom{n}{j}m^{n−j}W (j − 1, k − 2)

= ∑_{j≥0} W (j, k − 1)m^{−j} ∑_{n≥j+1} (\binom{n}{j} + \frac{r}{m} − 1) (mx)^{n}

+ ∑_{j≥1} W (j − 1, k − 2)m^{−j} ∑_{n≥j} \binom{n}{j}(mx)^{n}

= ∑_{j≥0} W (j, k − 1)m^{−j} (\frac{(mx)^{j}}{(1 − mx)^{j+1}} − (mx)^{j} + \frac{(\frac{r}{m} − 1) (mx)^{j+1}}{1 − mx} )

+ ∑_{j≥1} W (j − 1, k − 2)m^{−j} \frac{(mx)^{j}}{(1 − mx)^{j+1}}

= ∑_{j≥0} W (j, k − 1)\frac{x^{j}}{(1 − mx)^{j+1}} − \frac{1 − rx}{1 − mx} ∑_{j≥0} W (j, k − 1)x^{j}

+ ∑_{j≥1} W (j − 1, k − 2)\frac{x^{j}}{(1 − mx)^{j+1}}

= \frac{x^{k−1}}{(1 − mx)^{k} ∏_{i=0}^{k−1} (1 − \frac{(r+mi)x}{1−mx})} − \frac{x^{k−1}(1 − rx)}{(1 − mx) ∏_{i=0}^{k−1}(1 − (r + mi)x)}

+ \frac{x^{k−1}}{(1 − mx)^{k} ∏_{i=0}^{k−2} (1 − \frac{(r+mi)x}{1−mx})}

= \frac{x^{k−1}(1 − mx) − x^{k−1}(1 − (r + mk)x) + x^{k−1}(1 − (r + mk)x)}{(1 − mx) ∏_{i=1}^{k}(1 − (r + mi)x)}

= \frac{x^{k−1}}{∏_{i=1}^{k}(1 − (r + mi)x)},

as before, which implies (15).

Summing both sides of (15) over k ≥ 2, and noting W (n + 1, 0) = rW (n, 0), implies

D(n + 1) − rD(n) = W (n + 1, 1) − rW (n, 1) + ∑_{j=0}^{n−1} (\binom{n}{j} + \frac{r}{m} − 1) m^{n−j}D(j)

+ ∑_{j=1}^{n} \binom{n}{j}m^{n−j}D(j − 1) − ∑_{j=0}^{n−1} (\binom{n}{j} + \frac{r}{m} − 1) m^{n−j}W (j, 0).

From this, we see that identity (16) holds if and only if

W (n + 1, 1) − rW (n, 1) = m^{n} + ∑_{j=0}^{n−1} (\binom{n}{j} + \frac{r}{m} − 1) m^{n−j}r^{j}.

This last equality follows from the fact that W (n + 1, 1) − rW (n, 1) = (m + r)^{n} (which can be obtained by taking p = q = 1 and k = 0 in (4)). This gives (16) and completes the proof.

We have as special cases of the prior result the following recurrence formulas for the Stirling and Bell numbers which we did not find in the literature.

Corollary 8. If n ≥ 1 and k ≥ 2, then

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

and

B(n + 1) = 1 + ∑_{j=1}^{n} (\binom{n + 1}{j} − 1) B(j − 1).  (18)

Proof. Taking m = 1 and r = 0 in (15) gives (17). Taking m = 1 and r = 0 in (16) implies

B(n + 1) − 1 = ∑_{j=0}^{n−1} (\binom{n}{j} − 1) B(j) + ∑_{j=0}^{n−1} \binom{n}{j + 1}B(j)

= ∑_{j=0}^{n} (\binom{n}{j} + \binom{n}{j + 1} − 1) B(j) = ∑_{j=0}^{n} (\binom{n + 1}{j + 1} − 1) B(j)

= ∑_{j=1}^{n} (\binom{n + 1}{j} − 1) B(j − 1),

which gives (18).

Using (2) and (3), it is possible to obtain a q-generalization of formula (17).

Theorem 9. If n ≥ 1 and k ≥ 2, then

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

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

One can also give a combinatorial proof of formulas (17) and (18).

Combinatorial proof of Corollary 8.

We first show (17). To do so, we count members of P_{n+1,k} according to the contents of the block B containing the element 1. First suppose that it is not the case that B equals [i] for some i. Then k ≥ 2 implies |B| = n − j + 1 where 1 ≤ j ≤ n − 1. Thus, members of P_{n+1,k} may be formed in this case by picking some subset S of [2, n + 1] of cardinality n − j where S ≠ [2, n − j + 1], adding the element 1 to S to obtain B, and then partitioning the j members of [n + 1] − B into k − 1 blocks. Summing over all possible i, it follows that there are ∑_{j=1}^{n−1} (\binom{n}{n−j} − 1) S(j, k − 1) members of P_{n+1,k} in which B does not equal [i] for any i.

On the other hand, members of P_{n+1,k} in which B = [i] for some i where i ≥ 1 may be formed as follows. First select a subset T of [n+1] of size n−j +1 that contains the element 1, where 1 ≤ j ≤ n. Note that there are \binom{n}{j} choices for T and that j ≥ 1 implies T is a proper subset of [n + 1]. Let ℓ denote the smallest element of [n + 1] − T. Form a member of P_{n+1,k} by letting [ℓ − 1] be one block and {ℓ} ∪ (T ∩ [ℓ + 1, n + 1]) be another, with the members of [n + 1] − (T ∪ {ℓ}) arranged according to a partition containing k − 2 blocks (of which there are S(j − 1, k − 2) possibilities). Considering all possible j, it follows that there are ∑_{j=1}^{n} \binom{n}{j}S(j − 1, k − 2) members of P_{n+1,k} in which B = [i] for some i. Combining this case with the prior one gives (17).

Reasoning as in the previous two paragraphs, one may define a one-to-one correspondence between the members of P_{n+1} containing at least two blocks and the set of all ordered pairs (S, P), where S is a subset of [n + 1] of cardinality n − j + 1 for some 1 ≤ j ≤ n with S ≠ [2, n − j + 2] and P is a member of P_{j−1}. Considering the cardinality of the set of all such ordered pairs implies (18).

4 Related results

We can give analogues of some of the prior results involving related sequences. Given 0 ≤ k ≤ n, let c(n, k) denote the (signless) Stirling number of the first kind and L(n, k) be the (signless) Lah number; see, e.g., sequences \underline{A008275} and \underline{A008297} in OEIS [14]. Recall that c(n, k) counts the number of permutations of [n] containing k cycles and that L(n, k) counts partitions of [n] into k blocks in which the elements within each block are ordered (see, e.g., [6]). Extending the combinatorial arguments presented above for identity (11) above to allow for ordering within blocks yields the following result.

Theorem 10. If n, k ≥ 0 and d ≥ 1, then

c(n + d, k + 1) = ∑_{ℓ=0}^{d−1} ∑_{i=0}^{n} \binom{d − 1}{ℓ}\binom{n}{i}(n + d − i − ℓ − 1)!c(i + ℓ, k)  (20)

and

L(n + d, k + 1) = ∑_{ℓ=0}^{d−1} ∑_{i=0}^{n} \binom{d − 1}{ℓ}\binom{n}{i}(n + d − i − ℓ)!L(i + ℓ, k).  (21)

Remark 11. Summing (20) and (21) over k gives comparable formulas involving the n! and L(n) sequences, respectively, where L(n) = ∑_{k=0}^{n} L(n, k) (see \underline{A000262} in [14]).

We also have the following analogues of identity (17).

Theorem 12. If n ≥ 1 and k ≥ 2, then

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

(22)

and

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

(23)

Proof. We show only (22), as a similar proof will apply to (23). We proceed as in the combinatorial proof of formula (17) above. Let S_{n+1,k} be the set of permutations of [n + 1] containing k cycles and let B denote the cycle containing 1 within a member of S_{n+1,k}. Then the first term on the right-hand side of (22) is seen to count all members of S_{n+1,k} in which B does not comprise the elements of [i] for any i and has cardinality n − j + 1 for some 1 ≤ j ≤ n. Note that the (n − j)! factor accounts for the ordering of the elements within B.

Now consider members of S_{n+1,k} such that B comprises the elements of [i + 1] for some 0 ≤ i ≤ n − 1. Suppose further that the cycle containing the element i + 2 has cardinality n − i − j + 1 where 1 ≤ j ≤ n − i. Then there are \binom{n−i−1}{n−i−j} = \binom{n−i−1}{j−1} choices for the elements of this cycle and i!(n − i − j)! ways in which to order the elements of the first two cycles. The remaining n + 1 − (i + 1) − (n − i − j + 1) = j − 1 elements of [n + 1] are then arranged within cycles in c(j − 1, k − 2) ways. Summing over all possible i and j gives the second term on the right side of (22) and completes the proof.

Summing (22) and (23) over k ≥ 2 yields analogues of identity (16) involving n! and L(n). These formulas may also be given a combinatorial proof by extending the argument above for (18).

References

[1] M. Benoumhani, On Whitney numbers of Dowling lattices, Discrete Math. 159 (1996), 13–33.

[2] M. Benoumhani, On some numbers related to Whitney numbers of Dowling lattices, Adv. in Appl. Math. 19 (1997), 106–116.

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

[4] L. Carlitz, q-Bernoulli numbers and polynomials, Duke Math. J. 15 (1948), 987–1000.

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

[6] J. Lindsay, T. Mansour, and M. Shattuck, A new combinatorial interpretation of a q-analogue of the Lah numbers, J. Comb. 2 (2010), 245–264.

[7] M. M. Mangontarum and J. Katriel, On q-boson operators and q-analogues of the r-Whitney and r-Dowling numbers, J. Integer Sequences 18 (2015), Article 15.9.8.

[8] T. Mansour, J. L. Ramírez, and M. Shattuck, A generalization of the r-Whitney numbers of the second kind, J. Comb. 8 (2017), 29–55.

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

[10] I. Mező, The r-Bell numbers, J. Integer Sequences 14 (2011), Article 11.1.1.

[11] I. Mező and J. L. Ramírez, Some identities of the r-Whitney numbers, Aequationes Math. 90 (2016), 393–406.

[12] M. Rahmani, Some results on Whitney numbers of Dowling lattices, Arab J. Math. Sci. 20 (2014), 11–27.

[13] P. K. Saikia and D. Subedi, Bell numbers, determinants and series, Proc. Indian Acad. Sci. (Math. Sci.) 123 (2013), 151–166.

[14] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[15] R. P. Stanley, Enumerative Combinatorics, Vol. I, Cambridge University Press, 1997.

[16] C. G. Wagner, Generalized Stirling and Lah numbers, Discrete Math. 160 (1996), 199– 218.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 11B73, 05A15. Keywords: r-Whitney number, Stirling number, q-analogue, combinatorial identity.

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

Received April 18 2017; revised version received September 27 2017. Published in Journal of Integer Sequences, October 29 2017.

Return to Journal of Integer Sequences home page.