\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{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\usepackage{amsthm}

\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 Bijective Proofs of Parity Theorems for Partition Statistics}
\vskip 1cm
\large
Mark Shattuck\\
Department of Mathematics\\
University of Tennessee\\
Knoxville, TN 37996-1300 \\
USA\\
\href{mailto:shattuck@math.utk.edu}{\tt shattuck@math.utk.edu}\\
\end{center}

\vskip .2 in
\begin{abstract}
We give bijective proofs of parity theorems for four  related  statistics
on partitions of finite sets. A consequence of our results is a combinatorial
proof of a congruence between Stirling numbers and binomial coefficients.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 


%\usepackage{amsmath}
%\usepackage{amssymb}

\newtheorem{theo}{Theorem}
\theoremstyle{remark}
\newtheorem*{rem}{Remark}

\numberwithin{equation}{section}
\numberwithin{theo}{section}

\allowdisplaybreaks[4]


\section{Introduction}\label{sec1}

The notational conventions of this paper are as follows:
$\mathbb{N}:=\{0,1,2,\dots\}$, $\mathbb{P}:=\{1,2,\dots\}$,
$[0]:=\varnothing$, and $[n]:=\{1,\dots,n\}$ for $n\in\mathbb{P}$. Empty
sums take the value $0$ and empty products the value $1$, with
$0^0:=1$. The binomial coefficient $\binom nk$ is equal to zero if
$k$ is a negative integer or if $0\leqslant n<k$.

Let $\Pi(n,k)$ denote the set of all partitions of $[n]$ with $k$ blocks
and $\Pi(n)$ the set of all partitions of $[n]$. Associate to each
$\pi\in\Pi(n,k)$ the ordered partition $(E_1,\dots,E_k)$ of $[n]$ comprising
the same blocks as $\pi$, arranged in increasing order of their smallest
elements, and define statistics $\tilde w$, $\hat w$, $w^*$, and $w$ by
\begin{align}
\label{e1.1}
\tilde w(\pi) &:= \sum_{i=1}^k(i-1)(|E_i|-1),\\
\label{e1.2}
\hat w(\pi) &:= \sum_{i=1}^ki(|E_i|-1)=\tilde w(\pi)+n-k,\\
\label{e1.3}
w^*(\pi) &:= \sum_{i=1}^ki|E_i|=\tilde w(\pi)+n+\binom k2,\\
\intertext{and}
\label{e1.4}
w(\pi) &:= \sum_{i=1}^k(i-1)|E_i|=\tilde w(\pi)+\binom k2.
\end{align}
Consider the generating functions (see \cite{b1}, \cite{b2}, \cite{b4},
and \cite{b5})
\begin{align}
\label{e1.5}
\tilde S_q(n,k) &:=\sum_{\pi\in\Pi(n,k)}q^{\tilde w(\pi)},\\
\label{e1.6}
\hat S_q(n,k) &:= \sum_{\pi\in\Pi(n,k)}q^{\hat w(\pi)}=q^{n-k}\tilde S_q(n,k),\\
\label{e1.7}
S_q^*(n,k) &:= \sum_{\pi\in\Pi(n,k)}q^{w^*(\pi)}=q^{\binom k2+n}
\tilde S_q(n,k),\\
\intertext{and}
\label{e1.8}
S_q(n,k) &:= \sum_{\pi\in\Pi(n,k)}q^{w(\pi)}=q^{\binom k2}\tilde S_q(n,k).
\end{align}
Summing the $q$-Stirling numbers $\tilde S_q(n,k)$, $\hat S_q(n,k)$,
$S_q^*(n,k)$, and $S_q(n,k)$ over $k$ yields the respective $q$-Bell
numbers $\tilde B_q(n)$, $\hat B_q(n)$, $B_q^*(n)$, and $B_q(n)$.
These polynomials reduce to the classical Stirling and Bell numbers when
$q=1$. Wagner \cite{b6} evaluates the foregoing polynomials when $q=-1$
using algebraic techniques and raises the question of finding bijective
proofs.

We now describe a combinatorial method for evaluating these polynomials when
$q=-1$. More generally, let $\Delta$ be a finite set of discrete
structures and $I:\Delta\to\mathbb{N}$, with generating function
\begin{equation}
\label{e1.9}
G(I,\Delta;q):=\sum_{\delta\in\Delta}q^{I(\delta)}=\sum_k
|\{\delta\in\Delta:\ I(\delta)=k\}|q^k.
\end{equation}
Of course, $G(I,\Delta;1)=|\Delta|$. If $\Delta_i:=\{\delta\in\Delta:
\ I(\delta)\equiv i\pmod2\}$, then $G(I,\Delta;-1)=|\Delta_0|-|\Delta_1|$.
Our strategy for finding $G(I,\Delta;-1)$ will be to identify a subset
$\Delta^*$ of $\Delta$ contained completely within $\Delta_0$ or $\Delta_1$
and then to define an $I$-parity changing involution on $\Delta-\Delta^*$.
The subset $\Delta^*$ thus captures both the sign and magnitude of
$G(I,\Delta;-1)$. In the present setting, $\Delta$ will either be 
$\Pi(n)$ or $\Pi(n,k)$ and $I$, one of the aforementioned partition statistics.

In \S~\ref{sec2}, we give bijective proofs establishing $\tilde B_q(n)$ and
$\hat B_q(n)$ as well as the four $q$-Stirling numbers when $q=-1$. In
\S~\ref{sec3}, a bijection yielding $B_{-1}^*(n)$ and $B_{-1}(n)$ is given.
A consequence of our results is a combinatorial proof requested by Stanley
of the congruence \cite[p. 46]{b3}
\begin{equation}\label{e1.10}
S(n,k)\equiv\binom{n-\lfloor k/2\rfloor-1}{n-k}\pmod 2,
\quad0\leqslant k\leqslant n,
\end{equation}
where $S(n,k)=|\pi(n,k)|$ denotes the Stirling number of the second kind.

\section{The First Bijection}\label{sec2}

Throughout, we'll represent $\pi\in\Pi(n)$ by $(E_1,E_2,\dots)$, the
unique ordered partition of $[n]$ comprising the same blocks as $\pi$, arranged
in increasing order of their smallest elements. Let $F_0=F_1=1$, with
$F_n=F_{n-1}+F_{n-2}$ if $n\geqslant2$. 

\begin{theo}\label{t2.1}
For all $n\in\mathbb{N}$,
\begin{equation}\label{e2.1}
\tilde B_{-1}(n):=\sum_{k=0}^n\tilde S_{-1}(n,k)=F_n.
\end{equation}
\end{theo}
\begin{proof}[\bf Proof]
Let $\Pi_i(n):=\{\pi\in\Pi(n):\ \tilde w(\pi)\equiv i\pmod2\}$ so that
$\tilde B_{-1}(n)=|\Pi_0(n)|-|\Pi_1(n)|$. To prove \eqref{e2.1}, we'll
identify a subset $\tilde\Pi(n)$ of $\Pi_0(n)$ such that
$|\tilde\Pi(n)|=F_n$ along with a $\tilde w$-parity changing involution
of $\Pi(n)-\tilde\Pi(n)$.

The set $\tilde\Pi(n)$ consists of those partitions $\pi=(E_1,E_2,\dots)$
whose blocks satisfy the two conditions:
\begin{align}
\label{e2.2a}\tag{2.2a}
&\text{each block of odd index comprises a set of consecutive integers;}\\
\label{e2.2b}\tag{2.2b}
&\text{each block of even index is a singleton.}
\end{align}
Now $|\tilde\Pi(n)|=F_n$, as $|\tilde\Pi(n)|$ is seen to satisfy the Fibonacci
recurrence, upon considering whether or not $\{n\}$ is a block. For if
$\{n\}$ is not a block and $n-2$ belongs to an odd-numbered (respectively, 
even-numbered)
block of $\pi\in\tilde\Pi(n)$, then $\{n-1,n\}$ constitutes a proper subset of
(respectively, all of) the last block of $\pi$.

Suppose now that $\pi=(E_1,E_2,\dots)$ belongs to $\Pi(n)-\tilde\Pi(n)$ and
that $i_0$ is the smallest of the integers $i$ for which 
$E_{2i-1}$ fails to satisfy \eqref{e2.2a} or $E_{2i}$ fails to
satisfy \eqref{e2.2b}.
Let $M$ be the largest member of $E_{2i_0-1}\cup E_{2i_0}$. If $M$ belongs
to $E_{2i_0-1}$, move it to $E_{2i_0}$, while if $M$ belongs to $E_{2i_0}$,
move it to $E_{2i_0-1}$
(note that if $|E_{2i_0}|=1$, then necessarily 
$M\in E_{2i_0-1}$). The resulting map is a parity changing involution
of $\Pi(n)-\tilde\Pi(n)$.
\end{proof}

Below, we illustrate the fixed point set $\tilde\Pi(n)$ and the
pairings of $\Pi(n)-\tilde\Pi(n)$ when $n=4$, wherein the first
two members of each row are paired.
\begin{xalignat*}{3}
&\Pi_0(n)-\tilde\Pi(n) &\qquad &\Pi_1(n) &\qquad &\tilde\Pi(n)\\
&\{1,2,4\},\ \{3\} &\qquad &\{1,2\},\ \{3,4\} &\qquad &\{1,2,3,4\}\\
&\{1,3,4\},\ \{2\} &\qquad &\{1,3\},\ \{2,4\} &\qquad &\{1,2,3\},\ \{4\}\\
&\{1\},\ \{2,3,4\} &\qquad &\{1,4\},\ \{2,3\} &\qquad &\{1\},\ \{2\},\ \{3,4\}\\
&\{1,3\},\ \{2\},\ \{4\} &\qquad &\{1\},\ \{2,3\},\ \{4\} &\qquad
&\{1,2\},\ \{3\},\ \{4\}\\
&\{1,4\},\ \{2\},\ \{3\} &\qquad &\{1\},\ \{2,4\},\ \{3\} &\qquad
&\{1\},\ \{2\},\ \{3\},\ \{4\}
\end{xalignat*}
Note that the above bijection preserves the number of blocks of
$\pi\in\Pi(n)$. We'll use its restriction to $\Pi(n,k)$ to prove
\addtocounter{equation}{1}
\begin{theo}\label{t2.2}
For all $n\in\mathbb{N}$,
\begin{equation}\label{e2.3}
\tilde S_{-1}(n,k)=\binom{n-\lfloor k/2\rfloor-1}{n-k},\qquad
0\leqslant k\leqslant n.
\end{equation}
\end{theo}
\begin{proof}[\bf Proof]
Let $\Pi_i(n,k):=\Pi_i(n)\cap\Pi(n,k)$ for $i=0,1$, 
$\tilde\Pi(n,k):=\tilde\Pi(n)\cap\Pi(n,k)$, and $\pi=(E_1,\dots,E_k)
\in\tilde\Pi(n,k)$. If $k$ is even, identify each pair of blocks
$(E_{2i-1},E_{2i})$, $1\leqslant i\leqslant k/2$, with summands $x_i$ in 
a composition $x_1+\cdots+x_{k/2}=n$, where each $x_i\geqslant2$.
If $k$ is odd, identify $(E_1,E_2),\dots,(E_{k-2},E_{k-1}),(E_k)$
with summands $x_i$ in $x_1+\cdots +x_{(k+1)/2}=n$ where
$x_i\geqslant2$ for $1\leqslant i\leqslant\frac{k-1}2$ and 
$x_{(k+1)/2}\geqslant1$. The cardinality of $\tilde\Pi(n,k)$ is then
given by the right hand side of \eqref{e2.3}, and the restriction of the
prior bijection to $\Pi(n,k)-\tilde\Pi(n,k)$ is again an involution, and
inherits the parity changing property, which proves \eqref{e2.3}.
\end{proof}

From \eqref{e2.3} along with \eqref{e1.6}, \eqref{e1.7}, and \eqref{e1.8},
we have
\begin{align}
\label{e2.4}
\hat S_{-1}(n,k) &= (-1)^{n-k}\binom{n-\lfloor k/2\rfloor-1}{n-k},
\qquad 0\leqslant k\leqslant n,\\
\label{e2.5}
S_{-1}^*(n,k) &= (-1)^{\binom k2+n}\binom{n-\lfloor k/2\rfloor-1}{n-k},
\qquad0\leqslant k\leqslant n,\\
\intertext{and}
\label{e2.6}
S_{-1}(n,k) &= (-1)^{\binom k2}\binom{n-\lfloor k/2\rfloor-1}{n-k},
\qquad0\leqslant k\leqslant n.
\end{align}
The bijection establishing \eqref{e2.3} clearly applies to 
\eqref{e2.4}--\eqref{e2.6} as well. 

Let $S(n,k)=|\Pi(n,k)|$ denote the Stirling number of the second kind.
The bijection of Theorem~\ref{t2.2} also proves combinatorially that
\begin{equation}\label{e2.7}
S(n,k)\equiv\binom{n-\lfloor k/2\rfloor-1}{n-k}\pmod2,\qquad
0\leqslant k\leqslant n,
\end{equation}
since off of a set of cardinality $\binom{n-\lfloor k/2\rfloor-1}{n-k}$,
each partition $\pi\in\Pi(n,k)$ is paired with another of opposite 
$\tilde w$-parity. This furnishes an answer to a question raised by
Stanley \cite[p. 46]{b3}.

Let $F_{-3}=-1$, $F_{-2}=1$, and $F_{-1}=0$. We conclude this section
by proving

\begin{theo}\label{t2.3}
For all $n\in\mathbb{N}$,
\begin{equation}\label{e2.8}
\hat B_{-1}(n):=\sum_{k=0}^n\hat S_{-1}(n,k)=(-1)^{n-1}F_{n-3}.
\end{equation}
\end{theo}
\begin{proof}[\bf Proof]
Let $n\geqslant3$, $\tilde\Pi(n)$ be as in the proof of Theorem~\ref{t2.1},
and $\hat\Pi(n)\subseteq\tilde\Pi(n)$ consist of those partitions with an
odd number of blocks and whose last block is a singleton. First,
$|\hat\Pi(n)|=|\tilde\Pi(n-3)|=F_{n-3}$ as the removal of
$n-2$, $n-1$, and $n$ from $\pi\in\hat\Pi(n)$ is seen to be
a bijection between $\hat\Pi(n)$ and $\tilde\Pi(n-3)$. Since
$\hat w(\pi)=\tilde w(\pi)+n-k$ and since every $\pi\in\hat\Pi(n)$ has an
even $\tilde w(\pi)$ value and an odd number of blocks, the
$\hat w$-parity of each $\pi\in\hat\Pi(n)$ is opposite the parity of $n$.
Thus, $\hat\Pi(n)$ agrees with the right hand side of \eqref{e2.8} in both
sign and magnitude.

The $\tilde w$-parity changing involution of Theorem~\ref{t2.1} defined
on $\Pi(n)-\tilde\Pi(n)$ also changes the $\hat w$-parity. We now
extend this involution to $\Pi(n)-\hat\Pi(n)$ as follows:
if the last block of $\pi\in\tilde\Pi(n)-\hat\Pi(n)$ is $\{n\}$, merge it 
with the penultimate block; if the last block is not a singleton, take
$n$ from this block and form the singleton $\{n\}$. The resulting
extension is a $\hat w$-parity changing involution of $\Pi(n)-\hat\Pi(n)$.
\end{proof}

\section{A Second Bijection}\label{sec3}

The Bell numbers $B_{-1}^*(n)$ are quite different from the
numbers $\tilde B_{-1}(n)$ and $\hat B_{-1}(n)$, 
as demonstrated by the following theorem.

\begin{theo}\label{t3.1}
For all $n\in\mathbb{N}$,
\begin{equation}\label{e3.1}
B_{-1}^*(n):=\sum_{k=0}^nS_{-1}^*(n,k)=
\begin{cases}
1, &\text{if }n\equiv0\pmod3;\\
-1, &\text{if }n\equiv1\pmod3;\\
0, &\text{if }n\equiv2\pmod3.
\end{cases}
\end{equation}
\end{theo}
\begin{proof}[\bf Proof]
Let $\Pi_i(n):=\{\pi\in\Pi(n):\ w^*(\pi)\equiv i\pmod2\}$ and
$\Pi^*(n)$ consist of those partitions $\pi=(E_1,E_2,\dots)$ whose blocks
satisfy
\begin{equation}\label{e3.2}
E_{2i-1}=\{3i-2,3i-1\},\quad
E_{2i}=\{3i\}\quad\text{for }1\leqslant i\leqslant\lfloor n/3\rfloor.
\end{equation}
Then $\Pi^*(n)$ is a singleton contained in $\Pi_0(n)$ if $n\equiv0\pmod3$
or contained in $\Pi_1(n)$ if $n\equiv1\pmod3$. If $n\equiv2\pmod3$,
$\Pi^*(n)$ is a doubleton containing two partitions of opposite
$w^*$-parity, which we pair.

Suppose now that $\pi=(E_1,E_2,\dots)\in\Pi(n)-\Pi^*(n)$ and that
$i_0$ is the smallest index for which condition \eqref{e3.2} fails to hold.
Let $n_1=3i_0-2$,
$n_2=3i_0-1$, $n_3=3i_0$ and $V_1=E_{2i_0-1}$, $V_2=E_{2i_0}$,
$V_3=E_{2i_0+1}$ (the latter two if they occur). Consider the following
four disjoint cases concerning the relative positions of the $n_i$ within
the $V_i$:
\begin{center}
\begin{minipage}{0.9\linewidth}
\begin{itemize}
\item[\rm (I)] $n_2\in V_2$, $n_3\in V_3$, and $|V_2\cup V_3|\geqslant3$;
\item[\rm (II)] Either (a) or (b) holds where (a) $V_2=\{n_2\}$ and
$V_3=\{n_3\}$,\\ (b) $n_2,n_3\in V_1$;
\item[\rm (III)] $n_2\in V_2$ and $n_3\in V_1\cup V_2$;
\item[\rm (IV)] $n_2\in V_1$, $n_3\in V_2$, and $|V_1\cup V_2|\geqslant4$.
\end{itemize}
\end{minipage}
\end{center}
Within each case, we pair partitions of opposite parity as shown below,
leaving the other blocks undisturbed:
\begin{center}
\begin{minipage}{0.9\linewidth}
\begin{itemize}
\item[\rm (i)] $V_2=\{n_2,\dots,M\}$, $V_3=\{n_3,\dots\}$
$\leftrightarrow$
$V_2=\{n_2,\dots\}$,
$V_3=\{n_3,\dots,M\}$, where $M$ is the largest member of $V_2\cup V_3$;
\item[\rm (ii)] $V_1=\{n_1,\dots\}$, $V_2=\{n_2\}$,
$V_3=\{n_3\}$ $\leftrightarrow$ $V_1=\{n_1,n_2,n_3,\dots\}$;
\item[\rm (iii)] $V_1=\{n_1,n_3,\dots\}$, $V_2=\{n_2,\dots\}$
$\leftrightarrow$ $V_1=\{n_1,\dots\}$, $V_2=\{n_2,n_3,\dots\}$;
\item[\rm (iv)] $V_1=\{n_1,n_2,\dots,N\}$, $V_2=\{n_3,\dots\}$
$\leftrightarrow$ $V_1=\{n_1,n_2,\dots\}$,
$V_2=\{n_3,\dots,N\}$, where $N$ is the largest member of $V_1\cup V_2$. 
\end{itemize}
\end{minipage}
\end{center}
The resulting map is a parity changing involution of $\Pi(n)-\Pi^*(n)$,
which implies \eqref{e3.1}.
\end{proof}

Below, we illustrate the fixed point set $\Pi^*(n)$ along with the pairings of
$\Pi(n)-\Pi^*(n)$ when $n=4$.
\begin{xalignat*}{3}
&\Pi_0(n) &\qquad &\Pi_1(n)-\Pi^*(n) &\qquad &\Pi^*(n)\\
&\{1,2,3,4\} &\qquad &\{1,4\},\ \{2\},\ \{3\} &\qquad &\{1,2\},\ \{3\},\ \{4\}\\
&\{1,2\},\ \{3,4\} &\qquad &\{1,2,4\},\ \{3\}\\
&\{1,3\},\ \{2,4\} &\qquad &\{1\},\ \{2,3,4\}\\
&\{1,4\},\ \{2,3\} &\qquad &\{1,3,4\},\ \{2\}\\
&\{1\},\ \{2,3\},\ \{4\} &\qquad &\{1,3\},\ \{2\},\ \{4\}\\
&\{1\},\ \{2,4\},\ \{3\} &\qquad &\{1\},\ \{2\},\ \{3,4\}\\
&\{1\},\ \{2\},\ \{3\},\ \{4\} &\qquad &\{1,2,3\},\ \{4\}
\end{xalignat*}
Note that the bijection above, like the one used for Theorem~\ref{t2.3}, does
not always preserve the number of blocks and hence has no meaningful 
restriction to $\Pi(n,k)$, unlike the bijection of Theorem~\ref{t2.1}. 

\begin{rem}
In \cite{bnew}, Ehrlich evaluates $\sigma(n):=-\sum_{\pi\in\Pi(n)}
(-1)^{\alpha(\pi)}$, where
$\alpha(\pi):=\sum_{i\text{ odd}}|E_i|$ for $\pi=(E_1,E_2,\dots)\in\Pi(n)$.
The bijection of Theorem~\ref{t3.1} establishing $B^*_{-1}(n)$ also
provides an alternative to Ehrlich's iterative argument establishing
his $\sigma(n)$ since
\[
\begin{split}
\sigma(n) &= -\sum_{\pi=(E_1,E_2,\dots)\in\Pi(n)}(-1)^{|E_1|+|E_3|+|E_5|
+\cdots}\\
&= -\sum_{\pi=(E_1,E_2,\dots)\in\Pi(n)}(-1)^{|E_1|+2|E_2|+3|E_3|+\cdots}\\
&=-B_{-1}^*(n).
\end{split}
\]
\end{rem}

Since
$S_q(n,k)=q^{-n}S_q^*(n,k)$,
\[
B_{-1}(n):=\sum_{k=0}^nS_{-1}(n,k)=(-1)^nB_{-1}^*(n),
\]
and so by \eqref{e3.1},
\begin{equation}\label{e3.3}
B_{-1}(n)=
\begin{cases}
(-1)^n, &\text{if }n\equiv0\pmod3;\\
(-1)^{n+1}, &\text{if }n\equiv1\pmod3;\\
0, &\text{if }n\equiv2\pmod3,
\end{cases}
\end{equation}
with the above bijection clearly showing this. The preceding also supplies
a combinatorial proof that $B(n)$, the $n^{\text{th}}$ Bell number, is
even if and only if $n\equiv2\pmod3$ since every partition of $[n]$ is
paired with another of opposite $w^*$-parity when $n\equiv2\pmod3$ and
since all partitions are so paired except for one otherwise
(cf. Ehrlich \cite[p. 512]{bnew}).
\vspace{2ex}

\section{Acknowledgments}

The author would like to thank Professor
Donald Knuth for calling Ehrlich's paper to his attention.

\begin{thebibliography}{9}

\bibitem{b1} L. Carlitz, Generalized Stirling numbers, {\it
Combinatorial Analysis Notes}, Duke University (1968), 8--15.

\bibitem{bnew} G. Ehrlich, Loopless algorithms for generating permutations,
combinations, and other combinatorial configurations, {\it J. 
ACM} {\bf 20} (1973),
500--513.

\bibitem{b2} S. Milne, A $q$-analogue of restricted growth functions,
Dobinski's equality, and Charlier polynomials, {\it Trans. Amer. Math. Soc.}
{\bf 245} (1978), 89--118.

\bibitem{b3} R. Stanley, {\it Enumerative Combinatorics, Vol.} I, Wadsworth
and Brooks/Cole, 1986.

\bibitem{b4} M. Wachs and D. White, $p,q$-Stirling numbers and partition
statistics, {\it J. Combin. Theory A} {\bf 56} (1991), 27--46.

\bibitem{b5} C. Wagner, Generalized Stirling and Lah numbers,
{\it Discrete Math.} {\bf 160} (1996), 199--218.

\bibitem{b6} C. Wagner,
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Wagner/wagner3.html}{Partition statistics and 
$q$-Bell numbers ($q=-1$)},
{\it J. Integer Seq.} {\bf 7} (2004), Art.\ 4.1.1.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B73; Secondary 11B39.

\noindent \emph{Keywords:}
partition statistics, $q$-Stirling numbers, $q$-Bell numbers,
Fibonacci numbers.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000045}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 6 2004;
revised version received January 17 2005.
Published in {\it Journal of Integer Sequences}, January 17 2005.

\bigskip
\hrule
\bigskip

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


\end{document}