The (l, r)-Lah Numbers

Aleks Žigon Tankosič Milojka Štrukelj Elementary School Delpinova ulica 7 5000 Nova Gorica Slovenia

                     zigontaleks@gmail.com

Abstract

After reviewing the definitions and some properties of the Lah numbers and the Stirling numbers of both kinds, as well as their generalizations (r-Lah numbers, r-Stirling numbers of both kinds and (l, r)-Stirling numbers of both kinds), we define the (l, r)-Lah numbers analogously, prove a recurrence relation that they satisfy, express them explicitly as a multiple sum, and present the difference-differential equations satisfied by their column and row generating functions, respectively. Finally, we pose two conjectures, based on experimental evidence.

1 Introduction

After binomial coefficients, the Stirling numbers of the first and second kind are probably the best known triangular arrays of natural numbers, arising in many combinatorial, algebraic, and even analytic contexts. Recognized at least since the 18th century, they were joined and nicely complemented by the Lah numbers (a.k.a. Stirling numbers of the third kind) in the 1950s. In the 1980s, a third parameter was added to the definition of Stirling numbers, resulting in the r-Stirling numbers of the first and second kind. In the last decade, the r-Lah numbers were defined and their properties explored. In 2021, a fourth parameter was added to the definition of r-Stirling numbers, yielding the (l, r)-Stirling numbers of the first and second kind. Here we define and explore the analogous (l, r)-Lah numbers.

The article is organized as follows. Section 2 contains definitions of the Lah and r-Lah numbers, lists some recurrence relations that they satisfy, expresses them explicitly in terms of factorials, and presents some of their applications. With the exception of explicit representation, Section 3 does the same for the Stirling, r-Stirling, and (l, r)-Stirling numbers of both kinds. In Section 4, we define the new (l, r)-Lah numbers, prove a recurrence relation that they satisfy, express them explicitly in terms of a multiple sum, and present the difference-differential equations satisfied by their column and row generating functions, respectively. Finally, in Section 5, we pose two conjectures, based on experimental evidence.

2 The Lah and r-Lah numbers

The unsigned Lah numbers \left⌊{n \atop k}\right⌋ count partitions of the set [n] := \{1, 2, …, n\} into k nonempty linearly ordered blocks (lists, for short).

For n, k ≥ 1, they satisfy the recurrence

\left⌊{n \atop k}\right⌋ = (n + k − 1)\left⌊{n − 1 \atop k}\right⌋ + \left⌊{n − 1 \atop k − 1}\right⌋  (1)

which, together with the initial conditions \left⌊{0 \atop 0}\right⌋ = 1, \left⌊{n \atop 0}\right⌋ = \left⌊{0 \atop k}\right⌋ = 0 for n, k > 0, can be used to compute \left⌊{n \atop k}\right⌋ for all n, k ≥ 0.

\begin{matrix}nk & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 6 & 6 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 24 & 36 & 12 & 1 & 0 & 0 & 0 & 0 \\ 5 & 0 & 120 & 240 & 120 & 20 & 1 & 0 & 0 & 0 \\ 6 & 0 & 720 & 1800 & 1200 & 300 & 30 & 1 & 0 & 0 \\ 7 & 0 & 5040 & 15120 & 12600 & 4200 & 630 & 42 & 1 & 0 \\ 8 & 0 & 40320 & 141120 & 141120 & 58800 & 11760 & 1176 & 56 & 1 \end{matrix}

Table 1: Unsigned Lah numbers \left⌊{n \atop k}\right⌋ for 0 ≤ n, k ≤ 8.

They can also be expressed explicitly in terms of factorials and binomial coefficients as

\left⌊{n \atop k}\right⌋ = \frac{n!}{k!}\binom{n − 1}{n − k}.  (2)

For simple combinatorial proofs of (1) and (2), see, e.g., [13]. Another interesting property of Lah numbers is that they appear in the coefficients in the expansion of rising powers

x\overline{n} = x(x + 1)(x + 2) ⋯ (x + n − 1)

in terms of falling powers

x\underline{n} = x(x − 1)(x − 2) ⋯ (x − n + 1)

and vice versa, namely:

x\overline{n} = ∑_{k=0}^{n} \left⌊{n \atop k}\right⌋x\underline{k}, x\underline{n} = ∑_{k=0}^{n}(−1)^{n+k}\left⌊{n \atop k}\right⌋x\overline{k}

for all n ≥ 0 and all x, where x\overline{0} = x\underline{0} = 1. These identities can easily be proved by induction on n.

Lah numbers appear not only in combinatorics and algebra, but also in other areas of mathematics, such as mathematical analysis. For instance, the n-th derivative of the function e^{\frac{1}{x}} can be expressed for all n ≥ 0 as

(e^{\frac{1}{x}} )^{(n)} = e^{\frac{1}{x}} (−1)^{n} ∑_{k=0}^{n} \left⌊{n \atop k}\right⌋x^{−(n+k)} = e^{\frac{1}{x}} ∑_{k=0}^{n} \left⌊{n \atop k}\right⌋′x^{−(n+k)},  (3)

which again can be proved by induction on n. Here \left⌊{n \atop k}\right⌋′ = (−1)^{n}\left⌊{n \atop k}\right⌋ are the signed Lah numbers, introduced in [10] by Slovenian mathematician, statistician, and actuary Ivo Lah (1896–1979), and later named after him by Riordan in [14, pp. 43–44].

In the last decade, the r-Lah numbers, denoted by \left⌊{n \atop k}\right⌋_{r} (counting partitions of [n] into k non-empty lists such that the elements 1, 2, …, r are in distinct lists) were defined, and their properties explored (see [7, 1, 2, 15, 11, 16, 12]; note however that in [15, 11, 16, 12], the r-Lah number with parameters n, k, r equals our r-Lah number with parameters n + r, k + r, r).

For n, k ≥ 1, the r-Lah numbers satisfy the recurrence

\left⌊{n \atop k}\right⌋_{r} = (n + k − 1)\left⌊{n − 1 \atop k}\right⌋_{r} + \left⌊{n − 1 \atop k − 1}\right⌋_{r}  (4)

which, together with the initial conditions \left⌊{n \atop k}\right⌋_{r}= 0 if n < k or k < r, and \left⌊{n \atop n}\right⌋_{n}= 1, allows us to compute \left⌊{n \atop k}\right⌋_{r} for all n, k, r ≥ 0. They are expressed explicitly by the formula

\left⌊{n \atop k}\right⌋_{r} = \frac{(n + r − 1)!}{(k + r − 1)!}\binom{n − r}{k − r}.  (5)

Note that r-Lah numbers have applications in graph theory [12]. They also satisfy identities connecting rising and falling powers such as

(x + 2r)\overline{n} = ∑_{k=0}^{n} \left⌊{n + r \atop k + r}\right⌋_{r}x\underline{k},  (6)

(x − r)\underline{n} = ∑_{k=0}^{n}(−1)^{n+k}\left⌊{n + r \atop k + r}\right⌋_{r}(x + r)\overline{k}.  (7)

For proofs of identities (4)–(7), see [1] and [11].

\begin{matrix}nk & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 4 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 20 & 10 & 1 & 0 & 0 & 0 & 0 \\ 5 & 120 & 90 & 18 & 1 & 0 & 0 & 0 \\ 6 & 840 & 840 & 252 & 28 & 1 & 0 & 0 \\ 7 & 6720 & 8400 & 3360 & 560 & 40 & 1 & 0 \\ 8 & 60480 & 90720 & 45360 & 10080 & 1080 & 54 & 1 \end{matrix}

Table 2: 2-Lah numbers \left⌊{n \atop k}\right⌋_{2} for 2 ≤ n, k ≤ 8.

3 The Stirling, r-Stirling, and (l, r)-Stirling numbers

Stirling numbers were introduced by the Scottish mathematician James Stirling (1692–1770) in 1730. They come in two flavors: unsigned Stirling numbers of the first kind \left[{n \atop k}\right] count permutations of the set [n] with exactly k cycles (or, equivalently, partitions of the set [n] into k cyclically ordered blocks), while unsigned Stirling numbers of the second kind \left\{{n \atop k}\right\} count partitions of the set [n] into k unordered blocks.

Unsigned Stirling numbers of the first kind for n, k ≥ 1 satisfy the recurrence

\left[{n \atop k}\right] = (n − 1)\left[{n − 1 \atop k}\right] + \left[{n − 1 \atop k − 1}\right]  (8)

which, together with the initial conditions \left[{0 \atop 0}\right] = 1, \left[{n \atop 0}\right] = \left[{0 \atop k}\right] = 0 for n, k > 0, can be used to compute \left[{n \atop k}\right] for all n, k ≥ 0. They are also the coefficients in the expansion of rising powers in terms of ordinary powers:

x\overline{n} = ∑_{k=0}^{n} \left[{n \atop k}\right]x^{k}.  (9)

Similarly, unsigned Stirling numbers of the second kind for n, k ≥ 1 satisfy the recurrence

\left\{{n \atop k}\right\} = k\left\{{n − 1 \atop k}\right\} + \left\{{n − 1 \atop k − 1}\right\}  (10)

which, together with the initial conditions \left\{{0 \atop 0}\right\} = 1, \left\{{n \atop 0}\right\} = \left\{{0 \atop k}\right\} = 0 for n, k > 0, can be used to compute \left\{{n \atop k}\right\} for all n, k ≥ 0. They are also the coefficients in the expansion of ordinary powers in terms of falling powers:

x^{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}x\underline{k}.  (11)

There is a nice identity expressing Lah numbers with Stirling numbers of both kinds, namely

\left⌊{n \atop k}\right⌋ = ∑_{j=0}^{n} \left[{n \atop j}\right]\left\{{j \atop k}\right\}.  (12)

For proofs of identities (8)–(12), see, e.g., [8] or [13].

In the 1980’s, Stirling numbers of both kinds were generalized to r-Stirling numbers (cf. [5, 6, 4]). The unsigned r-Stirling numbers of the first kind \left[{n \atop k}\right]_{r} count permutations of [n] having k cycles such that the numbers 1, 2, …, r are in distinct cycles. They satisfy the same recurrence as the numbers \left[{n \atop k}\right]

\left[{n \atop k}\right]_{r} = (n − 1)\left[{n − 1 \atop k}\right]_{r} + \left[{n − 1 \atop k − 1}\right]_{r}, for n, k ≥ 1,  (13)

which, together with initial conditions \left[{n \atop k}\right]_{r} = 0 for n < k or k < r, and \left[{n \atop n}\right]_{r} = 1 for r ≤ n, can be used to compute \left[{n \atop k}\right]_{r} for all n, k, r ≥ 0. Another, so-called ‘cross’ recurrence (in which r changes but n stays fixed) satisfied by the unsigned r-Stirling numbers of the first kind is

\left[{n \atop k}\right]_{r} = \frac{1}{r − 1} (\left[{n \atop k − 1}\right]_{r−1} − \left[{n \atop k − 1}\right]_{r}) , for n, k ≥ 1, r ≥ 2  (14)

with initial conditions \left[{n \atop k}\right]_{r} = \left[{n \atop k}\right] for r ≤ 1, and \left[{n \atop k}\right]_{r} = 0 for n < k or k < r.

The unsigned r-Stirling numbers of the second kind \left\{{n \atop k}\right\}_{r} count partitions of [n] into k nonempty disjoint subsets such that the numbers 1, 2, …, r are in distinct subsets. They satisfy the same recurrence as the numbers \left\{{n \atop k}\right\}

\left\{{n \atop k}\right\}_{r} = k\left\{{n − 1 \atop k}\right\}_{r} + \left\{{n − 1 \atop k − 1}\right\}_{r}, for n, k ≥ 1,  (15)

which, together with initial conditions \left\{{n \atop k}\right\}_{r} = 0 for n < k or k < r, and \left\{{n \atop n}\right\}_{r} = 1 for r ≤ n, can be used to compute \left\{{n \atop k}\right\}_{r} for all n, k, r ≥ 0. The ‘cross’ recurrence satisfied by \left\{{n \atop k}\right\}_{r} is

\left\{{n \atop k}\right\}_{r} = \left\{{n \atop k}\right\}_{r−1} − (r − 1)\left\{{n − 1 \atop k}\right\}_{r−1}, for n, k, r ≥ 1  (16)

with initial conditions \left\{{n \atop k}\right\}_{0} = \left\{{n \atop k}\right\}, and \left\{{n \atop k}\right\}_{r} = 0 for n < k or k < r.

For proofs of identities (13)–(16), see [4].

In 2021, Belbachir and Djemmada [3] introduced (l, r)-Stirling numbers of the first kind \left[{n \atop k}\right]_{r}^{(l)} and (l, r)-Stirling numbers of the second kind \left\{{n \atop k}\right\}_{r}^{(l)} which count ordered l-tuples (π_{1}, π_{2}, …, π_{l}) of partitions of [n] into k cyclically ordered blocks, respectively into k unordered blocks, such that the numbers 1, 2, …, r are in distinct cycles, and satisfy

bl π_{1} = bl π_{2} = ⋯ = bl π_{l}

where for i = 1, 2, …, l and π_{i} = {b_{1}^{(i)}, b_{2}^{(i)}, …, b_{k}^{(i)}}, where b_{1}^{(i)}, … b_{k}^{(i)} are the blocks of partition π_{i}, we denote by

bl π_{i} = {min b_{1}^{(i)}, min b_{2}^{(i)}, …, min b_{k}^{(i)}}

the set of block leaders, i.e., of minima of the blocks of partition π_{i}.

Note that the (l, r)-Stirling numbers of the second kind are a generalization of the central factorial numbers of the second kind, see, e.g., [9].

Example 1. Let us compute \left\{{4 \atop 3}\right\}_{2}^{(2)}. Here n = 4, k = 3, l = r = 2, so we need to construct all partitions of the set [4] = {1, 2, 3, 4} into three nonempty blocks, such that 1 and 2 are in distinct blocks. There are five such partitions:

π_{1} = {{1}, {2}, {3, 4}},
π_{2} = {{1}, {2, 3}, {4}},
π_{3} = {{1}, {2, 4}, {3}},
π_{4} = {{1, 3}, {2}, {4}},
π_{5} = {{1, 4}, {2}, {3}},

and the sets of their block leaders are

bl π_{1} = bl π_{3} = bl π_{5} = {1, 2, 3},
bl π_{2} = bl π_{4} = {1, 2, 4}.

Now we compute the number of ordered l-tuples (i.e., ordered pairs) of partitions π_{1}, π_{2}, π_{3}, π_{4}, π_{5} such that partitions in the same pair share the same set of block leaders. As there are three partitions with the set of block leaders equal to {1, 2, 3}, and two partitions with the set of block leaders equal to {1, 2, 4}, we find that

\left\{{4 \atop 3}\right\}_{2}^{(2)} = 3^{2} + 2^{2} = 13.

The (l, r)-Stirling numbers of the first kind \left[{n \atop k}\right]_{r}^{(l)} satisfy the recurrence

\left[{n \atop k}\right]_{r}^{(l)} = (n − 1)^{l}\left[{n − 1 \atop k}\right]_{r}^{(l)} + \left[{n − 1 \atop k − 1}\right]_{r}^{(l)}, for n > k ≥ r ≥ 0,  (17)

which, together with initial conditions \left[{n \atop k}\right]_{r}^{(l)} = 0 for n < k or k < r, and \left[{n \atop k}\right]_{n}^{(l)} = δ_{n,k}, where δ_{n,k} = 1 if n = k and δ_{n,k} = 0 if n ≠ k, can be used to compute the numbers \left[{n \atop k}\right]_{r}^{(l)} for all n, k, l, r ≥ 0. They also satisfy the ‘cross’ recurrence

\left[{n \atop k}\right]_{r}^{(l)} = \frac{1}{(r − 1)^{l}} (\left[{n \atop k − 1}\right]_{r−1}^{(l)} − \left[{n \atop k − 1}\right]_{r}^{(l)}) , for n, k, l ≥ 1, r ≥ 2.  (18)

The (l, r)-Stirling numbers of the second kind \left\{{n \atop k}\right\}_{r}^{(l)} satisfy the recurrence

\left\{{n \atop k}\right\}_{r}^{(l)} = k^{l}\left\{{n − 1 \atop k}\right\}_{r}^{(l)} + \left\{{n − 1 \atop k − 1}\right\}_{r}^{(l)}, for n > k ≥ r ≥ 0,  (19)

which, together with initial conditions \left\{{n \atop k}\right\}_{r}^{(l)} = 0 for n < k or k < r, and \left\{{n \atop k}\right\}_{n}^{(l)} = δ_{n,k}, can be used to compute the numbers \left\{{n \atop k}\right\}_{r}^{(l)} for all n, k, l, r ≥ 0. They also satisfy the ‘cross’ recurrence

\left\{{n \atop k}\right\}_{r}^{(l)} = \left\{{n \atop k}\right\}_{r−1}^{(l)} − (r − 1)^{l}\left\{{n − 1 \atop k}\right\}_{r−1}^{(l)}, for n, k, l, r ≥ 1.  (20)

For proofs of identities (17)–(20), see [3].

4 The (l, r)-Lah numbers

Definition 2. (l, r)-Lah numbers \left⌊{n \atop k}\right⌋_{r}^{(l)} count ordered l-tuples (π_{1}, π_{2}, …, π_{l}) of partitions of [n] into k linearly ordered blocks (lists, for short) such that the numbers 1, 2, …, r are in distinct lists, and

bl π_{1} = bl π_{2} = ⋯ = bl π_{l}

where for i = 1, 2, …, l and π_{i} = {b_{1}^{(i)}, b_{2}^{(i)}, …, b_{k}^{(i)}}, where b_{1}^{(i)}, b_{2}^{(i)}, …, b_{k}^{(i)} are the blocks of partition π_{i},

bl π_{i} = {min b_{1}^{(i)}, min b_{2}^{(i)}, …, min b_{k}^{(i)}}

is the set of block leaders, i.e., of minima of the lists in partition π_{i}.

Example 3. Let us compute \left⌊{4 \atop 3}\right⌋_{2}^{(2)}. Here n = 4, k = 3, l = r = 2, so we need to construct all partitions of the set [4] = {1, 2, 3, 4} into three nonempty disjoint lists, such that 1 and 2 are in distinct lists. There are 10 such partitions:

π_{1} = {(1), (2), (3, 4)},
π_{2} = {(1), (2), (4, 3)},
π_{3} = {(1), (2, 3), (4)},
π_{4} = {(1), (3, 2), (4)},
π_{5} = {(1), (2, 4), (3)},
π_{6} = {(1), (4, 2), (3)},
π_{7} = {(1, 3), (2), (4)},
π_{8} = {(3, 1), (2), (4)},
π_{9} = {(1, 4), (2), (3)},
π_{10} = {(4, 1), (2), (3)},

and the sets of their block leaders are

bl π_{1} = bl π_{2} = bl π_{5} = bl π_{6} = bl π_{9} = bl π_{10} = {1, 2, 3},
bl π_{3} = bl π_{4} = bl π_{7} = bl π_{8} = {1, 2, 4}.

Now we compute the number of ordered l-tuples (i.e., ordered pairs) of partitions π_{1}, π_{2}, …, π_{10} such that partitions in the same pair share the same set of block leaders. As there are six partitions with the set of block leaders equal to {1, 2, 3}, and four partitions with the set of block leaders equal to {1, 2, 4}, we find that

\left⌊{4 \atop 3}\right⌋_{2}^{(2)} = 6^{2} + 4^{2} = 52.

Theorem 4. For n ≥ k ≥ r ≥ 1, (l, r)-Lah numbers satisfy the recurrence relation

\left⌊{n \atop k}\right⌋_{r}^{(l)} = (n + k − 1)^{l}\left⌊{n − 1 \atop k}\right⌋_{r}^{(l)} + \left⌊{n − 1 \atop k − 1}\right⌋_{r}^{(l)}.  (21)

Proof. Let π = (π_{1}, π_{2}, …, π_{l}) be an l-tuple of partitions of [n] into k nonempty lists such that the numbers 1, 2, …, r are in distinct lists, and bl π_{1} = bl π_{2} = ⋯ = bl π_{l}. Each such l-tuple π is of exactly one of the following two types:

Type A: There is an i ∈ [l] such that n is alone in its list in partition π_{i}. Then n is a block leader in each of π_{1}, π_{2}, …, π_{l}; hence n is alone in its list in each of the π_{i}. By deleting this list from each of the π_{i}, we obtain an l-tuple of partitions ρ = (ρ_{1}, ρ_{2}, …, ρ_{l}) of [n − 1] into k − 1 nonempty lists such that the numbers 1, 2, …, r are in distinct lists, and bl ρ_{1} = bl ρ_{2} = ⋯ = bl ρ_{l}. Going back, by appending the list (n) to each partition ρ_{i} we recover the initial l-tuple π, hence the number of l-tuples π of partitions of type A is \left⌊{n−1 \atop k−1}\right⌋_{r}^{(l)}.

Type B: Otherwise, for each i ∈ [l], the number n is not alone in its list in π_{i}, hence n is not a block leader in any of π_{1}, π_{2}, …, π_{l}. By deleting n from each of the π_{i}, we obtain an l-tuple of partitions ρ = (ρ_{1}, ρ_{2}, …, ρ_{l}) of the set [n − 1] into k nonempty lists such that the numbers 1, 2, …, r are in distinct lists, and bl ρ_{1} = bl ρ_{2} = ⋯ = bl ρ_{l}. Going back, by inserting n into some position of some list in each of the ρ_{i}, we obtain an l-tuple of partitions of [n] into k nonempty lists such that the numbers 1, 2, …, r are in distinct lists, and the sets of block leaders of these partitions are the same. As the number of possible insertion points in a list equals its length plus one, there are (n − 1) + k = n + k − 1 possible insertion points for n in a single partition ρ_{i}, and (n + k − 1)^{l} possibilities for the l-tuple of partitions ρ. Hence the number of l-tuples π of partitions of type B is (n + k − 1)^{l}\left⌊{n−1 \atop k}\right⌋_{r}^{(l)}.

It follows that the number \left⌊{n \atop k}\right⌋_{r}^{(l)} of all such l-tuples π of partitions of [n] equals the sum of the number of partitions of type A and the number of partitions of type B, which is \left⌊{n−1 \atop k−1}\right⌋_{r}^{(l)} + (n + k − 1)^{l}\left⌊{n−1 \atop k}\right⌋_{r}^{(l)}.

This recurrence, together with initial conditions \left⌊{n \atop k}\right⌋_{r}^{(l)} = 0 for n < k or k < r, \left⌊{n \atop n}\right⌋_{r}^{(l)} = 1, and \left⌊{r \atop k}\right⌋_{r}^{(l)} = δ_{k,r} can be used to compute the numbers \left⌊{n \atop k}\right⌋_{r}^{(l)} for all n, k, l, r ≥ 0.

\begin{matrix}nk & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 16 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 400 & 52 & 1 & 0 & 0 & 0 & 0 \\ 5 & 14400 & 2948 & 116 & 1 & 0 & 0 & 0 \\ 6 & 705600 & 203072 & 12344 & 216 & 1 & 0 & 0 \\ 7 & 45158400 & 17154432 & 1437472 & 38480 & 360 & 1 & 0 \\ 8 & 3657830400 & 1760601600 & 191088544 & 6978592 & 99320 & 556 & 1 \end{matrix}

Table 3: (2, 2)-Lah numbers \left⌊{n \atop k}\right⌋_{2}^{(2)} for 2 ≤ n, k ≤ 8.

\begin{matrix}nk & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 36 & 1 & 0 & 0 & 0 & 0 & 0 \\ 5 & 1764 & 100 & 1 & 0 & 0 & 0 & 0 \\ 6 & 112896 & 9864 & 200 & 1 & 0 & 0 & 0 \\ 7 & 9144576 & 1099296 & 34064 & 344 & 1 & 0 & 0 \\ 8 & 914457600 & 142159392 & 6004512 & 92200 & 540 & 1 & 0 \\ 9 & 110649369600 & 21385410048 & 1156921920 & 24075712 & 213700 & 796 & 1 \end{matrix}

Table 4: (2, 3)-Lah numbers \left⌊{n \atop k}\right⌋_{3}^{(2)} for 3 ≤ n, k ≤ 9.

Proposition 5 (some special cases).

\left⌊{n \atop r}\right⌋_{r}^{(l)} = (\left⌊{n \atop r}\right⌋_{r})^{l} = \frac{(n + r − 1)!^{l}}{(2r − 1)!^{l}} ,  (22)

\left⌊{n \atop n − 1}\right⌋_{r}^{(l)} = 2^{l} ∑_{j=r}^{n−1} j^{l}.  (23)

Proof. By Definition 2, \left⌊{n \atop r}\right⌋_{r}^{(l)} is the number of ordered l-tuples (π_{1}, π_{2}, …, π_{l}) of partitions of [n] into r lists such that the numbers 1, 2, …, r are in distinct lists, and bl π_{1} = bl π_{2} = ⋯ = bl π_{l}. As there are r lists in each partition, and 1, 2, …, r are in distinct lists, we have bl π = [r] for all partitions π, so \left⌊{n \atop r}\right⌋_{r}^{(l)} is simply the l-th power of the number of partitions of [n] into r lists such that the numbers 1, 2, …, r are in distinct lists. Hence \left⌊{n \atop r}\right⌋_{r}^{(l)} = (\left⌊{n \atop r}\right⌋_{r})^{l}, proving the first equality in (22), while the second equality in (22) follows from (5).

By (21) with k = n − 1, we have for n ≥ 1

\left⌊{n \atop n − 1}\right⌋_{r}^{(l)} = (2n − 2)^{l}\left⌊{n − 1 \atop n − 1}\right⌋_{r}^{(l)} + \left⌊{n − 1 \atop n − 2}\right⌋_{r}^{(l)}
= \left⌊{n − 1 \atop n − 2}\right⌋_{r}^{(l)} + (2n − 2)^{l}  (24)

since \left⌊{n−1 \atop n−1}\right⌋_{r}^{(l)} = 1. Using (24) repeatedly, we obtain

\left⌊{n \atop n − 1}\right⌋_{r}^{(l)} = \underline{\left⌊{n − 1 \atop n − 2}\right⌋_{r}^{(l)}} + (2n − 2)^{l}

\underline{\left⌊{n − 1 \atop n − 2}\right⌋_{r}^{(l)}} = \underline{\left⌊{n − 2 \atop n − 3}\right⌋_{r}^{(l)}} + (2n − 4)^{l}
⋮
\underline{\left⌊{r + 1 \atop r}\right⌋_{r}^{(l)}} = \left⌊{r \atop r − 1}\right⌋_{r}^{(l)} + (2r)^{l}.

Summing these equations and cancelling all the underlined terms, we find

\left⌊{n \atop n − 1}\right⌋_{r}^{(l)} = \left⌊{r \atop r − 1}\right⌋_{r}^{(l)} + ∑_{j=r}^{n−1}(2j)^{l} = 2^{l} ∑_{j=r}^{n−1} j^{l},

which is (23).

Theorem 6. (l, r)-Lah numbers can be expressed explicitly as

\left⌊{n \atop k}\right⌋_{r}^{(l)} = ∑_{r+1≤j_{1}<j_{2}<···<j_{n−k}≤n}(2j_{1} − 2)^{l}(2j_{2} − 3)^{l} ⋯ (2j_{n−k} − (n − k + 1))^{l}.  (25)

Proof. We will compute \left⌊{n \atop k}\right⌋_{r}^{(l)} by counting in how many ways one can construct an ltuple π = (π_{1}, π_{2}, …, π_{l}) of partitions of the set [n] into k lists such that 1, 2, …, r are in distinct lists, and bl π_{1} = bl π_{2} = ⋯ = bl π_{l}. In π_{1} there will be k leading elements 1, 2, …, r, λ_{r+1}, λ_{r+2}, …, λ_{k} ∈ [n] with r + 1 ≤ λ_{r+1} < λ_{r+2} < ⋯ < λ_{k} ≤ n, and n − k non-leading elements ν_{1}, ν_{2}, …, ν_{n−k} ∈ [n] with r + 1 ≤ ν_{1} < ν_{2} < ⋯ < ν_{n−k} ≤ n.

Starting with a set of k lists of length 1 containing their leaders, i.e., with

{(1), (2), …, (r), (λ_{r+1}), (λ_{r+2}), …, (λ_{k})},

we insert the non-leading elements ν_{1}, ν_{2}, …, ν_{n−k} one after another into the above lists, counting the ways to do this as we go along. A non-leading element ν_{i} can be inserted into a list iff this list’s leader is smaller than ν_{i}; on the other hand, ν_{i} can be inserted into any position within any such list. We now prove that for i = 1, 2, …, n − k, there are exactly 2ν_{i} − (i + 1) possible insertion points for ν_{i}. Recall that when inserting an element into any of k given lists in any position, where the sum of the list lengths is ℓ, the total number of possible insertion points is k + ℓ.

i = 1: Since ν_{1} is the least non-leader, all the smaller elements 1, 2, …, ν_{1} − 1 are leaders, hence there ν_{1} − 1 lists of length 1 into which ν_{1} can be inserted. Hence there are (ν_{1} − 1) + (ν_{1} − 1) = 2ν_{1} − 2 possible insertion points for ν_{1}.

i > 1: Assume that all the ν_{i} −1 elements smaller than ν_{i} have already been inserted into the lists. All of them, except for ν_{1}, ν_{2}, …, ν_{i−1}, are leaders, hence there are ν_{i}−1−(i−1) = ν_{i}−i lists into which ν_{i} can be inserted. These lists jointly contain ν_{i} − 1 elements, so there are (ν_{i} − i) + (ν_{i} − 1) = 2ν_{i} − (i + 1) possible insertion points for ν_{i} as claimed.

In all, we thus have (2ν_{1}−2)(2ν_{2}−3) ⋯ (2ν_{n−k}−(n−k+1)) ways to construct partition π_{1}, and the same number of ways also for each of π_{2}, π_{3}, …, π_{l} independently. Hence the number of ways to construct an l-tuple π = (π_{1}, π_{2}, …, π_{l}) for a fixed choice of ν_{1}, ν_{2}, …, ν_{n−k} is (2ν_{1} −2)^{l}(2ν_{2} −3)^{l} ⋯ (2ν_{n−k} −(n−k +1))^{l}, and the total number of such l-tuples is obtained by summing this product over all possible choices of ν_{1}, ν_{2}, …, ν_{n−k}. Hence

\left⌊{n \atop k}\right⌋_{r}^{(l)} = ∑_{r+1≤ν_{1}<ν_{2}<···<ν_{n−k}≤n}(2ν_{1} − 2)^{l}(2ν_{2} − 3)^{l} ⋯ (2ν_{n−k} − (n − k + 1))^{l},

which proves the theorem.

Theorem 7. For k ≥ r ≥ 1 and l ≥ 1, the column generating function

F_{k}^{l,r}(z) = ∑_{n=0}^{∞} \left⌊{n \atop k}\right⌋_{r}^{(l)}z^{n}

of (l, r)-Lah numbers, as a formal power series, satisfies the difference-differential equation

F_{k}^{l,r}(z) = zF_{k−1}^{l,r}(z) + ∑_{j=0}^{l} \binom{l}{j}(k − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\}z^{i} \frac{d^{i}}{dz^{i}} (zF_{k}^{l,r}(z)) .  (26)

Proof. Multiplying recurrence (21) by z^{n} and formally summing it on n from 2 to ∞ yields

∑_{n=2}^{∞} \left⌊{n \atop k}\right⌋_{r}^{(l)}z^{n} = ∑_{n=2}^{∞}(n + k − 1)^{l}\left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}z^{n} + ∑_{n=2}^{∞} \left⌊{n − 1 \atop k − 1}\right⌋_{r}^{(l)}z^{n}.  (27)

Rewrite the left-hand side of (27) as

∑_{n=2}^{∞} \left⌊{n \atop k}\right⌋_{r}^{(l)}z^{n} = F_{k}^{l,r}(z) − \left⌊{0 \atop k}\right⌋_{r}^{(l)} − \left⌊{1 \atop k}\right⌋_{r}^{(l)}z = \begin{cases}F_{k}^{l,r}(z), & if k ≥ 2; \\ F_{k}^{l,r}(z) − z, & if k = 1. \end{cases}

Rewrite the second term on the right-hand side of (27) as

∑_{n=2}^{∞} \left⌊{n − 1 \atop k − 1}\right⌋_{r}^{(l)}z^{n} = ∑_{n=1}^{∞} \left⌊{n \atop k − 1}\right⌋_{r}^{(l)}z^{n+1} = z (F_{k−1}^{l,r}(z) − \left⌊{0 \atop k − 1}\right⌋_{r}^{(l)})

= z \begin{cases}F_{k−1}^{l,r}(z), & if k ≥ 2; \\ F_{k−1}^{l,r}(z) − 1, & if k = 1, \end{cases} = \begin{cases}zF_{k−1}^{l,r}(z), & if k ≥ 2; \\ zF_{k−1}^{l,r}(z) − z, & if k = 1, \end{cases}

and the first term on the right-hand side of (27) as

∑_{n=2}^{∞}(n + k − 1)^{l}\left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}z^{n} = ∑_{n=2}^{∞} ∑_{j=0}^{l} \binom{l}{j}n^{j}(k − 1)^{l−j}\left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}z^{n}

= ∑_{j=0}^{l} \binom{l}{j}(k − 1)^{l−j} ∑_{n=2}^{∞} \left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}n^{j}z^{n}

= ∑_{j=0}^{l} \binom{l}{j}(k − 1)^{l−j} ∑_{n=2}^{∞} \left⌊{n − 1 \atop k}\right⌋_{r}^{(l)} ∑_{i=0}^{j} \left\{{j \atop i}\right\}n\underline{i} z^{n}

= ∑_{j=0}^{l} \binom{l}{j}(k − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\} ∑_{n=1}^{∞} \left⌊{n \atop k}\right⌋_{r}^{(l)}(n + 1)\underline{i} z^{n+1}

= ∑_{j=0}^{l} \binom{l}{j}(k − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\} ∑_{n=1}^{∞} \left⌊{n \atop k}\right⌋_{r}^{(l)}z^{i} \frac{d^{i}}{dz^{i}} z^{n+1}

= ∑_{j=0}^{l} \binom{l}{j}(k − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\}z^{i} \frac{d^{i}}{dz^{i}} (z ∑_{n=1}^{∞} \left⌊{n \atop k}\right⌋_{r}^{(l)}z^{n})

= ∑_{j=0}^{l} \binom{l}{j}(k − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\}z^{i} \frac{d^{i}}{dz^{i}} (zF_{k}^{l,r}(z)) .

Putting the three rewritten terms of equation (27) together again, we obtain

\begin{cases}F_{k}^{l,r}(z), & if k ≥ 2; \\ F_{k}^{l,r}(z) − z, & if k = 1, \end{cases} = \begin{cases}zF_{k−1}^{l,r}(z), & if k ≥ 2; \\ zF_{k−1}^{l,r}(z) − z, & if k = 1, \end{cases}

+ ∑_{j=0}^{l} \binom{l}{j}(k − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\}z^{i} \frac{d^{i}}{dz^{i}} (zF_{k}^{l,r}(z)) ,

which is equivalent to equation (26). Theorem 8. For n − 1 ≥ r ≥ 1 and l ≥ 1, the row generating function

P_{n}^{l,r}(x) = ∑_{k=0}^{n} \left⌊{n \atop k}\right⌋_{r}^{(l)}x^{k}  (28)

of (l, r)-Lah numbers, which is a polynomial in x of degree n, satisfies the difference-differential equation

P_{n}^{l,r}(x) = x P_{n−1}^{l,r}(x) + ∑_{j=0}^{l} \binom{l}{j}(n − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\}x^{i} \frac{d^{i}}{dx^{i}} (P_{n−1}^{l,r}(x)) .  (29)

Proof. Multiplying recurrence (21) by x^{k} and summing it on k from 2 to n yields

∑_{k=2}^{n} \left⌊{n \atop k}\right⌋_{r}^{(l)}x^{k} = ∑_{k=2}^{n}(n + k − 1)^{l}\left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}x^{k} + ∑_{k=2}^{n} \left⌊{n − 1 \atop k − 1}\right⌋_{r}^{(l)}x^{k}.  (30)

Rewrite the left-hand side of (30) as

∑_{k=2}^{n} \left⌊{n \atop k}\right⌋_{r}^{(l)}x^{k} = P_{n}^{l,r}(x) − \left⌊{n \atop 0}\right⌋_{r}^{(l)} − \left⌊{n \atop 1}\right⌋_{r}^{(l)}x.

Rewrite the second term on the right-hand side of (30) as

∑_{k=2}^{n} \left⌊{n − 1 \atop k − 1}\right⌋_{r}^{(l)}x^{k} = ∑_{k=1}^{n−1} \left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}x^{k+1} = x (P_{n−1}^{l,r}(x) − \left⌊{n − 1 \atop 0}\right⌋_{r}^{(l)})

and the first term on the right-hand side of (30) as

∑_{k=2}^{n}(n + k − 1)^{l}\left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}x^{k} = ∑_{k=2}^{n} ∑_{j=0}^{l} \binom{l}{j}k^{j}(n − 1)^{l−j}\left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}x^{k}

= ∑_{j=0}^{l} \binom{l}{j}(n − 1)^{l−j} ∑_{k=2}^{n} \left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}k^{j}x^{k}

= ∑_{j=0}^{l} \binom{l}{j}(n − 1)^{l−j} ∑_{k=2}^{n} \left⌊{n − 1 \atop k}\right⌋_{r}^{(l)} ∑_{i=0}^{j} \left\{{j \atop i}\right\}k\underline{i} x^{k}

= ∑_{j=0}^{l} \binom{l}{j}(n − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\} ∑_{k=2}^{n} \left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}k\underline{i} x^{k}

= ∑_{j=0}^{l} \binom{l}{j}(n − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\} ∑_{k=2}^{n} \left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}x^{i} \frac{d^{i}}{dx^{i}} x^{k}

= ∑_{j=0}^{l} \binom{l}{j}(n − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\}x^{i} \frac{d^{i}}{dx^{i}} (∑_{k=2}^{n} \left⌊{n − 1 \atop k}\right⌋_{r}^{(l)}x^{k})

= ∑_{j=0}^{l} \binom{l}{j}(n − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\}x^{i} \frac{d^{i}}{dx^{i}} (P_{n−1}^{l,r}(x) − \left⌊{n − 1 \atop 0}\right⌋_{r}^{(l)} − \left⌊{n − 1 \atop 1}\right⌋_{r}^{(l)}x) .

Putting the three rewritten terms of equation (30) together again, and checking that

\left⌊{n \atop 0}\right⌋_{r}^{(l)} + \left⌊{n \atop 1}\right⌋_{r}^{(l)} = \left⌊{n − 1 \atop 0}\right⌋_{r}^{(l)}x

+ ∑_{j=0}^{l} \binom{l}{j}(n − 1)^{l−j} ∑_{i=0}^{j} \left\{{j \atop i}\right\}x^{i} \frac{d^{i}}{dx^{i}} (\left⌊{n − 1 \atop 0}\right⌋_{r}^{(l)} + \left⌊{n − 1 \atop 1}\right⌋_{r}^{(l)}x)

for all n − 1 ≥ r ≥ 1 and l ≥ 1, we obtain equation (29).

5 Conclusion

We conclude the paper with two conjectures, based on experimental evidence. Conjecture 9. For n ≥ k ≥ r ≥ 1, the sequence (\left⌊{n \atop k}\right⌋_{r}^{(l)})_{k=0}^{n} is strictly log-concave. Conjecture 10. All the roots of polynomials P_{n}^{l,r}(x), defined in (28), are real and nonpositive.

6 Acknowledgments

The author thanks his parents for supporting him, Marko Petkovšek for his advice, support and review of the article, and an anonymous referee for advice that improved this article.

References

[1] H. Belbachir and A. Belkhir, Cross recurrence relations for r-Lah numbers, Ars Combin. 110 (2013), 199–203.

[2] H. Belbachir and I. E. Bousbaa, Combinatorial identities for the r-Lah numbers, Ars Combin. 115 (2014), 452–458.

[3] H. Belbachir and Y. Djemmada, The (l, r)-Stirling numbers: a combinatorial approach, arxiv preprint, arXiv:2101.11039 [math.NT], 2021. Available at

http://arxiv.org/abs/2101.11039.

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

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

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

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

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

[9] D. S. Kim, T. Kim, Central factorial numbers associated with sequences of polynomials, arxiv preprint, arXiv:2202.13130 [math.NT], 2022. Available at

https://arxiv.org/abs/2202.13130.

[10] I. Lah, A new kind of numbers and its application in the actuarial mathematics, Boletim do Instituto dos Atuários Portugueses 9 (1954), 7–15.

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

[12] G. Nyul and G. Rácz, Matchings in complete bipartite graphs and the r-Lah numbers, Czechoslovak Math. J. 71 (2021), 947–959.

[13] M. Petkovšek and T. Pisanski, Combinatorial interpretation of unsigned Stirling and Lah numbers, Pi Mu Epsilon J. 12 (2007), 417–424.

[14] J. Riordan, An Introduction to Combinatorial Analysis, John Wiley & Sons, Inc.; Chapman & Hall, Ltd., 1958.

[15] M. Shattuck, Generalized r-Lah numbers, arxiv preprint, arXiv:1412.8721 [math.NT],

2014. Available at http://arxiv.org/abs/1412.8721.

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

2020 Mathematics Subject Classification: Primary 05A19. Secondary 05A18, 11B37, 11B73.

Keywords: Lah numbers, Stirling number of the first and second kind, r-Lah number, r-Stirling number of the first and second kind, (l, r)-Lah number, (l, r)-Stirling number of the first and second kind, recurrence relation, explicit representation, generating function, (l, r)-Lah polynomial.

(Concerned with sequences \underline{A008277}, \underline{A008297}, \underline{A132393}, \underline{A143497}, \underline{A143498}, and \underline{A143499}.)

Received June 27 2022; revised version received January 25 2023. Published in Journal of Integer Sequences, February 25 2023.

Return to Journal of Integer Sequences home page.