m-Partition Boards and Poly-Stirling Numbers

Brian K. Miceli Department of Mathematics Trinity University One Trinity Place San Antonio, TX 78212-7200 USA

                  bmiceli@trinity.edu

Abstract

We define a generalization of the Stirling numbers of the first and second kinds and develop a new rook theory model to give combinatorial interpretations to these numbers. These rook-theoretic interpretations are used to give a direct combinatorial proof that two associated matrices are inverses of each other. We also give combinatorial interpretations of the numbers in terms of certain collections of permutations and in terms of certain collections of set partitions. In addition, many other well-known identities involving Stirling numbers are generalized using this new model.

1 Introduction

Define ℕ = {1, 2, 3, …} and ℕ^{0} = ℕ∪{0}. Let ℚ[x] be the polynomial ring over the rational numbers ℚ. The Stirling numbers of the first and second kind are the connection coefficient between power basis {x^{n}}_{n≥0} and the falling factorial basis {(x) ↓_{n}}_{n≥0} where (x) ↓_{0}= 1 and (x) ↓_{n}= x(x − 1) ⋯ (x − n + 1) for n ≥ 1. That is, the Stirling numbers of the first kind s_{n,k} are defined by the equation

(x) ↓_{n}= ∑_{k=1}^{n} s_{n,k}x^{k},  (1.1)

and the Stirling numbers of the second kind S_{n,k} are defined by the equation

x^{n} = ∑_{k=1}^{n} S_{n,k}(x) ↓_{k} .  (1.2)

They are also defined by the recursions

s_{n+1,k} = s_{n,k−1} − ns_{n,k}  (1.3)

where s_{0,0} = 1 and s_{n,k} = 0 if either k < 0 or k > n, and

S_{n+1,k} = S_{n,k−1} + kS_{n,k}  (1.4)

where S_{0,0} = 1 and S_{n,k} = 0 if either k < 0 or k > n. If we let c_{n,k} = (−1)^{n−k}s_{n,k}, then the c_{n,k}’s satisfy the recursion

c_{n+1,k} = c_{n,k−1} + nc_{n,k}  (1.5)

where c_{0,0} = 1 and c_{n,k} = 0 if either k < 0 or k > n. There are several combinatorial interpretations of the S_{n,k}’s and c_{n,k}’s. For example, S_{n,k} is the number of set partitions of {1, …, n} into k nonempty parts and c_{n,k} equals the number permutations σ in the symmetric group S_{n} that have k cycles. The S_{n,k}’s and c_{n,k}’s also have nice interpretations in terms of rook theory. Let F (0, 1, …, n − 1) be a rook board whose columns heights are 0, 1, …, n − 1 reading from right to left. Then S_{n,k} equals number of ways to place n − k rooks on F (0, 1, …, n − 1) so that no two rooks are in the same row or column, and c_{n,k} equals number of ways to place n − k rooks on F (0, 1, …, n − 1) so that no two rooks are in the same column.

The goal of this paper is to develop the combinatorics of what we call the poly-Stirling numbers. Let p_{s_{1}}x^{s_{1}} + p_{s_{2}}x^{s_{2}} + ⋯ + p_{s_{y}}x^{s_{y}} ∈ ℕ[x] where 0 ≤ s_{i} < s_{j} whenever i < j. We define the numbers s_{n,k}^{p(x)} and S_{n,k}^{p(x)} by the following recursions, respectively:

s_{0,0}^{p(x)} = 1 and s_{n,k}^{p(x)} = 0 if k < 0 or k > n, and  (1.6)
s_{n+1,k}^{p(x)} = s_{n,k−1}^{p(x)} − p(n)s_{n,k}^{p(x)} if 0 ≤ k ≤ n + 1 and n ≥ 0,

and

S_{0,0}^{p(x)} = 1 and S_{n,k}^{p(x)} = 0 if k < 0 or k > n, and  (1.7)
S_{n+1,k}^{p(x)} = S_{n,k−1}^{p(x)} + p(k)S_{n,k}^{p(x)} if 0 ≤ k ≤ n + 1 and n ≥ 0.

If we replace s_{n,k}^{p(x)} with (−1)^{n−k}c_{n,k}^{p(x)}, then we have the recursion

c_{0,0}^{p(x)} = 1 and c_{n,k}^{p(x)} = 0 if k < 0 or k > n, and  (1.8)
c_{n+1,k}^{p(x)} = c_{n,k−1}^{p(x)} + p(n)c_{n,k}^{p(x)} if 0 ≤ k ≤ n + 1 and n ≥ 0.

We will call the sequence of numbers in Equation (1.7) the poly-Stirling numbers of the second kind for p(x), the sequence of numbers in Equation (1.6) the poly-Stirling numbers of the first kind for p(x), and the sequence of numbers in Equation (1.8) the signless poly-Stirling numbers of the first kind for p(x).

We develop a new rook theory model to interpret the numbers S_{n,k}^{p(x)} and c_{n,k}^{p(x)}. We then use this model to prove various identities for the poly-Stirling numbers. We also give alternative combinatorial interpretations of c_{n,k}^{p(x)} in terms of certain collections of permutations and S_{n,k}^{p(x)} in terms of certain collections of sets partitions. For example, we shall show that S_{n,k}^{x^{m}} is the number of m-tuples of set partitions (P^{(1)}, …, P^{(m)}) of {1, …, n} into k parts such that the set of minimal elements in the parts of P^{(i)} is the same for all i. Similarly, we show that (−1)^{n−k}s_{n,k}^{x^{m}} is the number of m-tuples of permutations (σ^{(1)}, …, σ^{(m)}) of {1, …, n} into k cycles such that set of minimal elements in the cycles of σ^{(i)} is the same for all i.

It is also the case that for any p(x) ∈ ℕ[x], the matrices ||s_{n,k}^{p(x)}|| and ||S_{n,k}^{p(x)}|| are inverses of each other. This follows from general inversion formula due Milne [4] or can be directly verified by using recursions (1.6) and (1.7). We use our combinatorial interpretations the S_{n,k}^{p(x)}’s and s_{n,k}^{p(x)}’s to give a direct combinatorial proof of this fact.

The outline of this paper is as follows. In Section 2, we will develop a rook theory model which we call m-partition rook boards. This allows us to give combinatorial interpretations of the poly-Stirling numbers S_{n,k}^{p(x)} and c_{n,k}^{p(x)} in the special case where p(x) = x^{m}. We shall call such poly-Stirling numbers x^{m}-Stirling numbers. We shall show that various simple identities satisfied by the x^{m}-Stirling numbers are just special cases of more general formulas for the appropriate analogues of rook and file numbers for m-partition Ferrers boards. In Section 3, we use the theory of m-partition boards to show that the matrices defined by the x^{m}-Stirling numbers of the first and second kind are inverses of one another. In Section 4, we will generalize the results in Section 2 in order to discuss poly-Stirling numbers in full generality, first describing the case where p(0) = 0 and then describing the case where p(0) ≠ 0.

2 m-Partition Boards & Rook Placements

Let B = F (b_{1}, b_{2}, …, b_{n}) be a Ferrers board with column heights b_{1}, b_{2}, …, b_{n}, reading from left to right, where 0 ≤ b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n} are nonnegative integers. For any positive integer m, we may define B^{(m)}, called the m-partition of B, to be the board B where each column is partitioned into m subcolumns. We will define, for any board B, C_{(j)}(B^{(m)}) to be the j^{th} column of B^{(m)}, reading from left to right and C_{(l,j)}(B^{(m)}) to be the l^{th} subcolumn, reading from left to right, of the j^{th} column of B. Finally, the cell which is in the t^{th} row from the bottom of C_{(l,j)}(B^{(m)}) will be denoted by c(t, l, j). An example of these types of boards can be seen in Figure 1, where B = F (0, 1, 3, 4, 4) and m = 2.

Garsia and Remmel [1] define two kinds of rook placements in the board B^{(m)}: nonattacking placements and file placements. We let N_{k,(m)}(B^{(m)}) denote the set of placements of mk rooks in B^{(m)} such that the following three conditions hold.

(i.) If any subcolumn C_{(i,j)}(B^{(m)}) contains a rook, then for every 1 ≤ l ≤ m, the subcolumn C_{(l,j)}(B^{(m)}) must contain a rook. That is, if any subcolumn of the j^{th} column contains a rook, then every subcolumn of the j^{th} column must contain a rook.

(ii.) There is a most one rook in any one subcolumn.

(iii.) For any 1 ≤ l ≤ m and any row t, there is at most one rook in row t that lies in a subcolumn of the form C_{(l,j)}(B^{(m)}). That is, there is at most one rook in the l^{th} subcolumn of any column.

Figure 1: The board B^{(2)}, with B = F (0, 1, 3, 4, 4).

We shall call an element of N_{k,(m)}(B^{(m)}) a nonattacking placement of mk rooks in B^{(m)}. Another way to think of nonattacking rook placements is that as you place rooks from left to right, each rook r that lies in a cell c(t, l, j) cancels all the cells in the same row t that lie in subcolumns corresponding to l to its right. Then a placement of rooks satisfying (i) and (ii) above is a placement of nonattacking rooks if no rook lies in a cell which is canceled by another rook to its left. For example, on the left in Figure 2 we have pictured a nonattacking rook placement ℙ ∈ N_{k,(m)}(B^{(m)}) where B = F (0, 1, 3, 4, 4), m = 2, and k = 2. Here we denote each rook by an “X” and we have placed dots in the cells that are canceled by these rooks. Note that since rooks only cancel cells that correspond to the same subcolumn, we do allow the possibility of having rooks in the same row in a given column.

We let F_{k,(m)}(B^{(m)}) denote the set of placements of mk rooks in B^{(m)} such that the following two conditions hold.

(i.) If any subcolumn C_{(i,j)}(B^{(m)}) contains a rook, then for every 1 ≤ l ≤ m, the subcolumn C_{(l,j)}(B^{(m)}) must contain a rook.

(ii.) There is at most one rook in any subcolumn.

We call such placements file rook placements. For example, on the right in Figure 2 we have pictured a file placement ℚ ∈ F_{k,(m)}(B^{(m)}) where B = F (0, 1, 3, 4, 4), m = 2, and k = 2.

We then define

\begin{aligned}r_{k,(m)}(B^{(m)}) & := & |N_{k,(m)}(B^{(m)})| and \\ f_{k,(m)}(B^{(m)}) & := & |F_{k,(m)}(B^{(m)})|, \end{aligned}

and we call r_{k,(m)}(B^{(m)}) the k^{th} m-rook number of B^{(m)} and f_{k,(m)}(B^{(m)}) the k^{th} m-file number of B^{(m)}.

Next we shall prove some basic properties of the m-rook numbers and m-file numbers for Ferrers boards. First we show that these numbers satisfy some simple recursions.

Theorem 2.1. Suppose that B = F (b_{1}, …, b_{n}) and B̄ = F (b_{1}, …, b_{n}, b_{n+1}) are Ferrers boards. Then for all 0 ≤ k ≤ n + 1,

r_{k,(m)}(B̄^{(m)}) = r_{k,(m)}(B^{(m)}) + (b_{n+1} − (k − 1))^{m}r_{k−1,(m)}(B^{(m)})  (2.1)

Figure 2: Nonattacking and file rook placements in the board B^{(2)}, with B = F (0, 1, 3, 4, 4).

and

f_{k,(m)}(B̄^{(m)}) = f_{k,(m)}(B^{(m)}) + b_{n+1}^{m}f_{k−1,(m)}(B^{(m)}).  (2.2)

Proof. For (2.1), we will classify the nonattacking rook placements N_{k,(m)}(B̄^{(m)}) according to whether they have rooks in the last column. That is, if ℙ ∈ N_{k,(m)}(B̄^{(m)}) has no rooks in the last column, then ℙ can be viewed as an element of N_{k,(m)}(B^{(m)}) so that such rook placements are counted by r_{k,(m)}(B^{(m)}). If ℙ ∈ N_{k,(m)}((B̄^{(m)}) has rooks in the last column, then let ℙ^{∗} denote the rook placement in N_{k−1,(m)}(B̄^{(m)}) that results from ℙ by removing all the rooks in the last column. Now if we are given such a ℙ^{∗}, we claim that there are (b_{n+1} − (k − 1))^{m} ways to extend ℙ^{∗} to a rook placement in N_{k,(m)}(B̄^{(m)}). That is, in each subcolumn C_{(l,n+1)}, there will k − 1 cells which are canceled by rooks in ℙ^{∗}. Thus, we have b_{n+1} − (k − 1) choices of where to put a rook in C_{(l,n+1)} to extend ℙ^{∗}. It follows that the number of nonattacking rook placements in N_{k,(m)}(B̄^{(m)}) that have rooks in the last column is counted by (b_{n+1} − (k − 1))^{m}r_{k−1,(m)}(B^{(m)}).

The recursion (2.2) can be proved in the same way. That is, f_{k,(m)}(B^{(m)}) counts those file placements in F_{k,(m)}(B̄^{(m)}) that have no rooks in the last column. If ℚ^{∗} is file placement in F_{k−1,(m)}(B̄^{(m)}) which has no rooks in the last column, then there are b_{n+1}^{m} ways to extend ℚ^{∗} to a rook placement in F_{k,(m)}(B̄^{(m)}) by adding rooks in the last column because for file placements, there are no restrictions on where we can add rooks in any subcolumn C_{(l,n+1)}. Thus, the number of file placements in F_{k,(m)}(B̄^{(m)}) that have rooks in the last column is counted by b_{n+1}^{m}f_{k−1,(m)}(B^{(m)}).

2.1 m-Partition Boards & x^{m}-Stirling Numbers

Now we consider the special case of the poly-Stirling numbers where the polynomial p(x) = x^{m}. In such a case, we shall refer to such numbers as x^{m}-Stirling numbers. In particular, the x^{m}-Stirling numbers of the first kind, s_{n,k}^{x^{m}}, are defined by the following recursions:

s_{0,0}^{x^{m}} = 1 and s_{n,k}^{x^{m}} = 0 if k < 0 or k > n and  (2.3)
s_{n+1,k}^{x^{m}} = s_{n,k−1}^{x^{m}} − n^{m}s_{n,k}^{x^{m}} if 0 ≤ k ≤ n + 1 and n ≥ 0.

We now define s_{n,k}^{x^{m}} = (−1)^{n−k}c_{n,k}^{x^{m}}. Thus, the integers c_{n,k}^{x^{m}}, called the signless x^{m}-Stirling numbers of the first kind, satisfy the recursions:

c_{0,0}^{x^{m}} = 1 and c_{n,k}^{x^{m}} = 0 if k < 0 or k > n and  (2.4)
c_{n+1,k}^{x^{m}} = c_{n,k−1}^{x^{m}} + n^{m}c_{n,k}^{x^{m}} if 0 ≤ k ≤ n + 1 and n ≥ 0.

Finally, the x^{m}-Stirling numbers of the second kind, S_{n,k}^{x^{m}}, satisfy the following recursions:

S_{0,0}^{x^{m}} = 1 and S_{n,k}^{x^{m}} = 0 if k < 0 or k > n and  (2.5)
S_{n+1,k}^{x^{m}} = S_{n,k−1}^{x^{m}} + k^{m}S_{n,k}^{x^{m}} if 0 ≤ k ≤ n + 1 and n ≥ 0.

Now if we let B = F (0, 1, …, n − 1) and B̄ = F (0, 1, …, n − 1, n) in Theorem 2.1, then we see that

r_{n+1−k,(m)}(B̄^{(m)}) = r_{n−(k−1),(m)}(B^{(m)}) + k^{m}r_{n−k,(m)}(B^{(m)})  (2.6)

and

f_{n+1−k,(m)}(B̄^{(m)}) = f_{n−(k−1),(m)}(B^{(m)}) + n^{m}f_{n−k,(m)}(B^{(m)})  (2.7)

Thus, we have the following theorem which gives our promised rook theory interpretation for the x^{m}-Stirling numbers.

Theorem 2.2. Let m ∈ ℕ and B = F (0, 1, …, n − 1). Then

S_{n,k}^{x^{m}} = r_{n−k,(m)}(B^{(m)}),  (2.8)

c_{n,k}^{x^{m}} = f_{n−k,(m)}(B^{(m)}),  (2.9)

and

s_{n,k}^{x^{m}} = (−1)^{n−k}f_{n−k,(m)}(B^{(m)}).  (2.10)

It follows from a general inversion theorem of Milne [4] that the x^{m}-Stirling numbers of the first and second kind are inverses of each other. We will use our rook theory interpretations of the x^{m}-Stirling numbers to give a direct combinatorial proof of this fact in the next section. Moreover, notice that when m = 1, then the x^{m}-Stirling numbers defined here match exactly with the standard notion of Stirling numbers of the first and second kind. In the case where m = 2, these numbers are discussed in both Riordan [5] and Stanley [6] where they are referred to as triangle central factorial numbers.

Next we shall prove two general product formulas for m-rook and m-file numbers. These formulas will then be specialized to give the analogues of (1.1) and (1.2) for the x^{m}-Stirling numbers.

Theorem 2.3. Let m ∈ ℕ, n ∈ ℕ^{0}, x ∈ ℝ, and suppose that B = F (b_{1}, b_{2}, …, b_{n}) is a Ferrers board. Then

∏_{i=1}^{n}(x^{m} + b_{i}^{m}) = ∑_{k=0}^{n} f_{n−k,(m)}(B^{(m)})(x^{m})^{k}.  (2.11)

Figure 3: An example of the board B_{5}^{(2)}, with B = F (0, 1, 3, 4, 4), along with a corresponding example of a file placement.

Proof. We will prove that this result holds for the case where x is any nonnegative integer. The stated result then follows as a corollary to the Fundamental Theorem of Algebra.

Given a positive integer m, we define the board B_{x}^{(m)} to be the board B^{(m)} with x rows appended below, each with n columns partitioned into m subcolumns. We refer to this part of the board as the x-part and the part that corresponds to B^{(m)} will be called the upper part of B_{x}^{(m)}. We will say that these two parts are separated by the high bar. An example of this type of board can be seen in the lefthand side of Figure 3, where B = F (0, 1, 3, 4, 4), m = 2, and x = 5. For B_{x}^{(m)}, we will label the cells in the upper part of this board exactly as we would in the board B^{(m)}. For the x-part of B_{x}^{(m)}, we will label the rows, from top to bottom, with 1, 2, …, x. If a rook r is placed in column C_{(l,j)}(B_{x}^{(m)}) in the x-part in the row labeled with i, then we say that r lies in the cell c_{x}(i, l, j).

We let F_{n,(m)}(B_{x}^{(m)}) denote the set of all placements of mn rooks in B_{x}^{(m)} such that the following two conditions hold.

(i.) There is a rook in every subcolumn.

(ii.) If any of the m rooks placed in a given column lie above the high bar, then all m rooks in that column must lie above the high bar.

We call this type of placement a file placement in B_{x}^{(m)}. An illustration of this type of placement can be seen in the righthand side of Figure 3.

Given x ∈ ℕ, we count the number of file placements in B_{x}^{(m)} in two different ways. First, see that for each i, we have b_{i}^{m} ways to place the m rooks above the high bar and x^{m} ways to place m rooks below the bar in column i. Thus, we have ∏_{i=1}^{n}(x^{m} + b_{i}^{m}) file placements of mn rooks in B_{x}^{(m)}. On the other hand suppose that we fix a file placement ℚ of m(n − k) rooks in B^{(m)}. Then we can count the number of ways to extend ℚ to file placement of mn rooks in B_{x}^{(m)} by adding rooks below the bar in each of the k columns that have no rooks. There are x^{m} ways to place the rooks below the high bar for each such column. Thus, the number of file placements of mn rooks in B_{x}^{(m)} is

∑_{k=0}^{n} ∑_{ℚ∈F_{n−k,(m)}(B^{(m)})}(x^{m})^{k} = ∑_{k=0}^{n} f_{n−k,(m)}(B^{(m)})(x^{m})^{k}.

Note that in the special case of Theorem 2.3 where B = F (0, 1, …, n − 1), we see that (2.11) reduces to

∏_{i=1}^{n}(x^{m} + (i − 1)^{m}) = ∑_{k=o}^{n} c_{n,k}^{x^{m}}(x^{m})^{k}.  (2.12)

Since Theorem 2.3 shows that (2.12) holds for all integers x ≥ 0 and (2.12) is a polynomial identity if follows that (2.12) holds for all x. If we replace x^{m} by −x^{m} in (2.12) and then multiply by (−1)^{n}, the we obtain the following corollary.

Corollary 2.4. For m ∈ ℕ and n ∈ ℕ^{0},

∏_{i=1}^{n}(x^{m} − (i − 1)^{m}) = ∑_{k=o}^{n} s_{n,k}^{x^{m}}(x^{m})^{k}.  (2.13)

Next we prove a product formula for m-rook numbers.

Theorem 2.5. Let m ∈ ℕ and n, x ∈ ℕ^{0} and suppose that B = F (0, 1, 2, …, n − 1). Then

(x^{m})^{n} = ∑_{k=0}^{n} r_{n−k,(m)}(B^{(m)}) x^{m}(x^{m} − 1^{m}) ⋯ (x^{m} − (k − 1)^{m}).  (2.14)

Our proof will be a modification a general product formula proved by M. and Remmel [3]. Given B, m, and x, we will construct an augmented board B_{x}^{aug,(m)}. First we start with the board B_{x}^{(m)}. Then B_{x}^{aug,(m)} is formed by adding columns of heights 0, 1 …, n − 1, reading from left to right, that consist of m subcolumns below the x-part of B_{x}^{(m)}. We call the extra cells that we added to B_{x}^{(m)} to form B_{x}^{aug,(m)} the lower augmented part of B_{x}^{aug,(m)} and call the line that separates the x-part and the lower augmented part of B_{x}^{aug,(m)} the low bar. For example, we have pictured such an augmented board on the left in Figure 4, where B = F (0, 1, 3, 3, 4), m = 2, and x = 3.

Next we define the set of nonattacking rook placements, N_{n,(m)}(B_{x}^{aug,(m)}), of mn rooks in B_{x}^{aug,(m)} to be the set of placements ℙ in B_{x}^{aug,(m)} such that the following three conditions hold.

(i.) There is at most one rook in each subcolumn.

(ii.) For any given column C_{(j)}(B_{x}^{aug,(m)}), either all m rooks in that column are placed above the high bar, below the low bar, or in the x-part of B_{x}^{aug,(m)}.

(iii.) No rook lies in a cell which is canceled by another rook.

Figure 4: An example of the board B_{3}^{aug,(2)}, with B = F (0, 1, 3, 3, 4) along with a corresponding example of a nonattacking rook placement.

Here rooks that are placed in either the x-part or the lower augmented part of B_{x}^{aug,(m)} do not cancel any cells; however, rooks placed in the upper part of B_{x}^{aug,(m)} do cancel cells. If a rook r is placed in a cell c(t, l, j) in the upper part, then r will cancel all the cells in B^{(m)} of the form c(t, s, j) for s > l plus the lowest cells in the lower augmented part in the subcolumn C_{(s,j)} for s > l that have not been canceled by a rook that lies in subcolumn C_{(p,j)} of B^{(m)} to the left of r. To better illustrate this cancelation, we have pictured an element of N_{n,(m)}(B_{x}^{aug,(m)}) in the righthand side of Figure 4. We have placed dots in those cells that are canceled by the rooks in column 2 and ∗’s in the cells that are canceled by the rooks in column 4. The other rooks do not cancel any cells.

Finally we define the weight of a placement ℙ ∈ N_{n,(m)}(B_{x}^{aug,(m)}), w(ℙ), to be (−1)^{la(ℙ)} where la(ℙ) equals the number of columns in ℙ which contain rooks which lie in the lower augmented part of B_{x}^{aug,(m)}. We are now in a position to prove the previously stated theorem.

Proof. We claim that (2.14) arises from two different ways of computing the sum

∑_{ℙ∈N_{n,(m)}(B_{x}^{aug,(m)})}w(ℙ).  (2.15)

First we see that in column 1, there are x^{m} ways to place m rooks, and thus for the second column, we have no canceled cells. Hence there are 1^{m} ways to place m rooks above the high bar, x^{m} ways to place rooks in the x-part of B_{x}^{aug,(m)}, and 1^{m} way to place a rook below the low bar. Thus the sum of the weights of the rooks in the second column is 1^{m} +x^{m} −1^{m} = x^{m}. In general, if we have placed rooks in columns C_{(1)}(B_{x}^{aug,(m)}), …, C_{(t−1)}(B_{x}^{aug,(m)}) where exactly s of the columns have rooks above the high bar, then there will be t − 1 − s uncanceled cells above the high bar and t − 1 − s uncanceled cells below the low bar in subcolumn C_{(l,t)}(B_{x}^{aug,(m)}). Then in column t, there are (t − 1 − s)^{m} ways to place m rooks above the high bar, x^{m} ways to place m rooks in the x-part, and (t − 1 − s)^{m} ways to place m rooks below the low bar. In such a case, the weights of the rooks in the t^{th} column will contribute (t − 1 − s)^{m} + x^{m} − (t − 1 − s)^{m} = x^{m} to (2.15). It then follows that

(x^{m})^{n} = ∑_{ℙ∈N_{n,(m)}(B_{x}^{aug,(m)})}w(ℙ).

Now suppose that we fix a placement ℙ of m(n−k) rooks in B^{(m)}. Then we want to count the number of ways extend ℙ to a placement in N_{n,(m)}(B_{x}^{aug,(m)}). Let C_{(t_{i})}(B_{x}^{aug,(m)}) be the i^{th} column, reading left to right, which has no rooks in that column. By construction, t_{1} = 1 so that there are x^{m} ways to add rooks below the bar in column C_{(t_{1})}(B_{x}^{aug,(m)}). For 1 < i ≤ k, there will be t_{i} − (i − 1) columns to the left of C_{(t_{i})}(B_{x}^{aug,(m)}) which have rooks above the high bar and these rooks will cancel t_{i} − (i − 1) cells in each subcolumn of C_{(t_{i})}(B_{x}^{aug,(m)}) in the lower augmented part of the B_{x}^{aug,(m)}. Thus, there will be t_{i} − (t_{i} − (i − 1)) = (i − 1) uncanceled cells in each subcolumn of C_{(t_{i})}(B_{x}^{aug,(m)}) in the lower augmented part of the B_{x}^{aug,(m)}. We then see that if we sum the weights over all possible ways to place the m rooks in column C_{(t_{i})}(B_{x}^{aug,(m)}) we will get x^{m} − (i − 1)^{m}. It follows that

∑_{ℙ∈N_{n,(m)}(B_{x}^{aug,(m)})}w(ℙ) = ∑_{k=0}^{n} ∑_{ℙ∈N_{n−k,(m)}(B^{(m)})}x^{m}(x^{m} − 1^{m}) ⋯ (x^{m} − (k − 1)^{m})

= ∑_{k=0}^{n} r_{n−k,(m)}(B^{(m)}) x^{m}(x^{m} − 1^{m}) ⋯ (x^{m} − (k − 1)^{m}).

We note that it is possible to prove formulas which are similar to (2.14) for any Ferrers board F (b_{1}, b_{2}, …, b_{n}). That is, the author and J. Remmel [3] developed a rook theory model which allows one to prove more general product identities in rook theory. Suppose we are given any two sequences of nonnegative integers B = {b_{i}}_{i=1}^{n} and A = {a_{i}}_{i=1}^{n}, and two functions, sgn, \overline{sgn} : [n] → \{−1, +1\}. Let B = F (b_{1}, b_{2}, …, b_{n}) be a skyline board. M. and Remmel’s a rook theory model is defined with an appropriate notion of rook numbers r_{k}(B, A) such that the following product formula holds:

∏_{i=1}^{n}(x + sgn(i)b_{i}) = ∑_{k=0}^{n} r_{n−k}(B, B, A) ∏_{j=1}^{k}(x + ∑_{s≤j} \overline{sgn}(s)a_{s}).  (2.16)

Thus by replacing x by x^{m} and picking A and B appropriately, we can obtain identities of the form

∏_{i=1}^{n}(x^{m} + c_{i}^{m}) = ∑_{k=0}^{n} r_{n−k}(B, A) ∏_{j=0}^{k−1}(x^{m} − j^{m}),  (2.17)

of which (2.14) is a special case. (The m-rook theory model presented in this paper suffices to develop the rook-theoretic interpretations for the poly-Stirling numbers, although the more general rook theory model found in M. and Remmel [3] is more complicated.)

Theorem 2.5 yields the following corollary involving the S_{n,k}^{x^{m}}’s.

Corollary 2.6. For m ∈ ℕ and n ∈ ℕ^{0},

(x^{m})^{n} = ∑_{k=0}^{n} S_{n,k}^{x^{m}} x^{m}(x^{m} − 1^{m}) ⋯ (x^{m} − (k − 1)^{m}).  (2.18)

Another simple identity satisfied by the x^{m}-Stirling numbers of the second kind, which is a generalization of a well-known formula, is the following.

Theorem 2.7. For any k ≥ 1,

∑_{n≥k} S_{n,k}^{x^{m}}t^{n} = \frac{t^{k}}{(1 − t)(1 − 2^{m}t) ⋯ (1 − k^{m}t)}.  (2.19)

Proof. Let ϕ_{k}(t) = ∑_{n≥k} S_{n,k}^{x^{m}}t^{n}. From our combinatorial interpretation we see that the only way to place (n − 1)m rooks in B^{(m)} where B = F (0, 1, …, n − 1) is to place every rook at the top of its column. Thus S_{n,1}^{x^{m}} = 1 for all n and hence ϕ_{1}(t) = \frac{t}{(1−t)}. Then we know that

ϕ_{k}(t) = ∑_{n≥k} S_{n,k}^{x^{m}}t^{n}
= ∑_{n≥k}(S_{n−1,k−1}^{x^{m}} + k^{m}S_{n−1,k}^{x^{m}})t^{n}
= ∑_{n≥k} S_{n−1,k−1}^{x^{m}}t^{n} + ∑_{n≥k} k^{m}S_{n−1,k}^{x^{m}}t^{n}
= tϕ_{k−1}(t) + k^{m}tϕ_{k}(t).

Thus, ϕ_{k}(t) = \frac{t}{(1−k^{m}t)}ϕ_{k−1}(t), and our result follows by induction.

2.2 Set and Cycle Structure Interpretations of x^{m}-Stirling Numbers

Stirling numbers are intimately related to set partitions and cycle structures. We will show in this section that x^{m}-Stirling numbers have combinatorial interpretations relating to m-tuples of set partitions and cycles.

Let [n] := {1, 2, 3, …, n}. For m ≥ 1, let P_{n,k}^{(m)} = (P^{(1)}, P^{(2)}, … P^{(m)}) be an m-tuple of unordered set partitions of [n] into k parts and Π_{n,k}^{(m)} := {P_{n,k}^{(m)}| the parts of P_{i} and P_{j} have the same minimal elements for every 1 ≤ i < j ≤ m}. We set Π_{0,0}^{(m)} := {∅}.

Theorem 2.8. Let n be a nonnegative integer and let m ∈ ℕ. Then S_{n,k}^{x^{m}} = |Π_{n,k}^{(m)}| for every 0 ≤ k ≤ n.

Proof. Fix m ∈ ℕ. First we note that |Π_{n,k}^{(m)}| = 0 whenever k < 0 or k > n, and Π_{0,0}^{(m)} = {∅}, so |Π_{0,0}^{(m)}| = S_{0,0}^{x^{m}} = 1. For n = 1, |Π_{1,0}^{(m)}| = S_{1,0}^{x^{m}} = 0 and |Π_{1,1}^{(m)}| = S_{1,1}^{x^{m}} = 1 since Π_{1,1}^{(m)} is just the m-tuple ({1}, …, {1}). Proceeding by induction, we will pick n > 1 and assume that |Π_{n,k}^{(m)}| = S_{n,k}^{x^{m}} for every 0 ≤ k ≤ n.

Suppose that P_{n+1,k}^{(m)} ∈ Π_{n+1,k}^{(m)}. If {n+1} is in a part by itself in P^{(i)} ∈ P_{n+1,k}^{(m)}, then {n+1} is in a part by itself in P^{(j)} ∈ P_{n+1,k}^{(m)} for every j = 1, 2, …, m. Thus, we can transform an m-tuple P_{n,k−1}^{(m)} ↦ P_{n+1,k}^{(m)} by adding the part {n+1} to every partition of P_{n,k−1}^{(m)}. Similarly, if {n + 1} is not in a part by itself for some P^{(i)} ∈ P_{n+1,k}^{(m)}, then {n + 1} is not in a part by itself in any P^{(j)} ∈ P_{n+1,k}^{(m)} for j = 1, 2, …, m. Thus, we can transform an m-tuple P_{n,k}^{(m)} ↦ P_{n+1,k}^{(m)} by adding n + 1 to any of the k parts of each partition in P_{n,k}^{(m)}, of which there are k^{m} ways of doing this.

Thus,

|Π_{n+1,k}^{(m)}| = |Π_{n,k−1}^{(m)}| + k^{m}|Π_{n,k}^{(m)}|
= S_{n,k−1}^{x^{m}} + k^{m}S_{n,k}^{x^{m}}
= S_{n+1,k}^{x^{m}}.

As an example of this type of object, notice that we can compute S_{3,2}^{(2)} = 5, and thus there are the following five elements in the set Π_{3,2}^{(2)}. That is, there are five pairs (2-tuples) of set partitions of {1, 2, 3} into 2 parts such that every pair in the partition has common minimal elements. Specifically,

({1}{2, 3}, {1}{2, 3}),
({1}{2, 3}, {1, 3}{2}),
({1, 3}{2}, {1}{2, 3}),
({1, 3}{2}, {1, 3}{2}),
({1, 2}{3}, {1, 2}{3}).

For m ≥ 1, let C_{n,k}^{(m)} = (σ^{(1)}, σ^{(2)}, …, σ^{(m)}) be an m-tuple of permutations of [n] with k cycles and define Ω_{n,k}^{(m)} = {C_{n,k}^{(m)}| the cycles of σ^{(i)} and σ^{(j)} have the same minimal elements for every 1 ≤ i < j ≤ m}. Set Ω_{0,0}^{(m)} := {∅}.

Theorem 2.9. Let n be a nonnegative integer and let m ∈ ℕ. Then c_{n,k}^{x^{m}} = |Ω_{n,k}^{(m)}| for every 0 ≤ k ≤ n.

Proof. Fix m ∈ ℕ. First we note that |Ω_{n,k}^{(m)}| = 0 whenever k < 0 or k > n, and Ω_{0,0}^{(m)} = {∅}, so |Ω_{0,0}^{(m)}| = c_{0,0}^{x^{m}} = 1. For n = 1, |Ω_{1,0}^{(m)}| = c_{1,0}^{x^{m}} = 0 and |Ω_{1,1}^{(m)}| = c_{1,1}^{x^{m}} = 1 since Ω_{1,1}^{(m)} is just the m-tuple ((1), …, (1)). Proceeding by induction, we will pick n > 1 and assume that |Ω_{n,k}^{(m)}| = c_{n,k}^{x^{m}} for every 0 ≤ k ≤ n.

Suppose that C_{n+1,k}^{(m)} ∈ Ω_{n_{1},k}^{(m)}. If (n + 1) is a cycle in C_{i} ∈ C_{n+1,k}^{(m)}, then (n + 1) is a cycle in C_{j} ∈ C_{n+1,k}^{(m)} for every j = 1, 2, …, m. Thus, we can transform an m-tuple C_{n,k−1}^{(m)} ↦ C_{n+1,k}^{(m)} by adding the cycle (n + 1) to every collection of cycles of C_{n,k−1}^{(m)}. Similarly, if (n + 1) is not a cycle for some C_{i} ∈ C_{n+1,k}^{(m)}, then (n + 1) is not cycle in any C_{j} ∈ C_{n+1,k}^{(m)} for j = 1, 2, …, m. Thus, we can transform an m-tuple C_{n,k}^{(m)} ↦ C_{n+1,k}^{(m)} by inserting n + 1 immediately after one of the elements in each of the cycle structures in C_{n,k}^{(m)}, of which there are n^{m} ways of doing this.

Thus,

|Ω_{n+1,k}^{(m)}| = |Ω_{n,k−1}^{(m)}| + n^{m}|Ω_{n,k}^{(m)}|
= c_{n,k−1}^{x^{m}} + n^{m}c_{n,k}^{x^{m}}
= c_{n+1,k}^{x^{m}}.

3 A Combinatorial Proof That ||S_{n,k}^{x^{m}}||||s_{n,k}^{x^{m}}|| = I

In this section, we will use our combinatorial interpretations of the x^{m}-Stirling numbers of the first and second kind to give an involution-type combinatorial proof of the fact that

||S_{n,k}^{x^{m}}||||s_{n,k}^{x^{m}}|| = I.

Theorem 3.1. The lower triangular matrices defined by ||S_{n,k}^{x^{m}}|| and ||s_{n,k}^{x^{m}}|| are inverses of one another.

Proof. Consider the sum

S(n) = ∑_{k=0}^{n} ∑_{j=0}^{k} S_{n,k}^{x^{m}}s_{k,j}^{x^{m}}.  (3.1)

By definition, s_{n,k}^{x^{m}} = (−1)^{n−k}c_{n,k}^{x^{m}}, so we have

S(n) = ∑_{k=0}^{n} ∑_{j=0}^{k}(−1)^{k−j}S_{n,k}^{x^{m}}c_{k,j}^{x^{m}}.  (3.2)

Now, we can think of this sum as representing a certain weighting over pairs of rook placements (U, V) ∈ (N_{n−k,(m)}(B_{n}^{(m)}), F_{k−j,(m)}(B_{k}^{(m)})). Specifically, if for any Ferrers board B we define w(U) = (1)^{k} = 1 for every U ∈ N_{k,(m)}(B) and w̃(V) = (−1)^{k} for every V ∈ F_{k,(m)}(B), then (3.2) becomes

S(n) = ∑_{k=0}^{n} ∑_{j=0}^{k} ∑_{(U,V)∈(N_{n−k,(m)}(B_{n}^{(m)}),F_{k−j,(m)}(B_{k}^{(m)}))} w(U)w̃(V).  (3.3)

We now consider the involution I with the following properties:

(i.) If for (U, V) ∈ (N_{n−k,(m)}(B_{n}^{(m)}), F_{k−j,(m)}(B_{k}^{(m)})) U has m rooks in its last column, then I(U, V) = (U^{∗}, V^{∗}) ∈ (N_{n−k−1,(m)}(B_{n}^{(m)}), F_{k−j,(m)}(B_{k+1}^{(m)})), where

a. U^{∗} is the placement U with the rooks in the last column removed, and

b. if U had a rook in C_{(l,n)} in the w^{th} available cell, after cancelation, from the bottom of the board B_{n}^{(m)}, then V^{∗} is the placement V copied into the larger board, B_{k+1}^{(m)}, with a rook placed in the cell c(w, l, k) of B_{k+1}^{(m)}.

(ii.) If for (U^{∗}, V^{∗}) ∈ (N_{n−k−1,(m)}(B_{n}^{(m)}), F_{k−j+1,(m)}(B_{k+1}^{(m)})), U^{∗} has no rooks in its last column but V^{∗} does, then we reverse the above step.

(iii.) If for (U, V) ∈ (N_{n−k,(m)}(B_{n}^{(m)}), F_{k−j,(m)}(B_{k}^{(m)})) neither U nor V has m rooks in the last column, then remove the minimum number of columns, s, from both boards such that at least one of the two placements remaining now has m rooks in the last column. We now have a new pair (Û, V̂) ∈ (N_{n−k,(m)}(B_{n−s}^{(m)}), F_{k−j,(m)}(B_{k−s}^{(m)})). We now repeat the above steps of I on (Û, V̂) to get a pair (Û^{∗}, V̂^{∗}). We then add s empty column back to each board.

An example of parts 1 and 2 of the involution can be seen in the lefthand side of Figure 5, where both (U, V) and (U^{∗}, V^{∗}) are shown. In this figure we have (U, V) ∈ (N_{2,(3)}(B_{5}^{(3)}), F_{2,(3)}(B_{3}^{(3)})), and (U^{∗}, V^{∗}) ∈ (N_{1,(3)}(B_{5}^{(3)}), F_{3,(3)}(B_{4}^{(3)})). In the righthand side of Figure 5, an illustration of the third part of our involution is shown. Here (U, V) ∈ (N_{2,(3)}(B_{5}^{(3)}), F_{2,(3)}(B_{3}^{(3)})) with neither containing a rook in the last column, but V containing rooks in the second column from the right, that is, s = 1. Once we remove the last column of each board, we get new placements (Û, V̂) and from there, since V̂ contains rooks in its last column, we can invoke part 2 of I to give us (Û^{∗}, V̂^{∗}). We now add one empty column back to each board to complete the involution.

It is clear from I’s definition that I(I(U, V)) = (U, V). Moreover, if w(U)w̃(V) = +1, then w(U^{∗})w̃(V^{∗}) = −1 and also if w(U)w̃(V) = −1, then w(U^{∗})w̃(V^{∗}) = +1, thus I is a sign-reversing involution. We can now see, through I, that unless I(U, V) = (U, V) each pair of placements will have a counterpart (U^{∗}, V^{∗}) such that w(U)w̃(V) + w(U)w̃(V^{∗}) = 0. Thus,

S(n) = ∑_{k=0}^{n} ∑_{j=0}^{k} ∑_{I(U,V)=(U,V)^{(U,V )∈(N_{n−k,(m)}(B{(m) \atop n}),F_{k−j,(m)}(B{(m) \atop k}))}} w(U)w̃(V).

Figure 5: An example of Parts 1 and 2 of the involution I on the left side and an example of Part 3 on the right.

However, the only fixed points of I are those placement pairs which have no rooks in either placement. So, for a fixed n, k must equal n and j must equal k, or equivalently, w(U)w̃(V) = (1)(−1)^{k−j} = 1 = χ(n = j).

4 Poly-Stirling Numbers

4.1 Notation

In this section we wish to generalize the rook model setting of m-partition boards discussed in Section 2. Throughout this section, we shall fix a Ferrers board B = F (b_{1}, b_{2}, …, b_{n}) and a polynomial p(x) = p_{s_{1}}x^{s_{1}} + p_{s_{2}}x^{s_{2}} + ⋯ + p_{s_{y}}x^{s_{y}} ∈ ℕ[x], with 0 ≤ s_{i} < s_{j} for all i < j. We will then define a set of y m-partition boards B(p(x)) := {B^{(s_{1})}, B^{(s_{2})}, …, B^{(s_{y})}}, where B^{(0)} is a degenerate board with n columns. The best way think of B^{(0)} is that this board contains special columns of height 0 into which we allow rooks to be placed, and a more detailed description of the placement rules for such boards will be given in a subsequent section. We will call B(p(x)) the polyboard associated with B and p(x), and we will refer to the board B^{(s_{z})} as the z^{th} subboard of B(p(x)). In Figure 6, we see an example of a polyboard where B = F (1, 2, 3, 5, 5) and p(x) ∈ ℕ[x] is of the form p_{0} + p_{1}x + p_{2}x^{2}. Note that the coefficients of p(x) are irrelevant when constructing B(p(x)).

We wish to consider rook placements in these polyboards, and so we first define C_{(j)}^{z}(B(p(x))) to be the j^{th} column of B^{(s_{z})}, and we will refer to the collection of the j^{th} columns of the y boards in B(p(x)) to be the j^{th} column of B(p(x)), denoted by C_{(j)}(B(p(x))). We also Figure 6: An example of the polyboard B(p(x)), with B = F (1, 2, 3, 5, 5) and p(x) = p_{0} + p_{1}x + p_{2}x^{2}.

let C_{(l,j)}^{z}(B(p(x))) be the l^{th} subcolumn of the j^{th} column of B^{(s_{z})}. If a rook r is placed in column C_{(l,j)}^{z}(B(p(x))) in the t^{th} row from the bottom of B^{(s_{z})}, then we say that r lies in the cell c(z, t, l, j). As a convention, we will say that C_{(l,j)}^{z}(B(p(x))) lies to the right (left) of C_{(l′,j′)}^{z′}(B(p(x))) whenever j > j′ (j < j′), and accordingly, we will refer to the rook which lies in the leftmost column of B(p(x)) as the leftmost rook in the board.

4.2 Poly-Rook & Poly-File Numbers

Given B(p(x)), we shall define both nonattacking and file rook placements in the polyboard. This is best done by analyzing two different cases: p(0) = 0 and p(0) ≠ 0. We begin by studying the case where p(0) = 0, that is, our polyboard has no degenerate board.

4.2.1 \underline{Case I: p(0) = 0}

We now consider placements of nonattacking rooks in B(p(x)). These are placements of rooks such that the following two conditions hold.

(i.) if any rook is placed in the j^{th} column of a subboard, then that may be the only subboard which contains a rooks in its j^{th} column, and

(ii.) within any particular subboard, the nonattacking placement rules from Section 2 apply to that board.

We shall call such a placement of rooks into B(p(x)), in which k columns total among all of the subboards of B(p(x)) contain rooks, a k-placement of nonattacking rooks in B(p(x)). In such a k-placement, cancelation will occur in the following manner:

(i.) If r is the leftmost rook placed in the j^{th} column of the z^{th} subboard of B(p(x)), then r cancels as described in Section 2 within the z^{th} subboard. The rook r will also cancel the lowest cell in each subcolumn to its right in every other subboard in the board B(p(x)), and every cell in the j^{th} column of all other subboards.

(ii.) If r′ is any other rook which has been placed in the w^{th} subboard of B(p(x)), then r′ cancels as described in Section 2 within the w^{th} subboard. The rook r′ will also cancel the lowest cell in each subcolumn to its right, which has not yet been canceled by a rook to its left, in every other subboard in the board B(p(x)), and every cell in the j^{th} column of all other subboards which has yet to be canceled by a rook to its left.

Figure 7: An example of a nonattacking k-placement in the polyboard B(p(x)), with B = F (1, 2, 3, 5, 5), k = 3, and p(x) = p_{1}x + p_{3}x^{3}.

An example of such a placement and the corresponding cancelation can be seen in Figure 7, where B = F (1, 2, 3, 5, 5), k = 3, and p(x) = p_{1}x + p_{3}x^{3}. In this figure, a cell labeled with an “i” has been canceled by the rook labeled as “X_{i}”.

We also consider file placements in the polyboard. These are placements of rooks such that the following two conditions hold.

(i.) if any rook is placed in the j^{th} column of a subboard, then that may be the only subboard which contains rooks in its j^{th} column, and

(ii.) within any particular subboard, the file placement rules from Section 2 apply to that board.

For these placements, any rook which is placed in the j^{th} column of a subboard will cancel all cells in the j^{th} columns of all other subboards. An example of this type of placement can be seen in Figure 8, where again B = F (1, 2, 3, 5, 5), k = 3, and p(x) = p_{1}x + p_{3}x^{3}.

4.2.2 \underline{Case II: p(0) ≠ 0}

We now consider the nonattacking and file placements of rooks in B(p(x)) in the case where our polynomial p(x) ∈ ℕ[x] has a nonzero constant term. For nonattacking configurations, the same placements rules apply as in the case where p(0) = 0, and we will call such a placement of rooks into B(p(x)) in which k columns of B(p(x)) contain rooks a k-placement of nonattacking rooks in B(p(x)). The difference between these two cases lies in the cancelation, which is described here:

(i.) Suppose a rook r is the leftmost rook placed in the C_{(j)}(B(p(x))).

Figure 8: An example of a file k-placement in the polyboard B(p(x)), with B = F (1, 2, 3, 5, 5), k = 3, and p(x) = p_{1}x + p_{3}x^{3}.

a. If r is placed in the j^{th} column of the board B^{(0)}, it cancels no cells in B^{(0)} and it cancels the lowest cell in each subcolumn to its right in each of the other boards. It will also cancel every cell in the j^{th} column of every other subboard of B(p(x)).

b. If r is not placed in the board B^{(0)}, it cancels only the cell in the j^{th} column in B^{(0)} and among the remaining boards it will cancel as described in the case where p(0) = 0.

(ii.) Suppose r′ is any other rook which has been placed in the C_{(i)}^{w}(B(p(x))).

a. If r′ is placed in the board B^{(0)}, it cancels no cells in B^{(0)} and it cancels the lowest cell in each subcolumn to its right, which has yet to be canceled by a rook to its left, in each of the other boards. It will also cancel every cell in the i^{th} column of every other subboard of B(p(x)) which has yet to be canceled by a rook to its left.

b. If r′ is not placed in the board B^{(0)}, it cancels only the cell in the i^{th} column in B^{(0)} and among the remaining boards it will cancel as described in the case where p(0) = 0.

An example of such a placement and the corresponding cancelation can be seen in Figure 9, where B = F (1, 2, 3, 5, 5), k = 3, and p(x) = p_{0} + p_{1}x + p_{3}x^{3}. In this figure, a cell labeled with an “i” has been canceled by the rook labeled as “X_{i}”.

We also consider file placements in the polyboard. These are placements of rooks such that the following two conditions hold.

(i.) If any rook is placed in the j^{th} column of a subboard, then that may be the only subboard which contains rooks in its j^{th} column.

Figure 9: An example a nonattacking k-placement in the polyboard B(p(x)), with B = F (1, 2, 3, 5, 5), k = 3, and p(x) = p_{0} + p_{1}x + p_{3}x^{3}.

Figure 10: An example a file k-placement in the polyboard B(p(x)), with B = F (1, 2, 3, 5, 5), k = 3, and p(x) = p_{0} + p_{1}x + p_{3}x^{3}.

(ii.) Within any particular subboard, the file placement rules from Section 2 apply to that board.

For these placements, any rook which is placed in the j^{th} column of a subboard will cancel all cells in the j^{th} columns of all other subboards. An example of this type of placement can be seen in Figure 10, where again B = F (1, 2, 3, 5, 5), k = 3, and p(x) = p_{0} + p_{1}x + p_{3}x^{3}.

Now, given any p(x) ∈ ℕ[x], we let N_{k,p(x)}(B(p(x))) denote the set of colored nonattacking k-placements in the polyboard B(p(x)) such that that the following two conditions hold.

(i.) The rooks placed in the columns of B^{(s_{z})} are colored with distinct colors, c_{1}, …, c_{p_{sz}}.

(ii.) If any rook placed in the j^{th} column of a subboard is colored with color c_{w}, then every rook placed in the j^{th} column must be colored with c_{w} as well.

We also define F_{k,p(x)}(B(p(x))) to be the set of colored file k-placements in B(p(x)) under the exact same coloring conditions as N_{k,p(x)}(B(p(x))).

We then define

\begin{aligned}r_{k,p(x)}(B(p(x))) & := & |N_{k,p(x)}(B(p(x)))| and \\ f_{k,p(x)}(B(p(x))) & := & |F_{k,p(x)}(B(p(x)))|, \end{aligned}

and we call r_{k,p(x)}(B(p(x))) the k^{th} poly-rook number of B(p(x)) with respect to p(x) and f_{k,p(x)}(B(p(x))) the k^{th} poly-file number of B^{(m)} with respect to p(x).

Next we shall prove some basic properties of the poly-rook and poly-file numbers for polyboards. We begin by showing that these numbers satisfy some simple recursions.

Theorem 4.1. Suppose that B = F (b_{1}, …, b_{n}) and B̄ = F (b_{1}, …, b_{n}, b_{n+1}) are Ferrers boards and let p(x) ∈ ℕ[x]. Then for all 0 ≤ k ≤ n + 1,

r_{k,p(x)}(B̄(p(x)) = r_{k,p(x)}(B(p(x))) + p(b_{n+1} − (k − 1))r_{k−1,p(x)}(B(p(x)))  (4.1)

and

f_{k,p(x)}(B̄(p(x)) = f_{k,p(x)}(B(p(x))) + p(b_{n+1})f_{k−1,p(x)}(B(p(x))).  (4.2)

Proof. For (4.1), we classify the colored nonattacking k-placements in N_{k,p(x)}(B̄(p(x))) according to whether they have rooks in the last column. That is, if ℙ ∈ N_{k,p(x)}(B̄(p(x))) has no rooks in the last column, then ℙ can be viewed as an element of N_{k,p(x)}(B(p(x))) so that such rook placements are counted by r_{k,p(x)}(B(p(x))). If ℙ ∈ N_{k,p(x)}((B̄(p(x))) has rooks in the last column, then let ℙ^{∗} denote the rook placement in N_{k−1,p(x)}(B̄(p(x))) that results from ℙ by removing all the rooks in the last column. Now if we are given such a ℙ^{∗}, we claim that there p(b_{n+1} − (k − 1)) ways to extend ℙ^{∗} to a rook placement in N_{k,p(x)}(B̄(p(x))). That is, in each subcolumn C_{(l,n+1)}, there will k − 1 cells which are canceled by rooks ℙ^{∗}. Thus we have b_{n+1} − (k − 1) choices of where to put a rook in C_{(l,n+1)} to extend ℙ^{∗}. It follows that the number of colored nonattacking rook placements in N_{k,p(x)}(B̄(p(x))) that have rooks in the last column is counted by p(b_{n+1} − (k − 1))r_{k−1,p(x)}(B(p(x))).

Showing that recursion (4.2) holds can be proved in a similar fashion.

It is also worth noting here that Theorem 2.1 follows directly from this theorem by letting p(x) = x^{m} for m ∈ ℕ.

4.3 Polyboards & Poly-Stirling Numbers

We return to the various types of poly-Stirling numbers defined by Equations (1.6), (1.7), and (1.8) in Section 1. In particular, the poly-Stirling numbers of the first kind with respect to p(x), s_{n,k}^{p(x)}, are defined by the following recursion:

s_{0,0}^{p(x)} = 1 and s_{n,k}^{p(x)} = 0 if k < 0 or k > n and
s_{n+1,k}^{p(x)} = s_{n,k−1}^{p(x)} − p(n)s_{n,k}^{p(x)} if 0 ≤ k ≤ n + 1 and n ≥ 0.

We now define s_{n,k}^{p(x)} = (−1)^{n−k}c_{n,k}^{p(x)}. Thus, the integers c_{n,k}^{p(x)}, called the signless poly-Stirling numbers of the first kind with respect to p(x), satisfy the recursion:

c_{0,0}^{p(x)} = 1 and c_{n,k}^{p(x)} = 0 if k < 0 or k > n and
c_{n+1,k}^{p(x)} = c_{n,k−1}^{p(x)} + p(n)c_{n,k}^{p(x)} if 0 ≤ k ≤ n + 1 and n ≥ 0.

Finally, the poly-Stirling numbers of the second kind with respect to p(x), S_{n,k}^{p(x)}, satisfy the following recursion:

S_{0,0}^{p(x)} = 1 and S_{n,k}^{p(x)} = 0 if k < 0 or k > n and
S_{n+1,k}^{p(x)} = S_{n,k−1}^{p(x)} + p(k)S_{n,k}^{p(x)} if 0 ≤ k ≤ n + 1 and n ≥ 0.

Now if we let B = F (0, 1, …, n − 1) and B̄ = F (0, 1, …, n − 1, n) in Theorem 4.1, then we see that

r_{n+1−k,p(x)}(B̄(p(x))) = r_{n+1−k,p(x)}(B(p(x))) + p(k)r_{n−k,p(x)}(B(p(x)))  (4.3)

and

f_{n+1−k,p(x)}(B̄(p(x))) = f_{n+1−k,p(x)}(B(p(x))) + p(n)f_{n−k,p(x)}(B(p(x))).  (4.4)

Thus, we have the following theorem which gives our promised rook theory interpretation for the poly-Stirling numbers.

Theorem 4.2. Let B = F (0, 1, …, n − 1) and let p(x) = ℕ[x]. Then

S_{n,k}^{p(x)} = r_{n−k,p(x)}(B(p(x))),  (4.5)

c_{n,k}^{p(x)} = f_{n−k,p(x)}(B(p(x))),  (4.6)

and

s_{n,k}^{p(x)} = (−1)^{n−k}f_{n−k,p(x)}(B(p(x))).  (4.7)

Corollary 4.3. Given p(x) ∈ ℕ[x], ||S_{n,k}^{p(x)}|| = ||s_{n,k}^{p(x)}||^{−1}.

It is again a direct result of general inversion theorem due to Milne [4] that the matrices formed by poly-Stirling numbers of the first and second kind are inverses of each other; however, we could use our rook theoretic interpretations to give a direct combinatorial proof of this fact using an involution similar to the one given in the proof of Theorem 3.1.

Next we shall prove two general product formulas for poly-rook and poly-file numbers. We will first define two rook settings in order to make these assertions possible, and then these formulas will be specialized to give the analogues of (1.1) and (1.2) for the poly-Stirling numbers. These settings will be generalizations of m-partition boards, augmented boards, and polyboards. We begin with the case of file placements.

Consider the y-tuple of boards B_{x}(p(x)) = {B_{x}^{(s_{1})}, B_{x}^{(s_{2})}, …, B_{x}^{(s_{y})}} for some x ∈ ℕ, where B_{x}^{(s_{u})} is defined in Section 2. If s_{1} = 0, then the board B_{x}^{(0)} will be look like two copies of the board B^{(0)}, one which lies above the bar and one which lies below. That is, the x-part of B_{x}^{(0)} is also degenerate. We will refer to the upper parts of each board as such, and if we talk about the upper part of B_{x}(p(x)), then we are referring to the set of upper parts of each board in B_{x}(p(x)), and we use the same convention when talking about the x-part of B_{x}(p(x)). We then say that the upper part of B_{x}(p(x)) is separated from the x-part of B_{x}(p(x)) by the bar of B_{x}(p(x)). Let F_{n,p(x)}(B_{x}(p(x))) denote the set of colored placements in B_{x}(p(x)) such that that the following four conditions hold.

(i.) Every column of B_{x}(p(x)) must contain a rook.

(ii.) If any rook is placed in the j^{th} column of a subboard of B_{x}(p(x)), then that may be the only subboard which contains rooks in its j^{th} column.

(iii.) Within any particular subboard, the file placement rules from Section 2 apply to that board.

(iv.) The same coloring rules apply as before.

We define that any rook placed in the upper part of the j^{th} column of a subboard of B_{x}(p(x)) will cancel the upper parts of the j^{th} columns of every other subboard in B_{x}(p(x)), and any rook placed in the x-part of the j^{th} column of a subboard of B_{x}(p(x)) will cancel the x-parts of the j^{th} columns of every other subboard in B_{x}(p(x)). An example of this type of placement and the corresponding cancelation can be seen in Figure 11, where B = F (1, 2, 3, 5, 5), p(x) = p_{0} + p_{1}x + p_{3}x^{3}, and x = 5.

Theorem 4.4. Suppose n ∈ ℕ^{0} and p(x) = p_{s_{1}}x^{s_{1}} + p_{s_{2}}x^{s_{2}} + ⋯ + p_{s_{y}}x^{s_{y}} ∈ ℕ[x]. If B = F (b_{1}, b_{2}, …, b_{n}) is a Ferrers board, then

∏_{i=1}^{n}(p(x) + p(b_{i})) = ∑_{k=0}^{n} f_{n−k,p(x)}(B(p(x)))(p(x))^{k}.  (4.8)

Proof. Given a rook board B = F (b_{1}, b_{2}, …, b_{n}) and p(x) ∈ ℕ[x], we fix x ∈ ℕ to show that (4.8) represents two ways to count |F_{n,p(x)}(B_{x}(p(x)))|. We first consider the number of ways that we can place rooks in each column, starting with the leftmost column and working to the right. In the first column of B_{x}(p(x)) there will be x^{s_{1}} + x^{s_{2}} + ⋯ + x^{s_{y}} ways to place rooks below the high bar, and there will be b_{1}^{s_{1}} + b_{1}^{s_{2}} + ⋯ + b_{1}^{s_{y}} ways to place rooks above the high bar. However, the total number of placements is different since we are considering colored placements, and thus the total number of colored placements of rooks below the bar is p_{s_{1}}x^{s_{1}} + p_{s_{2}}x^{s_{2}} + ⋯ + p_{s_{y}}x^{s_{y}} = p(x) and the total number of placements above the bar is p_{s_{1}}b_{1}^{s_{1}} + p_{s_{2}}b_{1}^{s_{2}} + ⋯ + p_{s_{y}}b_{1}^{s_{y}} = p(b_{1}). So, the total number of placements in the first column of B_{x}(p(x)) is p(x) + p(b_{1}). In general, in the j^{th} column of the B_{x}(p(x)), there will be p(x) total colored placements below in the x-parts and p(b_{j}) colored placements above the bar, and thus Figure 11: An example of a file rook placement in B_{5}(p(x)), with B = F (1, 2, 3, 5, 5) and p(x) = p_{0} + p_{1}x + p_{3}x^{3}.

|F_{n,p(x)}(B_{x}(p(x)))| = ∏_{i=1}^{n}(p(x) + p(b_{i})).

Next, suppose that we first fix a placement ℙ ∈ F_{n−k,p(x)}(B(p(x)))) above the bar. We claim that there are (p(x))^{k} ways to extend ℙ to a placement ℚ ∈ F_{n,p(x)}(B_{x}(p(x))) such that ℚ ∩ B(p(x)) = ℙ. That is, we want to count the number of ways to extend ℙ to a placement ℚ ∈ F_{n,p(x)}(B_{x}(p(x))) by placing additional colored rooks below the bar in those columns which contain no rooks from ℙ. Here, we see that for each empty column, there are exactly p(x) ways to place colored rooks in that column. As there are k such columns, we have

|F_{n,p(x)}(B_{x}(p(x)))| = ∑_{k=0}^{n} ∑_{ℙ∈F_{n−k,p(x)}(B(p(x)))}(p(x))^{k}

= ∑_{k=0}^{n} f_{n−k,p(x)}(B(p(x))) (p(x))^{k}.

Note that in the special case of Theorem 4.4 where B = F (0, 1, …, n − 1), we see that Equation (4.8) reduces to

∏_{i=1}^{n}(p(x) + p(i − 1)) = ∑_{k=0}^{n} c_{n,k}^{p(x)}(p(x))^{k}.  (4.9)

If in Equation (4.9) we replace p(x) with −p(x) and multiply both sides by (−1)^{n}, we obtain the following corollary:

Corollary 4.5. For n ∈ ℕ^{0} and p(x) ∈ ℕ[x],

∏_{i=1}^{n}(p(x) − p(i − 1)) = ∑_{k=0}^{n} s_{n,k}^{p(x)}(p(x))^{k}.  (4.10)

Now we will prove a product formula for poly-rook numbers. Consider the y-tuple of boards B_{x}^{aug}(p(x)) = {B_{x}^{aug,(s_{1})}, B_{x}^{aug,(s_{2})}, …, B_{x}^{aug,(s_{y})}} for some x ∈ ℕ, where B_{x}^{aug,(s_{u})} is defined in Section 2. We call B_{x}^{aug}(p(x)) the augmented polyboard with respect to B and p(x). In the case where s_{1} = 0, B_{x}^{aug,(0)} will be the same as B_{x}^{(0)}. That is, B_{x}^{aug,(0)} will consist of a degenerate board and a degenerate x-part, but no lower augmented part. We will refer to the upper parts of each board as such, and if we talk about the upper part of B_{x}^{aug}(p(x)), then we are referring to the set of upper parts of each board in B_{x}^{aug}(p(x)), and we use the same convention when talking about the x-part of B_{x}(p(x)) and the lower augmented part of B_{x}^{aug}(p(x)). We then say that the upper part of B_{x}^{aug}(p(x)) is separated from the x-part of B_{x}^{aug}(p(x)) by the high bar of B_{x}^{aug}(p(x)) and the x-part is separated from the lower augmented part by the low bar of B_{x}^{aug}(p(x)). We allow placements in B_{x}^{aug}(p(x)) such that that the following four conditions hold.

(i.) Every column of B_{x}^{aug}(p(x)) must contain a rook.

(ii.) If any rook is placed in the j^{th} column of a subboard of B_{x}(p(x)), then that may be the only subboard which contains rooks in its j^{th} column.

(iii.) Within any particular subboard, the file placement rules from Section 2 apply to that board.

(iv.) No rook lies in a cell which is canceled by another rook.

Here cancelation in this board is defined as follows.

(i.) Suppose r is a rook placed in the first column of B_{x}^{aug}(p(x)).

a. If r is placed above the high bar in the subboard B_{x}^{aug,s_{w}}, then above the high bar, r will cancel within the upper part of B_{x}^{aug}(p(x)) as described previously (that is, as if there is no x-part or lower augmented part). It will also cancel the lowest cell to its right in each subcolumn of the lower augmented part in each of the other remaining subboards. b. If r is placed in the x-part in the subboard B_{x}^{aug,s_{w}}, then r will cancel the x-parts

in the first column of every other subboard in B_{x}^{aug}(p(x)).

(ii.) Suppose r′ is any other rook which has been placed in the j^{th} column of B_{x}^{aug}(p(x)).

a. If r′ is placed above the high bar in the subboard B_{x}^{aug,s_{u}}, then again, r′ cancels above the high bar in all boards as it would if there were no x-part or lower augmented part. It will also cancel the lowest remaining uncanceled cells to its right in each subcolumn of the lower augmented part in the remaining subboards which have yet to be canceled by a rook to their left.

b. If r′ is placed in the x-part, then r′ will cancel the x-parts in the j^{th} column of every other subboard in B_{x}^{aug}(p(x)).

c. If r′ is placed in the lower augmented part, then r′ cancels all uncanceled cells in the lower augmented parts of the j^{th} columns of the remaining subboards.

Now for any p(x) ∈ ℕ[x], we then let N_{n,p(x)}(B_{x}(p(x))) denote the set of colored placements in B_{x}^{aug}(p(x)) such that the above placement and cancelation rules hold as do the same coloring rules as before. An example of these placement and cancelation rules are illustrated in Figure 12, where B = F (1, 2, 3, 5, 5), p(x) = p_{0} + p_{1}x + p_{3}x^{3}, and x = 3. Finally, we assign to each colored placement of rooks ℙ ∈ N_{n,p(x)}(B_{x}(p(x))) a weight ν(ℙ) = (−1)^{LA(ℙ)}, where LA(ℙ) is the number of columns in ℙ which contain rooks which lie in the lower augmented part of B_{x}^{aug}(p(x)). We are now in a position to prove another product formula, this one involving the poly-rook numbers.

Theorem 4.6. Suppose n ∈ ℕ^{0} and p(x) = p_{s_{1}}x^{s_{1}} + p_{s_{2}}x^{s_{2}} + ⋯ + p_{s_{y}}x^{s_{y}} ∈ ℕ[x]. If B = F (0, 1, …, n − 1) then

(p(x))^{n} = ∑_{k=0}^{n} r_{n−k,p(x)}(B(p(x)))(p(x) − p(0))(p(x) − p(1)) ⋯ (p(x) − p(k − 1)). (4.11)

Proof. Given a rook board B = F (b_{1}, b_{2}, …, b_{n}) and p(x) ∈ ℕ[x], we fix x ∈ ℕ to show that (4.11) represents two ways to enumerate the sum

S(B, p(x)) := ∑_{ℙ∈N_{n,p(x)}(B_{x}^{aug}(p(x)))}ν(ℙ).  (4.12)

First we see that in column 1, there are x^{s_{1}} + x^{s_{2}} + ⋯ + x^{s_{y}} ways to place uncolored rooks, and so there are p(x) total ways to place colored rooks in the first column of our augmented polyboard. Thus for the second column, we have no canceled cells. Hence there are 1^{s_{1}} + 1^{s_{2}} + ⋯ + 1^{s_{y}} = p(1) ways to place colored rooks above the high bar, p(x) colored placements in the x-part, and 1^{s_{1}} + 1^{s_{2}} + ⋯ + 1^{s_{y}} = p(1) colored placements in the lower augmented part. The total weight of these placements is p(1)+p(x)−p(1) = p(x). In general, if we have placed rooks in columns C_{(1)}(B_{x}^{aug,(m)}), …, C_{(t−1)}(B_{x}^{aug,(m)}) where exactly s of the Figure 12: An example of a nonattacking rook placement in B_{3}^{aug}(p(x)), with B = F (1, 2, 3, 5, 5) and p(x) = p_{0} + p_{1}x + p_{3}x^{3}. columns have rooks above the high bar, then there will be t − 1 − s uncanceled cells above the high bar and t−1−s uncanceled cells below the low bar in every subcolumn of column t. That is, in column t there are (t−1−s)^{s_{1}} +(t−1−s)^{s_{2}} +⋯+(t−1−s)^{s_{y}} = p(t−1−s) ways to place colored rooks above the high bar, p(x) ways to place colored rooks in the x-part, and (t − 1 − s)^{s_{1}} + (t − 1 − s)^{s_{2}} + ⋯ + (t − 1 − s)^{s_{y}} = p(t − 1 − s) ways to place colored rooks below the low bar. In such a case, the weights of the rooks in the t^{th} column will contribute p(t − 1 − s) + p(x) − p(t − 1 − s) = p(x) to (4.12). It then follows that S(B, p(x)) = (p(x))^{n}.

Now suppose that we fix a placement ℙ of rooks in n − k columns of B(p(x)). Then we want to count the number of ways extend ℙ to a placement in N_{n,p(x)}(B_{x}^{aug}(p(x))). Let C_{(t_{i})}(B_{x}^{aug}(B(p(x)))) be the i^{th} column, reading left to right, which has no rooks in that column. By construction, t_{1} = 1 so that there are p(x) ways to add rooks below the bar in column C_{(t_{i})}(B_{x}^{aug}(B(p(x)))). For 1 < i ≤ k, there will be t_{i} − (i − 1) columns to the left of C_{(t_{i})}(B_{x}^{aug}(B(p(x)))) which have rooks above the high bar and these rooks will cancel t_{i} − (i − 1) cells in each subcolumn of C_{(t_{i})}(B_{x}^{aug}(B(p(x)))) in the lower augmented part of the B_{x}^{aug}(B(p(x))) and they will cancel no cells in the x-part. Thus, there will be t_{i} − (t_{i} − (i − 1)) = (i − 1) uncanceled cells in each subcolumn of C_{(t_{i})}(B_{x}^{aug}(B(p(x)))) in the lower augmented part of the B_{x}^{aug}(B(p(x))). We then see that if we sum the weights over all possible ways to place colored rooks in column C_{(t_{i})}(B_{x}^{aug}(B(p(x)))) will get p(x) − p(i − 1). It follows that

S(B, p(x)) = ∑_{k=0}^{n} ∑_{ℙ∈N_{n−k,(m)}(B^{(m)})} ∏_{j=1}^{k}(p(x) − p(j − 1))

= ∑_{k=0}^{n} r_{n−k,p(x)}(B(p(x))) ∏_{j=1}^{k}(p(x) − p(j − 1)).

We now have the following product formula involving poly-Stirling numbers of the second kind.

Corollary 4.7. For n ∈ ℕ^{0} and p(x) ∈ ℕ[x],

(p(x))^{n} = ∑_{k=0}^{n} S_{n,k}^{p(x)} ∏_{j=1}^{k}(p(x) − p(j − 1)).  (4.13)

Following the method in Section 2, we can also now prove the following generalization of a well-known formula involving the Stirling numbers of the second kind.

Corollary 4.8. For k ∈ ℕ and p(x) ∈ ℕ[x],

∑_{n≥k} S_{n,k}^{p(x)}t^{n} = \frac{t^{k}}{(1 − p(1)t)(1 − p(2)t) ⋯ (1 − p(k)t)}.

4.4 Set and Cycle Structure Interpretations of p(x)-Stirling Numbers

In this section, we show that p(x)-Stirling numbers have combinatorial interpretations in terms of certain collections of m-tuples of set partitions and cycles. Fix a polynomial p(x) = p_{0} + p_{1}x + ⋯ + p_{m}x^{m} where p_{i} ∈ ℕ^{0} and p_{m} ≠ 0. For each i such that p_{i} > 0, fix a set of colors c_{1,i}, …, c_{p_{i},i}.

We shall start with giving a combinatorial interpretation of S_{n,k}^{p(x)} in terms of certain collections of unordered set partitions in the case where p(0) ≠ 0. For m > 0, let P̄_{n,k}^{(m)} = (P̄^{(1)}, …, P̄^{(m)}) be an m-tuple of unordered set partitions of {0, 1, …, n} into k + 1 parts and let Π̄_{n,k}^{(m)} = {P̄_{n,k}^{(m)} | such that the parts P̄^{(i)} and P̄^{(j)} have the same minimal elements for every 1 ≤ i < j ≤ m}. We set P̄_{n,0} = Π̄_{n,0} = ({0, …, n}) for all n ≥ 0.

We define Θ_{0,0}^{p(x)} = {∅} and Θ_{n,k}^{p(x)} = {∅} if k < 0 or k > n. For n ≥ 1 and 0 ≤ k ≤ n, let Θ_{n,k}^{p(x)} denote the set of sequences (P̄_{n,k}^{(0)}, …, P̄_{n,k}^{(m)}) such that the following conditions hold.

(i.) If p_{i} = 0, then P̄_{n,k}^{(i)} = {∅}.

(ii.) If i > 0 and p_{i} ≠ 0, then P̄_{n,k}^{(i)} consists of an i-tuple of unordered set partitions (Q^{(1,i)}, …, Q^{(i,i)}) ∈ Π̄_{n,k}^{(i)}. In addition, we will color certain elements in the unordered set partitions that appear in P̄_{n,k}^{(i)} according to the following rules.

a. The elements in any unordered set partition that occurs in P̄_{n,k}^{(i)} which lie in the part that contains 0 or are the minimal element in its part are not colored.

b. For each 1 ≤ s ≤ n, if s is not in the part containing 0 and is not a minimal element in its part, then s is colored with the same color from c_{1,i}, …, c_{p_{i},i} in each of the unordered set partitions (Q^{(1,i)}, …, Q^{(i,i)}).

(iii.) P̄_{0,k} consists of the set partition ({0, …, n}) where some of the elements 1, …, n may be colored with one of the colors c_{1,0}, …, c_{p_{0},0}.

(iv.) For each 1 ≤ s ≤ n, if there exists a j ≥ 1 such that s is a colored element in one of the unordered set partitions occurring P̄_{n,k}^{(j)}, then s is in the part that contains 0 in all unordered set partitions that occur in P̄_{n,k}^{(i)} if i ≠ j and p_{i} ≠ 0. Moreover, s is not colored in P_{0,k}.

(v.) The set of common minimal elements in P̄_{n,k}^{(i)} are the same for all 1 ≤ i ≤ m where p_{i} ≠ 0.

(vi.) If s > 0 is not one of the common minimal elements in (P̄_{n,k}^{(0)}, …, P̄_{n,k}^{(m)}), and if s is not always in the set with 0, then in exactly one of the i-tuples P̄_{n,k}^{(i)} where p_{i} ≠ 0, all occurrences of s must be colored.

Theorem 4.9. Let n ∈ ℕ^{0} and let p(x) = p_{0} + p_{1}x + ⋯ + p_{m}x^{m} ∈ ℕ^{0}[x] where p_{0} ≠ 0. Then S_{n,k}^{p(x)} = |Θ_{n,k}^{p(x)}| for every 0 ≤ k ≤ n.

Proof. First observe that |Θ_{n,k}^{p(x)}| = 0 whenever k < 0 or k > n, and Θ_{0,0}^{p(x)} = {∅} so that |Θ_{0,0}^{p(x)}| = S_{0,0}^{p(x)} = 1. We now see that for all n ≥ 0,

S_{n+1,0}^{p(x)} = S_{n,−1}^{p(x)} + p(0)S_{n,0}^{p(x)}

Thus, it follows by induction that S_{n,0}^{p(x)} = p(0)^{n} for all n ≥ 0. Now suppose that (P̄_{n,0}^{(0)}, …, P̄_{n,0}^{(m)}) ∈ Θ_{n,0}^{p(x)}. Then for every j such that p_{j} ≠ 0, all unordered set partitions that appear P̄_{n,0}^{(j)} are just {0, …, n}. Thus if j ≥ 1 and p_{j} ≠ 0, then no elements are colored in P̄_{n,0}^{(j)}. This means that each of 1, 2, …, n must be colored in P̄_{n,0}^{(0)}. Since there are p_{0}^{n} ways to color the elements of P̄_{n,0}^{(0)}, it follows that |Θ_{n,0}^{p(x)}| = p(0)^{n} in this case.

For n = 1,

S_{1,1}^{p(x)} = S_{0,0}^{p(x)} + p(1)S_{0,1}^{p(x)} = 1.

In this case our definitions ensure that if (P̄_{n,0}^{(0)}, …, P̄_{n,0}^{(m)}) ∈ Θ_{1,1}^{p(x)}, then for every j such that p_{j} ≠ 0, every unordered set partition that occurs in P̄_{n,0}^{(j)} is just {0}, {1}. Thus no elements are allowed to be colored and hence |Θ_{1,1}^{p(x)}| = 1.

Proceeding by induction, we pick n > 1 and assume that |Θ_{n,k}^{p(x)}| = S_{n,k}^{p(x)} for every 0 ≤ k ≤ n. Now suppose that k ≥ 1 and (P̄_{n+1,k}^{(0)}, …, P̄_{n+1,k}^{(m)}) ∈ Θ_{n+1,k}^{p(x)}. Then if {n + 1} is a part in one of the unordered set partitions that occur in (P̄_{n+1,k}^{(1)}, …, P̄_{n+1,k}^{(m)}), then {n + 1} is a part in every unordered set partition that occurs in (P̄_{n+1,k}^{(1)}, …, P̄_{n+1,k}^{(m)}). Moreover it must be the case that n + 1 is not colored in P̄_{n+1,k}^{(0)}. It then follows that if we remove {n + 1} from every unordered set partition which occurs in (P̄_{n+1,k}^{(1)}, …, P̄_{n+1,k}^{(m)}) and we remove n + 1 from P̄_{n+1,k}^{(0)}, then we will obtain an element of Θ_{n,k−1}^{p(x)}.

If {n+1} is never a part in any of the unordered set partitions which occur in (P̄_{n+1,k}^{(0)}, …, P̄_{n+1,k}^{(m)}), then for all j > 0 such that p_{j} ≠ 0, n + 1 is not a minimal element in its part in any of the unordered set partitions that occur in P̄_{n+1,k}^{(j)} for any j with p_{j} ≠ 0. This means that we can remove n + 1 from all such unordered set partitions and end up with an element of Θ_{n,k}^{p(x)}. However, if we start with an element (Q̄_{n,k}^{(0)}, …, Q̄_{n,k}^{(m)}), we can create an element (P̄_{n+1,k}^{(0)}, …, P̄_{n+1,k}^{(m)}) ∈ Θ_{n+1,k}^{p(x)} by picking an i > 0 such that p_{i} ≠ 0 and a color c_{s,i} where 1 ≤ s ≤ p_{i}, and adding n + 1 colored with c_{s,i} to one of the existing parts, other than the part that contains 0, in each of the unordered set partitions in Q̄_{n,k}^{(i)}. Since we have k choices for each of the unordered set partitions in the i-tuple Q̄_{n,k}^{(i)}, there will be p_{i}k^{i} ways to do this. Then for each j ≠ i, we are forced to put n + 1 the part containing 0 in each of the unordered set partitions which occurs in Q̄_{n,k}^{(j)}. Moreover, n + 1 must be uncolored in Q̄_{n,k}^{(0)}. The only other way that we can create an element (P̄_{n+1,k}^{(0)}, …, P̄_{n+1,k}^{(m)}) ∈ Θ_{n+1,k}^{p(x)} from (Q̄_{n,k}^{(0)}, …, Q̄_{n,k}^{(m)}) is to color n + 1 in Q̄_{n,k}^{(0)} with one of the colors c_{1,0}, …, c_{p_{0},0}. In that case, we must add n + 1 to the part containing 0 in all unordered set partitions that occur in the i-tuple Q̄_{n,k}^{(i)} where i > 0 and p_{i} ≠ 0. Thus we have an additional p_{0} ways to create an element (P̄_{n+1,k}^{(0)}, …, P̄_{n+1,k}^{(m)}) ∈ Θ_{n+1,k}^{p(x)} from (Q̄_{n,k}^{(0)}, …, Q̄_{n,k}^{(m)}). It follows that

|Θ_{n+1,k}^{p(x)}| = |Θ_{n,k−1}^{p(x)}| + (∑_{j=0}^{m} p_{j}k^{j})|Θ_{n,k}^{p(x)}|
= S_{n,k−1}^{p(x)} + p(k)S_{n,k}^{p(x)}
= S_{n+1,k}^{p(x)}.

As an example of this type of object, notice that we can compute S_{3,2}^{(x^{2}+2x+1)} = 14, and thus there are fourteen elements, listed below, in the set Θ_{3,2}^{(x^{2}+2x+1)}. That is, there are 14 triples of set partitions of {0, 1, 2, 3} into 2 + 1 = 3 parts such which satisfy the above conditions. For clarity, suppose that we can color elements from our partition corresponding to P̄_{3,2}^{(0)} with the color yellow (Y), elements from the partition corresponding to P̄_{3,2}^{(1)} with either the color red (R) or the color blue (B), and elements corresponding to P̄_{3,2}^{(2)} with the color green (G). We will denote an element E colored with the color C by E_{C}.

{0, 1, 2, 3} | {0, 1}{2}{3} | ({0, 1}{2}{3}, {0, 1}{2}{3}),
{0, 1, 2_{Y} , 3} | {0, 2}{1}{3} | ({0, 2}{1}{3}, {0, 2}{1}{3}),
{0, 1_{Y} , 2, 3} | {0, 1}{2}{3} | ({0, 2}{1}{3}, {0, 2}{1}{3}),
{0, 1_{Y} , 2, 3} | {0, 1}{2}{3} | ({0, 2}{1}{3}, {0, 2}{1}{3}),
{0, 1_{Y} , 2, 3} | {0, 1}{2}{3} | ({0}{1, 2_{G}}{3}, {0}{1, 2_{G}}{3}),
{0, 1_{Y} , 2, 3} | {0, 3}{1}{2} | ({0}{1}{2, 3_{G}}, {0}{1}{2, 3_{G}}),
{0, 1_{Y} , 2, 3} | {0, 3}{1}{2} | ({0}{1}{2, 3_{G}}, {0}{1, 3_{G}}{2}),
{0, 1_{Y} , 2, 3} | {0, 3}{1}{2} | ({0}{1, 3_{G}}{2}, {0}{1}{2, 3_{G}}),
{0, 1_{Y} , 2, 3} | {0, 3}{1}{2} | ({0}{1, 3_{G}}{2}, {0}{1, 3_{G}}{2}),
{0, 1_{Y} , 2, 3} | {0}{1, 3_{B}}{2} | ({0, 3}{1}{2}, {0, 3}{1}{2}),
{0, 1_{Y} , 2, 3} | {0}{1, 3_{R}}{2} | ({0, 3}{1}{2}, {0, 3}{1}{2}),
{0, 1_{Y} , 2, 3} | {0}{1}{2, 3_{B}} | ({0, 3}{1}{2}, {0, 3}{1}{2}),
{0, 1_{Y} , 2, 3} | {0}{1}{2, 3_{R}} | ({0, 3}{1}{2}, {0, 3}{1}{2}),
{0, 1_{Y} , 2, 3_{Y} } | {0, 3}{1}{2} | ({0, 3}{1}{2}, {0, 3}{1}{2}).

Now if p_{0} = 0, then for all n ≥ 0,

S_{n+1,0}^{p(x)} = S_{n,−1}^{p(x)} + p(0)S_{n,0}^{p(x)} = 0.

In this case, we let Θ̄_{n,k}^{p(x)} be the set of elements of (P_{n,k}^{(0)}, …, P_{n,k}^{(m)}) ∈ Θ_{n,k}^{p(x)} so no element s ≥ 1 that lies in P_{n,0}^{(0)} is colored. By our argument in the proof of Theorem 4.9, this forces Θ̄_{n,0}^{p(x)} = {∅} for all n > 0 so that S_{n,0}^{p(x)} = |Θ̄_{n,0}^{p(x)}|. Then, essentially the same argument that we used to prove Theorem 4.9 will prove the following theorem.

Theorem 4.10. Let n ∈ ℕ^{0} and let p(x) = p_{1}x + ⋯ + p_{m}x^{m} ∈ ℕ^{0}[x]. Then S_{n,k}^{p(x)} = |Θ̄_{n,k}^{p(x)}| for every 0 ≤ k ≤ n.

Next we will give a combinatorial interpretation of c_{n,k}^{p(x)} in terms of certain collection of permutations in the case where p(0) ≠ 0.

Let C̄_{n,k}^{(m)} be the set of m-tuples of permutations of {0, 1, …, n} into k + 1 cycles and let Γ̄_{n,k}^{(m)} denote the sequences (σ^{(1)}, …, σ^{(m)}) ∈ C̄_{n,k}^{(m)} such that the set of minimal elements of the cycles of σ^{(i)} are the same for all i.

We define Δ_{0,0}^{p(x)} = {∅} and Δ_{n,k}^{p(x)} = ∅ if k < 0 or k > n. For n ≥ 1 and 0 ≤ k ≤ n, let Δ_{n,k}^{p(x)} denote the set of sequences (C̄_{n,k}^{(0)}, …, C̄_{n,k}^{(m)}) such that the following conditions hold.

(i.) If p_{i} = 0, then C̄_{n,k}^{(i)} = {∅}.

(ii.) If i > 0 and p_{i} ≠ 0, then C̄_{n,k}^{(i)} is an i-tuple of permutations (σ^{(1,i)}, …, σ^{(i,i)}) ∈ Γ̄_{n,k}^{(i)}. In addition, we will color certain of the elements that occur in the permutations in C̄_{n,k}^{(i)} according to the following rules.

a. For each 1 ≤ j ≤ i, the minimal elements in each cycle σ^{(j,i)} are not colored and 1 is not colored.

b. For each 1 ≤ s ≤ n, if s is not a minimal element in its cycle and is not in the cycle that contains 0, then s is colored with a fixed color from c_{1,i}, …, c_{p_{i},i} in each of the permutations (σ^{(1,i)}, …, σ^{(i,i)}). In addition, if s is in a cycle (0, b_{1}, …, b_{r}) that contains 0 and s is colored, then s cannot be b_{1} and s is colored with a fixed color from c_{1,i}, …, c_{p_{i},i} in each of the permutations (σ^{(1,i)}, …, σ^{(i,i)}).

(iii.) C̄_{0,k} consists of the cycle (0, …, n) where some of the elements 1, …, n may be colored with one of the colors c_{1,0}, …, c_{p_{0},0}

(iv.) For each 1 ≤ s ≤ n, if there exists a j such that s is a colored in some permutation in C̄_{n,k}^{(j)}, then s is in the cycle of the form (0, a_{1}, …, a_{r}) in all C̄_{n,k}^{(i)} such that i ≠ j and p_{i} ≠ 0 where s is not colored. Moreover, if s = a_{t}, then any occurrence of 1, …, s − 1 in that cycle must be among a_{1}, …, a_{t−1}. If j ≠ 0, then s is also not colored in C̄_{n,k}^{(0)}.

(v.) The set of common minimal elements in a cycle of the permutations that occur in C̄_{n,k}^{(i)} are the same for all 1 ≤ i ≤ m where p_{i} ≠ 0 and they are never colored.

(vi.) If s > 0 is not one of the common minimal elements in (C̄_{n,k}^{(0)}, …, C̄_{n,k}^{(m)}), , and if s is not always in the set with 0, then then in exactly one of the i-tuples C̄_{n,k}^{(i)} where p_{i} ≠ 0, all occurrences of s must be colored.

Theorem 4.11. Let n ∈ ℕ^{0} and let p(x) = p_{0} + p_{1}x + ⋯ + p_{m}x^{m} ∈ ℕ^{0}[x] where p_{0} ≠ 0 Then c_{n,k}^{p(x)} = |Δ_{n,k}^{p(x)}| for every 0 ≤ k ≤ n.

Proof. First observe that |Δ_{n,k}^{p(x)}| = 0 whenever k < 0 or k > n, and Δ_{0,0}^{p(x)} = {∅} so that |Δ_{0,0}^{p(x)}| = c_{0,0}^{p(x)} = 1.

For n = 1,

c_{1,1}^{p(x)} = c_{0,0}^{p(x)} + p(0)S_{0,1}^{p(x)} = 1.

In this case our definitions ensure that if (C̄_{1,1}^{(0)}, …, C̄_{1,1}^{(m)}) ∈ Δ_{1,1}^{p(x)}, then for every j such that p_{j} ≠ 0, every permutation that occurs in C̄_{1,1}^{(j)} is just (0)(1). Thus, no elements are allowed to be colored and hence |Δ_{1,1}^{p(x)}| = 1. Next

c_{1,0}^{p(x)} = c_{0,−1}^{p(x)} + p(0)S_{0,0}^{p(x)} = p_{0}.

In this case our definitions ensure that if (C̄_{1,0}^{(0)}, …, C̄_{1,0}^{(m)}) ∈ Δ_{1,0}^{p(x)}, then for every j such that p_{j} ≠ 0, every permutation that occurs in C̄_{1,0}^{(j)} is just (0, 1). Now 1 cannot be colored in any permutation that occurs in C̄_{1,0}^{(i)} for any i > 0 where p_{i} ≠ 0. Thus the only element that can be colored is the 1 which occurs in the permutation (0, 1) in C̄_{1,0}^{(0)}. Since we can color the 1 in p_{0} ways, it follows that |Δ_{1,0}^{p(x)}| = p(0).

Note that for all n ≥ 1,

c_{n+1,0}^{p(x)} = c_{n,−1}^{p(x)} + p(n)c_{n,0}^{p(x)}

Thus, it follows by induction that c_{n,0}^{p(x)} = p(0)p(1) ⋯ p(n − 1) for all n ≥ 1. Now assume by induction that |Δ_{n,0}^{p(x)}| = p(0)p(1) ⋯ p(n − 1) and suppose that (C̄_{n,0}^{(0)}, …, C̄_{n,0}^{(m)}) ∈ Δ_{n,0}^{p(x)}. By definition, C̄_{n,0}^{(0)} consists of the n + 1-cycle (0, 1, …, n) and for all i > 0 where p_{i} ≠ 0, C̄_{n,0}^{(i)} consists of an i-tuple (σ^{(1,i)}, …, σ^{(i,i)}) where each σ^{(j,i)} is an n + 1-cycle (0, α_{1}^{(j,i)}, …, α_{n}^{(j,i)}). We can then create an element of Δ_{n+1,0}^{p(x)} from (C̄_{n,0}^{(0)}, …, C̄_{n,0}^{(m)}) in two different ways. First we can add a colored version of n + 1 at the end of the cycle (0, 1, …, n) in C̄_{n,0}^{(0)}. Then we are forced by condition (iv.) of our general definition of Δ_{n,k}^{p(x)} to add an uncolored version of n + 1 at the end of every cycle in C̄_{n,0}^{(i)} for all i such that p_{i} ≠ 0. There are p_{0} ways to do this depending on which color we use for n + 1 when we add n + 1 at then end of the cycle in C̄_{n,0}^{(0)}. The other way we can create an element of Δ_{n+1,0}^{p(x)} from (C̄_{n,0}^{(0)}, …, C̄_{n,0}^{(m)}) is to pick an i > 0 where p_{i} ≠ 0 and a color c_{t,i} from c_{1,i}, …, c_{p_{i},i} and insert n + 1 colored with c_{t,i} immediately after some element from 1, …, n in the each of the cycles σ^{(1,i)}, …, σ^{(i,i)} that occur in C̄_{n,0}^{(i)}. Note we cannot insert this colored version of n + 1 immediately after 0 in any of the cycles by condition (ii.)b. of our definition of Δ_{n,k}^{p(x)}. We are then forced to add an uncolored version of n + 1 at the end of every cycle that occurs in C̄_{n,0}^{(j)} where j ≠ i. It follows that there are n different ways to insert the colored version of n + 1 in each of the cycles σ^{(1,i)}, …, σ^{(i,i)} so that there are a total of p_{i}n^{i} ways to do this. It follows that there p_{0} + ∑_{i=1}^{n} p_{i}n^{i} = p(n) ways to create a new element of Δ_{n+1,0}^{p(x)} from (C̄_{n,0}^{(0)}, …, C̄_{n,0}^{(m)}). Finally, it is easy to check that if we start with an element of Δ_{n+1,0}^{p(x)} and remove n + 1 from each of the (n + 2)-cycles that occur in that element, we we end up with an element of Δ_{n,0}^{p(x)}. Thus, it follows that

|Δ_{n+1,0}^{p(x)}| = p(n)|Δ_{n,0}^{p(x)}| = p(0) ⋯ p(n)

as desired.

Proceeding by induction, we will pick n > 1 and assume that |Δ_{n,k}^{p(x)}| = c_{n,k}^{p(x)} for every 0 ≤ k ≤ n. Now suppose that k ≥ 1 and (C̄_{n+1,k}^{(0)}, …, C̄_{n+1,k}^{(m)}) ∈ Δ_{n+1,k}^{p(x)}. Then if (n + 1) is a cycle in one of the permutations that occur in (C̄_{n+1,k}^{(1)}, …, C̄_{n+1,k}^{(m)}), then (n + 1) is a cycle in every permutation that occurs in (C̄_{n+1,k}^{(1)}, …, C̄_{n+1,k}^{(m)}). Moreover, it must be the case that n + 1 is not colored in C̄_{n+1,k}^{(0)}. It then follows that if we remove the cycle (n + 1) from every permutation which occurs in (C̄_{n+1,k}^{(1)}, …, C̄_{n+1,k}^{(m)}) and we remove n + 1 from the (n + 2)-cycle in C̄_{n+1,k}^{(0)}, then we will obtain an element of Δ_{n,k−1}^{p(x)}. If (n + 1) is never a cycle in any of the permutations which occur in (C̄_{n+1,k}^{(0)}, …, C̄_{n+1,k}^{(m)}), then for all j > 0 such that p_{j} ≠ 0, n + 1 is not a minimal element in its cycle in any of the permutations that occur in P_{n+1,k}^{(j)}. This means that we can remove n + 1 from every permutation that occurs in (C̄_{n+1,k}^{(0)}, …, C̄_{n+1,k}^{(m)}), and end up with an element of Δ_{n,k}^{p(x)}. We can create an element of Δ_{n+1,k}^{p(x)} from (C̄_{n,k}^{(0)}, …, C̄_{n,k}^{(m)}) ∈ Δ_{n,k}^{p(x)} in two different ways. First, we can add a colored version of n+1 at the end of the cycle (0, 1, …, n) in C̄_{n,k}^{(0)} so that we are forced by condition (iv.) of our definitions of Δ_{n+1,k}^{p(x)} to add an uncolored version of n + 1 at the end of every cycle in C̄_{n,k}^{(i)} for all i such that p_{i} ≠ 0. There are p_{0} ways to do this depending on which color we use for n + 1 when we add n + 1 at then end of the cycle in C̄_{n,k}^{(0)}. The other way we can create an element of Δ_{n+1,k}^{p(x)} from (C̄_{n,k}^{(0)}, …, C̄_{n,k}^{(m)}) is to pick an i > 0 where p_{i} ≠ 0 and a color c_{t,i} from c_{1,i}, …, c_{p_{i},i} and insert n + 1 colored with c_{t,i} immediately after some element from 1, …, n in the cycle structures of the permutations σ^{(1,i)}, …, σ^{(i,i)}. Note we cannot insert this colored version of n + 1 immediately after 0 in any of the cycles by condition (ii.)b. of our definition of Δ_{n,k}^{p(x)}. We are then forced to add an uncolored version of n + 1 at the end of every cycle that occurs in C̄_{n,0}^{(j)} where j ≠ i. It follows that there are n different ways to insert the colored version of n + 1 in each of the cycles of σ^{(1,i)}, …, σ^{(i,i)} so that there are a total of p_{i}n^{i} ways to do this. It follows that there p_{0} + ∑_{i=1}^{n} p_{i}n^{i} = p(n) ways to create a new element of Δ_{n+1,k}^{p(x)} from (C̄_{n,k}^{(0)}, …, C̄_{n,k}^{(m)}), and so

|Δ_{n+1,k}^{p(x)}| = |Δ_{n,k−1}^{p(x)}| + p(n)|Δ_{n,0}^{p(x)}|
= c_{n,k−1}^{p(x)} + p(n)c_{n,k}^{p(x)}
= c_{n+1,k}^{p(x)}

as desired.

Now if p_{0} = 0, then for all n ≥ 0,

c_{n+1,0}^{p(x)} = p(0) ⋯ p(n) = 0.

In this case, we let Δ̄_{n,k}^{p(x)} be the set of elements of (C̄_{n,k}^{(0)}, …, C̄_{n,k}^{(m)}) ∈ Δ_{n,k}^{p(x)} so that no element s ≥ 1 that occurs in n + 1-cycle in C̄_{n,k}^{(0)} is colored. By our argument in the proof of Theorem 4.11, this forces Δ̄_{n,0}^{p(x)} = {∅} for all n > 0 so that c_{n,0}^{p(x)} = |Δ̄_{n,0}^{p(x)}|. Then, essentially the same argument that we used to prove Theorem 4.11 will prove the following theorem. Theorem 4.12. Let n ∈ ℕ^{0} and let p(x) = p_{1}x + ⋯ + p_{m}x^{m} ∈ ℕ^{0}[x]. Then c_{n,k}^{p(x)} = |Δ̄_{n,k}^{p(x)}| for every 0 ≤ k ≤ n.

5 Q-Analogues of Poly-Stirling Numbers

For any positive integer x we can define the q-analogue of x to be

[x]_{q} = 1 + q + q^{2} + ⋯ + q^{x−1} = \frac{1 − q^{x}}{1 − q} .

There are two natural q-analogues of the numbers described in Section 4, namely, we can take the q-analogue of p(x) to be either p([x]_{q}) or [p(x)]_{q}. Thus, for example, we can define the q-analogues of s_{n,k}^{p(x)} and S_{n,k}^{p(x)} by the following recursions:

s_{0,0}^{p(x)}(q) = 1 and s_{n,k}^{p(x)}(q) = 0 if k < 0 or k > n, and  (5.1)
s_{n+1,k}^{p(x)}(q) = s_{n,k−1}^{p(x)}(q) − p([n]_{q})s_{n,k}^{p(x)}(q) if 0 ≤ k ≤ n + 1 and n ≥ 0,

and

S_{0,0}^{p(x)}(q) = 1 and S_{n,k}^{p(x)}(q) = 0 if k < 0 or k > n, and  (5.2)
S_{n+1,k}^{p(x)}(q) = S_{n,k−1}^{p(x)}(q) + p([k]_{q})S_{n,k}^{p(x)}(q) if 0 ≤ k ≤ n + 1 and n ≥ 0.

However, we can define a second q-analogue of s_{n,k}^{p(x)} and S_{n,k}^{p(x)} by the following recursions:

s̄_{0,0}^{p(x)}(q) = 1 and s̄_{n,k}^{p(x)}(q) = 0 if k < 0 or k > n, and  (5.3)
s̄_{n+1,k}^{p(x)}(q) = s̄_{n,k−1}^{p(x)}(q) − [p(n)]_{q}s̄_{n,k}^{p(x)}(q) if 0 ≤ k ≤ n + 1 and n ≥ 0,

and

S̄_{0,0}^{p(x)}(q) = 1 and S̄_{n,k}^{p(x)}(q) = 0 if k < 0 or k > n, and  (5.4)
S̄_{n+1,k}^{p(x)}(q) = S̄_{n,k−1}^{p(x)}(q) + [p(k])]_{q}S̄_{n,k}^{p(x)}(q) if 0 ≤ k ≤ n + 1 and n ≥ 0.

It can be shown how to find appropriate q-statistics related to the m-boards considered in Section 2 to give combinatorial interpretations of both s_{n,k}^{p(x)}(q) and S_{n,k}^{p(x)}(q) and s̄_{n,k}^{p(x)}(q) and S̄_{n,k}^{p(x)}(q). This will be the subject of future papers.

References

[1] A. M. Garsia and J. B. Remmel, Q-counting rook configurations and a formula of Frobenius, J. Combin. Theory Ser. A 41 (1986), 246–275.

[2] H. G. Gould, The q-Stirling numbers of the first and second kinds, Duke Math. J. 28 (1961), 281–289.

[3] B. K. Miceli and J. Remmel, Augmented rook boards and general product formulas, Electron. J. Combin., 15 (1) (2008), Paper #R85. Available at

    http://www.combinatorics.org/Volume 15/Abstracts/v15i1r85.html .

[4] S. C. Milne, Inversion properties of triangular arrays of numbers, Analysis 1 (1981), 1–7.

[5] J. Riordan, Combinatorial Identities, Wiley, New York, 1968.

[6] R. Stanley, Enumerative Combinatorics: Volume II, Cambridge, 1999

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05E05. Keywords: rook theory, rook placement, Stirling numbers, inverses.

Received September 8 2009; revised version received February 26 2010. Published in Journal of Integer Sequences, February 26 2010.

Return to Journal of Integer Sequences home page.