\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://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf $m$-Partition Boards and \\
\vskip .1in
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}{\tt bmiceli@trinity.edu}\\
\end{center}

\vskip .2 in

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


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

\newcommand{\sg}{\sigma}
\newcommand{\bbp}{\ensuremath{\mathbb{P}}}
\newcommand{\bbr}{\ensuremath{\mathbb{R}}}
\newcommand{\bbq}{\ensuremath{\mathbb{Q}}}
\newcommand{\bbn}{\ensuremath{\mathbb{N}}}
\newcommand{\bbz}{\ensuremath{\mathbb{Z}}}

\newcommand{\Fboard}{\ensuremath{F(b_1, b_2, \ldots, b_n)}}
\newcommand{\Bm}{\ensuremath{B^{(m)}}}
\newcommand{\Bmx}{\ensuremath{B^{(m)}_x}}
\newcommand{\Bmn}{\ensuremath{\textbf{B}^{(m)}_n}}
\newcommand{\xm}{\ensuremath{x^m}}
\newcommand{\Sm}{\ensuremath{S^{\xm}_{n,k}}}
\newcommand{\cm}{\ensuremath{c^{\xm}_{n,k}}}
\newcommand{\sm}{\ensuremath{s^{\xm}_{n,k}}}
\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{\mxattp}[1]{\ensuremath{\mathcal{F}_{#1,(m)}(\Bmx)}}
\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{\mtuple}[3]{\ensuremath{{#1}^{(m)}_{#2,#3} = (#1^{(1)}, #1^{(2)}, \ldots #1^{(m)}) }}
\newcommand{\Pset}[2]{\ensuremath{\Pi^{(m)}_{#1,#2}}}
\newcommand{\Bpx}{\ensuremath{B(\px)}}

\numberwithin{theorem}{section} \numberwithin{equation}{section}

\section{Introduction}
\label{sec:intro}


Define $\bbn = \{1,2,3,\ldots\}$ and $\bbn^0 = \bbn \cup \{0\}$. Let $\mathbb{Q}[x]$ be the polynomial ring over the rational numbers
$\mathbb{Q}$. The Stirling numbers of the first and second kind are
the connection coefficient between power basis $\{x^n\}_{n \geq 0}$
and the falling factorial basis $\{(x)\downarrow_n\}_{n \geq 0}$
where $(x)\downarrow_0 =1$ and $(x)\downarrow_n = x(x-1) \cdots
(x-n+1)$ for $n \geq 1$. That is, the Stirling numbers of the first
kind $s_{n,k}$ are defined by the equation
\begin{equation}\label{basic1}
(x)\downarrow_n = \sum_{k=1}^n s_{n,k} x^k,
\end{equation}
and
the Stirling numbers of the second kind $S_{n,k}$ are defined
by the equation
\begin{equation}\label{basic2}
x^n = \sum_{k=1}^n S_{n,k} (x)\downarrow_k.
\end{equation}
They are also defined by the recursions
\begin{equation}\label{rec1}
s_{n+1,k} = s_{n,k-1}-n s_{n,k}
\end{equation}
where $s_{0,0} =1$ and $s_{n,k} =0$ if either $k<0$ or $k>n$, and
\begin{equation}\label{rec2}
S_{n+1,k} = S_{n,k-1} + kS_{n,k}
\end{equation}
where $S_{0,0} =1$ and $S_{n,k} =0$ if either $k<0$ or $k>n$. If we
let $c_{n,k} = (-1)^{n-k}s_{n,k}$, then the $c_{n,k}$'s satisfy the
recursion
\begin{equation}\label{rec3}
c_{n+1,k} = c_{n,k-1}+n c_{n,k}
\end{equation}
where $c_{0,0} =1$ and $c_{n,k} =0$ if either $k<0$ or $k>n$. There
are several combinatorial interpretations of the $S_{n,k}$'s and
$c_{n,k}$'s. For example, $S_{n,k}$ is the number of set partitions
of $\{1,\ldots,n\}$ into $k$ nonempty parts and $c_{n,k}$ equals the number
permutations $\sigma$ in the symmetric group $\mathcal{S}_n$ that
have $k$ cycles. The $S_{n,k}$'s and $c_{n,k}$'s also have nice
interpretations in terms of rook theory. Let $F(0,1,\ldots, n-1)$ be
a rook board whose columns heights are $0,1, \ldots ,n-1$ reading
from right to left. Then $S_{n,k}$ equals number of ways to place
$n-k$ rooks on $F(0,1,\ldots, n-1)$ so that no two rooks are in the
same row or column, and $c_{n,k}$ equals number of ways to place
$n-k$ rooks on $F(0,1,\ldots, n-1)$ so that no two rooks are in the
same column.



The goal of this paper is to develop the combinatorics of what we
call the poly-Stirling numbers. Let
$\poly{x} \in \bbn[x]$ where $0 \leq s_i < s_j$ whenever $i < j$. We
define the numbers $\spoly$ and $\Spoly$ by the following
recursions, respectively:

\begin{eqnarray} \label{eqn:ps1}
&&s_{0,0}^{p(x)} = 1 \ \mbox{and} \ s_{n,k}^{p(x)} = 0 \ \mbox{if $k
< 0$ or
$k > n$, and}\\
&&s_{n+1,k}^{p(x)} = s_{n,k-1}^{p(x)} - p(n)s_{n,k}^{p(x)} \
\mbox{if $0 \leq k \leq n+1$ and $n \geq 0$},\nonumber
\end{eqnarray}
and
\begin{eqnarray} \label{eqn:ps2}
&&S_{0,0}^{p(x)} = 1 \ \mbox{and} \ S_{n,k}^{p(x)} = 0 \ \mbox{if $k
< 0$ or
$k > n$, and}\\
&&S_{n+1,k}^{p(x)} = S_{n,k-1}^{p(x)} + p(k)S_{n,k}^{p(x)} \
\mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}
If we replace $\spoly$ with $(-1)^{n-k}\cpoly$, then we have the
recursion

\begin{eqnarray} \label{eqn:ps1a}
&&c_{0,0}^{p(x)} = 1 \ \mbox{and} \ c_{n,k}^{p(x)} = 0 \ \mbox{if $k
< 0$ or
$k > n$, and}\\
&&c_{n+1,k}^{p(x)} = c_{n,k-1}^{p(x)} + p(n)c_{n,k}^{p(x)} \
\mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}

We will call the sequence of numbers in Equation~(\ref{eqn:ps2}) the
\emph{poly-Stirling numbers of the second kind} for $p(x)$, the
sequence of numbers in Equation~(\ref{eqn:ps1}) the
\emph{poly-Stirling numbers of the first kind} for $p(x)$, and the
sequence of numbers in Equation~(\ref{eqn:ps1a}) the \emph{signless
poly-Stirling numbers of the first kind} for $p(x)$.


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


It is also the case that for any $p(x) \in \bbn[x]$,
the matrices $||s_{n,k}^{p(x)}||$ and $||S_{n,k}^{p(x)}||$ are
inverses of each other. This follows from  general inversion formula
due Milne \cite{kn:milne2} or can be directly verified by using
recursions (\ref{eqn:ps1}) and (\ref{eqn:ps2}). We use our
combinatorial interpretations the $S_{n,k}^{p(x)}$'s and
$s_{n,k}^{p(x)}$'s to give a direct combinatorial proof of this
fact.

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








\section{$m$-Partition Boards $\&$ Rook Placements}
\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 may 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$.



\begin{figure}
\begin{center}
\epsfig{figure=mpartition.eps,height=2.5in}
\vspace{-.8in}\caption{The board $B^{(2)}$, with $B =
F(0,1,3,4,4)$.} \label{fig:B2}
\end{center}
\end{figure}

Garsia and Remmel \cite{kn:gr} define two kinds of rook placements in
the board $\Bm$: nonattacking placements and file placements.
We let $\mnonattp{\Bm}$ denote the set of
placements of $mk$ rooks in $\Bm$ 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.

\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 the $l^{th}$ subcolumn of any column.
\end{description}


We shall call an element of $\mnonattp{\Bm}$ a \emph{nonattacking placement} of $mk$ rooks in $\Bm$. Another way to think of nonattacking rook placements is that as you place rooks from left to right, each rook $r$ that lies in a cell $c(t,l,j)$ cancels all the cells in the same row $t$ that lie in subcolumns
corresponding to $l$ to its right. Then a placement of rooks
satisfying (i) and (ii) above is a placement of nonattacking rooks
if no rook lies in a cell which is canceled by another rook to its
left. For example, on the left in Figure \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$" and we have placed dots in the cells
that are canceled by these rooks. Note that since rooks only cancel
cells that correspond to the same subcolumn, we do allow the
possibility of having rooks in the same row in a given column.



We let $\mattp{\Bm}$ denote the set of
placements of $mk$ rooks in $\Bm$ 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.
\end{description}
We call such placements \emph{file rook placements}. For example, on
the right in Figure \ref{fig:Bmplace} we have pictured a file
placement $\mathbb{Q} \in \mattp{\Bm}$ where $B = F(0,1,3,4,4)$, $m
=2$, and $k=2$.


\begin{figure}
\begin{center}
\epsfig{figure=Bmplacement.eps,height=2in} 
\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{array}{rcl}
\mrook{k}{\Bm} & := & |\mnonattp{\Bm}| \ \ \ \mbox{and}
\rule[-.3in]{.01cm}{0cm}\\
\mbox{}\mfile{k}{\Bm} & := & |\mattp{\Bm}|,
\end{array}$$
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$}.


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

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

\begin{proof} For (\ref{mrookrec}), we will classify the
nonattacking rook placements $\mathcal{N}_{k,(m)}(\bar{B}^{(m)})$
according to whether they have rooks in the last column.  That is,
if $\mathbb{P} \in \mathcal{N}_{k,(m)}(\bar{B}^{(m)})$ has no rooks
in the last column, then $\mathbb{P}$ can be viewed as an element of
$\mathcal{N}_{k,(m)}(B^{(m)})$ so that such rook placements are
counted by $\mrook{k}{\Bm}$. If $\mathbb{P} \in
\mathcal{N}_{k,(m)}((\bar{B}^{(m)})$ has rooks in the last column,
then  let $\mathbb{P}^*$ denote the rook placement in
$\mathcal{N}_{k-1,(m)}(\bar{B}^{(m)})$ that results from
$\mathbb{P}$ by removing all the rooks in the last column.  Now if
we are given such a $\mathbb{P}^*$, we claim that there are
$(b_{n+1}-(k-1))^m$ ways to extend $\mathbb{P}^*$ to a rook
placement in $\mathcal{N}_{k,(m)}(\bar{B}^{(m)})$. That is, in each
subcolumn $C_{(l,n+1)}$, there will $k-1$ cells which are canceled
by rooks in $\mathbb{P}^*$. Thus, we have $b_{n+1}-(k-1)$ choices of
where to put a rook in $C_{(l,n+1)}$ to extend $\mathbb{P}^*$. It
follows that the number of nonattacking rook placements in
$\mathcal{N}_{k,(m)}(\bar{B}^{(m)})$ that have rooks in the last
column is counted by $(b_{n+1}-(k-1))^m \mrook{k-1}{\Bm}$.

The recursion (\ref{mfilerec}) can be proved in the
same way. That is, $\mfile{k}{\Bm}$ counts those file placements in
$\mathcal{F}_{k,(m)}(\bar{B}^{(m)})$ that have no rooks in the last
column. If $\mathbb{Q}^*$ is file placement in
$\mathcal{F}_{k-1,(m)}(\bar{B}^{(m)})$ which has no rooks in the
last column, then there are $b_{n+1}^m$ ways to extend
$\mathbb{Q}^*$ to a rook placement in
$\mathcal{F}_{k,(m)}(\bar{B}^{(m)})$ by adding rooks in the last
column because for file placements, there are no restrictions on
where we can add rooks in any subcolumn $C_{(l,n+1)}$. Thus, the
number of file placements in $\mathcal{F}_{k,(m)}(\bar{B}^{(m)})$
that have rooks in the last column is counted by $b_{n+1}^m
\mfile{k-1}{\Bm}$.

\end{proof}






\subsection{$m$-Partition Boards $\&$ $\xm$-Stirling Numbers}
\label{subsec:xmandrooks}




Now we consider the special case of the poly-Stirling numbers where
the polynomial $p(x) = x^m$.  In such a case, we shall refer to such
numbers as \emph{$x^m$-Stirling numbers}. In particular, the
\emph{$\xm$-Stirling numbers of the first kind}, $\sm$, are defined
by the following recursions:
\begin{eqnarray}
&&\smnk{0}{0} = 1 \ \mbox{and} \ \smnk{n}{k} = 0 \ \mbox{if $k < 0$
or
$k > n$} \ \ \mbox{and} \\
&&\smnk{n+1}{k} = \smnk{n}{k-1} - n^m\sm \ \mbox{if $0 \leq k \leq
n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}

\noindent We now define $\sm = (-1)^{n-k}\cm$.  Thus, the integers
$\cm$, called the \emph{signless $\xm$-Stirling numbers of the first
kind}, satisfy the recursions:

\begin{eqnarray}
&&\cmnk{0}{0} = 1 \ \mbox{and} \ \cmnk{n}{k} = 0 \ \mbox{if $k < 0$
or
$k > n$} \ \ \mbox{and} \\
&&\cmnk{n+1}{k} = \cmnk{n}{k-1} + n^m\cm \ \mbox{if $0 \leq k \leq
n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}

\noindent Finally, the \emph{$x^m$-Stirling numbers of the second kind},
$\Sm$, satisfy the following recursions:

\begin{eqnarray}
&&\Smnk{0}{0} = 1 \ \mbox{and} \ \Smnk{n}{k} = 0 \ \mbox{if $k < 0$
or
$k > n$} \ \ \mbox{and} \\
&&\Smnk{n+1}{k} = \Smnk{n}{k-1} + k^m\Sm \ \mbox{if $0 \leq k \leq
n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}


Now if we let $B =F(0,1, \ldots, n-1)$ and $\bar{B}= F(0,1, \ldots,n-1,n)$
in Theorem \ref{thm:rookrec}, then we see that


\begin{equation}\label{Smrookrec}
r_{n+1-k,(m)}(\bar{B}^{(m)}) = \mrook{n-(k-1)}{\Bm}+ k^m \mrook{n-k}{\Bm}
\end{equation}
and
\begin{equation}\label{smfilerec}
f_{n+1-k,(m)}(\bar{B}^{(m)}) = \mfile{n-(k-1)}{\Bm}+ n^m \mfile{n-k}{\Bm}
\end{equation}

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

\begin{theorem} Let $m \in \bbn$ and $B = F(0,1,\ldots,n-1)$. Then
\begin{equation}
\Smnk{n}{k} =  \mrook{n-k}{\Bm},
\end{equation}
\begin{equation}
\cmnk{n}{k} = \mfile{n-k}{\Bm},
\end{equation}
and
\begin{equation}
\smnk{n}{k} = (-1)^{n-k} \mfile{n-k}{\Bm}.
\end{equation}
\end{theorem}

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


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


\begin{theorem}\label{thm:mpartfile}
Let $m\in \bbn$, $n \in \bbn^0$, $x \in \bbr$, and suppose that $B = \Fboard$
is a Ferrers board. Then
\begin{equation}\label{eq:mpartfile}
\displaystyle \prod_{i=1}^n (x^m + b_i^m) = \displaystyle
\sum_{k=0}^n \mfile{n-k}{B^{(m)}}(x^m)^k.
\end{equation}
 \end{theorem}

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

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

We let $\mxattp{n}$ denote the set of all placements of
$mn$ rooks in $\Bmx$ such that the following two conditions hold.
\begin{description}
\item[(i.)] There is a rook in every subcolumn.
\item[(ii.)] If any of the $m$ rooks placed in a given column lie above the high bar, then all $m$ rooks in that column must lie above the high bar.
\end{description}


\begin{figure}
\begin{center}
\epsfig{figure=Bmxplacement.eps,height=2.2in} \caption{An example of
the board $B_5^{(2)}$, with $B = F(0,1,3,4,4)$, along with a
corresponding example of a file placement.} \label{fig:Bmxplace}
\end{center}
\end{figure}


\noindent We call this type of placement a \emph{file placement in}
$\Bmx$.  An illustration of this type of placement can be seen in
the righthand side of Figure~\ref{fig:Bmxplace}.

 Given $x \in \bbn$, we count the
number of file placements in $\Bmx$ in two different ways.  First,
see that for each $i$, we have $b_i^m$ ways to place the $m$ rooks
above the high bar and $x^m$ ways to place $m$ rooks below the bar
in column $i$. Thus, we have $\prod_{i=1}^n (x^m+ b_i^m)$ file
placements of $mn$ rooks in $\Bmx$.  On the other hand suppose that
we fix a file placement $\mathbb{Q}$ of $m(n-k)$ rooks in $\Bm$.
Then we can count the number of ways to extend   $\mathbb{Q}$ to
file placement of $mn$ rooks in $\Bmx$ by adding rooks below the bar
in each of the $k$ columns that have no rooks.  There are $x^m$ ways
to place the rooks below the high bar for each such column. Thus,
the number of file placements of $mn$ rooks in $\Bmx$ is
$$\sum_{k=0}^n \sum_{\mathbb{Q} \in \mathcal{F}_{n-k,(m)}{(\Bm)}} (x^m)^k =
\sum_{k=0}^n f_{n-k,(m)}(B^{(m)}) (x^m)^k.$$

\end{proof}


Note that in the special case of Theorem \ref{thm:mpartfile} where
$B=F(0,1,\ldots, n-1)$, we see that (\ref{eq:mpartfile}) reduces
to
\begin{equation}\label{cmnkprod}
\prod_{i=1}^n (x^m + (i-1)^m) = \sum_{k=o}^n c^{x^m}_{n,k} (x^m)^k.
\end{equation}
Since Theorem \ref{thm:mpartfile} shows that (\ref{cmnkprod}) holds
for all integers $x\geq 0$ and (\ref{cmnkprod}) is a polynomial identity
if follows that (\ref{cmnkprod}) holds for all $x$. If we
replace $x^m$ by $-x^m$ in (\ref{cmnkprod}) and then multiply by
$(-1)^n$, the we obtain the following corollary.

\begin{corollary} For $m \in \bbn$ and $n \in \bbn^0$,
\begin{equation}\label{eq:cmnkprod}
\prod_{i=1}^n (x^m - (i-1)^m) = \sum_{k=o}^n s^{x^m}_{n,k} (x^m)^k.
\end{equation}
\end{corollary}



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

\begin{theorem}\label{thm:mpartrook}
Let $m \in \bbn$ and $n,x\in \bbn^0$ and suppose that $B
=F(0,1,2,\ldots,n-1)$. Then
\begin{equation}\label{eq:mpartrook}
(x^m)^n = \displaystyle \sum_{k=0}^n \mrook{n-k}{\Bm} \ x^m
(x^m-1^m) \cdots (x^m - (k-1)^m).
\end{equation}
 \end{theorem}

Our proof will be a modification a general product formula proved by M. and Remmel
\cite{kn:mr}. Given $B$, $m$, and $x$, we will construct an
augmented board $B^{aug,(m)}_x$. First we start with the board
$\Bmx$.  Then $B^{aug,(m)}_x$ is formed by adding columns of heights
$0,1\ldots,n-1$, reading from left to right, that consist of $m$
subcolumns below the $x$-part of $\Bmx$. We call the extra cells
that we added to $\Bmx$ to form $B^{aug,(m)}_x$ the \emph{lower
augmented part} of $B^{aug,(m)}_x$ and call the line that separates
the $x$-part and the lower augmented part of $B^{aug,(m)}_x$ the
\emph{low bar}. 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$.


Next we define the set of nonattacking rook placements,
$\mathcal{N}_{n,(m)}(B^{aug,(m)}_x)$, of $mn$ rooks in
$B^{aug,(m)}_x$ to be the set of placements $\mathbb{P}$ in
$B^{aug,(m)}_x$ such that the following three conditions hold.

\begin{description}
\item[(i.)] There is at most one rook in each subcolumn.
\item[(ii.)] For any given column $C_{(j)}(B^{aug,(m)}_x$),
either all $m$ rooks in that column are placed above the high bar,
below the low bar, or in the $x$-part of $B^{aug,(m)}_x$.
\item[(iii.)] No rook lies in a cell which is canceled by another rook.
\end{description}

Here rooks that are placed in either the $x$-part or the lower
augmented part of  $B^{aug,(m)}_x$ do not cancel any cells; however,
rooks placed in the upper part of  $B^{aug,(m)}_x$ do cancel cells.
If a rook $r$ is  placed in a cell $c(t,l,j)$ in the upper part,
then $r$ will cancel all the cells in $\Bm$ 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$.
To better illustrate this cancelation, 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$.  We are now in a position to
prove the previously stated theorem.

\begin{figure}
\begin{center}
\epsfig{figure=Bmxrookplacement.eps,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}


\vspace{.1in}

\noindent \begin{proof} We claim that
(\ref{eq:mpartrook}) arises from two different ways of computing the
sum
\begin{equation}\label{eq:keysum}
\sum_{\mathbb{P} \in \mathcal{N}_{n,(m)}(B^{aug,(m)}_x)} w(\mathbb{P}).
\end{equation}

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

\begin{equation*}
(x^m)^n= \sum_{\mathbb{P} \in \mathcal{N}_{n,(m)}(B^{aug,(m)}_x)}
w(\mathbb{P}).
\end{equation*}

Now suppose that we fix a placement $\mathbb{P}$ of $m(n-k)$ rooks
in $\Bm$.  Then we want to count the number of ways extend
$\mathbb{P}$ to a placement in $\mathcal{N}_{n,(m)}(B^{aug,(m)}_x)$.
Let $C_{(t_i)}(B^{aug,(m)}_x)$ be the $i^{th}$ column, reading left
to right, which has no rooks in that column. By construction,
$t_1=1$ so that there are $x^m$ ways to add rooks below the bar in
column $C_{(t_1)}(B^{aug,(m)}_x)$. For $1 < i \leq k$, there will be
$t_i-(i-1)$ columns to the left of $C_{(t_i)}(B^{aug,(m)}_x)$ which
have rooks above the high bar and these rooks will cancel
$t_i-(i-1)$ cells in each subcolumn of $C_{(t_i)}(B^{aug,(m)}_x)$ in
the lower augmented part of the $B^{aug,(m)}_x$. Thus, there will be
$t_i-(t_i-(i-1)) = (i-1)$ uncanceled cells in each subcolumn of
$C_{(t_i)}(B^{aug,(m)}_x)$ in the lower augmented part of the
$B^{aug,(m)}_x$. We then see that if we sum the weights over all
possible ways to place the $m$ rooks in column
$C_{(t_i)}(B^{aug,(m)}_x)$ we will get $x^m -(i-1)^m$. It follows
that
\begin{eqnarray*}
\sum_{\mathbb{P} \in \mathcal{N}_{n,(m)}(B^{aug,(m)}_x)}
w(\mathbb{P}) & = & \sum_{k=0}^n \sum_{\mathbb{P} \in
\mathcal{N}_{n-k,(m)}(B^{(m)})}
x^m (x^m -1^m) \cdots (x^m -(k-1)^m) \\
& = & \sum_{k=0}^n \mrook{n-k}{\Bm} \ x^m(x^m -1^m) \cdots (x^m
-(k-1)^m).
\end{eqnarray*}

\end{proof}

We note that it is possible to prove formulas which are similar to  (\ref{eq:mpartrook}) for any Ferrers board $\Fboard$. That is, the author and J. Remmel \cite{kn:mr} developed a rook theory model which allows one to prove more general product identities in rook theory. Suppose we are given any two sequences of nonnegative integers $\mathcal{B} = \{b_i\}_{i=1}^n$ and  $\mathcal{A} = \{a_i\}_{i=1}^n$, and two functions, $\mbox{sgn}, \overline{\mbox{sgn}}:[n] \rightarrow \{-1,+1\}$. Let $B = \Fboard$ be a skyline board.  M. and Remmel's a rook theory model is defined with an appropriate notion of rook numbers $r_k(\mathcal{B},\mathcal{A})$ such that the following product formula holds:
\begin{equation}
\prod_{i=1}^n (x + \mbox{sgn}(i)b_i) = \sum_{k=0}^n r_{n-k}(B,\mathcal{B},\mathcal{A}) \prod_{j=1}^{k} (x + \sum_{s \leq j} \overline{\mbox{sgn}}(s)a_s).
\label{eq:gp}
\end{equation}
Thus by replacing $x$ by $x^m$ and picking $\mathcal{A}$ and $\mathcal{B}$ appropriately, we can obtain identities of the form
\begin{equation}
\prod_{i=1}^n (x^m + c_i^{m}) = \sum_{k=0}^n r_{n-k}(\mathcal{B},\mathcal{A}) \prod_{j=0}^{k-1} (x^m -j^m),
\label{eq:gp1}
\end{equation}
of which (\ref{eq:mpartrook}) is a special case. (The $m$-rook theory
model presented in this paper suffices to develop the rook-theoretic
interpretations for the poly-Stirling numbers, although the more
general rook theory model found in M. and Remmel \cite{kn:mr} is more
complicated.)



Theorem \ref{thm:mpartrook} yields the following corollary involving
the $S_{n,k}^{x^m}$'s.

\begin{corollary} For $m\in \bbn$ and $n \in \bbn^0$,
\begin{equation}\label{Smnkprod}
(x^m)^n = \sum_{k=0}^n S_{n,k}^{x^m} \ x^m(x^m -1^m) \cdots (x^m
-(k-1)^m).
\end{equation}
\end{corollary}


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

\begin{theorem} For any $k \geq 1$,
\begin{equation}
\sum_{n \geq k} S_{n,k}^{x^m} t^n = \frac{t^k}{(1-t)(1-2^mt) \cdots (1-k^mt)}.
\end{equation}
\end{theorem}

\noindent \begin{proof} Let $\phi_k(t) = \sum_{n \geq k}
S_{n,k}^{x^m} t^n$. From our combinatorial interpretation we see
that the only way to place $(n-1)m$ rooks in $\Bm$ where $B =F(0,1,
\ldots, n-1)$ is to place every rook at the top of its column. Thus
$S_{n,1}^{x^m} =1$ for all $n$ and hence $\phi_1(t) =
\frac{t}{(1-t)}.$ Then we know that
\begin{eqnarray*}
\phi_k(t) &=& \sum_{n \geq k} S_{n,k}^{x^m} t^n \\
&=& \sum_{n \geq k} (S_{n-1,k-1}^{x^m} + k^m S_{n-1,k}^{x^m}) t^n \\
&=&  \sum_{n \geq k} S_{n-1,k-1}^{x^m} t^n + \sum_{n \geq k} k^m S_{n-1,k}^{x^m} t^n \\
&=& t \phi_{k-1}(t) +k^m t \phi_k(t).
\end{eqnarray*}
Thus, $\phi_k(t) = \frac{t}{(1-k^mt)} \phi_{k-1}(t)$, and our result
follows by induction. 

\end{proof}




\subsection{Set and Cycle Structure Interpretations of $\xm$-Stirling Numbers}
\label{subsec:xmsetsub}

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

Let $[n] := \{1,2,3,\ldots,n\}$. For $m \geq 1$, let $\mtuple{P}{n}{k}$ be an
$m$-tuple of unordered set partitions of $[n]$ into $k$ parts and
$\Pset{n}{k} := \{P^{(m)}_{n,k} |$ the parts of $P_i$ and
$P_j$ have the same minimal elements for every $1 \leq i < j \leq m
\}$. We set $\Pset{0}{0} := \{\emptyset\}$.

\begin{theorem} Let $n$ be a nonnegative integer and let $m \in \bbn$.
Then $\Sm = |\Pset{n}{k}|$ for every $0 \leq k \leq n$.
\label{thm:Pset}
\end{theorem}

\noindent \begin{proof} Fix $m \in \bbn$.  First we note that
$|\Pset{n}{k}| = 0$ whenever $k<0$ or $k>n$, and $\Pset{0}{0} =
\{\emptyset\}$, so $|\Pset{0}{0}| = \Smnk{0}{0} = 1$. For $n=1$,
$|\Pset{1}{0}| = \Smnk{1}{0} = 0$ and $|\Pset{1}{1}| = \Smnk{1}{1} =
1$ since $\Pset{1}{1}$ is just the $m$-tuple $(\{1\}, \ldots, \{1\})$.
Proceeding by induction, we
will pick $n>1$ and assume that $|\Pset{n}{k}| = \Smnk{n}{k}$ for
every $0 \leq k \leq n$.

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

Thus,
$$\begin{array}{rcl}
|\Pset{n+1}{k}| & = & |\Pset{n}{k-1}|+k^m|\Pset{n}{k}|  \ \ \
\mbox{}
\rule[-.3in]{.01cm}{0cm}\\
\mbox{} & = & \Smnk{n}{k-1} +k^m\Smnk{n}{k} \ \ \ \mbox{}
\rule[-.3in]{.01cm}{0cm}\\
\mbox{} & = & \Smnk{n+1}{k}.
\end{array}$$

\end{proof}

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

\begin{center}
$(\{1\}\{2,3\}, \{1\}\{2,3\})$,

$(\{1\}\{2,3\}, \{1,3\}\{2\})$,

$(\{1,3\}\{2\}, \{1\}\{2,3\})$,

$(\{1,3\}\{2\}, \{1,3\}\{2\})$,

$(\{1,2\}\{3\}, \{1,2\}\{3\})$.
\end{center}

For $ m \geq 1$, let  $C^{(m)}_{n,k} = (\sg^{(1)}, \sg^{(2)}, \ldots, \sg^{(m)})$ be an $m$-tuple of
permutations of $[n]$ with $k$ cycles and define $\Omega^{(m)}_{n,k} =
\{C^{(m)}_{n,k} |$ the cycles of $\sg^{(i)}$ and $\sg^{(j)}$ have the same
minimal elements for every $1 \leq i < j \leq m\}$. Set
$\Omega^{(m)}_{0,0} := \{\emptyset\}$.

\begin{theorem} Let $n$ be a nonnegative integer and let $m \in \bbn$.
Then $\cm = |\Omega^{(m)}_{n,k}|$ for every $0 \leq k \leq n$.
\label{thm:Cset}
\end{theorem}

\noindent \begin{proof} Fix $m \in \bbn$.  First we note that
$|\Omega^{(m)}_{n,k}| = 0$ whenever $k<0$ or $k>n$, and
$\Omega^{(m)}_{0,0} = \{\emptyset\}$, so $|\Omega^{(m)}_{0,0}| =
c^{x^m}_{0,0} = 1$.  For $n=1$, $|\Omega^{(m)}_{1,0}| =
c^{x^m}_{1,0} = 0$ and $|\Omega^{(m)}_{1,1}| =
 c^{x^m}_{1,1} = 1$ since $\Omega^{(m)}_{1,1}$ is just
the $m$-tuple  $((1), \ldots, (1))$.  Proceeding by induction, we will pick $n>1$ and assume that $|\Omega^{(m)}_{n,k}| = c^{x^m}_{n,k}$ for every $0 \leq k \leq n$.

Suppose that $C^{(m)}_{n+1,k} \in \Omega^{(m)}_{n_1,k}$.  If $(n+1)$
is a cycle in $C_i \in C^{(m)}_{n+1,k}$, then $(n+1)$ is a cycle in
$C_j \in C^{(m)}_{n+1,k}$ for every $j = 1,2,\ldots,m$. Thus, we can
transform an $m$-tuple $C^{(m)}_{n,k-1} \mapsto C^{(m)}_{n+1,k}$ by
adding the cycle $(n+1)$ to every collection of cycles  of
$C^{(m)}_{n,k-1}$.  Similarly, if $(n+1)$ is not a cycle for some
$C_i \in C^{(m)}_{n+1,k}$, then $(n+1)$ is not cycle in any $C_j \in
C^{(m)}_{n+1,k}$ for $j = 1,2,\ldots,m$.  Thus, we can transform an
$m$-tuple $C^{(m)}_{n,k} \mapsto C^{(m)}_{n+1,k}$ by inserting $n+1$
immediately after one of the elements in each of the cycle
structures in  $C^{(m)}_{n,k}$, of which there are $n^m$ ways of
doing this.

Thus,
$$\begin{array}{rcl}
|\Omega^{(m)}_{n+1,k}| & = &
|\Omega^{(m)}_{n,k-1}|+n^m|\Omega^{(m)}_{n,k}|  \ \ \ \mbox{}
\rule[-.3in]{.01cm}{0cm}\\
\mbox{} & = & c^{x^m}_{n,k-1} +n^m c^{x^m}_{n,k} \ \ \ \mbox{}
\rule[-.3in]{.01cm}{0cm}\\
\mbox{} & = & c^{x^m}_{n+1,k}.
\end{array}$$

\end{proof}













\section{A Combinatorial Proof That $||S_{n,k}^{x^m}|| ||s_{n,k}^{x^m}|| =I$}
\label{sec:xmStirlings}

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

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

\begin{theorem} The lower triangular matrices defined by $||\Sm||$ and $||\sm||$ are inverses of one another.
\label{thm:xm1}
\end{theorem}

\noindent \begin{proof} Consider the sum
\begin{equation}
S(n) = \sum_{k=0}^n \sum_{j=0}^k \Sm \smnk{k}{j}.
\end{equation}

By definition, $\sm = (-1)^{n-k}\cm$, so we have
\begin{equation}
S(n) = \sum_{k=0}^n \sum_{j=0}^k (-1)^{k-j} \Sm \cmnk{k}{j}.
\label{eqn:aaa}
\end{equation}

Now, we can think of this sum as representing a certain weighting
over pairs of rook placements $(U,V) \in
(\mathcal{N}_{n-k,(m)}(\Bmn),\mathcal{F}_{k-j,(m)}(\textbf{B}^{(m)}_k))$.
Specifically, if for any Ferrers board $B$ we define $w(U) = (1)^k =
1$ for every $U \in \mnonattp{B}$ and $\tilde{w}(V) = (-1)^k$ for
every $V \in \mattp{B}$, then (\ref{eqn:aaa}) becomes
\begin{equation}
S(n) = \sum_{k=0}^n \sum_{j=0}^k \ \ \sum_{(U,V) \in
(\mathcal{N}_{n-k,(m)}(\Bmn),\mathcal{F}_{k-j,(m)}(\textbf{B}^{(m)}_k))}
w(U)\tilde{w}(V). \label{eqn:aab}
\end{equation}

We now consider the involution $I$ with the following properties:

\begin{description}
\item[(i.)] If for $(U,V) \in (\mathcal{N}_{n-k,(m)}(\Bmn),\mathcal{F}_{k-j,(m)}(\textbf{B}^{(m)}_k))$ $U$ has $m$
rooks in its last column, then $I(U,V) = (U^*,V^*) \in
(\mathcal{N}_{n-k-1,(m)}
(\textbf{B}^{(m)}_{n}),\mathcal{F}_{k-j,(m)}(\textbf{B}^{(m)}_{k+1}))$,
where
  \begin{description}
  \item[a.] $U^*$ is the placement $U$ with the rooks in the last column removed, and
  \item[b.] if $U$ had a rook in $C_{(l,n)}$ in the $w^{th}$ available cell, after cancelation, from the bottom of the board
  $\Bmn$, then $V^*$ is the placement $V$ copied into the larger board, $\textbf{B}^{(m)}_{k+1}$, with
  a rook placed in the cell $c(w,l,k)$ of $\textbf{B}^{(m)}_{k+1}$.
  \end{description}

\item[(ii.)] If for $(U^*,V^*) \in (\mathcal{N}_{n-k-1,(m)}(\textbf{B}^{(m)}_{n}),\mathcal{F}_{k-j+1,(m)}
(\textbf{B}^{(m)}_{k+1}))$, $U^*$ has no rooks in its last column
but $V^*$ does, then we reverse the above step.

\item[(iii.)] If for $(U,V) \in  (\mathcal{N}_{n-k,(m)}(\Bmn),\mathcal{F}_{k-j,(m)}(\textbf{B}^{(m)}_k))$
neither $U$ nor $V$ has $m$ rooks in the last column, then remove
the minimum number of columns, $s$, from both boards such that at
least one of the two placements remaining now has $m$ rooks in the
last column. We now have a new pair $(\hat{U},\hat{V}) \in
(\mathcal{N}_{n-k,(m)}(\textbf{B}^{(m)}_{n-s}),\mathcal{F}_{k-j,(m)}
(\textbf{B}^{(m)}_{k-s}))$.  We now repeat the above steps of $I$ on
$(\hat{U},\hat{V})$ to get a pair $(\hat{U}^*,\hat{V}^*)$.  We then
add $s$ empty column back to each board.
\end{description}

An example of parts 1 and 2 of the involution can be seen
in the lefthand side of Figure~\ref{fig:invoall}, where both $(U,V)$
and $(U^*,V^*)$ are shown. In this figure we have $(U,V) \in
(\mathcal{N}_{2,(3)}(\textbf{B}^{(3)}_5),\mathcal{F}_{2,(3)}(\textbf{B}^{(3)}_3))$,
and $(U^*,V^*) \in
(\mathcal{N}_{1,(3)}(\textbf{B}^{(3)}_5),\mathcal{F}_{3,(3)}(\textbf{B}^{(3)}_4))$.
In the righthand side of Figure~\ref{fig:invoall}, an illustration
of the third part of our involution is shown.  Here $(U,V) \in
(\mathcal{N}_{2,(3)}(\textbf{B}^{(3)}_5),\mathcal{F}_{2,(3)}(\textbf{B}^{(3)}_3))$
with neither containing a rook in the last column, but $V$
containing rooks in the second column from the right, that is,
$s=1$. Once we remove the last column of each board, we get new
placements $(\hat{U},\hat{V})$ and from there, since $\hat{V}$
contains rooks in its last column, we can invoke part 2 of $I$ to
give us $(\hat{U}^*,\hat{V}^*)$.  We now add one empty column back
to each board to complete the involution.

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

$$S(n) = \sum_{k=0}^n \sum_{j=0}^k \ \ \sum_{\stackrel{(U,V) \in (\mathcal{N}_{n-k,(m)}(\Bmn),\mathcal{F}_{k-j,(m)}
(\textbf{B}^{(m)}_k))}{I(U,V) = (U,V)}} w(U)\tilde{w}(V).$$

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

\end{proof}

\begin{figure}
\begin{center}
\epsfig{figure=invoall.eps,height=3in} \caption{An example of Parts
1 and 2 of the involution $I$ on the left side and an example of
Part 3 on the right.} \label{fig:invoall}
\end{center}
\end{figure}


















\section{Poly-Stirling Numbers}
\label{sec:psn}

\subsection{Notation}
\label{subsec:polymboards}

In this section we wish to generalize the rook model setting of
$m$-partition boards discussed in Section~\ref{sec:mboards}.
Throughout this section, we shall 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
will then define a set of $y$ $m$-partition boards $\Bpx :=
\{B^{(s_1)},B^{(s_2)},\ldots,B^{(s_y)}\}$, where $B^{(0)}$ is a
\emph{degenerate board} with $n$ columns.   The best way think of $B^{(0)}$ is that this board contains special columns of height 0 into which we allow rooks to be placed, and a more detailed description of the placement rules for such boards will be given in a subsequent section.  We will call $\Bpx$ the
\emph{polyboard associated with $B$ and $\px$}, and we will 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$.

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 will 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 will refer to the rook which lies in the leftmost
column of $\Bpx$ as the \emph{leftmost rook} in the board.


\begin{figure}
\centering \epsfig{figure=Npoly.eps,height=1in} \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 $\&$ Poly-File Numbers}
\label{subsec:polyrook}

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





\subsubsection{\textbf{\underline{Case I: \ $p(0) = 0$}}}
\label{subsubsec:zero}

We now consider placements of nonattacking rooks in $\Bpx$. These
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, and
\item[(ii.)] within any particular subboard, the nonattacking placement rules from
Section 2 apply to that board.
\end{description}

\noindent 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,
cancelation will occur in the following manner:

\begin{description}
\item[(i.)] If $r$ is the leftmost rook placed in the $j^{th}$ column of the $z^{th}$ subboard of $\Bpx$, then $r$
cancels as described in Section 2 within the $z^{th}$ subboard. The
rook $r$ will also cancel the lowest cell in each subcolumn to its
right in every other subboard in the board $\Bpx$, and every cell in
the $j^{th}$ column of all other subboards.
\item[(ii.)] If $r'$ is any other rook which has been placed in the $w^{th}$ subboard of $\Bpx$, then $r'$
cancels as described in Section 2 within the $w^{th}$ subboard. The
rook $r'$ will also cancel the lowest cell in each subcolumn to its
right, which has not yet been canceled by a rook to its left, in
every other subboard in the board $\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}

\noindent An example of such a placement and the corresponding
cancelation can be seen in Figure~\ref{fig:Npolycancelzero}, where
$B = F(1,2,3,5,5)$, $k = 3$, and $\px = p_1x + p_3x^3$. In this
figure, a cell labeled with an ``$i$" has been canceled by the rook
labeled as ``$X_i$".

\begin{figure}
\centering \epsfig{figure=Npolycancelzero2.eps,
height=3in,width=6in} \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_1x + p_3x^3$.} \label{fig:Npolycancelzero}
\end{figure}





We also consider file placements in the polyboard. These 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, and
\item[(ii.)] within any particular subboard, the file placement rules from
Section 2 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:Fpolycancelzero}, where again $B =
F(1,2,3,5,5)$, $k = 3$, and $\px = p_1x + p_3x^3$.

\begin{figure}
\centering \epsfig{figure=Fpolycancelzero2.eps,height=3in,width=6in}
\caption{An example of a file $k$-placement in the polyboard $\Bpx$,
with $B = F(1,2,3,5,5)$, $k=3$, and $\px = p_1x + p_3x^3$.}
\label{fig:Fpolycancelzero}
\end{figure}






\subsubsection{\textbf{\underline{Case II: \ $p(0) \neq 0$}}}
\label{subsubsec:nzero}

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

\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
    among the remaining boards it will cancel as described in the
    case where $p(0) = 0$.
    \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
    among the remaining boards it will cancel as described in the
    case where $p(0) = 0$.
    \end{description}
  \end{description}

\noindent An example of such a placement and the corresponding
cancelation 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
labeled as ``$X_i$".

\begin{figure}
\centering \epsfig{figure=Npolycancel.eps,height=2in,width=5.8in}
\caption{An example 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}


We also consider file placements in the polyboard. These 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 2 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=2in,width=5.8in}
\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}

Now, given any $\px \in \bbn[x]$, we let $\pxnonattp{\Bpx}$ denote
the set of colored nonattacking $k$-placements in the polyboard
$\Bpx$ such that 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}

\noindent We also define $\mathcal{F}_{k,\px}(\Bpx)$ to be the set
of colored file $k$-placements in $\Bpx$ under the exact same
coloring conditions as $\mathcal{N}_{k,\px}(\Bpx)$.

We then define
$$\begin{array}{rcl}
r_{k,\px}(\Bpx) & := & |\mathcal{N}_{k,\px}(\Bpx)| \ \ \ \mbox{and}
\rule[-.3in]{.01cm}{0cm}\\
f_{k,\px}(\Bpx) & := & |\mathcal{F}_{k,\px}(\Bpx)|,
\end{array}$$
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)$}.




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

\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 let $p(x) \in \bbn[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}

\noindent \begin{proof} For (\ref{polyrookrec}), we classify the
colored nonattacking $k$-placements in
$\mathcal{N}_{k,\px}(\bar{B}(\px))$ according to whether they have
rooks in the last column.  That is, if $\mathbb{P} \in
\mathcal{N}_{k,\px}(\bar{B}(\px))$ has no rooks in the last column,
then $\mathbb{P}$ can be viewed as an element of
$\mathcal{N}_{k,\px}(B(\px))$ so that such rook placements are
counted by $r_{k,\px}(\Bpx)$. If $\mathbb{P} \in
\mathcal{N}_{k,\px}((\bar{B}(\px))$ has rooks in the last column,
then let $\mathbb{P}^*$ denote the rook placement in
$\mathcal{N}_{k-1,\px}(\bar{B}(\px))$ that results from $\mathbb{P}$
by removing all the rooks in the last column.  Now if we are given
such a $\mathbb{P}^*$, we claim that there $p(b_{n+1}-(k-1))$ ways
to extend $\mathbb{P}^*$ to a rook placement in
$\mathcal{N}_{k,\px}(\bar{B}(\px))$. That is, in each subcolumn
$C_{(l,n+1)}$, there will $k-1$ cells which are canceled by rooks
$\mathbb{P}^*$. Thus we have $b_{n+1}-(k-1)$ choices of where to put
a rook in $C_{(l,n+1)}$ to extend $\mathbb{P}^*$. It follows that
the number of colored nonattacking rook placements in
$\mathcal{N}_{k,\px}(\bar{B}(\px))$ that have rooks in the last
column is counted by $p(b_{n+1}-(k-1)) r_{k-1,\px}(\Bpx)$.

Showing that recursion (\ref{polyfilerec}) holds can be proved in a
similar fashion.

\end{proof}

\noindent It is also worth noting here that
Theorem~\ref{thm:rookrec} follows directly from this theorem by
letting $\px = x^m$ for $m \in \bbn$.









\subsection{Polyboards $\&$ Poly-Stirling Numbers}
\label{subsec:polystirandrooks}



We return to the various types of poly-Stirling numbers defined by
Equations (1.6), (1.7), and (1.8) in Section 1. In particular, the
\emph{poly-Stirling numbers of the first kind with respect to
$p(x)$}, $\spoly$, are defined by the following recursion:
\begin{eqnarray*}
&&\spnk{0}{0} = 1 \ \mbox{and} \ \spnk{n}{k} = 0 \ \mbox{if $k < 0$
or $k > n$} \ \ \mbox{and} \\
 &&\spnk{n+1}{k} = \spnk{n}{k-1} -
p(n)\spoly \ \mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray*}

\noindent We now define $\spoly = (-1)^{n-k}\cpoly$.  Thus, the
integers $\cpoly$, called the \emph{signless poly-Stirling numbers
of the first kind with respect to $p(x)$}, satisfy the recursion:

\begin{eqnarray*}
&&\cpnk{0}{0} = 1 \ \mbox{and} \ \cpnk{n}{k} = 0 \ \mbox{if $k < 0$
or
$k > n$} \ \ \mbox{and} \\
&&\cpnk{n+1}{k} = \cpnk{n}{k-1} + p(n)\cpoly \ \mbox{if $0 \leq k
\leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray*}

\noindent Finally, the \emph{poly-Stirling numbers of the second kind with
respect to $p(x)$}, $\Spoly$, satisfy the following recursion:

\begin{eqnarray*}
&&\Spnk{0}{0} = 1 \ \mbox{and} \ \Spnk{n}{k} = 0 \ \mbox{if $k < 0$
or
$k > n$} \ \ \mbox{and} \\
&&\Spnk{n+1}{k} = \Spnk{n}{k-1} + p(k)\Spoly \ \mbox{if $0 \leq k
\leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray*}


Now if we let $B =F(0,1, \ldots, n-1)$ and $\bar{B}= F(0,1,
\ldots,n-1,n)$ in Theorem \ref{thm:polyrookrec}, then we see that


\begin{equation}\label{Spolyrookrec}
r_{n+1-k,\px}(\bar{B}(\px)) = r_{n+1-k,\px}(\Bpx)+ p(k)
r_{n-k,\px}(\Bpx)
\end{equation}
and
\begin{equation}\label{spolyfilerec}
f_{n+1-k,\px}(\bar{B}(\px)) = f_{n+1-k,\px}(\Bpx)+ p(n)
f_{n-k,\px}(\Bpx).
\end{equation}

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

\begin{theorem} Let $B = F(0,1,\ldots,n-1)$ and let $p(x) = \bbn[x]$. Then
\begin{equation}
\Spnk{n}{k} =  r_{n-k,\px}(\Bpx),
\end{equation}
\begin{equation}
\cpnk{n}{k} = f_{n-k,\px}(\Bpx),
\end{equation}
and
\begin{equation}
\spoly = (-1)^{n-k} f_{n-k,\px}(\Bpx).
\end{equation}
\end{theorem}

\begin{corollary}
Given $\px \in \bbn[x]$, $||\Spoly|| = ||\spoly||^{-1}$.
\end{corollary}

It is again a direct result of general inversion theorem due
to Milne  \cite{kn:milne2} that
the matrices formed by poly-Stirling numbers of the first and second
kind are inverses of each other; however, we could use our rook
theoretic interpretations to give a direct combinatorial proof of
this fact using an involution similar to the one given in the proof
of Theorem~\ref{thm:xm1}.


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

Consider the $y$-tuple of boards $B_x(\px) = \{
B^{(s_1)}_x,B^{(s_2)}_x,\ldots,B^{(s_y)}_x \}$ for some $x \in
\bbn$, where $B^{(s_u)}_x$ is defined in Section 2.  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 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, the file placement rules from
Section 2 apply to that board.
\item[(iv.)] The same coloring rules apply as before.
\end{description}

\noindent 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 cancelation can be seen in
Figure~\ref{fig:Fxpolycancel}, where $B = F(1,2,3,5,5)$, $\px = p_0
+ p_1x + p_3x^3$, and $x = 5$.

\begin{figure}
\centering \epsfig{figure=Fxpolycancel.eps,height=3.75in}
\caption{An example of a file rook placement in $B_5(\px)$, with $B
= F(1,2,3,5,5)$ and $\px = p_0 + p_1x + p_3x^3$.}
\label{fig:Fxpolycancel}
\end{figure}


\begin{theorem} Suppose $n \in \bbn^0$ and $\px = \poly{x} \in \bbn[x]$.  If $B = \Fboard$ is a 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}

\noindent \begin{proof}  Given a rook board $B = \Fboard$ and $\px
\in \bbn[x]$, we fix $x \in \bbn$ to show that
 (\ref{eqn:polyfileprod}) represents two ways to count
$|\mathcal{F}_{n,\px}(B_x(\px))|$. We first consider the number of
ways that we can place rooks in each column, starting with the
leftmost column and working to the right. In the first column of
$B_x(\px)$ there will be $x^{s_1} + x^{s_2} + \cdots + x^{s_y}$ ways
to place rooks below the high bar, and there will be $b_1^{s_1} +
b_1^{s_2} + \cdots + b_1^{s_y}$ ways to place rooks above the high
bar.  However, the total number of placements is different since we
are considering colored placements, and thus the total number of
colored placements of rooks below the bar is $p_{s_1} x^{s_1} +
p_{s_2} x^{s_2} + \cdots + p_{s_y} x^{s_y} = \px$ and the total
number of placements above the bar is $p_{s_1} b_1^{s_1} + p_{s_2}
b_1^{s_2} + \cdots + p_{s_y} b_1^{s_y} = p(b_1)$.  So, the total
number of placements in the first column of $B_x(\px)$ is $p(x) +
p(b_1)$. In general, in the $j^{th}$ column of the $B_x(\px)$, there
will be $p(x)$ total colored placements below in the $x$-parts and
$p(b_j)$ colored placements above the bar, and thus

\begin{equation*}
|\mathcal{F}_{n,\px}(B_x(\px))| = \prod_{i=1}^n (p(x) + p(b_i)).
\end{equation*}

Next, suppose that we first fix a placement $\bbp \in
\mathcal{F}_{n-k,\px}(\Bpx))$ above the bar. We claim that there are
$(p(x))^k$ ways to extend $\bbp$ to a placement $\mathbb{Q} \in
\mathcal{F}_{n,\px}(B_x(\px))$ such that $\mathbb{Q} \cap \Bpx =
\bbp$. That is, we want to count the number of ways to extend $\bbp$
to a placement $\mathbb{Q} \in \mathcal{F}_{n,\px}(B_x(\px))$ by
placing additional colored rooks below the bar in those columns
which contain no rooks from $\bbp$. Here, we see that for each empty
column, there are exactly $p(x)$ ways to place colored rooks in that
column.  As there are $k$ such columns, we have
\begin{eqnarray*}
|\mathcal{F}_{n,\px}(B_x(\px))| &=& \sum_{k=0}^n \sum_{\bbp \in \mathcal{F}_{n-k,\px}(\Bpx)} (p(x))^k \\
&=& \sum_{k=0}^n  \polyfile{n-k}{\Bpx} \ (p(x))^k.
\end{eqnarray*}

\end{proof}

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}


\noindent 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}



Now we will prove a product formula for poly-rook numbers. Consider
the $y$-tuple of boards $B^{aug}_x(\px) = \{B^{aug,(s_1)}_x,
B^{aug,(s_2)}_x, \ldots,B^{aug,(s_y)}_x \}$ for some $x \in \bbn$,
where $B^{aug,(s_u)}_x$ is defined in Section 2.  We call
$B^{aug}_x(\px)$ the \emph{augmented polyboard with respect to $B$
and $\px$}. In the case where $s_1 = 0$, $B^{aug,(0)}_x$ will be the
same as $B^{(0)}_x$. That is, $B^{aug,(0)}_x$ will consist of a
degenerate board and a degenerate $x$-part, but no lower augmented
part. We will refer to the upper parts of each board as such, and if
we talk about the \emph{upper part of $B^{aug}_x(\px)$}, 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 $B_x(\px)$} and the \emph{lower augmented part
of} $B^{aug}_x(\px)$. 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}
$B^{aug}_x(\px)$.  We allow placements in $B^{aug}_x(\px)$ such that that the following four conditions hold.

\begin{description}
\item[(i.)] Every column of $B^{aug}_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, the file placement rules from
Section 2 apply to that board.
\item[(iv.)] No rook lies in a cell which is canceled by another rook.
\end{description}

\noindent Here cancelation 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 $B^{aug}_x(\px)$ 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 $B^{aug}_x(\px)$.
    \end{description}
\item[(ii.)] Suppose $r'$ is any other rook which has been placed in
the $j^{th}$ 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_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 $B^{aug}_x(\px)$.
    \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 $\px \in \bbn[x]$, we then let
$\mathcal{N}_{n,\px}(B_x(\px))$ denote the set of colored placements
in $B^{aug}_x(\px)$ such that the above placement and cancelation
rules hold as do the same coloring rules as before.  An example of
these placement and cancelation rules are illustrated in
Figure~\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}(B_x(\px))$ a
weight $\nu(\mathbb{P}) = (-1)^{LA(\mathbb{P})}$, where
$LA(\mathbb{P})$ is the number of columns in $\mathbb{P}$ which
contain rooks which lie in the lower augmented part of
$B^{aug}_x(\px)$.  We are now in a position to prove another product
formula, this one involving the poly-rook numbers.

\begin{figure}
\centering \epsfig{figure=Nxpolycancel.eps,height=5.25in, width=6in}
\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}


\begin{theorem} Suppose $n \in \bbn^0$ and $\px = \poly{x} \in \bbn[x]$.  If $B = F(0,1,\ldots, n-1)$ then
\begin{equation}
(\px)^n = \sum_{k=0}^n r_{n-k,\px}(\Bpx)(\px - p(0))(\px -
p(1))\cdots (\px - p(k-1)). \label{eqn:polyrookprod}
\end{equation}
\label{thm:polyrookthm}
\end{theorem}




\noindent \begin{proof}  Given a rook board $B = \Fboard$ and $\px
\in \bbn[x]$, we fix $x \in \bbn$ to show that
 (\ref{eqn:polyrookprod}) represents two ways to enumerate
the sum
\begin{equation}
\mathcal{S}(B,\px) := \sum_{\mathbb{P} \in \mathcal{N}_{n,\px}(B^{aug}_x(\px))}
\nu(\mathbb{P}). \label{eqn:keysum7}
\end{equation}

First we see that in column 1, there are $x^{s_1} + x^{s_2} + \cdots
+ x^{s_y}$ ways to place uncolored rooks, and so there are $\px$
total ways to place colored rooks in the first column of our
augmented polyboard.  Thus for the second column, we have no
canceled cells. Hence there are $1^{s_1} + 1^{s_2} + \cdots +
1^{s_y} = p(1)$ ways to place colored rooks above the high bar,
$\px$ colored placements in the $x$-part, and $1^{s_1} + 1^{s_2} +
\cdots + 1^{s_y} = p(1)$ colored placements in the lower augmented
part. The total weight of these placements is $p(1) + \px - p(1) =
\px$. In general, if we have placed rooks in columns
$C_{(1)}(B^{aug,(m)}_x), \ldots , C_{(t-1)}(B^{aug,(m)}_x)$ where
exactly $s$ of the columns have rooks above the high bar, then there
will be $t-1-s$ uncanceled cells above the high bar and $t-1-s$
uncanceled cells below the low bar in every subcolumn of column $t$.
That is, in column $t$ there are $(t-1-s)^{s_1} + (t-1-s)^{s_2} +
\cdots + (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
$(t-1-s)^{s_1} + (t-1-s)^{s_2} + \cdots + (t-1-s)^{s_y} = p(t-1-s)$
ways to place colored rooks below the low bar. In such a case, the
weights of the rooks in the $t^{th}$ column will contribute
$p(t-1-s) + \px-p(t-1-s) = \px$ to (\ref{eqn:keysum7}). It then
follows that $\mathcal{S}(B,\px) = (\px)^n$.

Now suppose that we fix a placement $\mathbb{P}$ of rooks in $n-k$
columns of $\Bpx$. Then we want to count the number of ways extend
$\mathbb{P}$ to a placement in
$\mathcal{N}_{n,\px}(B^{aug}_x(\px))$. Let
$C_{(t_i)}(B^{aug}_x(\Bpx))$ be the $i^{th}$ column, reading left to
right, which has no rooks in that column. By construction, $t_1=1$
so that there are $\px$ ways to add rooks below the bar in column
$C_{(t_i)}(B^{aug}_x(\Bpx))$. For $1 < i \leq k$, there will be
$t_i-(i-1)$ columns to the left of $C_{(t_i)}(B^{aug}_x(\Bpx))$
which have rooks above the high bar and these rooks will cancel
$t_i-(i-1)$ cells in each subcolumn of $C_{(t_i)}(B^{aug}_x(\Bpx))$
in the lower augmented part of the $B^{aug}_x(\Bpx)$ and they will
cancel no cells in the $x$-part. Thus, there will be
$t_i-(t_i-(i-1)) = (i-1)$ uncanceled cells in each subcolumn of
$C_{(t_i)}(B^{aug}_x(\Bpx))$ in the lower augmented part of the
$B^{aug}_x(\Bpx)$. We then see that if we sum the weights over all
possible ways to place colored rooks in column
$C_{(t_i)}(B^{aug}_x(\Bpx))$ will get $\px - p(i-1)$. It follows
that
\begin{eqnarray*}
\mathcal{S}(B,\px) & = & \sum_{k=0}^n \sum_{\mathbb{P} \in
\mathcal{N}_{n-k,(m)}(B^{(m)})} \prod_{j=1}^k (\px - p(j-1)) \\
& = & \sum_{k=0}^n r_{n-k,\px}(\Bpx)\prod_{j=1}^k (\px - p(j-1)).
\end{eqnarray*}

\end{proof}

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

\begin{corollary}
For $n \in \bbn^0$ and $\px \in \bbn[x]$,
\begin{equation}
(\px)^n = \sum_{k=0}^n \Spoly \prod_{j=1}^k (\px - p(j-1)).
\end{equation}
\end{corollary}

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

\begin{corollary} For $k \in \bbn$ and $\px \in \bbn[x]$,
$$\sum_{n \geq k} \Spoly t^n = \frac{t^k}{(1-p(1)t)(1-p(2)t) \cdots (1-p(k)t)}.$$
\label{cor:pxmgf}
\end{corollary}














\subsection{Set and Cycle Structure Interpretations of $p(x)$-Stirling Numbers}
\label{subsec:p(x)setsub}

In this section, we show that $p(x)$-Stirling
numbers have combinatorial interpretations in terms of
certain collections of $m$-tuples of
set partitions and cycles.  Fix a polynomial $p(x) = p_0 + p_1 x + \cdots +
p_m x^m$ where $p_i \in \bbn^0$ and $p_m \neq 0$. For each $i$ such that
$p_i > 0$, fix a set of colors $c_{1,i}, \ldots, c_{p_i,i}$.


We shall start with giving a combinatorial interpretation of $S^{p(x)}_{n,k}$ in terms of certain
collections of unordered set partitions in the case where $p(0) \neq 0$. For $m > 0$, let $\bar{P}^{(m)}_{n,k} = (\bar{P}^{(1)}, \ldots, \bar{P}^{(m)})$ be an $m$-tuple of unordered set partitions of $\{0,1,\ldots, n\}$ into $k+1$ parts and let $\bar{\Pi}^{(m)}_{n,k} = \{\bar{P}^{(m)}_{n,k} \ |$ such that the parts $\bar{P}^{(i)}$ and $\bar{P}^{(j)}$ have the same minimal elements for every $1 \leq i < j \leq m\}$. We set $\bar{P}_{n,0}= \bar{\Pi}_{n,0}=(\{0, \ldots, n\})$ for all $n \geq 0$.

We define $\Theta^{p(x)}_{0,0} = \{\emptyset\}$ and $\Theta^{p(x)}_{n,k} = \{\emptyset\}$ if $k<0$ or $k>n$. For $n \geq 1$ and $0 \leq k \leq n$, let $\Theta^{p(x)}_{n,k}$ denote the set of sequences $(\bar{P}^{(0)}_{n,k}, \ldots,\bar{P}^{(m)}_{n,k})$ such that the following conditions hold.


\begin{description}
\item[(i.) \ ] If $p_i =0$, then $\bar{P}^{(i)}_{n,k} = \{\emptyset\}$.


\item[(ii.) \ ] If $i > 0$ and $p_i \neq 0$, then $\bar{P}^{(i)}_{n,k}$ consists of an $i$-tuple of unordered set partitions $(Q^{(1,i)}, \ldots, Q^{(i,i)}) \in \bar{\Pi}^{(i)}_{n,k}$. In addition, we will color certain elements in the unordered set partitions that appear in $\bar{P}^{(i)}_{n,k}$ according to the following rules.
    \begin{description}
    \item[a.] The elements in any unordered set partition that occurs in $\bar{P}^{(i)}_{n,k}$ which lie in the part that contains 0 or are the minimal element in its part are not colored.

    \item[b.] For each $1 \leq s \leq n$, if $s$ is not in the part containing 0 and is not a minimal element in its part, then $s$ is colored with the same color from $c_{1,i}, \ldots, c_{p_i,i}$ in each of the unordered set partitions $(Q^{(1,i)}, \ldots, Q^{(i,i)})$.
    \end{description}


\item[(iii.) \ ] $\bar{P}_{0,k}$ consists of the set partition $(\{0, \ldots, n\})$ where some of the elements $1, \ldots, n$ may be colored with one of the colors  $c_{1,0}, \ldots, c_{p_0,0}$.



\item[(iv.) \ ] For each $1 \leq s \leq n$, if there exists a $j \geq 1$ such that $s$ is a colored element in one of the unordered set partitions occurring $\bar{P}^{(j)}_{n,k}$, then $s$ is in the part that contains 0 in all unordered set partitions that occur in $\bar{P}^{(i)}_{n,k}$ if $i \neq j$ and $p_i \neq 0$. Moreover, $s$ is not colored in $\mathcal{P}_{0,k}$.



\item[(v.) \ ] The set of common minimal elements in $\bar{P}^{(i)}_{n,k}$ are the same for all $1 \leq i \leq m$ where $p_i \neq 0$.



\item[(vi.) \ ] If $s > 0$ is not one of the common minimal elements in $(\bar{P}^{(0)}_{n,k},  \ldots,\bar{P}^{(m)}_{n,k})$, and if $s$ is not always in the set with 0, then in exactly one of the $i$-tuples $\bar{P}^{(i)}_{n,k}$ where $p_i \neq 0$, all occurrences of $s$ must be colored.

\end{description}


\begin{theorem} Let $n\in \bbn^0$ and let
$p(x) =p_0+p_1x + \cdots + p_m x^m \in \bbn^0[x]$ where $p_0 \neq 0$.
Then $S^{p(x)}_{n,k} = |\Theta^{p(x)}_{n,k}|$ for every $0 \leq k \leq n$.
\label{thm:Ppxset}
\end{theorem}

\noindent \begin{proof} First observe that
$|\Theta^{p(x)}_{n,k}| = 0$ whenever $k<0$ or $k>n$, and $\Theta^{p(x)}_{0,0} = \{\emptyset\}$ so that $|\Theta^{p(x)}_{0,0}|= S^{p(x)}_{0,0} = 1$.  We now see that for all $ n\geq 0$,
$$S^{p(x)}_{n+1,0} = S^{p(x)}_{n,-1} +p(0) S^{p(x)}_{n,0}$$
Thus, it follows by induction that
$S^{p(x)}_{n,0} =p(0)^n$ for all $n \geq 0$. Now suppose that
$(\bar{P}^{(0)}_{n,0}, \ldots,\bar{P}^{(m)}_{n,0})
\in \Theta^{p(x)}_{n,0}$. Then for every $j$ such
that $p_j \neq 0$, all unordered set partitions that
appear $\bar{P}^{(j)}_{n,0}$ are just  $\{0, \ldots, n\}$.
Thus if $j \geq 1$ and $p_j \neq 0$, then no elements are colored in
$\bar{P}^{(j)}_{n,0}$. This means that
each of $1,2, \ldots, n$ must be colored in
$\bar{P}^{(0)}_{n,0}$. Since there are $p_0^n$ ways to color
the elements of $\bar{P}^{(0)}_{n,0}$, it follows
that $|\Theta^{p(x)}_{n,0}|=p(0)^n$ in this case.


For $n=1$,
$$S^{p(x)}_{1,1} = S^{p(x)}_{0,0} +p(1) S^{p(x)}_{0,1} =1.$$
In this case our definitions ensure that
if $(\bar{P}^{(0)}_{n,0}, \ldots,\bar{P}^{(m)}_{n,0})
\in \Theta^{p(x)}_{1,1}$, then for every $j$ such
that $p_j \neq 0$, every unordered set partition that
occurs in  $\bar{P}^{(j)}_{n,0}$ is just $\{0\},\{1\}$. Thus
no elements are allowed to be colored and hence
$|\Theta^{p(x)}_{1,1}|=1$.


Proceeding by induction, we pick $n>1$ and assume that $|\Theta^{p(x)}_{n,k}| = S^{p(x)}_{n,k}$ for
every $0 \leq k \leq n$.
Now suppose that $k \geq 1$ and $(\bar{P}^{(0)}_{n+1,k}, \ldots,\bar{P}^{(m)}_{n+1,k})
\in \Theta^{p(x)}_{n+1,k}$. Then if $\{n+1\}$ is a part in one of
the unordered set partitions that occur in  $(\bar{P}^{(1)}_{n+1,k}, \ldots,\bar{P}^{(m)}_{n+1,k})$, then $\{n+1\}$ is a part in every
unordered set partition that occurs in  $(\bar{P}^{(1)}_{n+1,k}, \ldots,\bar{P}^{(m)}_{n+1,k})$. Moreover it must be the
case that $n+1$ is not colored in $\bar{P}^{(0)}_{n+1,k}$.
It then follows that if we remove $\{n+1\}$ from every
unordered set partition which occurs in
$(\bar{P}^{(1)}_{n+1,k}, \ldots,\bar{P}^{(m)}_{n+1,k})$ and
we remove $n+1$ from $\bar{P}^{(0)}_{n+1,k}$, then
we will obtain an element of $\Theta^{p(x)}_{n,k-1}$.

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

\end{proof}


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

\begin{center}
$\{0,1,2,3\} \ | \ \{0,1\}\{2\}\{3\} \ | \ (\{0,1\}\{2\}\{3\},\{0,1\}\{2\}\{3\})$,

$\{0,1,2_Y,3\} \ | \ \{0,2\}\{1\}\{3\} \ | \ (\{0,2\}\{1\}\{3\},\{0,2\}\{1\}\{3\})$,

$\{0,1_Y,2,3\} \ | \ \{0,1\}\{2\}\{3\} \ | \ (\{0,2\}\{1\}\{3\},\{0,2\}\{1\}\{3\})$,

$\{0,1_Y,2,3\} \ | \ \{0,1\}\{2\}\{3\} \ | \ (\{0,2\}\{1\}\{3\},\{0,2\}\{1\}\{3\})$,

$\{0,1_Y,2,3\} \ | \ \{0,1\}\{2\}\{3\} \ | \ (\{0\}\{1,2_G\}\{3\},\{0\}\{1,2_G\}\{3\})$,



$\{0,1_Y,2,3\} \ | \ \{0,3\}\{1\}\{2\} \ | \ (\{0\}\{1\}\{2,3_G\},\{0\}\{1\}\{2,3_G\})$,

$\{0,1_Y,2,3\} \ | \ \{0,3\}\{1\}\{2\}  \ | \ (\{0\}\{1\}\{2,3_G\},\{0\}\{1,3_G\}\{2\})$,

$\{0,1_Y,2,3\} \ | \ \{0,3\}\{1\}\{2\}  \ | \ (\{0\}\{1,3_G\}\{2\},\{0\}\{1\}\{2,3_G\})$,

$\{0,1_Y,2,3\} \ | \ \{0,3\}\{1\}\{2\}  \ | \ (\{0\}\{1,3_G\}\{2\},\{0\}\{1,3_G\}\{2\})$,



$\{0,1_Y,2,3\} \ | \ \{0\}\{1,3_B\}\{2\} \ | \ (\{0,3\}\{1\}\{2\},\{0,3\}\{1\}\{2\})$,

$\{0,1_Y,2,3\} \ | \ \{0\}\{1,3_R\}\{2\} \ | \ (\{0,3\}\{1\}\{2\},\{0,3\}\{1\}\{2\})$,

$\{0,1_Y,2,3\} \ | \ \{0\}\{1\}\{2,3_B\} \ | \ (\{0,3\}\{1\}\{2\},\{0,3\}\{1\}\{2\})$,

$\{0,1_Y,2,3\} \ | \ \{0\}\{1\}\{2,3_R\} \ | \ (\{0,3\}\{1\}\{2\},\{0,3\}\{1\}\{2\})$,




$\{0,1_Y,2,3_Y\} \ | \ \{0,3\}\{1\}\{2\} \ | \ (\{0,3\}\{1\}\{2\},\{0,3\}\{1\}\{2\})$.
\end{center}



\noindent Now if $p_0 =0$, then  for all $ n\geq 0$,
$$S^{p(x)}_{n+1,0} = S^{p(x)}_{n,-1} +p(0) S^{p(x)}_{n,0} =0.$$
In this case, we let $\bar{\Theta}^{p(x)}_{n,k}$ be the set
of elements of $(\mathcal{P}^{(0)}_{n,k}, \ldots,\mathcal{P}^{(m)}_{n,k})
\in \Theta^{p(x)}_{n,k}$ so no element $s \geq 1$ that
lies in $\mathcal{P}^{(0)}_{n,0}$ is colored.
By our argument in the proof of Theorem
\ref{thm:Ppxset}, this forces $\bar{\Theta}^{p(x)}_{n,0} = \{\emptyset\}$
for all $n > 0$
so that $S^{p(x)}_{n,0} = |\bar{\Theta}^{p(x)}_{n,0}|$.
Then, essentially the same argument that we used to prove
Theorem \ref{thm:Ppxset} will prove the following theorem.


\begin{theorem} Let $n\in \bbn^0$ and let
$p(x) =p_1x + \cdots + p_m x^m \in \mathbb{N}^0[x]$.
Then $S^{p(x)}_{n,k} = |\bar{\Theta}^{p(x)}_{n,k}|$ for every
$0 \leq k \leq n$.
\label{thm:Ppxset0}
\end{theorem}



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


Let $\bar{C}^{(m)}_{n,k}$ be the set of
$m$-tuples of permutations of
$\{0,1, \ldots, n\}$ into $k+1$ cycles and let
$\bar{\Gamma}^{(m)}_{n,k}$ denote the sequences
$(\sg^{(1)}, \ldots, \sg^{(m)}) \in \bar{C}^{(m)}_{n,k}$ such that
the set of minimal elements of the cycles of $\sg^{(i)}$ are the
same for all $i$.


We define $\Delta^{p(x)}_{0,0} = \{\emptyset\}$ and
$\Delta^{p(x)}_{n,k} = \emptyset$ if $k < 0$ or $k>n$.
For $n \geq 1$ and $0 \leq k \leq n$,
let $\Delta^{p(x)}_{n,k}$ denote the set
of sequences $(\bar{C}^{(0)}_{n,k}, \ldots,\bar{C}^{(m)}_{n,k})$ such
that the following conditions hold.
\begin{description}
\item[(i.) \ ] If $p_i =0$, then $\bar{C}^{(i)}_{n,k} = \{\emptyset\}$.

\item[(ii.) \ ] If $i > 0$ and $p_i \neq 0$, then
$\bar{C}^{(i)}_{n,k}$ is an $i$-tuple of permutations
$(\sg^{(1,i)}, \ldots, \sg^{(i,i)}) \in \bar{\Gamma}^{(i)}_{n,k}$.
In addition,
we will color certain of the elements that occur in the permutations
in $\bar{C}^{(i)}_{n,k}$ according to the following
rules.
\begin{description}
\item[a.] For each $1 \leq j \leq i$, the minimal elements in each cycle
$\sg^{(j,i)}$ are not colored and 1 is not colored.

\item[b.] For each $1 \leq s \leq n$, if
$s$ is not a minimal element in its cycle and is not in the cycle that contains 0, then
$s$ is colored with a fixed  color from $c_{1,i}, \ldots, c_{p_i,i}$
in each of the permutations $(\sg^{(1,i)}, \ldots, \sg^{(i,i)})$.
In addition, if $s$ is in a cycle $(0,b_1, \ldots, b_r)$
that contains 0 and $s$ is colored,
then $s$ cannot be $b_1$ and
$s$ is colored with a fixed  color from $c_{1,i}, \ldots, c_{p_i,i}$
in each of the permutations $(\sg^{(1,i)}, \ldots, \sg^{(i,i)})$.
\end{description}

\item[(iii.) \ ] $\bar{C}_{0,k}$ consists of
the cycle $(0, \ldots, n)$ where some of
the elements $1, \ldots, n$ may be colored with one of
the colors  $c_{1,0}, \ldots, c_{p_0,0}$



\item[(iv.) \ ] For each $1 \leq s \leq n$, if there exists a $j$ such
that $s$ is a colored in some permutation in $\bar{C}^{(j)}_{n,k}$, then
$s$ is in the cycle of the form $(0,a_1, \ldots, a_r)$ in all $\bar{C}^{(i)}_{n,k}$ such
that $i \neq j$ and $p_i \neq 0$ where $s$ is not colored. Moreover, if
$s = a_t$, then any occurrence of $1, \ldots, s-1$ in that cycle must
be among $a_1, \ldots, a_{t-1}$.  If $j \neq 0$, then
$s$ is also not colored in $\bar{C}^{(0)}_{n,k}$.

\item[(v.) \ ] The set of common minimal elements in a cycle of the permutations
that occur in $\bar{C}^{(i)}_{n,k}$
are the same for all $1 \leq i \leq m$ where $p_i \neq 0$ and they
are never colored.

\item[(vi.) \ ] If $s > 0$ is not one of the common minimal elements in
$(\bar{C}^{(0)}_{n,k}, \ldots,\bar{C}^{(m)}_{n,k})$, , and if $s$ is not always in the set with 0, then
then in exactly one of the $i$-tuples $\bar{C}^{(i)}_{n,k}$ where $p_i \neq 0$, all occurrences of $s$ must be colored.



\end{description}


\begin{theorem} Let $n\in \bbn^0$ and let
$p(x) =p_0+p_1x + \cdots + p_m x^m \in \bbn^0[x]$ where $p_0 \neq 0$
Then $c^{p(x)}_{n,k} = |\Delta^{p(x)}_{n,k}|$ for every $0 \leq k \leq n$.
\label{thm:pxcycle}
\end{theorem}

\noindent \begin{proof} First observe that
$|\Delta^{p(x)}_{n,k}| = 0$ whenever $k<0$ or $k>n$, and $\Delta^{p(x)}_{0,0} = \{\emptyset\}$ so that $|\Delta^{p(x)}_{0,0}|= c^{p(x)}_{0,0} = 1$.

For $n=1$,
$$c^{p(x)}_{1,1} = c^{p(x)}_{0,0} +p(0) S^{p(x)}_{0,1} =1.$$
In this case our definitions ensure that
if $(\bar{C}^{(0)}_{1,1}, \ldots,\bar{C}^{(m)}_{1,1})
\in \Delta^{p(x)}_{1,1}$, then for every $j$ such
that $p_j \neq 0$, every permutation that
occurs in  $\bar{C}^{(j)}_{1,1}$ is just $(0)(1)$. Thus,
no elements are allowed to be colored and hence
$|\Delta^{p(x)}_{1,1}|=1$. Next
$$c^{p(x)}_{1,0} = c^{p(x)}_{0,-1} +p(0) S^{p(x)}_{0,0} =p_0.$$
In this case our definitions ensure that
if $(\bar{C}^{(0)}_{1,0}, \ldots,\bar{C}^{(m)}_{1,0})
\in \Delta^{p(x)}_{1,0}$, then for every $j$ such
that $p_j \neq 0$, every permutation that
occurs in  $\bar{C}^{(j)}_{1,0}$ is just $(0,1)$. Now 1 cannot
be colored in any permutation that occurs in $\bar{C}^{(i)}_{1,0}$
for any $i > 0$ where $p_i \neq 0$. Thus the only element
that can be colored is the 1 which occurs in the permutation
$(0,1)$ in $\bar{C}^{(0)}_{1,0}$. Since we can color
the 1 in $p_0$ ways, it follows that
$|\Delta^{p(x)}_{1,0}|=p(0)$.




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





Proceeding by induction, we
will pick $n>1$ and assume that $|\Delta^{p(x)}_{n,k}| = c^{p(x)}_{n,k}$ for
every $0 \leq k \leq n$.
Now suppose that $k \geq 1$ and $(\bar{C}^{(0)}_{n+1,k}, \ldots,\bar{C}^{(m)}_{n+1,k})
\in \Delta^{p(x)}_{n+1,k}$. Then if $(n+1)$ is a cycle in one of
the permutations that occur in  $(\bar{C}^{(1)}_{n+1,k}, \ldots,\bar{C}^{(m)}_{n+1,k})$, then $(n+1)$ is a cycle  in every
permutation that occurs in  $(\bar{C}^{(1)}_{n+1,k}, \ldots,\bar{C}^{(m)}_{n+1,k})$. Moreover, it must be the
case that $n+1$ is not colored in $\bar{C}^{(0)}_{n+1,k}$.
It then follows that if we remove the cycle $(n+1)$ from every
permutation which occurs in
$(\bar{C}^{(1)}_{n+1,k}, \ldots,\bar{C}^{(m)}_{n+1,k})$ and
we remove $n+1$ from the $(n+2)$-cycle in $\bar{C}^{(0)}_{n+1,k}$, then
we will obtain an element of $\Delta^{p(x)}_{n,k-1}$.
If $(n+1)$ is never a cycle  in any of the permutations
which occur in $(\bar{C}^{(0)}_{n+1,k}, \ldots,\bar{C}^{(m)}_{n+1,k})$, then for all $j >0$ such that $p_j \neq 0$,
$n+1$ is not a minimal element in its cycle in
any of the permutations that occur in $\mathcal{P}^{(j)}_{n+1,k}$.
This means that we can remove
$n+1$ from every permutation that occurs in $(\bar{C}^{(0)}_{n+1,k}, \ldots,\bar{C}^{(m)}_{n+1,k})$, and end up with
an element of $\Delta^{p(x)}_{n,k}$.
We  can create an element of
$\Delta^{p(x)}_{n+1,k}$ from $(\bar{C}^{(0)}_{n,k}, \ldots,\bar{C}^{(m)}_{n,k}) \in \Delta^{p(x)}_{n,k}$
in
two different ways. First, we can add a colored version
of $n+1$ at the end of the cycle $(0,1, \ldots, n)$ in
$\bar{C}^{(0)}_{n,k}$ so that we are forced by condition (iv.)
of our definitions
of $\Delta^{p(x)}_{n+1,k}$ to
add an uncolored version of $n+1$ at the end of every cycle
in $\bar{C}^{(i)}_{n,k}$ for all $i$ such that $p_i \neq 0$.
There are $p_0$ ways to do this depending on which color
we use for $n+1$ when we add $n+1$ at then end of the cycle in
$\bar{C}^{(0)}_{n,k}$. The other way we can create an
element of
$\Delta^{p(x)}_{n+1,k}$ from $(\bar{C}^{(0)}_{n,k}, \ldots,\bar{C}^{(m)}_{n,k})$ is to
pick an $i > 0$ where $p_i \neq 0$ and a color $c_{t,i}$ from
$c_{1,i}, \ldots, c_{p_i,i}$ and insert $n+1$ colored with
$c_{t,i}$ immediately  after some element from $1, \ldots, n$ in
the cycle structures of the permutations
$\sg^{(1,i)}, \ldots, \sg^{(i,i)}$. Note we cannot insert this colored
version of $n+1$ immediately after 0 in any of the cycles by
condition (ii.)b. of our definition of $\Delta^{p(x)}_{n,k}$.
We are then forced to add an uncolored version of $n+1$ at the
end of every cycle that occurs in $\bar{C}^{(j)}_{n,0}$ where
$j \neq i$.  It follows that there are $n$ different ways
to insert the colored version of $n+1$ in each of the cycles of
$\sg^{(1,i)}, \ldots, \sg^{(i,i)}$ so that there are a total
of $p_i n^i$ ways to do this. It follows that there
$p_0 + \sum_{i=1}^n p_i n^i = p(n)$ ways to create a new
element of $\Delta^{p(x)}_{n+1,k}$ from $(\bar{C}^{(0)}_{n,k}, \ldots,\bar{C}^{(m)}_{n,k})$, and so
\begin{eqnarray*}
|\Delta^{p(x)}_{n+1,k}| &=&
|\Delta^{p(x)}_{n,k-1}| + p(n)|\Delta^{p(x)}_{n,0}| \\
&=& c^{p(x)}_{n,k-1}+ p(n)c^{p(x)}_{n,k} \\
&=& c^{p(x)}_{n+1,k}
\end{eqnarray*}
as desired.

\end{proof}

Now if $p_0 =0$, then  for all $ n\geq 0$,
$$c^{p(x)}_{n+1,0} = p(0) \cdots p(n) =0.$$
In this case, we let $\bar{\Delta}^{p(x)}_{n,k}$ be the set
of elements of $(\bar{C}^{(0)}_{n,k}, \ldots,\bar{C}^{(m)}_{n,k})
\in \Delta^{p(x)}_{n,k}$ so that no element $s \geq 1$ that
occurs in $n+1$-cycle in $\bar{C}^{(0)}_{n,k}$ is colored.
By our argument in the proof of Theorem
\ref{thm:pxcycle}, this forces $\bar{\Delta}^{p(x)}_{n,0} = \{\emptyset\}$
for all $n > 0$
so that $c^{p(x)}_{n,0} = |\bar{\Delta}^{p(x)}_{n,0}|$.
Then, essentially the same argument that we used to prove
Theorem \ref{thm:pxcycle} will prove the following theorem.


\begin{theorem} Let $n\in \bbn^0$ and let
$p(x) =p_1x + \cdots + p_m x^m \in \bbn^0[x]$.
Then $c^{p(x)}_{n,k} = |\bar{\Delta}^{p(x)}_{n,k}|$ for every
$0 \leq k \leq n$.
\label{thm:pxcycle0}
\end{theorem}
















\section{$Q$-Analogues of Poly-Stirling Numbers}
\label{sec:qpsn}

For any positive integer $x$ 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 are two natural $q$-analogues of the numbers described in
Section~\ref{sec:psn}, namely, we can take the $q$-analogue of
$p(x)$ to be either $p([x]_q)$ or $[p(x)]_q$.  Thus, for example,
we can define the $q$-analogues of $s^{p(x)}_{n,k}$ and
$S^{p(x)}_{n,k}$ by the following recursions:
\begin{eqnarray} \label{eqn:ps1q1}
&&s_{0,0}^{p(x)}(q) = 1 \ \mbox{and} \ s_{n,k}^{p(x)}(q) = 0 \ \mbox{if $k
< 0$ or
$k > n$, and}\\
&&s_{n+1,k}^{p(x)}(q) = s_{n,k-1}^{p(x)}(q) - p([n]_q)s_{n,k}^{p(x)}(q) \
\mbox{if $0 \leq k \leq n+1$ and $n \geq 0$},\nonumber
\end{eqnarray}
and
\begin{eqnarray} \label{eqn:ps2q1}
&&S_{0,0}^{p(x)}(q) = 1 \ \mbox{and} \ S_{n,k}^{p(x)}(q) = 0 \ \mbox{if $k
< 0$ or
$k > n$, and}\\
&&S_{n+1,k}^{p(x)}(q) = S_{n,k-1}^{p(x)}(q) + p([k]_q)S_{n,k}^{p(x)}(q) \
\mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}
However, we can define a second $q$-analogue of
$s^{p(x)}_{n,k}$ and
$S^{p(x)}_{n,k}$ by the following recursions:
\begin{eqnarray} \label{eqn:ps1q2}
&&\bar{s}_{0,0}^{p(x)}(q) = 1 \ \mbox{and} \ \bar{s}_{n,k}^{p(x)}(q) = 0 \ \mbox{if $k
< 0$ or
$k > n$, and}\\
&&\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{if $0 \leq k \leq n+1$ and $n \geq 0$},\nonumber
\end{eqnarray}
and
\begin{eqnarray} \label{eqn:ps2q2}
&&\bar{S}_{0,0}^{p(x)}(q) = 1 \ \mbox{and} \ \bar{S}_{n,k}^{p(x)}(q) = 0 \ \mbox{if $k
< 0$ or
$k > n$, 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) \
\mbox{if $0 \leq k \leq n+1$ and $n \geq 0$}.\nonumber
\end{eqnarray}



It can be shown how to find appropriate $q$-statistics related to the $m$-boards considered
in Section~\ref{sec:mboards} to give combinatorial interpretations of both $s^{p(x)}_{n,k}(q)$ and $S^{p(x)}_{n,k}(q)$ and $\bar{s}^{p(x)}_{n,k}(q)$ and $\bar{S}^{p(x)}_{n,k}(q)$. This will be the subject of future papers.


\bibliographystyle{plain}
\begin{thebibliography}{99}

\bibitem{kn:gr} A. M. Garsia and J. B. Remmel, $Q$-counting rook configurations and a formula of Frobenius, \emph{J. Combin. Theory Ser. A} {\bf 41} (1986), 246--275.

\bibitem{kn:gould} H. G. Gould, The $q$-Stirling numbers of the first and second kinds, \emph{Duke Math. J.} {\bf 28} (1961), 281--289.

\bibitem{kn:mr} B. K. Miceli and J. Remmel, Augmented rook boards and
general product formulas, \emph{Electron. J. Combin.}, {\bf 15} (1)
(2008), Paper \#R85.  Available at \href{http://www.combinatorics.org/Volume_15/Abstracts/v15i1r85.html}{\tt http://www.combinatorics.org/Volume\_15/Abstracts/v15i1r85.html} .

\bibitem{kn:milne2} S. C. Milne, Inversion properties of triangular arrays of numbers,
\emph{Analysis} {\bf 1} (1981), 1--7.

\bibitem{kn:riordan}  J. Riordan, \emph{Combinatorial Identities}, Wiley, New York, 1968.

\bibitem{kn:stanley2}  R. Stanley, \emph{Enumerative Combinatorics: Volume II}, Cambridge, 1999

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05E05.

\noindent \emph{Keywords: } rook theory, rook placement, Stirling
numbers, inverses.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  September 8 2009;
revised version received  February 26 2010.
Published in {\it Journal of Integer Sequences}, February 26 2010.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}