The Multivariate Lah and Stirling Numbers

Amine Belkhir Faculty of Mathematics USTHB BP 32, El Alia 16111 Bab Ezzouar Algiers Algeria

                      ambelkhir@gmail.com

Abstract An ordered partition of {1, 2, …, n} into k blocks B_{1}, B_{2}, …, B_{k} is a partition where the order of blocks is considered. In the present paper, we we consider the case that each block B_{i} has r_{i} copies. Using this extension of ordered set partitions, we introduce a new generalization of the Lah and Stirling numbers of both kinds which called multivariate Lah and Stirling numbers, respectively. We study several combinatorial properties such as explicit formulas, recurrence relations, generating functions, and some convolution identities.

1 Introduction

Let [n] = {1, …, n}. A partition π of [n] is a family of nonempty, pairwise disjoint subsets called blocks. A partition of [n] into k blocks is denoted B_{1}/B_{2}/ ⋯ /B_{k} such that min(B_{1}) < min(B_{2}) < ⋯ < min(B_{k}).

For any n ≥ k ≥ 0, let \left\{{n \atop k}\right\}, \left[{n \atop k}\right] and \left⌊{n \atop k}\right⌋ be the Stirling numbers of the second kind, first kind and Lah numbers, respectively. The numbers \left\{{n \atop k}\right\} count the number of set partitions of [n] into k blocks, \left[{n \atop k}\right] count the number of partitions of [n] into k cycles. Similarly, the Lah numbers \left⌊{n \atop k}\right⌋ count the number of partitions of set [n] into k nonempty lists.

The falling and rising factorials are defined, respectively by

(x)_{n} = x(x + 1)(x + 2) ⋯ (x + n − 1), (x)_{0} = 1,

and

⟨x⟩_{n} = x(x − 1)(x − 2) ⋯ (x − n + 1), ⟨x⟩_{0} = 1.

The Stirling numbers of second kind appear in the expansion x^{n} = ∑_{k} \left\{{n \atop k}\right\}⟨x⟩_{k}, and the Stirling numbers of first kind appear in the expansion (x)_{n} = ∑_{k} \left[{n \atop k}\right]x^{k}. The Lah numbers are connection coefficients between rising and falling factorials (x)_{n} = ∑_{k} \left⌊{n \atop k}\right⌋⟨x⟩_{k}.

The Lah numbers can be expressed in terms of Stirling numbers of second and first kinds [6, p. 156], as follows:

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

The Lah numbers have the following explicit formula [6, p. 134]:

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

An ordered partition π of [n] into k blocks is a partition where the order of blocks is important π_{σ} = B_{σ(1)}/B_{σ(2)}/ ⋯ /B_{σ(k)}, where σ is a permutation of [k]. The number of ordered set partitions of [n] into k blocks is given by k!\left\{{n \atop k}\right\}, [9, p. 106], as follows:

k!\left\{{n \atop k}\right\} = ∑_{r_{1}+r_{2}+···+r_{k}=n_{r_{i}≥1}} \binom{n}{r_{1}, r_{2}, …, r_{k}},  (1)

where \binom{n}{r_{1},r_{2},...,r_{k}} = \frac{n!}{r_{1}!r_{2}!···r_{k}!} is the multinomial coefficient. The coefficients \binom{n}{r_{1},r_{2},...,r_{k}} have the following horizontal generating function

(x_{1} + x_{2} + ⋯ + x_{k})^{n} = ∑_{r_{1}+r_{2}+···+r_{k}=n} \binom{n}{r_{1}, r_{2}, …, r_{k}}x_{1}^{r_{1}}x_{2}^{r_{2}} ⋯ x_{k}^{r_{k}}.  (2)

The relation (2) can be generalized to multivariate falling and rising factorials [7, p. 149]:

⟨x_{1} + x_{2} + ⋯ + x_{k}⟩_{n} = ∑_{r_{1}+r_{2}+···+r_{k}=n} \binom{n}{r_{1}, r_{2}, …, r_{k}}⟨x_{1}⟩_{r_{1}}⟨x_{2}⟩_{r_{2}} ⋯ ⟨x_{k}⟩_{r_{k}},  (3)

and

(x_{1} + x_{2} + ⋯ + x_{k})_{n} = ∑_{r_{1}+r_{2}+···+r_{k}=n} \binom{n}{r_{1}, r_{2}, …, r_{k}}(x_{1})_{r_{1}}(x_{2})_{r_{2}} ⋯ (x_{k})_{r_{k}}.  (4)

Many authors have investigated the Stirling and Lah numbers; see, for instance, [1, 2, 4, 8, 12].

The present paper is organized as follows: Section 2 introduces the multivariate Lah numbers multipartitions set which generalize the set partitions and ordered set partitions. Section 3 presents several properties of the multivariate Lah numbers by algebraic and combinatorial arguments. In the last section, we define the multivariate Stirling numbers of the first and second kinds and we provide an expression for the multivariate Lah numbers in terms of the multivariate Stirling numbers and multinomial Stirling numbers were introduced by Moak [10].

2 Combinatorial definition of multivariate Lah numbers

Let r_{k} := (r_{1}, r_{2}, …, r_{k}) be a sequence of nonnegative integers. Now suppose that we have k categories of lists (C_{1}, C_{2}, …, C_{k}) such that |C_{i}| = r_{i}. Let OP_{n}^{r_{k}} be the set partitions of [n] into (r_{1} + r_{2} + ⋯ + r_{k})-lists. A partition π ∈ OP_{n}^{r_{k}} is of the form π = B_{1}^{r_{1}}/B_{2}^{r_{2}}/ ⋯ /B_{k}^{r_{k}}

where B_{i}^{r_{i}} = \underbrace{B_{i}/B_{i}/ ⋯ /B_{i}}_{r_{i} times}.

Definition 1. Let π = B_{1}^{r_{1}}/B_{2}^{r_{2}}/ ⋯ /B_{k}^{r_{k}} be a partition of the set OP_{n}^{r_{k}}. A multipartition is a permutation of the multiset {B_{1}^{r_{1}}, B_{2}^{r_{2}}, …, B_{k}^{r_{k}}}. We let 𝔖_{n,r_{k}}(π) denote the set of all multipartitions of the multiset {B_{1}^{r_{1}}, B_{2}^{r_{2}}, …, B_{k}^{r_{k}}}.

Example 2. Let π = \underline{1, 2}_{B_{1}}/ \underline{3}_{B_{1}},/\underline{4, 5}_{B_{2}}/ \underline{6}_{B_{3}}, be a partition of the set [6] into (2, 1, 1)-lists. The set

𝔖_{6,r_{3}}(π) of multipartitions associated with the partition π is

\underline{1, 2}_{B_{1}}/ \underline{3}_{B_{1}},/\underline{4, 5}_{B_{2}}/ \underline{6}_{B_{3}}, \underline{1, 2}_{B_{1}}/\underline{4, 5}_{B_{2}}/ \underline{3}_{B_{1}}/ \underline{6}_{B_{3}}; \underline{1, 2}_{B_{1}}/\underline{4, 5}_{B_{2}}/ \underline{6}_{B_{3}}/ \underline{3}_{B_{1}};

\underline{4, 5}_{B_{2}}/\underline{1, 2}_{B_{1}}/ \underline{6}_{B_{3}}/ \underline{3}_{B_{1}}; \underline{4, 5}_{B_{2}}/ \underline{6}_{B_{3}}/\underline{1, 2}_{B_{1}}/ \underline{3}_{B_{1}}; \underline{4, 5}_{B_{2}}/\underline{1, 2}_{B_{1}}/ \underline{3}_{B_{1}}/ \underline{6}_{B_{3}}.

Definition 3. For any n, r_{1}, r_{2}, …, r_{k} ≥ 1, the multivariate Lah number, which we denote by \left⌊{n \atop r_{1},r_{2},...,r_{k}}\right⌋, is the number of multipartitions of the set [n] into nonempty r_{k}-lists.

\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = ∑_{π∈OP_{n}^{r_{k}}} |𝔖_{n,r_{k}}(π)|.  (5)

Example 4. There are 3 multipartitions of the set [3] into (1, 2)-lists

1/2/3 ; 2/1/3 ; 2/3/1.

We have \left⌊{3 \atop 1,1}\right⌋ = 12, so the corresponding multipartitions are

1/2, 3 ; 2, 3/1 ; 1/3, 2 ; 3, 2/1 ; 1, 2/3 ; 3/1, 2 ;
2, 1/3 ; 3/2, 1 ; 1, 3/2 ; 2/1, 3 ; 3, 1/2 ; 2/3, 1.

In the following theorem we provide an explicit formula for the multivariate Lah numbers.

Theorem 5. For any n, r_{1}, r_{2}, …, r_{k} ≥ 1, we have

\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = \frac{(n − 1)!}{(r_{1} + r_{2} + ⋯ + r_{k} − 1)!}\binom{n}{r_{1}, r_{2}, …, r_{k}, n − ∑_{j=1}^{k} r_{j}}.  (6)

Proof. To construct a multipartition of [n] into r_{k}-lists we can do the following. First, we select r_{1} elements from [n], each element corresponding to the beginning of one list of category C_{1}. There are \binom{n}{r_{1}} possibilities. Then, we choose r_{2} elements from the remaining n − r_{1} elements, which we place at the beginning of the lists of category C_{2} with \binom{n−r_{1}}{r_{2}} possible ways, and so on. We choose r_{k} of the remaining n − r_{1} − ⋯ − r_{k−1} elements, which we place at the start of the lists of category C_{k}. There are \binom{n−r_{1}−···−r_{k−1}}{r_{k}} possibilities. The remaining n−r_{1}−⋯−r_{k} elements can be added with (r_{1}+⋯+r_{k})(r_{1}+⋯+r_{k}+1) ⋯ (n−1) possibilities. This gives us,

\binom{n}{r_{1}}\binom{n − r_{1}}{r_{2}} ⋯ \binom{n − r_{1} − ⋯ − r_{k−1}}{r_{k}} ∏_{i=0}^{n−1−r_{1}−···−r_{k})}(n − 1 − i)

= \frac{(n − 1)!}{(r_{1} + r_{2} + ⋯ + r_{k} − 1)!}\binom{n}{r_{1}, r_{2}, …, r_{k}, n − ∑_{j=1}^{k} r_{j}},

which completes the proof.

As particular cases of the multivariate Lah numbers, when k = 1 we obtain the classical Lah numbers and for r_{1} + r_{2} + ⋯ + r_{k} = n we get the multinomial coefficient

\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = \binom{n}{r_{1}, r_{2}, …, r_{k}}.

Also, when r_{i} = 1 for all i ∈ [k] we obtain the ordered Lah numbers,

\left⌊{n \atop \underbrace{1, 1, …, 1}_{k−times}}\right⌋ = n!\binom{n − 1}{k − 1}.

Let σ(1), σ(2), …, σ(k) be a permutation of [k]. Then

\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = \left⌊{n \atop r_{σ(1)}, r_{σ(2)}, …, r_{σ(k)}}\right⌋.

From Relation (6), we deduce an expression for the multivariate Lah numbers in terms of classical Lah numbers.

Corollary 6. For any n, r_{1}, …, r_{k} ≥ 1, we have

\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = \binom{r_{1} + r_{2} + ⋯ + r_{k}}{r_{1}, r_{2}, …, r_{k}}\left⌊{n \atop r_{1} + r_{2} + ⋯ + r_{k}}\right⌋.  (7)

3 Fundamental properties of multivariate Lah numbers

In this section, we provide some fundamental properties of the multivariate Lah numbers. We start by given the exponential generating function.

Theorem 7. The exponential generating function of the multivariate Lah numbers is

∑_{n≥0} \left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ \frac{t^{n}}{n!} = ∏_{i=1}^{k} \frac{1}{r_{i}!} (\frac{t}{1 − t})^{r_{i}} .  (8)

Proof. From Theorem 5 and relation (7), we have

∑_{n≥0} \left⌊{n \atop r_{1}, …, r_{k}}\right⌋ \frac{t^{n}}{n!} = ∑_{n≥0} \frac{(n − 1)!}{(r_{1} + ⋯ + r_{k} − 1)!}\binom{n}{r_{1}, …, r_{k}, n − ∑_{j=1}^{k} r_{j}} \frac{t^{n}}{n!}

= \frac{1}{r_{1}! ⋯ r_{k}!} ∑_{n≥0} \binom{n − 1}{r_{1} + r_{2} + ⋯ + r_{k} − 1}t^{n}

= \frac{t^{r_{1}+r_{2}+···+r_{k}}}{r_{1}! ⋯ r_{k}!} ∑_{n≥0} \binom{n − 1}{n − r_{1} − r_{2} − ⋯ − r_{k}}t^{n}

= \frac{t^{r_{1}+r_{2}+···+r_{k}}}{r_{1}! ⋯ r_{k}!} ∑_{n≥0} \binom{n + r_{1} + r_{2} + ⋯ + r_{k} − 1}{n}t^{n}

= \frac{t^{r_{1}+r_{2}+···+r_{k}}}{r_{1}! ⋯ r_{k}!} ∑_{n≥0} \binom{−r_{1} − r_{2} − ⋯ − r_{k}}{n}(−t)^{n}

= \frac{1}{r_{1}! ⋯ r_{k}!} ∏_{i=1}^{k} (\frac{t}{1 − t})^{r_{i}} ,

which completes the proof.

In the following theorem, we give the multivariate exponential generating function for the multivariate Lah numbers.

Theorem 8. We have

∑_{n≥0} ∑_{r_{1}≥0} ∑_{r_{2}≥0} ⋯ ∑_{r_{k}≥0} \left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ \frac{t^{n}}{n!}z_{1}^{r_{1}}z_{2}^{r_{2}} ⋯ z_{k}^{r_{k}} = exp (\frac{t}{1 − t}(z_{1} + z_{2} + ⋯ + z_{k})) . (9)

Proof. The result follows immediately from Theorem (7).

An expression for the multivariate falling factorial in terms of the classical rising factorial is given by the following theorem.

Theorem 9. For any n ≥ 1, we have

(x_{1} + x_{2} + ⋯ + x_{k})_{n} = ∑_{r_{1}+r_{2}+···+r_{k}≤n} \left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋⟨x_{1}⟩_{r_{1}}⟨x_{2}⟩_{r_{2}} ⋯ ⟨x_{k}⟩_{r_{k}},  (10)

and

⟨x_{1} +x_{2} +⋯+x_{k}⟩_{n} = ∑_{r_{1}+r_{2}+···+r_{k}≤n}(−1)^{n−r_{1}−···−r_{k}} \left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋(x_{1})_{r_{1}}(x_{2})_{r_{2}} ⋯ (x_{k})_{r_{k}}. (11)

Proof. We have

(1 + \frac{t}{1 − t})^{x_{1}+x_{2}+···+x_{k}} = (1 + \frac{t}{1 − t})^{x_{1}} (1 + \frac{t}{1 − t})^{x_{2}} ⋯ (1 + \frac{t}{1 − t})^{x_{k}}

= (∑_{r_{1}≥0} (\frac{t}{1 − t})^{r_{1}} \frac{⟨x_{1}⟩_{r_{1}}}{r_{1}!} ) (∑_{r_{2}≥0} (\frac{t}{1 − t})^{r_{2}} \frac{⟨x_{2}⟩_{r_{2}}}{r_{2}!} )

× ⋯ × (∑_{r_{k}≥0} (\frac{t}{1 − t})^{r_{k}} \frac{⟨r_{k}⟩_{r_{k}}}{r_{k}!} )

= ∑_{r_{1},r_{2},...,r_{k}≥0} ∏_{i=1}^{k} \frac{1}{r_{i}!} (\frac{t}{1 − t})^{r_{i}} ⟨x_{1}⟩_{r_{1}}⟨x_{2}⟩_{r_{2}} ⋯ ⟨x_{k}⟩_{r_{k}}

= ∑_{r_{1},r_{2},...,r_{k}} (∑_{n≥0} \left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ \frac{t^{n}}{n!}) ⟨x_{1}⟩_{r_{1}}⟨x_{2}⟩_{r_{2}} ⋯ ⟨x_{k}⟩_{r_{k}}

= ∑_{n≥0} ∑_{r_{1},r_{2},...,r_{k}} \left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋⟨x_{1}⟩_{r_{1}}⟨x_{2}⟩_{r_{2}} ⋯ ⟨x_{k}⟩_{r_{k}} \frac{t^{n}}{n!}.  (12)

The left hand side of the first equality is

(1 + \frac{t}{1 − t})^{x_{1}+x_{2}+···+x_{k}} = (1 − t)^{−(x_{1}+x_{2}+···+x_{k})}

= ∑_{n≥0}(−1)^{n}\binom{−x_{1} − x_{2} − ⋯ − x_{k}}{n}t^{n}

= ∑_{n≥0} \binom{x_{1} + x_{2} + ⋯ + x_{k} + n − 1}{n}t^{n}

= ∑_{n≥0}(x_{1} + x_{2} + ⋯ + x_{k})_{n} \frac{t^{n}}{n!}.  (13)

Equating the coefficients of \frac{t^{n}}{n!} in (12) and (13) yields (10). Equation (11) follows by substituting (−x_{i}) for i ∈ [k].

Using Theorem 9, we get, for example

(x_{1} + x_{2})_{2} = ⟨x_{1}⟩_{2} + 2x_{1}x_{2} + ⟨x_{2}⟩_{2} + 2(x_{1} + x_{2}),
(x_{1} + x_{2})_{3} = ⟨x_{1}⟩_{3} + 3⟨x_{1}⟩_{2}x_{2} + 3x_{1}⟨x_{2}⟩_{2} + ⟨x_{2}⟩_{3} + 6(⟨x_{1}⟩_{2} + 2x_{1}x_{2} + ⟨x_{2}⟩_{2})
+ 6(x_{1} + x_{2}),
(x_{1} + x_{2} + x_{3})_{2} = ⟨x_{1}⟩_{2} + ⟨x_{2}⟩_{2} + ⟨x_{3}⟩_{2} + 2(x_{1}x_{2} + x_{1}x_{3} + x_{2}x_{3}) + 2(x_{1} + x_{2} + x_{3}).
⟨x_{1} + x_{2}⟩_{2} = 3(x_{1})_{2} − 6x_{1} − 6x_{2} + 6x_{1}x_{2} + 3(x_{2})_{2}.

Theorem 10. For any n, r_{1}, r_{2}, …, r_{k} ≥ 1, we have

∑_{s_{1}+s_{2}+...+s_{k}≤n}(−1)^{∑_{i} s_{i}−r_{i}} \left⌊{n \atop s_{1}, s_{2}, …, s_{k}}\right⌋\left⌊{s_{1} \atop r_{1}}\right⌋\left⌊{s_{2} \atop r_{2}}\right⌋ ⋯ \left⌊{s_{k} \atop r_{k}}\right⌋ = \binom{n}{r_{1}, r_{2}, …, r_{k}}.  (14)

Proof. From Relation (10), we have

(x_{1} + x_{2} + ⋯ + x_{k})_{n} = ∑_{s_{1}+s_{2}+···+s_{k}≤n} \left⌊{n \atop s_{1}, s_{2}, …, s_{k}}\right⌋⟨x_{1}⟩_{s_{1}}⟨x_{2}⟩_{s_{2}} ⋯ ⟨x_{k}⟩_{s_{k}}

= ∑_{s_{1}+s_{2}+···+s_{k}≤n} \left⌊{n \atop s_{1}, s_{2}, …, s_{k}}\right⌋ ∑_{r_{1},r_{2},...,r_{k}}(−1)^{∑_{i} s_{i}−r_{i}} \left⌊{s_{1} \atop r_{1}}\right⌋\left⌊{s_{2} \atop r_{2}}\right⌋ ⋯ \left⌊{s_{k} \atop r_{k}}\right⌋

× (x_{1})_{r_{1}}(x_{2})_{r_{2}} ⋯ (x_{k})_{r_{k}}.

On other hand, we have

(x_{1} + x_{2} + ⋯ + x_{k})_{n} = ∑_{r_{1}+···+r_{k}=n} \binom{n}{r_{1}, r_{2}, …, r_{k}}(x)_{r_{1}}(x)_{r_{2}} ⋯ (x)_{r_{k}}.  (15)

Equating the coefficients of (x)_{r_{1}}(x)_{r_{2}} ⋯ (x)_{r_{k}} we obtain the result. Corollary 11. The following identity holds

(x_{1})_{r_{1}}(x_{2})_{r_{2}} ⋯ (x_{k})_{r_{k}} = ∑_{s_{1},s_{2},...,s_{k}} \left⌊{r_{1} \atop s_{1}}\right⌋\left⌊{r_{2} \atop s_{2}}\right⌋ ⋯ \left⌊{r_{k} \atop s_{k}}\right⌋⟨x_{1}⟩_{s_{1}}⟨x_{2}⟩_{s_{2}} ⋯ ⟨x_{k}⟩_{s_{k}}.  (16)

In the next theorem, we give a convolution identity involving the multivariate Lah numbers. Theorem 12. We have

∏_{i=1}^{k} \binom{r_{i} + s_{i}}{r_{i}}\left⌊{n \atop r_{1} + s_{1}, r_{2} + s_{2}, …, r_{k} + s_{k}}\right⌋ = ∑_{j=1}^{n} \binom{n}{j}\left⌊{j \atop r_{1}, r_{2}, …, r_{k}}\right⌋\left⌊{n − j \atop s_{1}, s_{2}, …, s_{k}}\right⌋. (17)

Proof. From Theorem 7, we have

∑_{n≥0} ∏_{i=1}^{k} \binom{r_{i} + s_{i}}{r_{i}}\left⌊{n \atop r_{1} + s_{1}, …, r_{k} + s_{k}}\right⌋ \frac{t^{n}}{n!} = ∏_{i=1}^{k} \binom{r_{i} + s_{i}}{r_{i}} \frac{1}{(r_{i} + s_{i})!} (\frac{t}{1 − t})^{(r_{i}+s_{i})}

= (∏_{i=1}^{k} \frac{1}{(r_{i})!} (\frac{t}{1 − t})^{r_{i}}) (∏_{j=1}^{k} \frac{1}{(s_{j})!} (\frac{t}{1 − t})^{s_{j}})

= (∑_{l≥0} \left⌊{l \atop r_{1}, r_{2}, …, r_{k}}\right⌋ \frac{t^{l}}{l!})

× (∑_{m≥0} \left⌊{m \atop s_{1}, s_{2}, …, s_{k}}\right⌋ \frac{t^{m}}{m!}) .

Equating the coefficients of \frac{t^{n}}{n!} in both sides, we get the desired result.

Combinatorial proof of Theorem 12. Let C = {1, 2, …, k} be a list of k different colors. The left hand side of the identity counts the number of multipartitions of the set [n] into (r_{1} + s_{1}, …, r_{k} + s_{k})-lists such that the elements of r_{i} lists among r_{i} + s_{i} lists get colour i, for all i ∈ [k]. In the right hand side, we start by choosing j elements from n and there are \binom{n}{j} ways to do. The j elements have to be partitioned into (r_{1}, …, r_{k})-lists such that the elements of the lists r_{i} get colour i and the remaining n − j elements have to be partitioned into (s_{1}, …, s_{k})-lists.

In the following theorem we give a generalization of the formula (17).

Theorem 13. We have

∏_{i=1}^{k} \binom{r_{i}}{r_{1,i}, …, r_{t,i}}\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = ∑_{j_{1},...,j_{t}} \binom{n}{j_{1}, …, j_{t}} ∏_{i=1}^{t} \left⌊{j_{i} \atop r_{1,i}, r_{2,i}, …, r_{t,i}}\right⌋.  (18)

with r_{1,i} + r_{2,i} + ⋯ + r_{t,i} = r_{i} for i ∈ [t].

Now we give some recurrence relations satisfied by the multivariate Lah numbers.

Theorem 14. The multivariate Lah numbers satisfy the following recurrence relations (i) Triangular recurrence relation:

\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = ∑_{i=1}^{k} \left⌊{n − 1 \atop r_{1}, …, r_{i} − 1, …, r_{k}}\right⌋

+ (n + r_{1} + ⋯ + r_{k} − 1)\left⌊{n − 1 \atop r_{1}, r_{2}, …, r_{k}}\right⌋,  (19)

with initial terms \left⌊{n \atop r_{1},r_{2},...,r_{k}}\right⌋ = 0 if n < r_{1} + r_{2} + ⋯ + r_{k}.

(ii) Horizontal recurrence relation:

\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = ∑_{r_{1}+···+r_{k}≤j≤n}(r_{1} + ⋯ + r_{k} + j)_{n−j} ∑_{i=1}^{k} \left⌊{j − 1 \atop r_{1}, …, r_{i} − 1, …, r_{k}}\right⌋.  (20)

(iii) Diagonal recurrence relation:

\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = ∑_{j=0}^{r_{1}+···+r_{k}} ∑_{s_{1}+···+s_{k}=j} \binom{j}{s_{1}, …, s_{k}}

× (n + r_{1} + ⋯ + r_{k} − 2j − 1)\left⌊{n − j − 1 \atop r_{1} − s_{1}, …, r_{k} − s_{k}}\right⌋. (21)

Proof. Let us show (19). A multipartition of the set [n] into (r_{1}, r_{2}, …, r_{k})-lists can be obtained from a multipartition of the set [n − 1] into (r_{1}, ⋯, r_{i} − 1, ⋯, r_{k})-lists (1 ≤ i ≤ k) to which we add a single list {n} of category C_{i}, or from a multipartition of the set [n − 1] into (r_{1}, r_{2}, …, r_{k})-lists, by adding the element {n} before any existing elements or at the end of any list. Then there are (n + r_{1} + ⋯ + r_{k} − 1)\left⌊{n−1 \atop r_{1},r_{2},...,r_{k}}\right⌋ ways.

Next, we show (20). For a given r_{1} + ⋯ + r_{k} ≤ j ≤ n and 1 ≤ i ≤ k, let us consider the elements of [j − 1] which are not in the same list with the element {n}. The number of multipartitions of [j − 1] into (r_{1}, …, r_{i} − 1, …, r_{k})-lists is \left⌊{j−1 \atop r_{1},...,r_{i}−1,...,r_{k}}\right⌋, and there are (r_{1} +⋯+r_{k} +j)_{n−j} ways to add the remaining elements of [j, n−1] into (r_{1}, r_{2}, …, r_{k})-lists. Summing over all possible j and i gives the result.

Finally, we show (21). Let j (0 ≤ j ≤ r_{1} + ⋯ + r_{k}) be the number of lists which contain exactly one element, then the number of ways to choose a such lists is \binom{j}{s_{1},...,s_{k}}. Now it remains to count the number of multipartitions of [j + 1, n] into (r_{1} − s_{1}, …, r_{k} − s_{k})-lists. So, the number of multipartitions of [j+1, n−1] into (r_{1}−s_{1}, …, r_{k}−s_{k})-lists is \left⌊{n−j−1 \atop r_{1}−s_{1},...,r_{k}−s_{k}}\right⌋ and there are (n + r_{1} + ⋯ + r_{k} − 2j − 1) ways to add the element {n} in any list. Summing up yields the desired result.

4 Multivariate Stirling numbers

Definition 15. For any n, r_{1}, r_{2}, …, r_{k} ≥ 0, the multivariate Stirling numbers of the first kind, denoted \left[{n \atop r_{1},r_{2},...,r_{k}}\right], are defined as the numbers of multipartitions of the set [n] into (r_{1}, r_{2}, …, r_{k})-cycles. Analogously, we define the multivariate Stirling numbers of second kind, denoted \left\{{n \atop r_{1},r_{2},...,r_{k}}\right\}, as the numbers of multipartitions of [n] into (r_{1}, r_{2}, …, r_{k})-blocks.

From Definition 15, we deduce that the multivariate Stirling numbers of the first kind satisfy the following recurrence relation

\left[{n \atop r_{1}, r_{2}, …, r_{k}}\right] = ∑_{i=1}^{k} \left[{n − 1 \atop r_{1}, …, r_{i} − 1, …, r_{k}}\right] + (n − 1)\left[{n − 1 \atop r_{1}, r_{2}, …, r_{k}}\right],  (22)

with \left[{n \atop r_{1},r_{2},...,r_{k}}\right] = 0 if n < r_{1} + r_{2} + ⋯ + r_{k}. The multivariate Stirling numbers of the second kind satisfy the following recurrence relation

\left\{{n \atop r_{1}, r_{2}, …, r_{k}}\right\} = ∑_{i=1}^{k} \left\{{n − 1 \atop r_{1}, …, r_{i} − 1, …, r_{k}}\right\} + (r_{1} + r_{2} + ⋯ + r_{k})\left\{{n − 1 \atop r_{1}, r_{2}, …, r_{k}}\right\}. (23)

with \left\{{n \atop r_{1},r_{2},...,r_{k}}\right\} = 0 if n < r_{1} + r_{2} + ⋯ + r_{k}.

As particular cases, we have

\left[{n \atop \underbrace{1, 1, …, 1}_{k−times}}\right] = k!\left[{n \atop k}\right], for n ≥ k,

\left\{{n \atop \underbrace{1, 1, …, 1}_{k−times}}\right\} = k!\left\{{n \atop k}\right\}, for n ≥ k,

and

\left\{{n \atop r_{1}, r_{2}, …, r_{k}}\right\} = \binom{n}{r_{1}, r_{2}, …, r_{k}}, for r_{1} + r_{2} + ⋯ + r_{k} = n.

Next, we give an explicit formula for the multivariate Stirling of the second kind.

Theorem 16. For any n ≥ 0, we have

\left\{{n \atop r_{1}, r_{2}, …, r_{k}}\right\} = \frac{1}{r_{1}!r_{2}! ⋯ r_{k}!} ∑_{j=0}^{r_{1}+···+r_{k}}(−1)^{j}\binom{r_{1} + ⋯ + r_{k}}{j}(r_{1} + ⋯ + r_{k} − j)^{n}. (24)

Proof. The result is obtained by applying the inclusion-exclusion principle.

Theorem 17. For any n ≥ 1, we have

(x_{1} + x_{2} + ⋯ + x_{k})^{n} = ∑_{r_{1}+r_{i}+···+r_{k}≤n} \left\{{n \atop r_{1}, r_{2}, …, r_{k}}\right\}⟨x_{1}⟩_{r_{1}}⟨x_{2}⟩_{r_{2}} ⋯ ⟨x_{k}⟩_{r_{k}}.  (25)

and

(x_{1} + x_{2} + ⋯ + x_{k})_{n} = ∑_{r_{1}+r_{i}+···+r_{k}≤n} \left[{n \atop r_{1}, r_{2}, …, r_{k}}\right]x_{1}^{r_{1}}x_{2}^{r_{2}} ⋯ x_{k}^{r_{k}}.  (26)

Proof. The result is obtained using induction proof.

Theorem 18. The exponential generating function of the multivariate Stirling numbers of the first and second kind

∑_{n≥0} \left[{n \atop r_{1}, r_{2}, …, r_{k}}\right] \frac{t^{n}}{n!} = ∏_{i=1}^{k} \frac{1}{r_{i}!} (ln (\frac{1}{1 − t}))^{r_{i}} ,  (27)

and

∑_{n≥0} \left\{{n \atop r_{1}, r_{2}, …, r_{k}}\right\} \frac{t^{n}}{n!} = ∏_{i=1}^{k} \frac{(e^{t} − 1)^{r_{i}}}{r_{i}!} .  (28)

From Theorem 18, we obtain

∑_{n≥0} ∑_{r_{i}≥0} \left[{n \atop r_{1}, r_{2}, …, r_{k}}\right] \frac{t^{n}}{n!}z_{1}^{r_{1}} ⋯ z_{k}^{r_{k}} = (1 − t)^{−z_{1}−···−z_{k}} ,  (29)

and

∑_{n≥0} ∑_{r_{i}≥0} \left\{{n \atop r_{1}, r_{2}, …, r_{k}}\right\} \frac{t^{n}}{n!}z_{1}^{r_{1}} ⋯ z_{k}^{r_{k}} = exp ((e^{t} − 1)(z_{1} + ⋯ + z_{k})) .  (30)

The connection relation between the multivariate Stirling numbers and classical Stirling numbers is

\left\{{n \atop r_{1}, r_{2}, …, r_{k}}\right\} = \binom{r_{1} + r_{2} + ⋯ + r_{k}}{r_{1}, r_{2}, …, r_{k}}\left\{{n \atop r_{1} + r_{2} + ⋯ + r_{k}}\right\},  (31)

and

\left[{n \atop r_{1}, r_{2}, …, r_{k}}\right] = \binom{r_{1} + r_{2} + ⋯ + r_{k}}{r_{1}, r_{2}, …, r_{k}}\left[{n \atop r_{1} + r_{2} + ⋯ + r_{k}}\right].  (32)

In the following theorem we express the multivariate Lah numbers in terms of the multivariate Stirling numbers.

Theorem 19. For any n ≥ 1, we have

\left⌊{n \atop r_{1}, r_{2}, …, r_{k}}\right⌋ = ∑_{j_{1}+···+j_{k}=r_{1}+···+r_{k}}^{n} \left[{n \atop j_{1}, j_{2}, …, j_{k}}\right]\left\{{j_{1} \atop r_{1}}\right\}\left\{{j_{2} \atop r_{2}}\right\} ⋯ \left\{{j_{k} \atop r_{k}}\right\}.  (33)

Proof. The result is obtained from (10) and (25).

5 Acknowledgments

The author would like to thank the referee and the editor for helpful comments and suggestions.

References

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

[2] H. Belbachir, A. Belkhir, and I. E. Bousbaa, Combinatorial approach of certain generalized Stirling numbers, Ars Combin., to appear.

[3] H. Belbachir and L. Szalay, Unimodal rays in the regular and generalized Pascal pyramids, Elec. J. Combin. 18 (2011), #P79.

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

[5] A. Dzhumadil’daev and D. Yeliussizov, Stirling permutations on multisets, European J. Combin. 36 (2014), 377–392.

[6] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, D. Reidel, 1974.

[7] J. M. Harris, J. L. Hirst, and M. J. Mossinghoff, Combinatorics and Graph Theory, Springer, 2008.

[8] T. Mansour and M. Shattuck, A polynomial generalization of some associated sequences related to set partitions, Period Math Hung. 75 (2017) 398–412.

[9] C. Mariconda and A. Tonolo, Discrete Calculus: Methods for Counting, Springer, 2015.

[10] D. S. Moak, Combinatorial multinomial matrices and multinomial Stirling numbers, Proc. Amer. Math. Soc. 1 (1990), 1–8.

[11] D. S. Moak, K. Heuver, K. P. S. Raob, and K. Collins, An inversion relation of multinomial type, Discrete Math. 13 (1994), 195–204.

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

[13] D. Qiu and J. Remmel, Patterns in words of ordered set partitions, J. Comb. 10 (2019), 433–490.

[14] E. Steingrímsson, Statistics on ordered partitions of sets, 2019. Available at https://

arxiv.org/abs/math/0605670.

[15] J. Zeng, Multinomial convolution polynomials, Discrete Math. 160 (1996), 219–228.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 05A19. Keywords: Lah number, Stirling number, ordered set partition, multinomial coefficient.

(Concerned with sequences \underline{A008277}, \underline{A132393}, and \underline{A271703}.)

Received October 27 2019; revised versions received March 14 2020; April 7 2020. Published in Journal of Integer Sequences, April 8 2020.

Return to Journal of Integer Sequences home page.