\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{epsfig}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Two $q$-Analogues of Poly-Stirling Numbers
}
\vskip 1cm
\large
Brian K. Miceli \\
Department of Mathematics \\
Trinity University \\
One Trinity Place \\
San Antonio, TX 78212-7200\\
USA\\
\href{mailto:bmiceli@trinity.edu}{\texttt{bmiceli@trinity.edu}} \\
\end{center}
\vskip .2 in
\newcommand{\bbp}{\ensuremath{\mathbb{P}}}
\newcommand{\bbn}{\ensuremath{\mathbb{N}}}
\newcommand{\Fboard}{\ensuremath{F(b_1, b_2, \ldots, b_n)}}
\newcommand{\Bm}{\ensuremath{B^{(m)}}}
\newcommand{\Bmx}{\ensuremath{B^{(m)}_x}}
\newcommand{\xm}{\ensuremath{x^m}}
\newcommand{\Smnk}[2]{\ensuremath{S^{\xm}_{#1,#2}}}
\newcommand{\cmnk}[2]{\ensuremath{c^{\xm}_{#1,#2}}}
\newcommand{\smnk}[2]{\ensuremath{s^{\xm}_{#1,#2}}}
\newcommand{\mrook}[2]{\ensuremath{r_{#1,(m)}(#2)}}
\newcommand{\mfile}[2]{\ensuremath{f_{#1,(m)}(#2)}}
\newcommand{\px}{\ensuremath{p(x)}}
\newcommand{\mnonattp}[1]{\ensuremath{\mathcal{N}_{k,(m)}(#1)}}
\newcommand{\mattp}[1]{\ensuremath{\mathcal{F}_{k,(m)}(#1)}}
\newcommand{\pxnonattp}[1]{\ensuremath{\mathcal{N}_{k,\px}(#1)}}
\newcommand{\poly}[1]{\ensuremath{p_{s_1}{#1}^{s_1} + p_{s_2}{#1}^{s_2} + \cdots + p_{s_y}{#1}^{s_y}}}
\newcommand{\Spoly}{\ensuremath{S^{\px}_{n,k}}}
\newcommand{\cpoly}{\ensuremath{c^{\px}_{n,k}}}
\newcommand{\spoly}{\ensuremath{s^{\px}_{n,k}}}
\newcommand{\Spnk}[2]{\ensuremath{S^{\px}_{#1,#2}}}
\newcommand{\cpnk}[2]{\ensuremath{c^{\px}_{#1,#2}}}
\newcommand{\spnk}[2]{\ensuremath{s^{\px}_{#1,#2}}}
\newcommand{\polyfile}[2]{\ensuremath{f_{#1,\px}(#2)}}
\newcommand{\Bpx}{\ensuremath{B(\px)}}
\newcommand{\Bxpx}{\ensuremath{B_x(\px)}}
\newcommand{\Baxpx}{\ensuremath{B^{aug}_x(\px)}}
\newcommand{\qan}[1]{\ensuremath{[#1]_q}}
\newcommand{\pqan}[1]{\ensuremath{[#1]_{p,q}}}
\newcommand{\qSpolyone}{\ensuremath{S^{\px}_{n,k}(q)}}
\newcommand{\qcpolyone}{\ensuremath{c^{\px}_{n,k}(q)}}
\newcommand{\qspolyone}{\ensuremath{s^{\px}_{n,k}(q)}}
\newcommand{\qSpolynkone}[2]{\ensuremath{S^{\px}_{#1,#2}(q)}}
\newcommand{\qcpolynkone}[2]{\ensuremath{c^{\px}_{#1,#2}(q)}}
\newcommand{\qspolynkone}[2]{\ensuremath{s^{\px}_{#1,#2}(q)}}
\newcommand{\qSpolytwo}{\ensuremath{\overline{S}^{\px}_{n,k}(q)}}
\newcommand{\qcpolytwo}{\ensuremath{\overline{c}^{\px}_{n,k}(q)}}
\newcommand{\qspolytwo}{\ensuremath{\overline{s}^{\px}_{n,k}(q)}}
\newcommand{\qSpolynktwo}[2]{\ensuremath{\overline{S}^{\px}_{#1,#2}(q)}}
\newcommand{\qcpolynktwo}[2]{\ensuremath{\overline{c}^{\px}_{#1,#2}(q)}}
\newcommand{\qspolynktwo}[2]{\ensuremath{\overline{s}^{\px}_{#1,#2}(q)}}
\newcommand{\qmrook}[2]{\ensuremath{r_{#1,(m)}(#2,q)}}
\newcommand{\qmrookII}[2]{\ensuremath{\overline{r}_{#1,(m)}(#2,q)}}
\newcommand{\qmfile}[2]{\ensuremath{f_{#1,(m)}(#2,q)}}
\newcommand{\qmfileII}[2]{\ensuremath{\overline{f}_{#1,(m)}(#2,q)}}
\newcommand{\qprookII}[2]{\ensuremath{\overline{r}_{#1,\px}(#2,q)}}
\newcommand{\qpfileII}[2]{\ensuremath{\overline{f}_{#1,\px}(#2,q)}}
\newcommand{\bnu}{\ensuremath{\overline{\nu}}}
\begin{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.
\end{abstract}
\section{Introduction}
\label{sec:intro}
Define $\bbn = \{1,2,3,\ldots\}$ and $\bbn^0 = \bbn \cup \{0\}$. Given any nonzero $\px \in \bbn^0[x]$, Miceli~\cite{kn:miceli} defines generalizations of Stirling numbers, called \emph{poly-Stirling numbers with respect to} $\px$. Poly-Stirling numbers of the first kind, $\spoly$, are defined by the recursions
\begin{equation}\label{prec1}
\spnk{n+1}{k} = \spnk{n}{k-1} - p(n) \spoly
\end{equation}
where $\spnk{0}{0} =1$ and $\spoly =0$ if either $k<0$ or $k>n$. Similarly, poly-Stirling numbers of the second kind, $\Spoly$, are defined by the recursions
\begin{equation}\label{prec2}
\Spnk{n+1}{k} = \Spnk{n}{k-1} + p(k) \Spoly
\end{equation}
where $\Spnk{0}{0} =1$ and $\Spoly =0$ if either $k<0$ or $k>n$. If we let $\cpoly = (-1)^{n-k}\spoly$, then the $\cpoly$'s satisfy the recursion
\begin{equation}\label{prec3}
\cpnk{n+1}{k} = \cpnk{n}{k-1} + p(n) \cpoly
\end{equation}
where $\cpnk{0}{0} =1$ and $\cpoly =0$ if either $k<0$ or $k>n$. We can see that in the case where $\px = x$, the generalized numbers reduce to the classical Stirling numbers. In the case where $\px = x^2$, these numbers are the \emph{triangle central factorial numbers}, discussed in both Riordan~\cite{kn:riordan} and Stanley~\cite{kn:stanley2}.
For any $x \in \bbn$ we can define the $q$-analogue of $x$ to be
$$[x]_q := 1 + q + q^2 + \cdots + q^{x-1} = \dfrac{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 \emph{Type I $q$-analogues} of $s^{p(x)}_{n,k}$ and $S^{p(x)}_{n,k}$ by the following recursions:
\begin{eqnarray} \label{eqn:psnq1}
s_{n+1,k}^{p(x)}(q) & = & s_{n,k-1}^{p(x)}(q) - p([n]_q)s_{n,k}^{p(x)}(q), \ \mbox{and} \\
S_{n+1,k}^{p(x)}(q) & = & S_{n,k-1}^{p(x)}(q) + p([k]_q)S_{n,k}^{p(x)}(q)
\end{eqnarray}
if $ 0 \leq k \leq 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 \emph{Type II $q$-analogues} of $s^{p(x)}_{n,k}$ and $S^{p(x)}_{n,k}$ by the following recursions:
\begin{eqnarray} \label{eqn:psnq2}
\bar{s}_{n+1,k}^{p(x)}(q) & = & \bar{s}_{n,k-1}^{p(x)}(q) - [p(n)]_q\bar{s}_{n,k}^{p(x)}(q), \ \mbox{and} \\
\bar{S}_{n+1,k}^{p(x)}(q) & = & \bar{S}_{n,k-1}^{p(x)}(q) + [p(k)]_q\bar{S}_{n,k}^{p(x)}(q)
\end{eqnarray}
if $ 0 \leq k \leq n+1$ with $\bar{s}_{0,0}^{p(x)}(q) = \bar{S}_{0,0}^{p(x)}(q) = 1$ and $\bar{s}_{n,k}^{p(x)}(q) = \bar{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~\ref{sec:mboards}, we summarize the results in Miceli~\cite{kn:miceli}, where the author describes the general setting of $m$-partition boards, polyboards, poly-rook and file numbers, and poly-Stirling numbers. Section~\ref{sec:mboards} is given for completeness, and accordingly, a reader who is familiar with the results in Miceli~\cite{kn:miceli} may wish to begin with Section~\ref{sec:qpsnTI}, where the two $q$-rook models are described. The first model describes $q$-counting in polyboards when the $q$-analogue of $\px$ is taken to be $p(\qan{x})$, and the second rook model describes $q$-counting in polyboards when the $q$-analogue of $\px$ is taken to be $\qan{\px}$.
\section{Polyboards, rook placements, and poly-Stirling numbers}
\label{sec:mboards}
Let $B = F(b_1,b_2,\ldots,b_n)$ be a Ferrers board with column heights $b_1, b_2, \ldots, b_n$, reading from left to right, where $0 \leq b_1 \leq b_2 \leq \cdots \leq b_n$ are nonnegative integers. For any positive integer $m$, we define $\Bm$, called the \emph{$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)}(\Bm)$ to be the $j^{th}$ column of $\Bm$, reading from left to right and $C_{(l,j)}(\Bm)$ 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)}(\Bm)$ will be denoted by $c(t,l,j)$. An example of these types of boards can be seen in Figure~\ref{fig:B2}, where $B = F(0,1,3,4,4)$ and $m = 2$. We also define $B^{(0)}$ to be a \emph{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.
\begin{figure}
\begin{center}
\epsfig{figure=mpartitionxxx.ps,height=2in}
\caption{The board $B^{(2)}$, with $B = F(0,1,3,4,4)$.} \label{fig:B2}
\end{center}
\end{figure}
\subsection{$m$-Partition boards}
\label{sec:xmcase}
Miceli~\cite{kn:miceli} defines two kinds of rook placements in the board $\Bm$ which mirror those found in Garsia and Remmel~\cite{kn:gr}: nonattacking placements and file placements. We let $\mnonattp{\Bm}$ denote the set of
placements of $mk$ nonattacking rooks in $\Bm$. These are placements such that the following three conditions hold.
\begin{description}
\item[(i.)] If any subcolumn $C_{(i,j)}(\Bm)$ contains a rook, then for every $1 \leq l \leq m$, the subcolumn $C_{(l,j)}(\Bm)$ 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.
\item[(ii.)] There is a most one rook in any one subcolumn of a given column.
\item[(iii.)] For any $1 \leq l \leq 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)}(\Bm)$. That is, there is at most one rook in cell $t$ of the $l^{th}$ subcolumn of any column.
\end{description}
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 \ref{fig:Bmplace} we have pictured a nonattacking rook placement $\mathbb{P} \in \mnonattp{\Bm}$ 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 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 $\mattp{\Bm}$ denote the set of placements of $mk$ file rooks in $\Bm$. These are placements such that the following two conditions hold.
\begin{description}
\item[(i.)] If any subcolumn $C_{(i,j)}(\Bm)$ contains a rook, then for every $1 \leq l \leq m$, the subcolumn
$C_{(l,j)}(\Bm)$ must contain a rook.
\item[(ii.)] There is at most one rook in any subcolumn of a given column.
\end{description}
For example, on the right in Figure \ref{fig:Bmplace} we have pictured a file placement $\mathbb{F} \in \mattp{\Bm}$ where $B = F(0,1,3,4,4)$, $m =2$, and $k=2$.
\begin{figure}
\begin{center}
\epsfig{figure=Bmplacementxxx.ps,height=1.75in}
\caption{Nonattacking and file rook placements in the board $B^{(2)}$, with $B = F(0,1,3,4,4)$.} \label{fig:Bmplace}
\end{center}
\end{figure}
We then define
\begin{eqnarray*}
\mrook{k}{\Bm} & := & |\mnonattp{\Bm}| \ \ \mbox{and} \\
\mfile{k}{\Bm} & := & |\mattp{\Bm}|,
\end{eqnarray*}
and we call $\mrook{k}{\Bm}$ the $k^{th}$ \emph{$m$-rook number of $\Bm$} and $\mfile{k}{\Bm}$ the $k^{th}$ \emph{$m$-file number of $\Bm$}.
Defined in this way, it is shown in \cite{kn:miceli} that these numbers satisfy some simple recursions.
\begin{theorem} \label{thm:rookrec}
Suppose that $B =F(b_1,\ldots,b_n)$ and $\bar{B} = F(b_1, \ldots, b_n,b_{n+1})$ are Ferrers boards. Then for all $0 \leq k \leq n+1$,
\begin{equation}\label{mrookrec}
r_{k,(m)}(\bar{B}^{(m)}) = \mrook{k}{\Bm}+ (b_{n+1}-(k-1))^m \mrook{k-1}{\Bm}
\end{equation}
and
\begin{equation}\label{mfilerec}
f_{k,(m)}(\bar{B}^{(m)}) = \mfile{k}{\Bm}+ b_{n+1}^m \mfile{k-1}{\Bm}.
\end{equation}
\end{theorem}
From here, it is shown that when $B=F(0,1,2,\ldots,n-1)$, the $m$-rook and $m$-file numbers of $B$ correspond to poly-Stirling numbers with respect to $\px = x^m$. We call such poly-Stirling number $x^m$-\emph{Stirling numbers}, and we have the following rook theory interpretation for the $\xm$-Stirling numbers.
\begin{theorem} Let $m \in \bbn$ and $B = F(0,1,\ldots,n-1)$. Then
\begin{eqnarray*}
\Smnk{n}{k} & = & \mrook{n-k}{\Bm}, \\
\cmnk{n}{k} & = & \mfile{n-k}{\Bm}, \ \mbox{and} \\
\smnk{n}{k} & = & (-1)^{n-k} \mfile{n-k}{\Bm}.
\end{eqnarray*}
\end{theorem}
\subsection{Polyboards}
\label{sec:polyboards}
Fix a Ferrers board $B = \Fboard$ and a polynomial $\px = \poly{x} \in \bbn[x]$, with $0 \leq s_i < s_j$ for all $i < j$. We define a set of $y$ $m$-partition boards $\Bpx :=
\{B^{(s_1)},B^{(s_2)},\ldots,B^{(s_y)}\}$. We call $\Bpx$ the \emph{polyboard associated with $B$ and $\px$}, and we refer to the board $B^{(s_z)}$ as the $z^{th}$ \emph{subboard of $\Bpx$}. In Figure~\ref{fig:Npoly}, we see an example of a polyboard where $B = F(1,2,3,5,5)$ and $\px \in \bbn[x]$ is of the form $p_0 + p_1x + p_2x^2$. Note that the coefficients of $\px$ are irrelevant when constructing $\Bpx$, although the coefficients of $\px$ 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^z_{(j)}(\Bpx)$ 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 $\Bpx$ to be the $j^{th}$ \emph{column of $\Bpx$}, denoted by $C_{(j)}(\Bpx)$. We also let $C^z_{(l,j)}(\Bpx)$ be the $l^{th}$ subcolumn of the $j^{th}$ column of $B^{(s_z)}$. If a rook $r$ is placed in column $C^z_{(l,j)}(\Bpx)$ 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^z_{(l,j)}(\Bpx)$ lies to the right (left) of $C^{z'}_{(l',j')}(\Bpx)$ whenever $j > j'$ ($j < j'$), and accordingly, we refer to the rook which lies in the \emph{leftmost column} of $\Bpx$ as the \emph{leftmost rook} in the board.
\begin{figure}
\centering \epsfig{figure=Npolyxxx.ps,height=1.25in} \caption{An example of the polyboard $\Bpx$, with $B = F(1,2,3,5,5)$ and $\px = p_0 + p_1x + p_2x^2$.}
\label{fig:Npoly}
\end{figure}
\subsection{Poly-rook numbers, poly-file numbers, and poly-Stirling numbers}
\label{subsec:polyrook}
Given $\Bpx$, we shall define both nonattacking and file rook placements in the polyboard. Nonattacking rook placements in $\Bpx$ are placements of rooks such that the following two conditions hold.
\begin{description}
\item[(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.
\item[(ii.)] Within any particular subboard, the nonattacking placement rules from Section~\ref{sec:xmcase} apply to that board.
\end{description}
We shall call such a placement of rooks into $\Bpx$, in which $k$ columns total among all of the subboards of $\Bpx$ contain rooks, a \emph{$k$-placement of nonattacking rooks} in $\Bpx$. In such a $k$-placement, cancellation will occur in the following manner:
\begin{description}
\item[(i.)] Suppose a rook $r$ is the leftmost rook placed in the $C_{(j)}(\Bpx)$.
\begin{description}
\item[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 $\Bpx$.
\item[b.] If $r$ is \textbf{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~\ref{sec:xmcase} 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 $\Bpx$, and every cell in the $j^{th}$ column of all other subboards.
\end{description}
\item[(ii.)] Suppose $r'$ is any other rook which has been placed in the $C^w_{(i)}(\Bpx)$.
\begin{description}
\item[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 $\Bpx$ which has yet to be canceled by a rook to its left.
\item[b.] If $r'$ is \textbf{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~\ref{sec:xmcase} 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 $\Bpx$, and every cell in the $j^{th}$ column of all other subboards which has yet to be canceled by a rook to its left.
\end{description}
\end{description}
An example of such a placement and the corresponding cancellation can be seen in Figure~\ref{fig:Npolycancel}, where $B = F(1,2,3,5,5)$, $k = 3$, and $\px = p_0 + p_1x + p_3x^3$. In this figure, a cell labeled with an $i$ has been canceled by the rook $X_i$.
\begin{figure}
\centering \epsfig{figure=Npolycancelxxx.ps,height=1.75in,width=5.5in}
\caption{An example of a nonattacking $k$-placement in the polyboard
$\Bpx$, with $B = F(1,2,3,5,5)$, $k=3$, and $\px = p_0 + p_1x +
p_3x^3$.} \label{fig:Npolycancel}
\end{figure}
File rook placements in $\Bpx$ are placements of rooks such that the following two conditions hold.
\begin{description}
\item[(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.
\item[(ii.)] Within any particular subboard, the file placement rules from Section~\ref{sec:xmcase} apply to that board.
\end{description}
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~\ref{fig:Fpolycancel}, where again $B = F(1,2,3,5,5)$, $k = 3$, and $\px = p_0 + p_1x + p_3x^3$.
\begin{figure}
\centering \epsfig{figure=Fpolycancel.eps,height=1.75in,width=5.5in}
\caption{An example a file $k$-placement in the polyboard $\Bpx$,
with $B = F(1,2,3,5,5)$, $k=3$, and $\px = p_0 + p_1x + p_3x^3$.}
\label{fig:Fpolycancel}
\end{figure}
Given any nonzero $\px \in \bbn^0[x]$, we let $\pxnonattp{\Bpx}$ denote the set of \emph{colored nonattacking $k$-placements} in the polyboard $\Bpx$ such that the following two conditions hold.
\begin{description}
\item[(i.)] The rooks placed in the columns of $B^{(s_z)}$ are colored with distinct colors, $c_1,\ldots,c_{p_{s_z}}$.
\item[(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.
\end{description}
We also define $\mathcal{F}_{k,\px}(\Bpx)$ to be the set of colored file placements with rooks in $k$ of the columns of $\Bpx$ under the exact same coloring conditions as placements in $\mathcal{N}_{k,\px}(\Bpx)$. We shall call such a placement of rooks a \emph{colored file $k$-placement}.
We then define
\begin{eqnarray*}
r_{k,\px}(\Bpx) & := & |\mathcal{N}_{k,\px}(\Bpx)| \ \ \mbox{and} \\
f_{k,\px}(\Bpx) & := & |\mathcal{F}_{k,\px}(\Bpx)|,
\end{eqnarray*}
and we call $r_{k,\px}(\Bpx)$ the $k^{th}$ \emph{poly-rook number of $\Bpx$ with respect to $p(x)$} and $f_{k,\px}(\Bpx)$ the $k^{th}$ \emph{poly-file number of $\Bm$ with respect to $p(x)$}.
Using these definitions, we have the following theorem.
\begin{theorem} \label{thm:polyrookrec}
Suppose that $B =F(b_1,\ldots,b_n)$ and $\bar{B} = F(b_1, \ldots, b_n,b_{n+1})$ are Ferrers boards and consider a nonzero $p(x) \in \bbn^0[x]$. Then for all $0 \leq k \leq n+1$,
\begin{equation}\label{polyrookrec}
r_{k,p(x)}(\bar{B}(p(x)) = r_{k,\px}(\Bpx)+ p(b_{n+1}-(k-1)) r_{k-1,\px}(\Bpx)
\end{equation}
and
\begin{equation}\label{polyfilerec}
f_{k,p(x)}(\bar{B}(p(x)) = f_{k,\px}(\Bpx)+ p(b_{n+1}) f_{k-1,\px}(\Bpx).
\end{equation}
\end{theorem}
From here, it is shown that when $B=F(0,1,2,\ldots,n-1)$, the poly-rook and poly-file numbers of $\Bpx$ with respect to $\px$ correspond to poly-Stirling numbers with respect to $\px$ in the following way.
\begin{theorem} Let $B = F(0,1,\ldots,n-1)$ and let $p(x) = \bbn[x]$. Then
\begin{eqnarray*}
\Spoly & = & r_{n-k,\px}(\Bpx), \\
\cpoly & = & f_{n-k,\px}(\Bpx), \ \mbox{and} \\
\spoly & = & (-1)^{n-k} f_{n-k,\px}(\Bpx).
\end{eqnarray*}
\label{thm:aabb}
\end{theorem}
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(\px) = \{B^{(s_1)}_x,B^{(s_2)}_x,\ldots,B^{(s_y)}_x \}$, where given $x \in \bbn$, $B^{(s_u)}_x$ 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$-\emph{part} and the imaginary line that separates the original board from $x$-part is called the \emph{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^{(0)}_x$ 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^{(0)}_x$ is also degenerate. We will refer to the upper parts of each board as such, and if we talk about the \emph{upper part of $B_x(\px)$}, then we are referring to the set of upper parts of each board in $B_x(\px)$, and we use the same convention when talking about the $x$-\emph{part of $B_x(\px)$}. We then say that the upper part of $B_x(\px)$ is separated from the $x$-part of $B_x(\px)$ by the \emph{bar of $B_x(\px)$}. Let $\mathcal{F}_{n,\px}(B_x(\px))$ denote the set of colored placements in $B_x(\px)$ such that the following four conditions hold.
\begin{description}
\item[(i.)] Every column of $B_x(\px)$ must contain a rook.
\item[(ii.)] If any rook is placed in the $j^{th}$ column of a subboard of $B_x(\px)$, then that may be the only subboard which contains rooks in its $j^{th}$ column.
\item[(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~\ref{sec:xmcase} apply to the upper and $x$-parts, respectively.
\item[(iv.)] The same coloring rules apply as before.
\end{description}
We define that any rook placed in the upper part of the $j^{th}$ column of a subboard of $B_x(\px)$ will cancel the upper parts of the $j^{th}$ columns of every other subboard in $B_x(\px)$, and any rook placed in the $x$-part of the $j^{th}$ column of a subboard of $B_x(\px)$ will cancel the $x$-parts of the $j^{th}$ columns of every other subboard in $B_x(\px)$. An example of this type of placement and the corresponding cancellation can be seen in Figure~\ref{fig:Fxpolycancel}, where $B = F(1,2,3,5,5)$, $\px = p_0 + p_1x + p_3x^3$, $x = 6$, and the rook denoted by X$_i$ cancels the cells labeled with an $i$.
\begin{figure}
\centering \epsfig{figure=Fxpolycancel.eps,height=3in}
\caption{An example of a file rook placement in $B_6(\px)$, with $B
= F(1,2,3,5,5)$ and $\px = p_0 + p_1x + p_3x^3$.}
\label{fig:Fxpolycancel}
\end{figure}
By counting $|\mathcal{F}_{n,\px}(B_x(\px))|$ in two different ways, we get the following theorem.
\begin{theorem} Suppose $n \in \bbn$ and $\px = \poly{x} \in \bbn[x]$. If $B = \Fboard$ is any Ferrers board, then
\begin{equation}
\prod_{i=1}^n (\px + p(b_i)) = \sum_{k=0}^n \polyfile{n-k}{\Bpx}(\px)^k. \label{eqn:polyfileprod}
\end{equation}
\label{thm:polyfilethm}
\end{theorem}
Note that in the special case of Theorem~\ref{thm:polyfilethm} where $B = F(0,1,\ldots,n-1)$, we see that Equation~(\ref{eqn:polyfileprod}) reduces to
\begin{equation}
\prod_{i=1}^n (\px + p(i-1)) = \sum_{k=0}^n \cpoly(\px)^k,
\label{eqn:cpolyprod}
\end{equation}
and if in Equation~(\ref{eqn:cpolyprod}) we replace $\px$ with $-\px$ and multiply both sides by $(-1)^n$, we obtain the following corollary:
\begin{corollary}
For $n \in \bbn^0$ and $\px \in \bbn[x]$,
\begin{equation}
\prod_{i=1}^n (\px - p(i-1)) = \sum_{k=0}^n \spoly(\px)^k.
\label{eqn:spolyprod}
\end{equation}
\label{cor:polys}
\end{corollary}
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^{aug,(m)}_x$~\cite{kn:miceli}, a modification of the augmented rook boards originally defined by Miceli and Remmel~\cite{kn:mr}. To construct these boards, we first we start with the board $\Bmx$. Then $B^{aug,(m)}_x$ is formed by adding, below the $x$-part of $\Bmx$, columns of heights $0,1\ldots,n-1$, reading from left to right, that consist of $m$ subcolumns. We call the extra cells that we added to $\Bmx$ to form $B^{aug,(m)}_x$ the \emph{augmented part} of $B^{aug,(m)}_x$ and call the line that separates the $x$-part and the augmented part of $B^{aug,(m)}_x$ the \emph{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~\ref{fig:Bmxrookplace}, where $B=F(0,1,3,3,4)$, $m=2$, and $x=3$. In particular, $B^{aug,(0)}_x$ will be similar to $B^{(0)}_x$, that is, $B^{aug,(0)}_x$ will consist of a degenerate board, a degenerate $x$-part, and a degenerate augmented part.
\begin{figure}
\begin{center}
\epsfig{figure=Bmxrookplacementxxx.ps,height=3in} \caption{An example of the board $B^{aug,(2)}_3$, with $B = F(0,1,3,3,4)$ along with a corresponding example of a nonattacking rook placement.}
\label{fig:Bmxrookplace}
\end{center}
\end{figure}
We define a nonattacking rook placement $\mathbb{P}$ of $mn$ rooks in $B^{aug,(m)}_x$ to be a placement such that the following three conditions hold.
\begin{description}
\item[(i.)] Every column of $B^{aug,(m)}_x$ must contain a rook.
\item[(ii.)] Rooks that are placed in either the $x$-part or the lower augmented part of $B^{aug,(m)}_x$ do not cancel any cells.
\item[(iii.)] If $r$ is a rook placed in the cell $c(t,l,j)$ in the upper part of $B^{aug,(m)}_x$, 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 $\Bm$ to the left of $r$.
\end{description}
To better illustrate this cancellation, we have pictured an element of $\mathcal{N}_{n,(m)}(B^{aug,(m)}_x)$ in the righthand side of Figure~\ref{fig:Bmxrookplace}. We have placed dots in those cells that are canceled by the rooks in column 2 and $\ast$'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 $\mathbb{P} \in \mathcal{N}_{n,(m)}(B^{aug,(m)}_x)$, $w(\mathbb{P})$, to be $(-1)^{la(\mathbb{P})}$ where $la(\mathbb{P})$ equals the number of columns in $\mathbb{P}$ which contain rooks which lie in the lower augmented part of $B^{aug,(m)}_x$.
Now, consider the $y$-tuple of boards $\Baxpx = \{B^{aug,(s_1)}_x, B^{aug,(s_2)}_x, \ldots,B^{aug,(s_y)}_x \}$, called the \emph{augmented polyboard with respect to $B$ and $\px$}. We will refer to the upper parts of each board as such, and if we talk about the \emph{upper part of $\Baxpx$}, then we are referring to the set of upper parts of each board in $B^{aug}_x(\px)$, and we use the same convention when talking about the $x$-\emph{part of $\Bxpx$} and the \emph{lower augmented part of} $\Baxpx$. We then say that the upper part of $B^{aug}_x(\px)$ is separated from the $x$-part of $B^{aug}_x(\px)$ by the \emph{high bar of $B^{aug}_x(\px)$} and the $x$-part is separated from the lower augmented part by the \emph{low bar of} $\Baxpx$. Next we define a nonattacking rook placement $\mathbb{P}$ in $B^{aug}_x(\px)$ such that the following three conditions hold.
\begin{description}
\item[(i.)] Every column of $\Baxpx$ must contain a rook.
\item[(ii.)] If any rook is placed in the $j^{th}$ column of a subboard of $\Bxpx$, then that may be the only subboard which contains rooks in its $j^{th}$ column.
\item[(iii.)] Within any particular subboard, the following rules are observed.
\begin{description}
\item[a.] There is at most one rook in each subcolumn.
\item[b.] For any given column $C_{(j)}(B^{aug,(m)}_x$), 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^{aug,(m)}_x$.
\item[c.] No rook lies in a cell which is canceled by another rook.
\end{description}
\end{description}
\begin{figure}[ht]
\centering \epsfig{figure=NxpolycancelIIIxxx.ps,height=4.5in}
\caption{An example of a nonattacking rook placement in $B^{aug}_3(\px)$, with $B = F(1,2,3,5,5)$ and $\px = p_0 + p_1x + p_3x^3$.} \label{fig:Nxpolycancel}
\end{figure}
Here cancellation in this board is defined as follows.
\begin{description}
\item[(i.)] Suppose $r$ is a rook placed in the first column of
$B^{aug}_x(\px)$.
\begin{description}
\item[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 $\Baxpx$ 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.
\item[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 $\Baxpx$.
\end{description}
\item[(ii.)] Suppose $r'$ is any other rook which has been placed in the $j^{th}$ column of $\Baxpx$.
\begin{description}
\item[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.
\item[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 $\Baxpx$.
\item[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.
\end{description}
\end{description}
Now for any nonzero $\px \in \bbn^0[x]$, we then let $\mathcal{N}_{n,\px}(\Baxpx)$ denote the set of colored placements in $\Baxpx$ 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~\ref{fig:Nxpolycancel}, where $B = F(1,2,3,5,5)$, $\px = p_0 + p_1x + p_3x^3$, and $x = 3$. Finally, we assign to each colored placement of rooks $\mathbb{P} \in \mathcal{N}_{n,\px}(\Baxpx)$ a weight of $(-1)^{LA(\mathbb{P})}$, where $LA(\mathbb{P})$ is the number of columns in $\mathbb{P}$ that contain rooks which lie in the lower augmented part of $B^{aug}_x(\px)$. This model, combined with Theorem~\ref{thm:aabb}, gives the following result.
\begin{theorem} Suppose $n \in \bbn$ and $\px = \poly{x} \in \bbn[x]$. If $B = F(0,1,\ldots, n-1)$ is any Ferrers board, then
\begin{eqnarray}
(\px)^n & = & \sum_{k=0}^n r_{n-k,\px}(\Bpx)\prod_{j=1}^k (\px - p(j-1)) \ \mbox{ } \ \label{eqn:polyrookprod} \\
& = & \sum_{k=0}^n \Spoly \prod_{j=1}^k (\px - p(j-1)) \notag.
\end{eqnarray}
\label{thm:polyrookthm}
\end{theorem}
\section{Two $q$-analogues}
\label{sec:qpsnTI}
\begin{figure}[t]
\centering \epsfig{figure=qcountingxxx.ps, height=1.5in}
\caption{$q$-counting, where the sum over all placements in $\mathcal{K(B)}$ with $B = F(5)$ is $q^4+q^3+q^2+q^1+q^0 = \qan{5}$.} \label{fig:qcounting}
\end{figure}
To begin, we recall that $\qan{0} = 0$ and for any $n \in \bbn$,
$$\qan{n} = 1 + q + q^2 + \cdots + q^{n-1} = \dfrac{1-q^n}{1-q}.$$ Now, assume that we have the single-column Ferrers board $B=F(b_1)$ and that $\px = x$. Then we can define, for any placement $\bbp$ of a single rook in this board, the statistic $w(\bbp) = q^{\gamma(\bbp)}$, where $\gamma(\bbp)$ is the number of cells which lie above the rook in $\bbp$. If we set $\mathcal{K}(B)$ to be the set of all rook placements in $B$, then
$$W(B) = \sum_{\bbp \in \mathcal{K}(B)} w(\bbp) = \qan{b_1}.$$ An example of this can be seen in Figure~\ref{fig:qcounting}, where $b_1=5$. This method of $q$-counting generalizes further, where if $B=F(b_1)$ and $\px = cx^m \in \bbn[x]$ with $m \geq 1$, then $W(B) = c\qan{b_1}^m = p(\qan{b_1}).$
\subsection{Type I $q$-counting in polyboards}
In this section we describe the first of our two $q$-analogues. Here, given a nonzero $\px \in \bbn^0[x]$, we define the \emph{type I q-analogue of p(x)} to be $p(\qan{x})$. Suppose that we are given a placement $\bbp \in \mathcal{F}_{k,\px}(\Bpx)$, 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^{\alpha(r)},$$
where $\alpha(r)$ is the number of cells in $\Bpx$ that lie directly above the rooks of $r$. We then define the $q$-weight of $\bbp$ to be
$$G(\bbp,q) := \prod_{r \in \bbp} g(r,q).$$
An illustration of this type of $q$-counting can be seen in Figure~\ref{fig:qFpolycancel}, where the same placement is used as in Figure~\ref{fig:Fpolycancel}. Here we see that, when looking at rooks from left to right, $\bbp$ has a $q$-weight of
\begin{eqnarray*}
G(\bbp,q) & = & g(r^{(2,1,1)},q) \ g(r^{(3,3,2)},q) \ g(r^{(1,4,1)},q) \\
& = & (1)(q)(1) \\
& = & q.
\end{eqnarray*}
\begin{figure}
\centering \epsfig{figure=qFpolycancel.eps, height=1.75in, width=5.5in}
\caption{$q$-counting in the board $\Bpx$, with the same placement as in Figure~\ref{fig:Fpolycancel}. Here the $q$-weight is $(1)(q)(1) = q$.} \label{fig:qFpolycancel}
\end{figure}
We then define the $k^{th}$ \emph{type I $q$-poly-file number of} $\Bpx$ to be
\begin{equation}
f_{k,\px}(\Bpx,q) := \sum_{\bbp \in \mathcal{F}_{k,\px}(\Bpx)} G(\bbp,q).
\end{equation}
Now suppose that we are given a placement $\bbp \in \mathcal{F}_{n,\px}(\Bxpx)$. 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 \in \bbp$, the $q$-weight of $r$ by
$$g_x(r,q) := q^{\alpha_x(r)},$$
where
\begin{description}
\item[(i.)] $\alpha_x(r)$ is the number if uncanceled cells which lie directly above $r$ if $r$ is not in the $x$-part of $\Bxpx$, and
\item[(ii.)] $\alpha_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 $\Bxpx$.
\end{description}
The $q$-weight of $\bbp$ is then defined to be
$$G_x(\bbp,q) := \prod_{r \in \bbp} g_x(r,q).$$
This $q$-counting in the board $\Bxpx$ is pictured in Figure~\ref{fig:qFxpolycancel}, where the placement shown has, when looking at the rooks from left to right, a $q$-weight of
\begin{eqnarray*}
G_x(\bbp,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.
\end{eqnarray*}
\begin{figure}
\centering \epsfig{figure=qFxpolycancel.eps, width=5.5in}
\caption{$q$-counting in the board $\Bxpx$, with the same placement as in Figure~\ref{fig:Fxpolycancel}. Here the $q$-weight is $(1)(1)(q)(1)(q^5) = q^6$.} \label{fig:qFxpolycancel}
\end{figure}
\begin{theorem} Suppose $x,n \in \bbn^0$ and $\px = a_{s_1}x^{s_1} + a_{s_2}x^{s_2} + \cdots + a_{s_y}x^{s_y} \in \bbn[x]$. If $B = \Fboard$ is any Ferrers board, then
\begin{equation}
\prod_{i=1}^n (p(\qan{x}) + p(\qan{b_i})) = \sum_{k=0}^n f_{n-k,\px}(\Bpx,q) \ (p(\qan{x}))^k. \label{eqn:qpolyfileprod}
\end{equation}
\label{thm:qpolyfilethm}
\end{theorem}
\begin{proof} Given $\px$ and a Ferrers board $B = \Fboard$, define
$$S_q(\Bxpx) := \sum_{\bbp \in \mathcal{F}_{n,\px}(\Bxpx)} G_x(\bbp,q).$$
We first consider the number of ways that we can place rooks in each column of $\Bxpx$, starting with the leftmost column and working to the right. In the first column of $\Bxpx$ there will be $x^{s_1} + x^{s_2} + \cdots + x^{s_y}$ ways to place rooks in the $x$-part, and there will be $b_1^{s_1} + b_1^{s_2} + \cdots + b_1^{s_y}$ ways to place rooks in the upper part. The total $q$-weight for all of these placements would be
$$(\qan{x}^{s_1} + \qan{x}^{s_2} + \cdots + \qan{x}^{s_y}) + (\qan{b_1}^{s_1} + \qan{b_1}^{s_2} + \cdots + \qan{b_1}^{s_y})$$ if these placements were uncolored. Coloring the placements leads to the total $q$-weight of
$$(a_{s_1}\qan{x}^{s_1} + a_{s_2}\qan{x}^{s_2} + \cdots + a_{s_y}\qan{x}x^{s_y}) + (a_{s_1}\qan{b_1}^{s_1} + a_{s_2}\qan{b_1}^{s_2} + \cdots + a_{s_y}\qan{b_1}^{s_y}) = p(\qan{x})+p(\qan{b_1})$$ in the first column of $\Bxpx$. In general, since no rook cancels to its right, the $j^{th}$ column of the $\Bxpx$ will get a total $q$-weight of $p(\qan{x})+p(\qan{b_j})$, giving that
$$S_q(\Bxpx) = \prod_{i=1}^n (p(\qan{x} + p(\qan{b_i})).$$
Next, suppose that we first fix a colored $n-k$-file placement $W \in \mathcal{F}_{n-k,\px}(\Bpx)$. Then the $q$-weight of $W$ is $G(W,q)$. We wish to extend $W$ to a colored placement $\bbp$ in $\mathcal{F}_{n,\px}(\Bxpx)$, that is, $\bbp \cap \Bpx = W$. To do this, we will place rooks in the remaining columns of the $x$-part of $\Bxpx$ which do not already contain rooks from $W$. In each of these columns there will be $x^{s_1} + x^{s_2} + \cdots + x^{s_y}$ ways to place rooks, each with a $q$-weight of $p(\qan{x})$. As there are $k$ such empty columns, we have
\begin{eqnarray*}
S_q(\Bxpx) & = & \sum_{k=0}^n \sum_{W \in \mathcal{F}_{n-k,\px}(\Bpx)} \hspace{-.35in} G(W,q) p(\qan{x})^k \\
& = & \sum_{k=0}^n p(\qan{x})^k \sum_{W \in \mathcal{F}_{n-k,\px}(\Bpx)} \hspace{-.35in} G(W,q) \\
& = & \sum_{k=0}^n p(\qan{x})^k f_{n-k,\px}(\Bpx,q),
\end{eqnarray*}
which is the desired result.
\end{proof}
Suppose that we are given a placement $\bbp \in \mathcal{N}_{k,\px}(\Bpx)$. We define the $q$-weight of $r$ by
$$h(r,q) := q^{\beta(r)},$$
where $\beta(r)$ is the number of uncanceled cells which lie above the rooks of $r$.
We then define the $q$-weight of $\bbp$ to be
$$H(\bbp,q) := \prod_{r \in \bbp} h(r,q).$$
\begin{figure}
\centering \epsfig{figure=Npolycancelqxxx.ps,height=1.75in,width=5.5in}
\caption{$q$-counting in the board $\Bpx$, with the same placement as in Figure~\ref{fig:Npolycancel}. Here the $q$-weight is $(1)(1)(q^3) = q^3$.} \label{fig:Npolycancelq}
\end{figure}
In Figure~\ref{fig:Npolycancelq}, which is the identical placement to Figure~\ref{fig:Npolycancel}, we see that the placement shown has a $q$-weight, when looking at rooks from left to right, of
\begin{eqnarray*}
H(\bbp,q) & = & h(r^{(2,1,1)},q) \ h(r^{(1,3,0)},q) \ h(r^{(3,4,2)},q) \\
\mbox{} & = & (1)(1)(q^3) \\
\mbox{} & = & q^3.
\end{eqnarray*}
We then define the $k^{th}$ \emph{type I} $q$-\emph{poly-rook number of $\Bpx$} to be
\begin{equation}
r_{k,\px}(\Bpx,q) := \sum_{\bbp \in \mathcal{N}_{k,\px}(\Bpx)} H(\bbp,q).
\end{equation}
Now suppose that we are given a colored placement $\bbp \in \mathcal{N}_{n,\px}(\Baxpx)$. 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 \in \bbp$, the $q$-weight of $r$ to be
$$h_x(r,q) = q^{\beta^{aug}_x(r)},$$
where
\begin{description}
\item[(i.)] $\beta^{aug}_x(r)$ is equal to $\beta(r)$ if $r$ is above the high bar in $\Baxpx$,
\item[(ii.)] $\beta^{aug}_x(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 $\Baxpx$, and
\item[(iii.)] $\beta^{aug}_x(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 $\Baxpx$.
\end{description}
Using this weighting scheme we set the $q$-weight of $\bbp$ to be
$$H_x(\bbp,q) = (-1)^{LA(\bbp)} \prod_{r \in \bbp} h_x(r,q),$$
where again, $LA(\bbp)$ is the number of columns of $\Baxpx$ which contain rooks from $\bbp$ below the low bar. This type of $q$-counting in the board $\Baxpx$ can be seen in Figure~\ref{fig:qNxpolycancel}, where the placement shown has $q$-weight
\begin{eqnarray*}
H_x(\bbp,q) & = & (-1)^{LA(\bbp)}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) \\
\mbox{} & = & (-1)^1(1)(q)(q^2)(q^2)(q) \\
\mbox{} & = & -q^6.
\end{eqnarray*}
\begin{figure}[t]
\centering \epsfig{figure=NxpolycancelIIIqxxx.ps,height=4.5in}
\caption{$q$-counting in the board $B^{aug}_3(\px)$, with the same placement as in Figure~\ref{fig:Nxpolycancel}. Here the $q$-weight is $-q^6$.} \label{fig:qNxpolycancel}
\end{figure}
\begin{theorem} Suppose $x, n \in \bbn^0$ and $\px = a_{s_1}x^{s_1} + a_{s_2}x^{s_2} + \cdots + a_{s_y}x^{s_y} \in \bbn[x]$. If $B = F(0,1,\ldots,n-1)$, then
\begin{equation}
(p(\qan{x}))^n = \sum_{k=0}^n r^{aug}_{n-k,\px}(\Bpx,q) \prod_{i=1}^k (p(\qan{x}) - p(\qan{i-1})). \label{eqn:qpolyrookprod}
\end{equation}
\label{thm:qpolyrookthm}
\end{theorem}
\begin{proof} Given $\px$ and the Ferrers board $B = F(0,1,\ldots,n-1)$, define
$$T_q(\Baxpx) := \sum_{\bbp \in \mathcal{N}_{n,\px}(\Baxpx)} H_x(\bbp,q).$$
We see that in the first column of $\Baxpx$ there are $x^{s_1} + x^{s_2} + \cdots + 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(\qan{x})$ to $T_q(\Baxpx)$. 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 $\Baxpx$. These both contribute a total $q$-weight of $p(0) = p(\qan{0})$ to $T_q(\Baxpx)$, although the rooks placed below the low bar are weight by $LA(\bbp)$. Thus, the total $q$-weight over all placements in the first column of $\Baxpx$ is $p(\qan{x}) + p(\qan{0}) - p(\qan{0}) = p(\qan{x})$. In general, if we have placed rooks in the first $t-1$ columns of $\Baxpx$ 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} + \cdots + a_y(t-1-s)^{s_y} = p(t-1-s)$ ways to place colored rooks above the high bar, $\px$ ways to place colored rooks in the $x$-part, and $a_1(t-1-s)^{s_1} + a_2(t-1-s)^{s_2} + \cdots + 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 $\Baxpx$ will contribute
$p(\qan{x}) + p(\qan{t-1-s}) - p(\qan{t-1-s}) = p(\qan{x})$ to $T_q(\Baxpx)$. It then follows that
$$T_q(\Baxpx) = (p(\qan{x}))^n.$$
Now suppose that we fix a colored $(n-k)$-nonattacking rook placement $V$ in the upper part of $\Baxpx$. Then we want to count the number of ways extend $V$ to a placement in $\mathcal{N}_{n,\px}(\Baxpx)$. Let $C_{(t_i)}(\Baxpx)$ be the $i^{th}$ column of $\Baxpx$, reading left to right, which has no rooks from $V$ in that column. Then for $1 \leq i \leq k$, there will be $t_i-i$ columns to the left of $C_{(t_i)}(\Baxpx)$ which have rooks above the high bar and these rooks will cancel $t_i-i$ cells in each subcolumn of $C_{(t_i)}(\Baxpx)$ in the lower augmented part of the $\Baxpx$. Thus, there will be $t_i-1-(t_i-i) = (i-1)$ uncanceled cells in each subcolumn of $C_{(t_i)}(\Baxpx)$ in the lower augmented part of the $\Baxpx$, contributing a total $q$-weight of $-p(\qan{i-1})$ to $T_q(\Baxpx)$. 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(\qan{x})$ to $T_q(\Baxpx)$. We then see that if we sum the weights over all possible ways to place colored rooks in column
$C_{(t_i)}(\Baxpx)$ will get $p(\qan{x} - p(\qan{i-1})$. It follows that
\begin{eqnarray*}
T_q(\Baxpx) & = & \sum_{k=0}^n \sum_{V \in \mathcal{N}_{n-k,\px}(\Bpx)} \hspace{-.35in} H(V,q) \prod_{i=1}^k (p(\qan{x})-p(\qan{i-1}))\\
& = & \sum_{k=0}^n \prod_{i=1}^k (p(\qan{x})-p(\qan{i-1})) \sum_{V \in \mathcal{N}_{n-k,\px}(\Bpx))} \hspace{-.35in} H(V,q) \\
& = & \sum_{k=0}^n \left(\prod_{i=1}^k (p(\qan{x})-p(\qan{i-1}))\right) r^{aug}_{n-k,\px}(\Bpx,q),
\end{eqnarray*}
which is the desired result.
\end{proof}
\subsection{Type I $q$-poly-Stirling numbers}
\label{subsec:tIpsn}
In this section we will study the polynomials defined by the recursions
\begin{eqnarray}
&&\qSpolynkone{0}{0} = 1 \ \mbox{and} \ \qSpolyone = 0 \ \mbox{if $k < 0$ or $k > n$ and} \\
&&\qSpolynkone{n+1}{k} = \qSpolynkone{n}{k-1} + p(\qan{k})\qSpolyone\ \mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}
We will call these numbers the \emph{Type I $q$-poly Stirling numbers of the second kind}. We then define the numbers
\begin{eqnarray}
&&\qspolynkone{0}{0} = 1 \ \mbox{and} \ \qspolyone = 0 \ \mbox{if $k < 0$ or $k > n$ and} \\
&&\qspolynkone{n+1}{k} = \qspolynkone{n}{k-1} - p(\qan{n})\qspolyone\ \mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}
We will call these numbers the \emph{Type I $q$-poly Stirling numbers of the first kind}. If we now replace $\qspolyone$ with $(-1)^{(n-k)}\qcpolyone$, then we have the numbers which satisfy the recursion
\begin{eqnarray}
&&\qcpolynkone{0}{0} = 1 \ \mbox{and} \ \qcpolyone = 0 \ \mbox{if $k < 0$ or $k > n$ and} \\
&&\qcpolynkone{n+1}{k} = \qcpolynkone{n}{k-1} + p(\qan{n})\qcpolyone\ \mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}, \nonumber
\end{eqnarray}
and we will call these numbers the \emph{signless Type I $q$-poly Stirling numbers of the first kind}.
\begin{theorem} Let $n \in \bbn^0$ and consider a nonzero $\px \in \bbn^0[x]$. If $B = F(0,1,\ldots,n-1)$, then, for every $0 \leq k \leq n$,
\begin{equation}
\qcpolyone = f_{n-k,\px}(\Bpx,q).
\end{equation}
\end{theorem}
\begin{proof} We see that $f_{0-0,\px}(\Bpx,q) = f_{0,\px}(\Bpx,q) = 1 = \qcpolynkone{0}{0}$. Now, we proceed by induction and consider the boards $B=F(0,1,\ldots,n-1)$ and $\overline{B}=F(0,1,\ldots,n-1,n)$. Then $f_{n+1-k,\px}(\overline{B}(\px),q)$ gives the total $q$-weight over all possible colored $(n+1-k)$-placements of file rooks in the board $\overline{B}(\px)$. 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,\px}(\Bpx,q)$. Otherwise, there is a rook placed in the last column of $\overline{B}(\px)$. In this case, there are rooks placed in $n-k$ of the first $n$ columns of $\overline{B}(\px)$, and those rooks contribute a total $q$-weight of $f_{n-k,\px}(\Bpx,q)$. Since the rooks placed in the last column of $\overline{B}(\px)$ 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(\qan{n})$ to the total weight of these placements. Thus,
\begin{eqnarray*}
f_{n+1-k,\px}(\overline{B}(\px),q) & = & f_{n+1-k,\px}(\Bpx,q) + p(\qan{n})f_{n-k,\px}(\Bpx,q) \\
& = & \qcpolynkone{n}{k-1} + p(\qan{n})\qcpolyone, \ \mbox{by induction} \\
& = & \qcpolynkone{n+1}{k}.
\end{eqnarray*}
\end{proof}
Combining this result with Theorem~\ref{thm:qpolyfilethm}, we have the product formula
\begin{equation}
\prod_{i=1}^n (p(\qan{x}) + p(\qan{i-1})) = \sum_{k=0}^n \qcpolyone (p(\qan{x}))^k. \label{eqn:ccc}
\end{equation}
If we then replace $p(\qan{x})$ in the above equation with $-p(\qan{x})$ and multiply both sides by $(-1)^n$, we get
\begin{equation}
\prod_{i=1}^n (p(\qan{x}) - p(\qan{i-1})) = \sum_{k=0}^n \qspolyone (p(\qan{x}))^k \label{eqn:sss}
\end{equation}
Now, we can apply Milne Inversion~\cite{kn:milne2} to show that the matrices $||\qSpolyone||$ and $||\qspolyone||$ are inverses of one
another, which also leads to the product formula
\begin{equation}
(p(\qan{x}))^n = \sum_{k=0}^n \qSpolyone \prod_{j=1}^k (p(\qan{x}) - p(\qan{j-1})), \label{eqn:SSS}
\end{equation}
although this formula also arises as a corollary to Theorem~\ref{thm:qpolyrookthm} and the following theorem.
\begin{theorem} Let $n \in \bbn^0$ and consider a nonzero $\px \in \bbn^0[x]$. If $B = F(0,1,\ldots,n-1)$, then, for every $0 \leq k \leq n$,
\begin{equation}
\qSpolyone = r^{aug}_{n-k,\px}(\Bpx,q).
\end{equation}
\label{thm:AS}
\end{theorem}
\begin{proof} We see that $r^{aug}_{0-0,\px}(\Bpx,q) = r^{aug}_{0,\px}(\Bpx,q) = 1 = \qSpolynkone{0}{0}$. Now, we proceed by induction and consider the boards $B=F(0,1,\ldots,n-1)$ and $\overline{B}=F(0,1,\ldots,n-1,n)$. Then $r^{aug}_{n+1-k,\px}(\overline{B}(\px),q)$ gives the total $q$-weight over all possible colored $(n+1-k)$-placements of nonattacking rooks in the board $\overline{B}(\px)$. Now, all rooks could be placed in the first $n$ columns, and the total $q$-weight over those placements is given by $r^{aug}_{n+1-k,\px}(\Bpx,q)$. Otherwise, there is a rook placed in the last column of $\overline{B}(\px)$. In this case, there are nonattacking rooks placed in $n-k$ of the first $n$ columns of $\overline{B}(\px)$, and those rooks contribute a total $q$-weight of $r^{aug}_{n-k,\px}(\Bpx,q)$. Then, the last column in each of the subboards of $\overline{B}(\px)$ 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}(\px)$. So, there are $n - (n-k) = k$ available cells in each subcolumn of the final column of $\overline{B}(\px)$, giving that the rooks placed in the last column of $\overline{B}(\px)$ will contribute a $q$-weight of $p(\qan{k})$ to the total weight of our $(n+1-k)$-placement. Thus,
\begin{eqnarray*}
r^{aug}_{n+1-k,\px}(\overline{B}(\px),q) & = & r^{aug}_{n+1-k,\px}(\Bpx,q) + p(\qan{k})r^{aug}_{n-k,\px}(\Bpx,q) \\
& = & \qSpolynkone{n}{k-1} + p(\qan{k})\qSpolyone, \ \mbox{by induction} \\
& = & \qSpolynkone{n+1}{k}.
\end{eqnarray*}
\end{proof}
Using the recursions given above, the following is a generalization of a well-known generating function for the Stirling numbers of the second kind.
\begin{theorem} For any $k \geq 1$,
\begin{equation}
\sum_{n \geq k} \qSpolynkone{n}{k} t^n = \frac{t^k}{(1-p(\qan{1})t)(1-p(\qan{2})t) \cdots (1-p(\qan{k})t)}.
\end{equation}
\label{thm:gftypeI}
\end{theorem}
\begin{proof} Let $\phi_k(t,q) = \sum_{n \geq k} \qSpolynkone{n}{k} t^n$. From our combinatorial interpretation we see that the only way to have an $n$-placement in $\Baxpx$, where $B =F(0,1, \ldots, n-1)$, is to place every rook at the top of its column. So, for all $n \in \bbn$, $\qSpolynkone{n}{1} = p(1) = p(\qan{1})$, giving $\phi_1(t,q) = \dfrac{t}{(1-p(\qan{1})t)}.$ Using our recursion for $\qSpolynkone{n}{k}$ we obtain
\begin{eqnarray*}
\phi_k(t,q) & = & \sum_{n \geq k} \qSpolynkone{n}{k} t^n \\
& = & \sum_{n \geq k} (\qSpolynkone{n-1}{k-1}+p(\qan{k})\qSpolynkone{n-1}{k}) t^n \\
& = & \sum_{n \geq k} \qSpolynkone{n-1}{k-1} t^n + \sum_{n \geq k} p(\qan{k})\qSpolynkone{n-1}{k} t^n \\
& = & t \phi_{k-1}(t,q) + t p(\qan{k}) \phi_k(t,q).
\end{eqnarray*}
Thus, $\phi_k(t,q) = \left( \dfrac{t}{(1-p(\qan{k})t)} \right) \phi_{k-1}(t,q)$, and our result follows by induction.
\end{proof}
\subsection{Type II $q$-counting in polyboards}
\label{sec:qpsnTII}
Here, given a nonzero $\px \in \bbn^0[x]$, we define the \emph{type II q-analogue of p(x)} to be $\qan{\px}$. We can express the polynomial $\qan{\px}$ in various forms. Recall that for nonnegative integers $x$ and $a$, we have the identity $\qan{x+a} = \qan{x} + q^x\qan{a}$. As an example, consider the type II $q$-analogue of the polynomial $\px = x^3 + 2x + 4$. We rewrite $\qan{\px}$ as
\begin{eqnarray*}
\qan{x^3 + 2x + 4} & = & \qan{x^3 + 2x} + q^{x^3 + 2x}\qan{4} \\
& = & \qan{x^3} + q^{x^3}\qan{2x} + q^{x^3 + 2x}\qan{4} \\
& = & \qan{x^3} + q^{x^3}(1+q^x)\qan{x} + q^{x^3 + 2x}(1+q+q^2+q^3)\qan{1}.
\end{eqnarray*}
So, we see that the $q$-analogue of $\px$ 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 $\Bpx$ with extra factors of $q$. We call this \emph{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)}(\Bm)$ 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 $\bbp \in \mathcal{N}_{2,(3)}(B^{(3)})$, as in Figure~\ref{fig:qrookII}, where the rooks are placed in columns $C_{i_1} = C_2$ and $C_{i_2} = C_4$.
\begin{figure}
\centering \epsfig{figure=qrookII.eps,height=1.5in}
\caption{A placement of non-attacking rooks in two columns of $B^{(3)}$ with $B = F(1,2,2,4,5)$.}
\label{fig:qrookII}
\end{figure}
\emph{Step 1:} We remove all of the rooks of $\bbp$ from $\Bm$, and we number each subcolumn of $\Bm$, from top to bottom, with the digits $0,1,2,\ldots,b_n-1$, as in Figure~\ref{fig:qrookIIb}.
\begin{figure}
\centering \epsfig{figure=qrookIIb.eps,height=1.5in}
\caption{Step 1: A numbering of the blank board $B^{(3)}$ with $B = F(1,2,2,4,5)$.}
\label{fig:qrookIIb}
\end{figure}
\emph{Step 2:} We will place the rooks which were in column $C_{i_1} = C_2$ of the original placement in $\Bm$ 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, \ldots, a_m$, we will assign these rooks a $q$-weight of $\nu_C(C_{i_1},q) = q^{(a_1 a_2 \cdots a_m)_{b_{i_1}}}$, where $(a_1 a_2 \cdots a_n)_p$ is the $p$-ary digit $a_1 (p^{n-1}) + a_2 (p^{n-2}) + \cdots + a_n (p^0)$. In this case, the rooks placed in column $C_{i_1}$ give us a $q$-weight of $\nu_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~\ref{fig:qrookIIc}.
\begin{figure}
\centering \epsfig{figure=qrookIIc.eps,height=1.5in}
\caption{Step 2: We begin to place the original rooks back into the board $\Bm$, 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.}
\label{fig:qrookIIc}
\end{figure}
\emph{Step 3:} Now we will place the rooks back into column $C_{i_2}$, which here is the fourth column of $\Bm$. We then assign those rooks a $q$-weight of $\nu_C(C_{i_2},q) = q^{(a_1 a_2 \cdots a_m)_{b_{i_2}-1}}$, again reading the $a_i$ from left to right. Here the rooks in the fourth column of $\Bm$ will be assigned a $q$-weight of $\nu_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~\ref{fig:qrookIId}.
\emph{Step 4:} In general, we will, after replacing the rooks in a given column $C_{i_w}$, give those rooks a $q$-weight of $\nu_C(C_{i_w},q) := q^{(a_1 a_2 \cdots a_m)_{b_{i_w}-(w-1)}}$. We will then define the type-II $q$-weight of the original placement $\bbp \in \mnonattp{\Bm}$ to be
$$\nu(\bbp,q) := \prod_{w=1}^k \nu_C(C_{i_w},q).$$
Thus, the placement in Figure~\ref{fig:qrookII} has a type-II $q$-weight of
$$\nu(\bbp,q) = \prod_{w=1}^2 \nu_C(C_{i_w},q) = \nu_C(C_2,q)\nu_C(C_4,q) = q^4q^{11} = q^{15}.$$
We now define the $k^{th}$ \emph{type-II $qm$-rook number of $\Bm$} to be
\begin{equation}
\qmrookII{k}{\Bm} := \sum_{\bbp \in \mnonattp{\Bm}} \nu(\bbp,q).
\end{equation}
\begin{figure}
\centering \epsfig{figure=qrookIId.eps,height=1.5in}
\caption{Step 3: We repeat Step 2 for the rooks in column $C_4$.}
\label{fig:qrookIId}
\end{figure}
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 $\Bm$ with rooks placed in the cells $c(a_1,1,i_w)$, $c(a_2,2,i_w)$, $\ldots$, $c(a_m,m,i_w)$ of the column $C_{i_w}$, we define
$$\mu_C(C_{i_w},q) := q^{(a_1 a_2 \cdots a_m)_{b_{i_w}}}.$$
Then, given any placement $\bbp \in \mathcal{F}_{k,(m)}(\Bm)$, we define the type-II $q$-weight of $\bbp$ to be
$$\mu(\bbp,q) := \prod_{w=1}^k \mu_C(C_{i_w},q).$$
We then define the $k^{th}$ \emph{type II-$qm$-file number of $\Bm$} to be
\begin{equation}
\qmfileII{k}{\Bm} := \sum_{\bbp \in \mattp{\Bm}} \mu(\bbp,q).
\end{equation}
An example of this $q$-weighting can be seen in Figure~\ref{fig:qfileII}, and the placement shown has a type-II $q$-weight of $$\mu(\bbp,q) = q^{(101)_2} q^{(221)_5} q^{(204)_5} = q^5 q^{61} q^{54} = q^{120}.$$
\begin{figure}
\centering \epsfig{figure=qxmcountII.eps,height=2.2in}
\caption{An example of a $q$-count for a file rook placement $\bbp \in \mattp{\Bm}$, where $B = (0,1,2,4,5,5)$. This placement has a $q$-weight of $q^{120}$.}
\label{fig:qfileII}
\end{figure}
Using these definitions, one could prove that these type-II $qm$-rook and file numbers satisfy some simple recursions, much like in Theorem~\ref{thm:rookrec}.
\begin{theorem} \label{thm:rookrecII}
Suppose that $B =F(b_1,\ldots,b_n)$ and $\bar{B} = F(b_1, \ldots, b_n,b_{n+1})$ are Ferrers boards. Then for all $0 \leq k \leq n+1$,
\begin{equation}\label{mrookrecII}
\qmrookII{k}{\bar{B}^{(m)}} = \qmrookII{k}{\Bm} + \qan{(b_n-(k-1))^m}\qmrookII{k-1}{\Bm}
\end{equation}
and
\begin{equation}\label{mfilerecII}
\qmfileII{k}{\bar{B}^{(m)}} = \qmfileII{k}{\Bm} + \qan{(b_n)^m}\qmfileII{k-1}{\Bm},
\end{equation}
where $\qmrookII{0}{\Bm} = \qmfileII{0}{\Bm} = 1$ and $\qmrookII{k}{\Bm} = \qmfileII{k}{\Bm} = 0$ if $k < 0$ or
$k > n$.
\end{theorem}
We now further generalize this notion of type-II $q$-counting to include rook placements in our more generalized boards. To begin, suppose that $\bbp \in \mathcal{F}_{n,(m)}(\Bmx)$ and define
$$M_{\Bmx}(\bbp,q) := \prod_{j=1}^n M_{C,\Bmx}(C_j,q),$$
where we define $M_{C,\Bmx}(C_j,q)$ as follows.
\begin{description}
\item[(i.)] If the $m$ rooks in $C_j$ lie in the cells $c(a_1,1,j)$, $c(a_2,2,j)$, $\ldots$, $c(a_m,m,j)$, then $M_{C,\Bmx}(C_j,q) = \mu_C(C_j,q) = q^{(a_1a_2 \cdots a_m)_{b_j}}$.
\item[(ii.)] If the $m$ rooks in $C_j$ lie in the cells $c_x(a_1,1,j)$, $c_x(a_2,2,j)$, $\ldots$, $c_x(a_m,m,j)$, then $M_{C,\Bmx}(C_j,q) = q^{(d_1d_2 \cdots d_m)_x}$, where $d_i = a_i-1$.
\end{description}
An example of this type of $q$-weighting can be seen in Figure~\ref{fig:qxfileII}, where the same board and placement as in Figure~\ref{fig:qfileII} is used above the bar. Here,
\begin{eqnarray*}
M_{B_5^{(3)}}(\bbp,q) & = & \prod_{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^7q^5q^{79}q^{61}q^{54} \\
& = & q^{273}.
\end{eqnarray*}
\begin{figure}
\centering \epsfig{figure=qxmcountIIbxxx.ps,height=4.2in}
\caption{An example of a $q$-count for a file rook placement $\bbp \in \mathcal{F}_{6,(3)}(\mathcal{B}^{(3)}_x)$, where $B = (0,1,2,4,5,5)$ and $x=5$. This placement has a $q$-weight of $q^{273}$.}
\label{fig:qxfileII}
\end{figure}
\begin{theorem} Suppose $x,n \in \bbn^0$. If $B = \Fboard$ is any Ferrers board, then
\begin{equation}
\prod_{i=1}^n (\qan{x^m} + \qan{b_i^m}) = \sum_{k=0}^n \qmfileII{n-k}{\Bm} (\qan{x^m})^k.
\label{eqn:qxfileII}
\end{equation}
\label{thm:qxfileII}\end{theorem}
\begin{proof} Given a Ferrers board $B = \Fboard$, define
$$\bar{S}_q(\Bmx) := \sum_{\bbp \in \mathcal{F}_{n,(m)}(\Bmx)} M_{\Bmx}(\bbp,q).$$
We first consider the number of ways that we can place $m$ rooks in each column of $\Bmx$, starting with the leftmost column and working to the right. In the first column of $\Bmx$, there will be $x^m$ ways to place rooks in the $x$-part with a total $q$-weight of $\qan{\xm}$. Similarly, there are $b_1^m$ ways to place rooks above the bar, with a total $q$-weight of $\qan{b_1^m}$. So, the $q$-weight over all possible placements of $m$ rooks in $C_1$ is $M_{C,\Bmx}(C_1,q) = \qan{\xm} + \qan{b^m_1}$. 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,\Bmx}(C_j,q) = \qan{\xm} + \qan{b^m_j}$, and thus,
$$\bar{S}_q(\Bmx) = \prod_{i=1}^n (\qan{\xm} + \qan{b^m_i}).$$
Next, suppose we first fix a file placement $Z \in \mathcal{F}_{n-k,(m)}(\Bm)$. Then the $q$-weight of $Z$ is $\mu(Z,q)$. We wish to extend $Z$ to a placement $\bbp \in \mathcal{F}_{n,(m)}(\Bmx)$ such that $\bbp \cap \Bm = Z$. Each such $\bbp$ 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 $\xm$ ways of placing these $m$ rooks, which will give a total $q$-weight of $\qan{\xm}$ for each such column. As there are $k$ such empty columns, we have
\begin{eqnarray*}
\bar{S}_q(\Bmx) & = & \sum_{k=0}^n \sum_{Z \in \mathcal{F}_{n-k,(m)}(\Bm)} \mu(Z,q)(\qan{\xm})^k \\
& = & \sum_{k=0}^n (\qan{\xm})^k \sum_{Z \in \mathcal{F}_{n-k,(m)}(\Bm)} \mu(Z,q) \\
& = & \sum_{k=0}^n (\qan{x^m})^k \qmfileII{n-k}{\Bm}.
\end{eqnarray*}
\end{proof}
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 $\bbp \in \mathcal{N}_{n,(m)}(B^{aug,(m)}_x)$ with rooks placed, from left to right in columns $C_1,\ldots,C_n$ and define
$$V_{B^{aug,(m)}_x}(\bbp,q) = (-1)^{LA(\bbp)} \prod_{i=1}^n \bnu_C(C_i,q),$$
where we define $\bnu_C(C_j,q)$ as follows.
\begin{description}
\item[(i.)] If the $m$ rooks in $C_j$ lie in board $\Bm$, then $\bnu_C(C_j,q) = \nu_C(C_j,q)$.
\item[(ii.)] If the $m$ rooks in $C_j$ lie in the $x$-part of $B^{aug,(m)}_x$, then $\bnu_C(C_j,q) = M_{C,\Bmx}(C_j,q)$, that is, these rooks have the same $q$-weight as if they were in a file placement in $\Bmx$.
\item[(iii.)] If the $m$ rooks in $C_j$ lie in the cells $c_a(a_1,1,j), c_a(a_2,2,j), \ldots, 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 $\bnu(C_j,q) = q^{(e_1e_2 \cdots e_m)_{\alpha}}$, where $e_i = a_i - 1$, and $\alpha = j - 1 - t$.
\end{description}
An example of this type-II q-weighting can be seen in Figure~\ref{fig:qrookIIaug}, where the same board and placement as in Figure~\ref{fig:qrookII} are used above the high bar. Here,
\begin{eqnarray*}
V_{B^{aug,(m)}_x}(\bbp,q) & = & (-1)^{LA(\bbp)} \prod_{i=1}^5 \bnu(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}.
\end{eqnarray*}
\begin{figure}[t]
\centering \epsfig{figure=qrookIIaugxxx.ps,height=3.5in}
\caption{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)$.}
\label{fig:qrookIIaug}
\end{figure}
\begin{theorem} Suppose $x, n \in \bbn^0$. If $B = F(0,1,\ldots,n-1)$, then
\begin{equation}
(\qan{x^m})^n = \sum_{k=0}^n \qmrookII{n-k}{\Bm}\prod_{j=1}^k (\qan{\xm} - \qan{(j-1)^m}).
\label{eqn:qAmrook}
\end{equation}
\label{thm:qxrookII}
\end{theorem}
\begin{proof} Let $B=F(0,1,\ldots,n-1)$ and define
$$\overline{T}_q(B_x^{aug,(m)}) := \sum_{\bbp \in \mathcal{N}_{n,(m)}(B_x^{aug,(m)})} V_{B_x^{aug,(m)}}(\bbp,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 $q$-weight of $\bnu(C_1,q) = \qan{x^m}$. 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(\bbp)$, $\qan{x^m} + \qan{((j-1)-s)^m} - \qan{((j-1)-s)^m} = \qan{x^m}$. Thus,
$$\overline{T}_q(B_x^{aug,(m)} = (\qan{x^m})^n.$$
Next, suppose we first fix an $(n-k)$-nonattacking rook placement $U \in \mathcal{N}_{n-k,(m)}(\Bm)$, Then the $q$-weight of $U$ is $\nu(U,q)$. We wish to extend $U$ to a placement $\bbp \in \mathcal{N}_{n,(m)}(B_x^{aug,(m)})$ such that $\bbp \cap \Bm = U$. Each such $\bbp$ 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 $\qan{x^m} = \qan{x^m} - \qan{0^m}$. 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 $\qan{x^m} - \qan{(i-1)^m}$. As there are $k$ such empty columns, we have
\begin{eqnarray*}
\overline{T}_q(B_x^{aug,(m)}) &=& \sum_{k=0}^n \sum_{U \in \mathcal{N}_{n-k,(m)}(\Bm)} \nu(U,q) \prod_{j=0}^k(\qan{x^m} - \qan{(j-1)^m}) \\
& = & \sum_{k=0}^n \left(\prod_{j=0}^k(\qan{x^m} - \qan{(j-1)^m})\right) \sum_{U \in \mathcal{N}_{n-k,(m)}(\Bm)} \nu(U,q) \\
& = & \sum_{k=0}^n \left(\prod_{j=0}^k(\qan{x^m} - \qan{(j-1)^m})\right) \overline{r}_{n-k,(m)}(\Bm,q),
\end{eqnarray*}
which is the desired result.
\end{proof}
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~\ref{thm:rookrecII}.
\begin{corollary}
Suppose that $B =F(b_1,\ldots,b_n)$ and $\bar{B} = F(b_1, \ldots, b_n,b_{n+1})$ are Ferrers boards and let $\px \in \bbn[x]$. Then for all $0 \leq k \leq n+1$,
\begin{equation}\label{mrookrecIII}
\qprookII{k}{\Bpx} = \qprookII{k}{\Bpx} + \qan{p(b_n-(k-1))}\qprookII{k-1}{\Bpx}
\end{equation}
and
\begin{equation}\label{mfilerecIII}
\qpfileII{k}{\Bpx} = \qpfileII{k}{\Bpx} + \qan{p(b_n)}\qpfileII{k-1}{\Bpx},
\end{equation}
where $$\qprookII{0}{\Bpx} = \qpfileII{0}{\Bpx} = 1$$ and $$\qprookII{k}{\Bpx} = \qpfileII{k}{\Bpx} = 0 \ \mbox{if} \ k < 0 \ \mbox{or} \
k > n.$$
\end{corollary}
\subsection{Type II $q$-poly-Stirling numbers}
Consider the numbers defined by the recursions
\begin{eqnarray}
&&\qSpolynktwo{0}{0} = 1 \ \mbox{and} \ \qSpolytwo = 0 \ \mbox{if $k < 0$ or $k > n$ and} \\
&&\qSpolynktwo{n+1}{k} = \qSpolynktwo{n}{k-1} + \qan{p(k)}\qSpolytwo\ \mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}
We will call these numbers the \emph{Type II $q$-poly Stirling numbers of the second kind}. We then define the numbers
\begin{eqnarray}
&&\qspolynktwo{0}{0} = 1 \ \mbox{and} \ \qspolytwo = 0 \ \mbox{if $k < 0$ or $k > n$ and} \\
&&\qspolynktwo{n+1}{k} = \qspolynktwo{n}{k-1} - \qan{p(n)}\qspolytwo\ \mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}
We will call these numbers the \emph{Type II $q$-poly Stirling numbers of the first kind}. If we now replace $\qspolytwo$ with $(-1)^{(n-k)}\qcpolytwo$, then we have the numbers which satisfy the recursion
\begin{eqnarray}
&&\qcpolynktwo{0}{0} = 1 \ \mbox{and} \ \qcpolytwo = 0 \ \mbox{if $k < 0$ or $k > n$ and} \\
&&\qcpolynktwo{n+1}{k} = \qcpolynktwo{n}{k-1} + \qan{p(n)}\qcpolytwo\ \mbox{if $0 \leq k \leq n+1$ and $n \geq 0$},\nonumber
\end{eqnarray}
and we will call these numbers the \emph{signless Type II $q$-poly Stirling numbers of the first kind}.
\begin{theorem} Let $n \in \bbn$ and consider a nonzero $\px \in \bbn^0[x]$. If $B = F(0,1,\ldots,n-1)$, then, for every $0 \leq k \leq n$,
\begin{equation}
\qcpolytwo = \overline{f}_{n-k,\px}(\Bpx,q)
\end{equation}
and
\begin{equation}
\qSpolytwo = \overline{r}_{n-k,\px}(\Bpx,q).
\end{equation}
\label{thm:xyz}
\end{theorem}
We omit the proof of this theorem, as it again shows that the respective polynomials satisfy the same recursions.
Combining this result with Theorem~\ref{thm:qxfileII}, we have the product formula
\begin{equation}
\prod_{i=1}^n (\qan{\px} + \qan{p(i-1)}) = \sum_{k=0}^n \qcpolytwo (\qan{\px})^k. \label{eqn:ccc2}
\end{equation}
If we then replace $\qan{\px}$ in the above equation with $-\qan{\px}$ and multiply both sides by $(-1)^n$, then we get
\begin{equation}
\prod_{i=1}^n (\qan{\px} - \qan{p(i-1)}) = \sum_{k=0}^n \qspolytwo (\qan{\px})^k. \label{eqn:sss2}
\end{equation}
Now, we can apply Milne Inversion~\cite{kn:milne2} to show that the matrices $||\qSpolytwo||$ and $||\qspolytwo||$ are inverses of one another, which also leads to the product formula
\begin{equation}
(\qan{\px})^n = \sum_{k=0}^n \qSpolytwo \prod_{j=1}^k (\qan{\px} - \qan{p(j-1)}), \label{eqn:SSS2}
\end{equation}
although this formula also arises as a corollary to Theorems~\ref{thm:qxrookII} and \ref{thm:xyz}.
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~\ref{thm:gftypeI}.
\begin{theorem} For any $k \geq 1$,
\begin{equation}
\sum_{n \geq k} \qSpolynktwo{n}{k} t^n = \frac{t^k}{(1-\qan{p(1)}t)(1-\qan{p(2)}t) \cdots (1-\qan{p(k)}t)}.
\end{equation}
\end{theorem}
\section{Concluding remarks}
We have given two different $q$-analogues of the generalizations of the poly-Stirling numbers defined by Miceli~\cite{kn:miceli}. 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 \in \bbn$ is given by
$$\pqan{n} = p^{n-1} + qp^{n-2} + \cdots + 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~\cite{kn:mr} 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~\cite{kn:riordan} provides a result for $\px = x^2$, it would be nice to have results for a general $\px$.
\section{Acknowledgement}
I would like to thank the referee for his/her time and helpful suggestions.
\begin{thebibliography}{9}
\bibitem{kn:gr} A. M. Garsia and J. B. Remmel,
$Q$-counting rook placements and a formula of Frobenius,
\emph{J. Combin. Theory Ser. A} \textbf{41} (1986), 246--275.
\bibitem{kn:miceli} B. K. Miceli,
$m$-Partition boards and poly-Stirling numbers,
\emph{J. Integer Seq.} \textbf{13} (2010),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Miceli/miceli.html}{Article 10.3.3}.
\bibitem{kn:mr} B. K. Miceli and J. Remmel,
Augmented rook boards and general product formulas,
\emph{Electron. J. Combin.} \textbf{15} (2008), \#R85.
\bibitem{kn:milne2} S. C. Milne
Inversion properties of triangular arrays of numbers,
\emph{Analysis} \textbf{1} (1981), 1--7.
\bibitem{kn:riordan} J. Riordan,
\emph{Combinatorial Identities}, Wiley, 1968.
\bibitem{kn:stanley2} R. P. Stanley,
\emph{Enumerative Combinatorics: Volume II}, Cambridge, 1999.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05E05.
\noindent \emph{Keywords: }
rook theory, rook placement, file placement, Stirling numbers,
poly-Stirling numbers, inverses, $q$-analogues.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 6 2011;
revised versions received September 29
2011; October 17 2011.
Published in {\it Journal of Integer Sequences},
November 4 2011.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}