Two q-Analogues of 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 develop two q-analogues of the previously defined poly-Stirling numbers of the first and second kinds. We also develop the corresponding q-rook theory models to give combinatorial interpretations to these numbers.

1 Introduction

Define ℕ = {1, 2, 3, …} and ℕ^{0} = ℕ ∪ {0}. Given any nonzero p(x) ∈ ℕ^{0}[x], Miceli [2] defines generalizations of Stirling numbers, called poly-Stirling numbers with respect to p(x). Poly-Stirling numbers of the first kind, s_{n,k}^{p(x)}, are defined by the recursions

s_{n+1,k}^{p(x)} = s_{n,k−1}^{p(x)} − p(n)s_{n,k}^{p(x)}  (1)

where s_{0,0}^{p(x)} = 1 and s_{n,k}^{p(x)} = 0 if either k < 0 or k > n. Similarly, poly-Stirling numbers of the second kind, S_{n,k}^{p(x)}, are defined by the recursions

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

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

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

where c_{0,0}^{p(x)} = 1 and c_{n,k}^{p(x)} = 0 if either k < 0 or k > n. We can see that in the case where p(x) = x, the generalized numbers reduce to the classical Stirling numbers. In the case where p(x) = x^{2}, these numbers are the triangle central factorial numbers, discussed in both Riordan [5] and Stanley [6].

For any 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 now are two natural q-analogues of the poly-Stirling numbers, namely, we can take the q-analogue of p(x) to be either p([x]_{q}) or [p(x)]_{q}. Accordingly, we define the Type I q-analogues of s_{n,k}^{p(x)} and S_{n,k}^{p(x)} by the following recursions:

s_{n+1,k}^{p(x)}(q) = s_{n,k−1}^{p(x)}(q) − p([n]_{q})s_{n,k}^{p(x)}(q), and  (4)
S_{n+1,k}^{p(x)}(q) = S_{n,k−1}^{p(x)}(q) + p([k]_{q})S_{n,k}^{p(x)}(q)  (5)

if 0 ≤ k ≤ n + 1 with s_{0,0}^{p(x)}(q) = S_{0,0}^{p(x)}(q) = 1 and s_{n,k}^{p(x)}(q) = S_{n,k}^{p(x)}(q) = 0 if k < 0 or k > n. We also define the Type II q-analogues of s_{n,k}^{p(x)} and S_{n,k}^{p(x)} by the following recursions:

s̄_{n+1,k}^{p(x)}(q) = s̄_{n,k−1}^{p(x)}(q) − [p(n)]_{q}s̄_{n,k}^{p(x)}(q), and  (6)
S̄_{n+1,k}^{p(x)}(q) = S̄_{n,k−1}^{p(x)}(q) + [p(k)]_{q}S̄_{n,k}^{p(x)}(q)  (7)

if 0 ≤ k ≤ n + 1 with s̄_{0,0}^{p(x)}(q) = S̄_{0,0}^{p(x)}(q) = 1 and s̄_{n,k}^{p(x)}(q) = S̄_{n,k}^{p(x)}(q) = 0 if k < 0 or k > n.

The goal of this paper is to define two methods for q-counting in the rook theory setting of polyboards, and to use those methods to give combinatorial interpretations for Type I and Type II poly-Stirling numbers of the first and second kind. In Section 2, we summarize the results in Miceli [2], where the author describes the general setting of m-partition boards, polyboards, poly-rook and file numbers, and poly-Stirling numbers. Section 2 is given for completeness, and accordingly, a reader who is familiar with the results in Miceli [2] may wish to begin with Section 3, where the two q-rook models are described. The first model describes q-counting in polyboards when the q-analogue of p(x) is taken to be p([x]_{q}), and the second rook model describes q-counting in polyboards when the q-analogue of p(x) is taken to be [p(x)]_{q}.

2 Polyboards, rook placements, and poly-Stirling numbers

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 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

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

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. We also define B^{(0)} to be a degenerate board, that is, a board with n “special” columns of height 0; these will be columns that, although they have height 0, can still have rooks placed into them, and further descriptions will be given later.

2.1 m-Partition boards

Miceli [2] defines two kinds of rook placements in the board B^{(m)} which mirror those found in Garsia and Remmel [1]: nonattacking placements and file placements. We let N_{k,(m)}(B^{(m)}) denote the set of placements of mk nonattacking rooks in B^{(m)}. These are placements 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 of a given column.

(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 cell t of the l^{th} subcolumn of any column.

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 it is the case that 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_{i} and we have placed an i in the cells that are canceled by those rooks of the same subscript. Note that since rooks only cancel Figure 2: Nonattacking and file rook placements in the board B^{(2)}, with B = F (0, 1, 3, 4, 4).

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 file rooks in B^{(m)}. These are placements 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 of a given column.

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

r_{k,(m)}(B^{(m)}) := |N_{k,(m)}(B^{(m)})| and
f_{k,(m)}(B^{(m)}) := |F_{k,(m)}(B^{(m)})|,

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)}.

Defined in this way, it is shown in [2] that these numbers satisfy some simple recursions.

Theorem 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)})  (8)

and

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

From here, it is shown that when B = F (0, 1, 2, …, n−1), the m-rook and m-file numbers of B correspond to poly-Stirling numbers with respect to p(x) = x^{m}. We call such poly-Stirling number x^{m}-Stirling numbers, and we have the following rook theory interpretation for the x^{m}-Stirling numbers.

Figure 3: 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}.

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

S_{n,k}^{x^{m}} = r_{n−k,(m)}(B^{(m)}),
c_{n,k}^{x^{m}} = f_{n−k,(m)}(B^{(m)}), and
s_{n,k}^{x^{m}} = (−1)^{n−k}f_{n−k,(m)}(B^{(m)}).

2.2 Polyboards

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 define a set of y m-partition boards B(p(x)) := {B^{(s_{1})}, B^{(s_{2})}, …, B^{(s_{y})}}. We call B(p(x)) the polyboard associated with B and p(x), and we refer to the board B^{(s_{z})} as the z^{th} subboard of B(p(x)). In Figure 3, 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)), although the coefficients of p(x) are important in how we enumerate rook placements in this setting.

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 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 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 refer to the rook which lies in the leftmost column of B(p(x)) as the leftmost rook in the board.

2.3 Poly-rook numbers, poly-file numbers, and poly-Stirling numbers

Given B(p(x)), we shall define both nonattacking and file rook placements in the polyboard. Nonattacking rook placements in B(p(x)) 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.

(ii.) Within any particular subboard, the nonattacking placement rules from Section 2.1 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, cancellation will occur in the following manner:

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

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 r cancels as described in Section 2.1 within the z^{th} subboard. Among the remaining boards, r will 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.) 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 r′ cancels as described in Section 2.1 within the w^{th} subboard. Among the remaining boards, r′ will 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.

An example of such a placement and the corresponding cancellation can be seen in Figure 4, 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 X_{i}.

File rook placements in B(p(x)) 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.

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

Figure 4: 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_{0} + p_{1}x + p_{3}x^{3}.

Figure 5: 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}.

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 5, where again B = F (1, 2, 3, 5, 5), k = 3, and p(x) = p_{0} + p_{1}x + p_{3}x^{3}.

Given any nonzero p(x) ∈ ℕ^{0}[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 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 placements with rooks in k of the columns of B(p(x)) under the exact same coloring conditions as placements in N_{k,p(x)}(B(p(x))). We shall call such a placement of rooks a colored file k-placement.

We then define

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)))|,

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).

Using these definitions, we have the following theorem.

Theorem 3. Suppose that B = F (b_{1}, …, b_{n}) and B̄ = F (b_{1}, …, b_{n}, b_{n+1}) are Ferrers boards and consider a nonzero p(x) ∈ ℕ^{0}[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)))  (10)

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))).  (11)

From here, it is shown that when B = F (0, 1, 2, …, n − 1), the poly-rook and poly-file numbers of B(p(x)) with respect to p(x) correspond to poly-Stirling numbers with respect to p(x) in the following way.

Theorem 4. 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))),
c_{n,k}^{p(x)} = f_{n−k,p(x)}(B(p(x))), and
s_{n,k}^{p(x)} = (−1)^{n−k}f_{n−k,p(x)}(B(p(x))).

To get generalized product formulae for the poly-Stirling numbers, two special types of rooks boards are defined. For the first, consider the y-tuple of boards B_{x}(p(x)) = {B_{x}^{(s_{1})}, B_{x}^{(s_{2})}, …, B_{x}^{(s_{y})}}, where given x ∈ ℕ, B_{x}^{(s_{u})} is the board B^{(s_{u})} with x rows of n columns appended below such that each column is partitioned into s_{u} columns. We call this appended portion the x-part and the imaginary line that separates the original board from x-part is called the bar. We define c_{x}(t, l, j) to be the cell which is in the t^{th} row, reading from bottom to top, of the x-part in the l^{th} subcolumn of the j^{th} column. 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 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, 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, and otherwise, all m rooks in that column lie in the x-part. The same file placement rules from Section 2.1 apply to the upper and x-parts, respectively.

(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 cancellation can be seen in Figure 6, where B = F (1, 2, 3, 5, 5), p(x) = p_{0} + p_{1}x + p_{3}x^{3}, x = 6, and the rook denoted by X_{i} cancels the cells labeled with an i.

By counting |F_{n,p(x)}(B_{x}(p(x)))| in two different ways, we get the following theorem.

Theorem 5. Suppose n ∈ ℕ 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 any 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}.  (12)

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

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

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

Figure 6: An example of a file rook placement in B_{6}(p(x)), with B = F (1, 2, 3, 5, 5) and p(x) = p_{0} + p_{1}x + p_{3}x^{3}.

Corollary 6. 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}.  (14)

Our second type of rook board allows us to obtain a product formula for poly-rook numbers, which in turn gives a product formula for poly-Stirling number of the second kind. Consider the board B_{x}^{aug,(m)} [2], a modification of the augmented rook boards originally defined by Miceli and Remmel [3]. To construct these boards, we first we start with the board B_{x}^{(m)}. Then B_{x}^{aug,(m)} is formed by adding, below the x-part of B_{x}^{(m)}, columns of heights 0, 1 …, n − 1, reading from left to right, that consist of m subcolumns. We call the extra cells that we added to B_{x}^{(m)} to form B_{x}^{aug,(m)} the augmented part of B_{x}^{aug,(m)} and call the line that separates the x-part and the augmented part of B_{x}^{aug,(m)} the low bar. We define c_{a}(t, l, j) to be the cell which is in the t^{th} row, reading from top to bottom, of the augmented part in the l^{th} subcolumn of the j^{th} column. For example, we have pictured such an augmented board on the left in Figure 7, where B = F (0, 1, 3, 3, 4), m = 2, and x = 3. In particular, B_{x}^{aug,(0)} will be similar to B_{x}^{(0)}, that is, B_{x}^{aug,(0)} will consist of a degenerate board, a degenerate x-part, and a degenerate augmented part.

We define a nonattacking rook placement ℙ of mn rooks in B_{x}^{aug,(m)} to be a placement such that the following three conditions hold.

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

(ii.) Rooks that are placed in either the x-part or the lower augmented part of B_{x}^{aug,(m)} do not cancel any cells.

Figure 7: 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.

(iii.) If r is a rook placed in the cell c(t, l, j) in the upper part of B_{x}^{aug,(m)}, then r will cancel all the cells in the upper part 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 cancellation, we have pictured an element of N_{n,(m)}(B_{x}^{aug,(m)}) in the righthand side of Figure 7. 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)}.

Now, 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})}}, called the augmented polyboard with respect to B and p(x). 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)). Next we define a nonattacking rook placement ℙ in B_{x}^{aug}(p(x)) such that the following three 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 following rules are observed.

a. There is at most one rook in each subcolumn.

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

c. No rook lies in a cell which is canceled by another rook.

Figure 8: 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}.

Here cancellation 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 nonzero p(x) ∈ ℕ^{0}[x], we then let N_{n,p(x)}(B_{x}^{aug}(p(x))) denote the set of colored placements in B_{x}^{aug}(p(x)) such that the above placement and cancellation rules hold as do the same coloring rules as before. An example of these placement and cancellation rules is illustrated in Figure 8, 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}^{aug}(p(x))) a weight of (−1)^{LA(ℙ)}, where LA(ℙ) is the number of columns in ℙ that contain rooks which lie in the lower augmented part of B_{x}^{aug}(p(x)). This model, combined with Theorem 4, gives the following result.

Theorem 7. Suppose n ∈ ℕ 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) is any Ferrers board, then

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

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

3 Two q-analogues

To begin, we recall that [0]_{q} = 0 and for any n ∈ ℕ,

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

Now, assume that we have the single-column Ferrers board B = F (b_{1}) and that p(x) = x. Then we can define, for any placement ℙ of a single rook in this board, the statistic w(ℙ) = Figure 9: q-counting, where the sum over all placements in K(B) with B = F (5) is q^{4} + q^{3} + q^{2} + q^{1} + q^{0} = [5]_{q}.

q^{γ(ℙ)}, where γ(ℙ) is the number of cells which lie above the rook in ℙ. If we set K(B) to be the set of all rook placements in B, then

W (B) = ∑_{ℙ∈K(B)}w(ℙ) = [b_{1}]_{q}.

An example of this can be seen in Figure 9, where b_{1} = 5. This method of q-counting generalizes further, where if B = F (b_{1}) and p(x) = cx^{m} ∈ ℕ[x] with m ≥ 1, then W (B) = c[b_{1}]_{q}^{m} = p([b_{1}]_{q}).

3.1 Type I q-counting in polyboards

In this section we describe the first of our two q-analogues. Here, given a nonzero p(x) ∈ ℕ^{0}[x], we define the type I q-analogue of p(x) to be p([x]_{q}). Suppose that we are given a placement ℙ ∈ F_{k,p(x)}(B(p(x))), and let r denote the collection of rooks which have been placed in the j^{th} column of the board s_{z}. We then write r = r^{(z,j,s_{z})}, and we define the q-weight of r by

g(r, q) := q^{α(r)},

where α(r) is the number of cells in B(p(x)) that lie directly above the rooks of r. We then define the q-weight of ℙ to be

G(ℙ, q) := ∏_{r∈ℙ}g(r, q).

An illustration of this type of q-counting can be seen in Figure 10, where the same placement is used as in Figure 5. Here we see that, when looking at rooks from left to right, ℙ has a q-weight of

G(ℙ, q) = g(r^{(2,1,1)}, q) g(r^{(3,3,2)}, q) g(r^{(1,4,1)}, q)
= (1)(q)(1)
= q.

Figure 10: q-counting in the board B(p(x)), with the same placement as in Figure 5. Here the q-weight is (1)(q)(1) = q.

We then define the k^{th} type I q-poly-file number of B(p(x)) to be

f_{k,p(x)}(B(p(x)), q) := ∑_{ℙ∈F_{k,p(x)}(B(p(x)))}G(ℙ, q).  (16)

Now suppose that we are given a placement ℙ ∈ F_{n,p(x)}(B_{x}(p(x))). We write r = r^{(z,j,s_{z})_{x}} denote the collection of rooks which have been placed the x-part in the j^{th} column of the board s_{z}, and we will define, for each rook r ∈ ℙ, the q-weight of r by

g_{x}(r, q) := q^{α_{x}(r)},

where

(i.) α_{x}(r) is the number if uncanceled cells which lie directly above r if r is not in the x-part of B_{x}(p(x)), and

(ii.) α_{x}(r) is the number if uncanceled cells which lie directly above r but below the bar if r is in the x-part of B_{x}(p(x)).

The q-weight of ℙ is then defined to be

G_{x}(ℙ, q) := ∏_{r∈ℙ}g_{x}(r, q).

This q-counting in the board B_{x}(p(x)) is pictured in Figure 11, where the placement shown has, when looking at the rooks from left to right, a q-weight of

G_{x}(ℙ, q) = g_{x}(r^{(2,1,1)}, q) g_{x}(r^{(1,2,1)_{x}}, q) g_{x}(r^{(3,3,2)}, q) g_{x}(r^{(1,4,1)}, q) g_{x}(r^{(3,5,2)_{x}}, q)
= (1)(1)(q)(1)(q^{5})
= q^{6}.

Figure 11: q-counting in the board B_{x}(p(x)), with the same placement as in Figure 6. Here the q-weight is (1)(1)(q)(1)(q^{5}) = q^{6}.

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

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

Proof. Given p(x) and a Ferrers board B = F (b_{1}, b_{2}, …, b_{n}), define

S_{q}(B_{x}(p(x))) := ∑_{ℙ∈F_{n,p(x)}(B_{x}(p(x)))}G_{x}(ℙ, q).

We first consider the number of ways that we can place rooks in each column of B_{x}(p(x)), 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 in the x-part, and there will be b_{1}^{s_{1}} + b_{1}^{s_{2}} + ⋯ + b_{1}^{s_{y}} ways to place rooks in the upper part. The total q-weight for all of these placements would be

([x]_{q}^{s_{1}} + [x]_{q}^{s_{2}} + ⋯ + [x]_{q}^{s_{y}}) + ([b_{1}]_{q}^{s_{1}} + [b_{1}]_{q}^{s_{2}} + ⋯ + [b_{1}]_{q}^{s_{y}})

if these placements were uncolored. Coloring the placements leads to the total q-weight of

(a_{s_{1}}[x]_{q}^{s_{1}} +a_{s_{2}}[x]_{q}^{s_{2}} +⋯+a_{s_{y}}[x]_{q}x^{s_{y}})+(a_{s_{1}}[b_{1}]_{q}^{s_{1}} +a_{s_{2}}[b_{1}]_{q}^{s_{2}} +⋯+a_{s_{y}}[b_{1}]_{q}^{s_{y}}) = p([x]_{q})+p([b_{1}]_{q})

in the first column of B_{x}(p(x)). In general, since no rook cancels to its right, the j^{th} column of the B_{x}(p(x)) will get a total q-weight of p([x]_{q}) + p([b_{j}]_{q}), giving that

S_{q}(B_{x}(p(x))) = ∏_{i=1}^{n}(p([x]_{q} + p([b_{i}]_{q})).

Figure 12: q-counting in the board B(p(x)), with the same placement as in Figure 4. Here the q-weight is (1)(1)(q^{3}) = q^{3}.

Next, suppose that we first fix a colored n − k-file placement W ∈ F_{n−k,p(x)}(B(p(x))). Then the q-weight of W is G(W, q). We wish to extend W to a colored placement ℙ in F_{n,p(x)}(B_{x}(p(x))), that is, ℙ ∩ B(p(x)) = W. To do this, we will place rooks in the remaining columns of the x-part of B_{x}(p(x)) which do not already contain rooks from W. In each of these columns there will be x^{s_{1}} + x^{s_{2}} + ⋯ + x^{s_{y}} ways to place rooks, each with a q-weight of p([x]_{q}). As there are k such empty columns, we have

S_{q}(B_{x}(p(x))) = ∑_{k=0}^{n} ∑_{W ∈F_{n−k,p(x)}(B(p(x)))} G(W, q)p([x]_{q})^{k}

= ∑_{k=0}^{n} p([x]_{q})^{k} ∑_{W ∈F_{n−k,p(x)}(B(p(x)))} G(W, q)

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

which is the desired result.

Suppose that we are given a placement ℙ ∈ N_{k,p(x)}(B(p(x))). We define the q-weight of r by

h(r, q) := q^{β(r)},

where β(r) is the number of uncanceled cells which lie above the rooks of r.

We then define the q-weight of ℙ to be

H(ℙ, q) := ∏_{r∈ℙ}h(r, q).

In Figure 12, which is the identical placement to Figure 4, we see that the placement shown has a q-weight, when looking at rooks from left to right, of

H(ℙ, q) = h(r^{(2,1,1)}, q) h(r^{(1,3,0)}, q) h(r^{(3,4,2)}, q)
= (1)(1)(q^{3})
= q^{3}.

We then define the k^{th} type I q-poly-rook number of B(p(x)) to be

r_{k,p(x)}(B(p(x)), q) := ∑_{ℙ∈N_{k,p(x)}(B(p(x)))}H(ℙ, q).  (18)

Now suppose that we are given a colored placement ℙ ∈ N_{n,p(x)}(B_{x}^{aug}(p(x))). We define r = r^{(z,j,s_{z})_{a}} to denote that the rooks lie in the augmented part of the board, and we set, for each r ∈ ℙ, the q-weight of r to be

h_{x}(r, q) = q^{β_{x}^{aug}(r)},

where

(i.) β_{x}^{aug}(r) is equal to β(r) if r is above the high bar in B_{x}^{aug}(p(x)),

(ii.) β_{x}^{aug}(r) is equal to the number of uncanceled cells directly above the rooks in r but below the high bar if r is in the x-part of B_{x}^{aug}(p(x)), and

(iii.) β_{x}^{aug}(r) is equal to the number of uncanceled cell directly above a rook in r but below the low bar if r is in the augmented part of B_{x}^{aug}(p(x)).

Using this weighting scheme we set the q-weight of ℙ to be

H_{x}(ℙ, q) = (−1)^{LA(ℙ)} ∏_{r∈ℙ}h_{x}(r, q),

where again, LA(ℙ) is the number of columns of B_{x}^{aug}(p(x)) which contain rooks from ℙ below the low bar. This type of q-counting in the board B_{x}^{aug}(p(x)) can be seen in Figure 13, where the placement shown has q-weight

H_{x}(ℙ, q) = (−1)^{LA(ℙ)}h_{x}(r^{(1,1,0)_{x}}, q) h_{x}(r^{(2,2,1)}, q) h_{x}(r^{(3,3,3)_{x}}, q) h_{x}(r^{(2,4,1)}, q) h_{x}(r^{(2,5,1)_{a}}, q)
= (−1)^{1}(1)(q)(q^{2})(q^{2})(q)
= −q^{6}.

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

(p([x]_{q}))^{n} = ∑_{k=0}^{n} r_{n−k,p(x)}^{aug}(B(p(x)), q) ∏_{i=1}^{k}(p([x]_{q}) − p([i − 1]_{q})).  (19)

Figure 13: q-counting in the board B_{3}^{aug}(p(x)), with the same placement as in Figure 8. Here the q-weight is −q^{6}.

Proof. Given p(x) and the Ferrers board B = F (0, 1, …, n − 1), define

T_{q}(B_{x}^{aug}(p(x))) := ∑_{ℙ∈N_{n,p(x)}(B_{x}^{aug}(p(x)))}H_{x}(ℙ, q).

We see that in the first column of B_{x}^{aug}(p(x)) there are x^{s_{1}} + x^{s_{2}} + ⋯ + x^{s_{y}} ways to place uncolored rooks in the x-part, and so once we color the rooks and assign a q-weight, these placements contribute a total q-weight of p([x]_{q}) to T_{q}(B_{x}^{aug}(p(x))). By construction, rooks not placed in the x-part of the first column may only be placed in a degenerate board (if there is one), and so there are always p(0) possible ways to place colored rooks both above the high bar and in the augmented part of B_{x}^{aug}(p(x)). These both contribute a total q-weight of p(0) = p([0]_{q}) to T_{q}(B_{x}^{aug}(p(x))), although the rooks placed below the low bar are weight by LA(ℙ). Thus, the total q-weight over all placements in the first column of B_{x}^{aug}(p(x)) is p([x]_{q}) + p([0]_{q}) − p([0]_{q}) = p([x]_{q}). In general, if we have placed rooks in the first t − 1 columns of B_{x}^{aug}(p(x)) such that 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 every subcolumn of column t. That is, in column t there are a_{1}(t − 1 − s)^{s_{1}} + a_{2}(t − 1 − s)^{s_{2}} + ⋯ + a_{y}(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 a_{1}(t − 1 − s)^{s_{1}} + a_{2}(t − 1 − s)^{s_{2}} + ⋯ + a_{y}(t − 1 − s)^{s_{y}} = p(t − 1 − s) ways to place colored rooks below the low bar. In such a case, the q-weights over all possible placements in the t^{th} column of B_{x}^{aug}(p(x)) will contribute p([x]_{q}) + p([t − 1 − s]_{q}) − p([t − 1 − s]_{q}) = p([x]_{q}) to T_{q}(B_{x}^{aug}(p(x))). It then follows that

T_{q}(B_{x}^{aug}(p(x))) = (p([x]_{q}))^{n}.

Now suppose that we fix a colored (n − k)-nonattacking rook placement V in the upper part of B_{x}^{aug}(p(x)). Then we want to count the number of ways extend V to a placement in N_{n,p(x)}(B_{x}^{aug}(p(x))). Let C_{(t_{i})}(B_{x}^{aug}(p(x))) be the i^{th} column of B_{x}^{aug}(p(x)), reading left to right, which has no rooks from V in that column. Then for 1 ≤ i ≤ k, there will be t_{i} − i columns to the left of C_{(t_{i})}(B_{x}^{aug}(p(x))) which have rooks above the high bar and these rooks will cancel t_{i} − i cells in each subcolumn of C_{(t_{i})}(B_{x}^{aug}(p(x))) in the lower augmented part of the B_{x}^{aug}(p(x)). Thus, there will be t_{i} − 1 − (t_{i} − i) = (i − 1) uncanceled cells in each subcolumn of C_{(t_{i})}(B_{x}^{aug}(p(x))) in the lower augmented part of the B_{x}^{aug}(p(x)), contributing a total q-weight of −p([i−1]_{q}) to T_{q}(B_{x}^{aug}(p(x))). Moreover, the rooks from V will not cancel any cells in the x-part of this column, and so the colored rook placements from rooks placed in the x-part contribute a total q-weight of p([x]_{q}) to T_{q}(B_{x}^{aug}(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}(p(x))) will get p([x]_{q} − p([i − 1]_{q}). It follows that

T_{q}(B_{x}^{aug}(p(x))) = ∑_{k=0}^{n} ∑_{V ∈N_{n−k,p(x)}(B(p(x)))} H(V, q) ∏_{i=1}^{k}(p([x]_{q}) − p([i − 1]_{q}))

= ∑_{k=0}^{n} ∏_{i=1}^{k}(p([x]_{q}) − p([i − 1]_{q})) ∑_{V ∈N_{n−k,p(x)}(B(p(x))))} H(V, q)

= ∑_{k=0}^{n} (∏_{i=1}^{k}(p([x]_{q}) − p([i − 1]_{q}))) r_{n−k,p(x)}^{aug}(B(p(x)), q),

which is the desired result.

3.2 Type I q-poly-Stirling numbers

In this section we will study the polynomials defined by the recursions

S_{0,0}^{p(x)}(q) = 1 and S_{n,k}^{p(x)}(q) = 0 if k < 0 or k > n and  (20)
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.

We will call these numbers the Type I q-poly Stirling numbers of the second kind. We then define the numbers

s_{0,0}^{p(x)}(q) = 1 and s_{n,k}^{p(x)}(q) = 0 if k < 0 or k > n and  (21)
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.

We will call these numbers the Type I q-poly Stirling numbers of the first kind. If we now replace s_{n,k}^{p(x)}(q) with (−1)^{(n−k)}c_{n,k}^{p(x)}(q), then we have the numbers which satisfy the recursion

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

and we will call these numbers the signless Type I q-poly Stirling numbers of the first kind.

Theorem 10. Let n ∈ ℕ^{0} and consider a nonzero p(x) ∈ ℕ^{0}[x]. If B = F (0, 1, …, n − 1), then, for every 0 ≤ k ≤ n,

c_{n,k}^{p(x)}(q) = f_{n−k,p(x)}(B(p(x)), q).  (23)

Proof. We see that f_{0−0,p(x)}(B(p(x)), q) = f_{0,p(x)}(B(p(x)), q) = 1 = c_{0,0}^{p(x)}(q). Now, we proceed by induction and consider the boards B = F (0, 1, …, n − 1) and \overline{B} = F (0, 1, …, n − 1, n). Then f_{n+1−k,p(x)}(\overline{B}(p(x)), q) gives the total q-weight over all possible colored (n + 1 − k)- placements of file rooks in the board \overline{B}(p(x)). Now, all rooks could be placed in the first n columns, and the total q-weight over those placements is given by f_{n+1−k,p(x)}(B(p(x)), q). Otherwise, there is a rook placed in the last column of \overline{B}(p(x)). In this case, there are rooks placed in n − k of the first n columns of \overline{B}(p(x)), and those rooks contribute a total q-weight of f_{n−k,p(x)}(B(p(x)), q). Since the rooks placed in the last column of \overline{B}(p(x)) can be placed in any of the subboards, each of which has a last column with height n (except possibly a degenerate board), those rooks will contribute a q-weight of p([n]_{q}) to the total weight of these placements. Thus,

f_{n+1−k,p(x)}(\overline{B}(p(x)), q) = f_{n+1−k,p(x)}(B(p(x)), q) + p([n]_{q})f_{n−k,p(x)}(B(p(x)), q)
= c_{n,k−1}^{p(x)}(q) + p([n]_{q})c_{n,k}^{p(x)}(q), by induction
= c_{n+1,k}^{p(x)}(q).

Combining this result with Theorem 8, we have the product formula

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

If we then replace p([x]_{q}) in the above equation with −p([x]_{q}) and multiply both sides by (−1)^{n}, we get

∏_{i=1}^{n}(p([x]_{q}) − p([i − 1]_{q})) = ∑_{k=0}^{n} s_{n,k}^{p(x)}(q)(p([x]_{q}))^{k}  (25)

Now, we can apply Milne Inversion [4] to show that the matrices ||S_{n,k}^{p(x)}(q)|| and ||s_{n,k}^{p(x)}(q)|| are inverses of one another, which also leads to the product formula

(p([x]_{q}))^{n} = ∑_{k=0}^{n} S_{n,k}^{p(x)}(q) ∏_{j=1}^{k}(p([x]_{q}) − p([j − 1]_{q})),  (26)

although this formula also arises as a corollary to Theorem 9 and the following theorem.

Theorem 11. Let n ∈ ℕ^{0} and consider a nonzero p(x) ∈ ℕ^{0}[x]. If B = F (0, 1, …, n − 1), then, for every 0 ≤ k ≤ n,

S_{n,k}^{p(x)}(q) = r_{n−k,p(x)}^{aug}(B(p(x)), q).  (27)

Proof. We see that r_{0−0,p(x)}^{aug}(B(p(x)), q) = r_{0,p(x)}^{aug}(B(p(x)), q) = 1 = S_{0,0}^{p(x)}(q). Now, we proceed by induction and consider the boards B = F (0, 1, …, n − 1) and \overline{B} = F (0, 1, …, n − 1, n). Then r_{n+1−k,p(x)}^{aug}(\overline{B}(p(x)), q) gives the total q-weight over all possible colored (n + 1 − k)-placements of nonattacking rooks in the board \overline{B}(p(x)). Now, all rooks could be placed in the first n columns, and the total q-weight over those placements is given by r_{n+1−k,p(x)}^{aug}(B(p(x)), q). Otherwise, there is a rook placed in the last column of \overline{B}(p(x)). In this case, there are nonattacking rooks placed in n − k of the first n columns of \overline{B}(p(x)), and those rooks contribute a total q-weight of r_{n−k,p(x)}^{aug}(B(p(x)), q). Then, the last column in each of the subboards of \overline{B}(p(x)) has height n (except possibly a degenerate board), and n − k cells have been canceled in each subcolumn of the last column of each board in \overline{B}(p(x)). So, there are n − (n − k) = k available cells in each subcolumn of the final column of \overline{B}(p(x)), giving that the rooks placed in the last column of \overline{B}(p(x)) will contribute a q-weight of p([k]_{q}) to the total weight of our (n + 1 − k)-placement. Thus,

r_{n+1−k,p(x)}^{aug}(\overline{B}(p(x)), q) = r_{n+1−k,p(x)}^{aug}(B(p(x)), q) + p([k]_{q})r_{n−k,p(x)}^{aug}(B(p(x)), q)
= S_{n,k−1}^{p(x)}(q) + p([k]_{q})S_{n,k}^{p(x)}(q), by induction
= S_{n+1,k}^{p(x)}(q).

Using the recursions given above, the following is a generalization of a well-known generating function for the Stirling numbers of the second kind.

Theorem 12. For any k ≥ 1,

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

Proof. Let ϕ_{k}(t, q) = ∑_{n≥k} S_{n,k}^{p(x)}(q)t^{n}. From our combinatorial interpretation we see that the only way to have an n-placement in B_{x}^{aug}(p(x)), where B = F (0, 1, …, n − 1), is to place every rook at the top of its column. So, for all n ∈ ℕ, S_{n,1}^{p(x)}(q) = p(1) = p([1]_{q}), giving

ϕ_{1}(t, q) = \frac{t}{(1 − p([1]_{q})t)}. Using our recursion for S_{n,k}^{p(x)}(q) we obtain

ϕ_{k}(t, q) = ∑_{n≥k} S_{n,k}^{p(x)}(q)t^{n}
= ∑_{n≥k}(S_{n−1,k−1}^{p(x)}(q) + p([k]_{q})S_{n−1,k}^{p(x)}(q))t^{n}
= ∑_{n≥k} S_{n−1,k−1}^{p(x)}(q)t^{n} + ∑_{n≥k} p([k]_{q})S_{n−1,k}^{p(x)}(q)t^{n}
= tϕ_{k−1}(t, q) + tp([k]_{q})ϕ_{k}(t, q).

Thus, ϕ_{k}(t, q) = (\frac{t}{(1 − p([k]_{q})t)}) ϕ_{k−1}(t, q), and our result follows by induction.

3.3 Type II q-counting in polyboards

Here, given a nonzero p(x) ∈ ℕ^{0}[x], we define the type II q-analogue of p(x) to be [p(x)]_{q}. We can express the polynomial [p(x)]_{q} in various forms. Recall that for nonnegative integers x and a, we have the identity [x + a]_{q} = [x]_{q} + q^{x}[a]_{q}. As an example, consider the type II q-analogue of the polynomial p(x) = x^{3} + 2x + 4. We rewrite [p(x)]_{q} as

[x^{3} + 2x + 4]_{q} = [x^{3} + 2x]_{q} + q^{x^{3}+2x}[4]_{q}
= [x^{3}]_{q} + q^{x^{3}}[2x]_{q} + q^{x^{3}+2x}[4]_{q}
= [x^{3}]_{q} + q^{x^{3}}(1 + q^{x})[x]_{q} + q^{x^{3}+2x}(1 + q + q^{2} + q^{3})[1]_{q}.

So, we see that the q-analogue of p(x) is a weighted sum of q-analogues of monomials. Using this fact, we can q-count both non-attacking and file placements of rooks in the polyboard if we can determine how to modify our q-counting techniques for m-partition boards, then we can extend those results to polyboards by appropriately weighting the cells in each of the boards of B(p(x)) with extra factors of q. We call this type-II q-counting, and this alternative way of q-counting rook and file placements is best explained by through an example. For the purposes of this section, as we will primarily be dealing with single m-partition boards, we will denote C_{(j)}(B^{(m)}) by C_{j}, as no confusion should arise as to which column we are referring.

Suppose we have a Ferrers board B = F (1, 2, 2, 4, 5) and a placement ℙ ∈ N_{2,(3)}(B^{(3)}), as in Figure 14, where the rooks are placed in columns C_{i_{1}} = C_{2} and C_{i_{2}} = C_{4}.

Step 1: We remove all of the rooks of ℙ from B^{(m)}, and we number each subcolumn of B^{(m)}, from top to bottom, with the digits 0, 1, 2, …, b_{n} − 1, as in Figure 15.

Figure 14: A placement of non-attacking rooks in two columns of B^{(3)} with B = F (1, 2, 2, 4, 5).

Figure 15: Step 1: A numbering of the blank board B^{(3)} with B = F (1, 2, 2, 4, 5).

Step 2: We will place the rooks which were in column C_{i_{1}} = C_{2} of the original placement in B^{(m)} back into the numbered board, and cancel in the normal way. We will then note which numbers were in the cells now filled by these m rooks. Supposing the numbers are, reading from left to right, a_{1}, a_{2}, …, a_{m}, we will assign these rooks a q-weight of ν_{C}(C_{i_{1}}, q) = q^{(a_{1}a_{2}···a_{m})_{b_{i_{1}}}} , where (a_{1}a_{2} ⋯ a_{n})_{p} is the p-ary digit a_{1}(p^{n−1}) + a_{2}(p^{n−2}) + ⋯ + a_{n}(p^{0}). In this case, the rooks placed in column C_{i_{1}} give us a q-weight of ν_{C}(C_{i_{1}}, q) = q^{(100)_{2}} = q^{1(4)+0(2)+0(1)} = q^{4}. We will then renumber the remaining uncanceled cells in the columns to the right of C_{i_{1}} as we did in Step 1. This step can be seen in Figure 16.

Step 3: Now we will place the rooks back into column C_{i_{2}}, which here is the fourth column of B^{(m)}. We then assign those rooks a q-weight of ν_{C}(C_{i_{2}}, q) = q^{(a_{1}a_{2}···a_{m})_{b_{i_{2}} −1}}, again reading the a_{i} from left to right. Here the rooks in the fourth column of B^{(m)} will be assigned a q-weight of ν_{C}(C_{i_{2}}, q) = q^{(102)_{4−1}} = q^{(102)_{3}} = q^{1(9)+0(3)+2(1)} = q^{11}. This step can be seen in Figure 17.

Step 4: In general, we will, after replacing the rooks in a given column C_{i_{w}}, give those rooks a q-weight of ν_{C}(C_{i_{w}}, q) := q^{(a_{1}a_{2}···a_{m})_{b_{iw} −(w−1)}}. We will then define the type-II q-weight of the original placement ℙ ∈ N_{k,(m)}(B^{(m)}) to be

ν(ℙ, q) := ∏_{w=1}^{k} ν_{C}(C_{i_{w}}, q).

Thus, the placement in Figure 14 has a type-II q-weight of Figure 16: Step 2: We begin to place the original rooks back into the board B^{(m)}, and we keep track of the numbers in those cells, which are, reading from left to right: 1, 0, 0. We then assign a q-weight to those rooks, and renumber uncanceled cells to the right of those rooks.

Figure 17: Step 3: We repeat Step 2 for the rooks in column C_{4}.

ν(ℙ, q) = ∏_{w=1}^{2} ν_{C}(C_{i_{w}}, q) = ν_{C}(C_{2}, q)ν_{C}(C_{4}, q) = q^{4}q^{11} = q^{15}.

We now define the k^{th} type-II qm-rook number of B^{(m)} to be

\overline{r}_{k,(m)}(B^{(m)}, q) := ∑_{ℙ∈N_{k,(m)}(B^{(m)})}ν(ℙ, q).  (29)

There are also analogous file numbers, which can be defined in a very similar way to the rook numbers. Given an m-file placement in the board B^{(m)} with rooks placed in the cells c(a_{1}, 1, i_{w}), c(a_{2}, 2, i_{w}), …, c(a_{m}, m, i_{w}) of the column C_{i_{w}}, we define

μ_{C}(C_{i_{w}}, q) := q^{(a_{1}a_{2}···a_{m})_{b_{iw}}} .

Then, given any placement ℙ ∈ F_{k,(m)}(B^{(m)}), we define the type-II q-weight of ℙ to be

μ(ℙ, q) := ∏_{w=1}^{k} μ_{C}(C_{i_{w}}, q).

We then define the k^{th} type II-qm-file number of B^{(m)} to be

\overline{f}_{k,(m)}(B^{(m)}, q) := ∑_{ℙ∈F_{k,(m)}(B^{(m)})}μ(ℙ, q).  (30)

Figure 18: An example of a q-count for a file rook placement ℙ ∈ F_{k,(m)}(B^{(m)}), where B = (0, 1, 2, 4, 5, 5). This placement has a q-weight of q^{120}.

An example of this q-weighting can be seen in Figure 18, and the placement shown has a type-II q-weight of

μ(ℙ, q) = q^{(101)_{2}}q^{(221)_{5}}q^{(204)_{5}} = q^{5}q^{61}q^{54} = q^{120}.

Using these definitions, one could prove that these type-II qm-rook and file numbers satisfy some simple recursions, much like in Theorem 1.

Theorem 13. 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,

\overline{r}_{k,(m)}(B̄^{(m)}, q) = \overline{r}_{k,(m)}(B^{(m)}, q) + [(b_{n} − (k − 1))^{m}]_{q}\overline{r}_{k−1,(m)}(B^{(m)}, q)  (31)

and

\overline{f}_{k,(m)}(B̄^{(m)}, q) = \overline{f}_{k,(m)}(B^{(m)}, q) + [(b_{n})^{m}]_{q}\overline{f}_{k−1,(m)}(B^{(m)}, q),  (32)

where \overline{r}_{0,(m)}(B^{(m)}, q) = \overline{f}_{0,(m)}(B^{(m)}, q) = 1 and \overline{r}_{k,(m)}(B^{(m)}, q) = \overline{f}_{k,(m)}(B^{(m)}, q) = 0 if k < 0 or k > n.

We now further generalize this notion of type-II q-counting to include rook placements in our more generalized boards. To begin, suppose that ℙ ∈ F_{n,(m)}(B_{x}^{(m)}) and define

M_{B_{x}^{(m)}}(ℙ, q) := ∏_{j=1}^{n} M_{C,B_{x}^{(m)}}(C_{j}, q),

where we define M_{C,B_{x}^{(m)}}(C_{j}, q) as follows.

(i.) If the m rooks in C_{j} lie in the cells c(a_{1}, 1, j), c(a_{2}, 2, j), …, c(a_{m}, m, j), then M_{C,B_{x}^{(m)}}(C_{j}, q) =

μ_{C}(C_{j}, q) = q^{(a_{1}a_{2}···a_{m})_{b_{j}}}.

(ii.) If the m rooks in C_{j} lie in the cells c_{x}(a_{1}, 1, j), c_{x}(a_{2}, 2, j), …, c_{x}(a_{m}, m, j), then M_{C,B_{x}^{(m)}}(C_{j}, q) = q^{(d_{1}d_{2}···d_{m})_{x}}, where d_{i} = a_{i} − 1.

Figure 19: An example of a q-count for a file rook placement ℙ ∈ F_{6,(3)}(B_{x}^{(3)}), where B = (0, 1, 2, 4, 5, 5) and x = 5. This placement has a q-weight of q^{273}.

An example of this type of q-weighting can be seen in Figure 19, where the same board and placement as in Figure 18 is used above the bar. Here,

M_{B_{5}^{(3)}}(ℙ, q) = ∏_{j=1}^{6} M_{C,B_{5}^{(3)}}(C_{j}, q)
= q^{(232)_{5}}q^{(012)_{5}}q^{(101)_{2}}q^{(304)_{5}}q^{(221)_{5}}q^{(204)_{5}}
= q^{67}q^{7}q^{5}q^{79}q^{61}q^{54}
= q^{273}.

Theorem 14. Suppose x, n ∈ ℕ^{0}. If B = F (b_{1}, b_{2}, …, b_{n}) is any Ferrers board, then

∏_{i=1}^{n}([x^{m}]_{q} + [b_{i}^{m}]_{q}) = ∑_{k=0}^{n} \overline{f}_{n−k,(m)}(B^{(m)}, q)([x^{m}]_{q})^{k}.  (33)

Proof. Given a Ferrers board B = F (b_{1}, b_{2}, …, b_{n}), define

S̄_{q}(B_{x}^{(m)}) := ∑_{ℙ∈F_{n,(m)}(B_{x}^{(m)})}M_{B_{x}^{(m)}}(ℙ, q).

We first consider the number of ways that we can place m rooks in each column of B_{x}^{(m)}, starting with the leftmost column and working to the right. In the first column of B_{x}^{(m)}, there will be x^{m} ways to place rooks in the x-part with a total q-weight of [x^{m}]_{q}. Similarly, there are b_{1}^{m} ways to place rooks above the bar, with a total q-weight of [b_{1}^{m}]_{q}. So, the q-weight over all possible placements of m rooks in C_{1} is M_{C,B_{x}^{(m)}}(C_{1}, q) = [x^{m}]_{q} + [b_{1}^{m}]_{q}. Since rooks do not cancel to their right in this board, if we place m rooks in C_{j}, then the total q-weight over all placements of rooks in this column will be M_{C,B_{x}^{(m)}}(C_{j}, q) = [x^{m}]_{q} + [b_{j}^{m}]_{q}, and thus,

S̄_{q}(B_{x}^{(m)}) = ∏_{i=1}^{n}([x^{m}]_{q} + [b_{i}^{m}]_{q}).

Next, suppose we first fix a file placement Z ∈ F_{n−k,(m)}(B^{(m)}). Then the q-weight of Z is μ(Z, q). We wish to extend Z to a placement ℙ ∈ F_{n,(m)}(B_{x}^{(m)}) such that ℙ ∩ B^{(m)} = Z. Each such ℙ arises by placing m rooks in the x-part in each column which does not contain a rook of Z. In each such column there will be x^{m} ways of placing these m rooks, which will give a total q-weight of [x^{m}]_{q} for each such column. As there are k such empty columns, we have

S̄_{q}(B_{x}^{(m)}) = ∑_{k=0}^{n} ∑_{Z∈F_{n−k,(m)}(B^{(m)})} μ(Z, q)([x^{m}]_{q})^{k}

= ∑_{k=0}^{n}([x^{m}]_{q})^{k} ∑_{Z∈F_{n−k,(m)}(B^{(m)})} μ(Z, q)

= ∑_{k=0}^{n}([x^{m}]_{q})^{k}\overline{f}_{n−k,(m)}(B^{(m)}, q).

We would now like to prove a similar product formula for the type-II qm-rook numbers, and to do so, we must first define how to type-II q-count in augmented boards. To begin, suppose that ℙ ∈ N_{n,(m)}(B_{x}^{aug,(m)}) with rooks placed, from left to right in columns C_{1}, …, C_{n} and define

V_{B_{x}^{aug,(m)}}(ℙ, q) = (−1)^{LA(ℙ)} ∏_{i=1}^{n} \overline{ν}_{C}(C_{i}, q),

where we define \overline{ν}_{C}(C_{j}, q) as follows.

(i.) If the m rooks in C_{j} lie in board B^{(m)}, then \overline{ν}_{C}(C_{j}, q) = ν_{C}(C_{j}, q).

(ii.) If the m rooks in C_{j} lie in the x-part of B_{x}^{aug,(m)}, then \overline{ν}_{C}(C_{j}, q) = M_{C,B_{x}^{(m)}}(C_{j}, q), that

is, these rooks have the same q-weight as if they were in a file placement in B_{x}^{(m)}.

(iii.) If the m rooks in C_{j} lie in the cells c_{a}(a_{1}, 1, j), c_{a}(a_{2}, 2, j), …, c_{a}(a_{m}, m, j) in the augmented part of B_{x}^{aug,(m)}, and if there are t columns to the right of C_{j} which contain rooks above the high bar, then \overline{ν}(C_{j}, q) = q^{(e_{1}e_{2}···e_{m})_{α}}, where e_{i} = a_{i} − 1, and α = j − 1 − t.

Figure 20: An example of a q-weighting of a placement of non-attacking rooks in the board B_{3}^{aug,(3)} with B = F (1, 2, 2, 4, 5).

An example of this type-II q-weighting can be seen in Figure 20, where the same board and placement as in Figure 14 are used above the high bar. Here,

V_{B_{x}^{aug,(m)}}(ℙ, q) = (−1)^{LA(ℙ)} ∏_{i=1}^{5} \overline{ν}(C_{i}, q)
= (−1)^{1}q^{(112)_{3}}q^{(100)_{2}}q^{(101)_{3}}q^{(102)_{3}}q^{(101)_{2}}
= (−1)q^{14}q^{4}q^{3}q^{11}q^{5}
= −q^{37}.

Theorem 15. Suppose x, n ∈ ℕ^{0}. If B = F (0, 1, …, n − 1), then

([x^{m}]_{q})^{n} = ∑_{k=0}^{n} \overline{r}_{n−k,(m)}(B^{(m)}, q) ∏_{j=1}^{k}([x^{m}]_{q} − [(j − 1)^{m}]_{q}).  (34)

Proof. Let B = F (0, 1, …, n − 1) and define

\overline{T}_{q}(B_{x}^{aug,(m)}) := ∑_{ℙ∈N_{n,(m)}(B_{x}^{aug,(m)})}V_{B_{x}^{aug,(m)}}(ℙ, q).

We first consider the number of ways to places rooks in the first column of B_{x}^{aug,(m)}, starting with the leftmost column and working right. In the fist column of B_{x}^{aug,(m)}, there are x^{m} possible rook placement, and by our weighting scheme, these come with a total qweight of \overline{ν}(C_{1}, q) = [x^{m}]_{q}. Now suppose that we are placing rooks in column C_{j} with j > 1, and further suppose that we have placed rooks above the high bar in s of the columns to the right of C_{j}. Then above the high bar we will have ((j − 1) − s)^{m} ways to place rooks, and similarly, we will have ((j −1)−s)^{m} ways to place rooks in the augmented part. Since we still have x^{m} ways to place rooks in the x-part, the total q-weight over all such placement is, when considering the sign contributed by LA(ℙ), [x^{m}]_{q} +[((j −1)−s)^{m}]_{q} −[((j −1)−s)^{m}]_{q} = [x^{m}]_{q}. Thus,

\overline{T}_{q}(B_{x}^{aug,(m)} = ([x^{m}]_{q})^{n}.

Next, suppose we first fix an (n − k)-nonattacking rook placement U ∈ N_{n−k,(m)}(B^{(m)}), Then the q-weight of U is ν(U, q). We wish to extend U to a placement ℙ ∈ N_{n,(m)}(B_{x}^{aug,(m)}) such that ℙ ∩ B^{(m)} = U. Each such ℙ arises by placing m rooks below the high bar in each column which does not contain a rook of U. In the first such column, reading from left to right, there will be x^{m} ways to place rooks in the x-part and 0 ways to place rooks in the augmented part, contributing a total q-weight of [x^{m}]_{q} = [x^{m}]_{q} − [0^{m}]_{q}. In general, suppose we are placing rooks in the i^{th} such column below the high bar. Then there will still be x^{m} ways to place rooks in the x-part, and there will be (i − 1)^{m} ways to place rooks in the augments part, giving a total q-weight of [x^{m}]_{q} − [(i − 1)^{m}]_{q}. As there are k such empty columns, we have

\overline{T}_{q}(B_{x}^{aug,(m)}) = ∑_{k=0}^{n} ∑_{U∈N_{n−k,(m)}(B^{(m)})} ν(U, q) ∏_{j=0}^{k}([x^{m}]_{q} − [(j − 1)^{m}]_{q})

= ∑_{k=0}^{n} (∏_{j=0}^{k}([x^{m}]_{q} − [(j − 1)^{m}]_{q})) ∑_{U∈N_{n−k,(m)}(B^{(m)})} ν(U, q)

= ∑_{k=0}^{n} (∏_{j=0}^{k}([x^{m}]_{q} − [(j − 1)^{m}]_{q})) \overline{r}_{n−k,(m)}(B^{(m)}, q),

which is the desired result.

Using these notions of q-counting in m-partition boards, we could extend these results to obtain type-II q-poly rook and file numbers, which would yield the following corollary to Theorem 13.

Corollary 16. 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,

\overline{r}_{k,p(x)}(B(p(x)), q) = \overline{r}_{k,p(x)}(B(p(x)), q) + [p(b_{n} − (k − 1))]_{q}\overline{r}_{k−1,p(x)}(B(p(x)), q)  (35)

and

\overline{f}_{k,p(x)}(B(p(x)), q) = \overline{f}_{k,p(x)}(B(p(x)), q) + [p(b_{n})]_{q}\overline{f}_{k−1,p(x)}(B(p(x)), q),  (36)

where

\overline{r}_{0,p(x)}(B(p(x)), q) = \overline{f}_{0,p(x)}(B(p(x)), q) = 1

and

\overline{r}_{k,p(x)}(B(p(x)), q) = \overline{f}_{k,p(x)}(B(p(x)), q) = 0 if k < 0 or k > n.

3.4 Type II q-poly-Stirling numbers

Consider the numbers defined by the recursions

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

We will call these numbers the Type II q-poly Stirling numbers of the second kind. We then define the numbers

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

We will call these numbers the Type II q-poly Stirling numbers of the first kind. If we now replace \overline{s}_{n,k}^{p(x)}(q) with (−1)^{(n−k)}\overline{c}_{n,k}^{p(x)}(q), then we have the numbers which satisfy the recursion

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

and we will call these numbers the signless Type II q-poly Stirling numbers of the first kind.

Theorem 17. Let n ∈ ℕ and consider a nonzero p(x) ∈ ℕ^{0}[x]. If B = F (0, 1, …, n − 1), then, for every 0 ≤ k ≤ n,

\overline{c}_{n,k}^{p(x)}(q) = \overline{f}_{n−k,p(x)}(B(p(x)), q)  (40)

and

\overline{S}_{n,k}^{p(x)}(q) = \overline{r}_{n−k,p(x)}(B(p(x)), q).  (41)

We omit the proof of this theorem, as it again shows that the respective polynomials satisfy the same recursions.

Combining this result with Theorem 14, we have the product formula

∏_{i=1}^{n}([p(x)]_{q} + [p(i − 1)]_{q}) = ∑_{k=0}^{n} \overline{c}_{n,k}^{p(x)}(q)([p(x)]_{q})^{k}.  (42)

If we then replace [p(x)]_{q} in the above equation with −[p(x)]_{q} and multiply both sides by (−1)^{n}, then we get

∏_{i=1}^{n}([p(x)]_{q} − [p(i − 1)]_{q}) = ∑_{k=0}^{n} \overline{s}_{n,k}^{p(x)}(q)([p(x)]_{q})^{k}.  (43)

Now, we can apply Milne Inversion [4] to show that the matrices ||\overline{S}_{n,k}^{p(x)}(q)|| and ||\overline{s}_{n,k}^{p(x)}(q)|| are inverses of one another, which also leads to the product formula

([p(x)]_{q})^{n} = ∑_{k=0}^{n} \overline{S}_{n,k}^{p(x)}(q) ∏_{j=1}^{k}([p(x)]_{q} − [p(j − 1)]_{q}),  (44)

although this formula also arises as a corollary to Theorems 15 and 17.

Finally, using the recursions given above, the following is a generalization of a well-known generating function for the Stirling numbers of the second kind, the proof of which is similar to that of Theorem 12.

Theorem 18. For any k ≥ 1,

∑_{n≥k} \overline{S}_{n,k}^{p(x)}(q)t^{n} = \frac{t^{k}}{(1 − [p(1)]_{q}t)(1 − [p(2)]_{q}t) ⋯ (1 − [p(k)]_{q}t)}.  (45)

4 Concluding remarks

We have given two different q-analogues of the generalizations of the poly-Stirling numbers defined by Miceli [2]. It is the case that Type I and Type II p, q-analogues of poly-Stirling numbers may be defined in a similar fashion, where the p, q-analogue of n ∈ ℕ is given by

[n]_{p,q} = p^{n−1} + qp^{n−2} + ⋯ + q^{n−2}p + q^{n−1}.

Most of the results of this paper have p, q-analogue counterparts, and the proofs are similar once a combinatorial interpretation has been given. Miceli and Remmel [3] provide some insight into how to p, q-count in this rook setting.

For future work, it may be interesting to see if exponential generating functions can be found for poly-Stirling numbers in general. While Riordan [5] provides a result for p(x) = x^{2}, it would be nice to have results for a general p(x).

5 Acknowledgement

I would like to thank the referee for his/her time and helpful suggestions.

References

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

[2] B. K. Miceli, m-Partition boards and poly-Stirling numbers, J. Integer Seq. 13 (2010), Article 10.3.3.

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

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

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

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

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05E05. Keywords: rook theory, rook placement, file placement, Stirling numbers, poly-Stirling numbers, inverses, q-analogues.

Received June 6 2011; revised versions received September 29 2011; October 17 2011. Published in Journal of Integer Sequences, November 4 2011.

Return to Journal of Integer Sequences home page.