<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsthm}

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

\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 Partition Statistics and $q$-Bell Numbers ($q=-1$)}

\vskip 1cm
\large
Carl G. Wagner\\
Department of Mathematics\\
University of Tennessee\\
Knoxville, TN 37996-1300, USA\\
\href{wagner@math.utk.edu}{\tt wagner@math.utk.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
We study three partition statistics and the $q$-Stirling and $q$-Bell
numbers that serve as their generating functions,
evaluating these numbers when $q=-1$. Among the numbers that arise in this
way are (1) Fibonacci numbers and (2) numbers occurring in the study of
fermionic oscillators.
\end{abstract}

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



%\usepackage{amsmath}
%\usepackage{amssymb}
%\usepackage{amscd}
%\usepackage{amsthm}

%\numberwithin{equation}{section}

%\theoremstyle{plain}
%\newtheorem{theo}{Theorem}
%\numberwithin{theo}{section}




\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 letter $q$ denotes an
indeterminate, with $0_q:=0$, $n_q:=1+q+\dots+q^{n-1}$ for
$n\in\mathbb{P}$, $0\mathop{!}\limits_q:=1$, and $n\mathop{!}\limits_q:=1_q2_q\cdots n_q$ for
$n\in\mathbb{P}$. The binomial coefficient $\binom nk$ is equal to zero if
$k$ is a negative integer or if $0\leqslant n&lt;k$.

Let $\Delta$ be a finite set of discrete structures, with $I:\Delta\to
\mathbb{N}$. The generating function
\begin{equation*}%\label{e1.1}
G(I,\Delta;q):=\sum_{\delta\in\Delta}q^{I(\delta)}=\sum_k
\left|\{\delta\in\Delta:\ I(\delta)=k\}\right|q^k
\end{equation*}
is a useful tool for studying the statistic $I$. Elementary examples
include the binomial theorem,
\begin{equation}\label{e1.2}
(1+q)^n=\sum_{S\subset[n]}q^{|S|}=\sum_{k=0}^n\binom nkq^k,
\end{equation}
and
\begin{equation}\label{e1.3}
n\mathop{!}\limits_q=\sum_{\sigma\in\mathcal{S}_n}q^{i(\sigma)},
\end{equation}
where $\mathcal{S}_n$ is the set of permutations of $[n]$ and $i(\sigma)$
is the number of inversions in the permutation $\sigma=i_1i_2\dots i_n$,
i.e., the number of pairs $(r,s)$ with $1\leqslant r&lt;s\leqslant n$ and
$i_r&gt;i_s$ \cite[Corollary 1.3.10]{bSt}.

Of course, $G(I,\Delta;1)=|\Delta|$. On the other hand,
\begin{equation}\label{e1.4}
G(I,\Delta;-1)=\left|\{\delta\in\Delta:\ I(\delta)\text{ is even}\}\right|
-\left|\{\delta\in\Delta:\ I(\delta)\text{ is odd}\}\right|.
\end{equation}
Hence if $G(I,\Delta;-1)=0$, the set $\Delta$ is ``balanced'' with respect
to the parity of $I$.
In particular, setting $q=-1$ in \eqref{e1.2} yields the familiar result
that a finite nonempty set has as many subsets of odd cardinality as it has
subsets of even cardinality. Setting $q=-1$ in \eqref{e1.3} reveals that
if $n\geqslant2$, then among the permutations of $[n]$ there are as many
with an odd number of inversions as there are with an even number of
inversions.

In this note we consider three $q$-generalizations of Stirling numbers of the
second kind, denoted $S_q^*(n,k)$, $S_q(n,k)$, and $\tilde S_q(n,k)$. These
polynomials are generating functions for three closely related
statistics on the set of partitions of $[n]$ with $k$ blocks. Most of the
properties of these $q$-Stirling numbers, to be established below in
\S~\ref{sec3}, have appeared in the literature in various contexts, Carlitz
\cite{bCa} having apparently been the first to construe these numbers as 
generating functions for partition statistics.
See also
\cite{bESW}, \cite{bMi}, \cite{bWa}, and \cite{bWW}. Our aim
here is to offer a compact, unified treatment of these numbers. 
Our analysis
is facilitated by a powerful formal algebraic result of Comtet
\cite{bCo}.

We derive in \S~\ref{sec4}  new results on the evaluation of
$S_q^*(n,k)$, $S_q(n,k)$, and $\tilde S_q(n,k)$ and their associated $q$-Bell numbers
(gotten by summing $q$-Stirling numbers over $k$ for fixed $n$) when $q=-1$.
Apart from the interpretation of these results in terms of \eqref{e1.4},
the evaluation of $S_{-1}(n,k)$ and its associated Bell numbers may
be of additional interest, since these numbers arise in the study of
fermionic oscillators \cite{bSc}. 

In \S~\ref{sec5} we discuss an alternative
approach to establishing our results by means of bijective proofs.

In \S~\ref{sec6} the numbers $S_{-1}^*(n,k)$, $S_{-1}(n,k)$, and
$\tilde S_{-1}(n,k)$ are displayed as triangular arrays for
$1\leqslant k\leqslant n\leqslant 8$. Here, for immediate reference,
we record these arrays in linearized form:
\[
\begin{aligned}
S_{-1}^*(n,k) &amp;= \mbox{\small$\begin{array}[t]{rrrrrrrrrrrrr}
                \!-1,&amp;\!1,&amp;\!-1,&amp;\!-1,&amp;\!1,&amp;\!1,&amp;\!1,&amp;\!-1,&amp;\!-2,&amp;\!1,&amp;\!-1,&amp;\!1,\\
                \!3,&amp;\!-2,&amp;\!-1,&amp;\!1,&amp;\!-1,&amp;\!-4,&amp;\!3,&amp;\!3,&amp;\!-1,&amp;\!-1,&amp;\!1,&amp;\!5,\\
			    \!-4,&amp;\!-6,&amp;\!3,&amp;\!1,&amp;1,&amp;\!-1,&amp;\!-6,&amp;\!5,&amp;\!10,&amp;\!-6,&amp;\!-4,&amp;\!1,&amp;\!\dots\end{array}$}\\
S_{-1}(n,k)   &amp;= \mbox{\small$\begin{array}[t]{rrrrrrrrrrrrr}
                \!1,&amp;\!1,&amp;\!-1,&amp;\!1,&amp;\!-1,&amp;\!-1,&amp;\!1,&amp;\!-1,&amp;\!-2,&amp;1,&amp;\!1,&amp;\!-1,\\
                \!-3,&amp;\!2,&amp;\!1,&amp;\!1,&amp;\!-1,&amp;\!-4,&amp;\!3,&amp;\!3,&amp;-1,&amp;\!1,&amp;\!-1,&amp;\!-5,\\
			    \!4,&amp;\!6,&amp;\!-3,&amp;\!-1,&amp;\!1,&amp;\!-1,&amp;\!-6,&amp;\!5,&amp;10,&amp;\!-6,&amp;\!-4,&amp;\!1,&amp;\!\dots
				\end{array}$}\\
\tilde S_{-1}(n,k)	&amp;= \mbox{\small$\begin{array}[t]{rrrrrrrrrrrrr}
                1,&amp;1,&amp;1,&amp;1,&amp;1,&amp;1,&amp;1,&amp;1,&amp;2,&amp;1,&amp;1,&amp;1,\\
                3,&amp;2,&amp;1,&amp;1,&amp;1,&amp;4,&amp;3,&amp;3,&amp;1,&amp;1,&amp;1,&amp;5,\\
			    4,&amp;6,&amp;3,&amp;1,&amp;1,&amp;1,&amp;6,&amp;5,&amp;10,&amp;6,&amp;4,&amp;1,&amp;\dots
				\end{array}$}
\end{aligned}
\]

\section{Preliminaries}\label{sec2}

This section reviews some material to be used later in the paper.

2.1. {\em Comtet Numbers}. The following theorem, due to Comtet \cite{bCo}
greatly facilitates the analysis of many combinatorial arrays:

\begin{theorem}\label{th2.1}
Let $D$ be an integral domain. If $(u_n)_{n\geqslant0}$ is a sequence in
$D$ and $x$ is an indeterminate over $D$, then the following are equivalent
characterizations of an array $(U(n,k))_{n,k\geqslant0}$:
\begin{gather}
\label{e2.3}
U(n,k)=U(n-1,k-1)+u_kU(n-1,k),\qquad \forall\ n,k\in\mathbb{P},\\
\intertext{with $U(n,0)=u_0^n$ and $U(0,k)=\delta_{0,k}$ $\forall$
$n,k\in\mathbb{N}$,}
\label{e2.1}
U(n,k)=\sum_{\substack{d_0+d_1+\dots+d_k=n-k\\ d_i\in\mathbb{N}}}
u_0^{d_0}u_1^{d_1}\cdots u_k^{d_k},\qquad
\forall\ n,k\in\mathbb{N},\\
\label{e2.2}
\sum_{n\geqslant0}U(n,k)x^n=\frac{x^k}{(1-u_0x)(1-u_1x)\cdots(1-u_kx)},\qquad
\forall\ k\in\mathbb{N},\\
\intertext{and}
\label{e2.4}
x^n=\sum_{k=0}^nU(n,k)p_k(x),\qquad\forall\ n\in\mathbb{N},
\end{gather}
where $p_0(x):=1$ and $p_k(x):=(x-u_0)\cdots(x-u_{k-1})$ for $k\in\mathbb{P}$.
\end{theorem}

\begin{proof}[\bf Proof]
Straightforward algebraic exercise.
\end{proof}

In what follows, we call the numbers $U(n,k)$ the {\em Comtet numbers 
associated with the sequence} $(u_n)_{n\geqslant0}$.

2.2 {\em Partitions of a Set}. A {\em partition} of a set $S$ is a set of
nonempty, pairwise disjoint subsets (called {\em blocks}) of $S$, with union
$S$. For all $n,k\in\mathbb{N}$, let $S(n,k)$ denote the number of 
partitions of $[n]$ with $k$ blocks. Then $S(0,0)=1$, $S(n,0)=S(0,k)=0$,
$\forall$ $n,k\in\mathbb{P}$, and
\begin{equation}\label{e2.5}
S(n,k)=S(n-1,k-1)+kS(n-1,k),\qquad\forall\ n,k\in\mathbb{P},
\end{equation}
$S(n-1,k-1)$ enumerating those partitions in which $n$ is the sole element
of one of the blocks, and $kS(n-1,k)$ those in which the block containing
$n$ contains at least one other element of $[n]$. From \eqref{e2.5} it follows
that the numbers $S(n,k)$, called {\em Stirling numbers of the second kind},
are the Comtet numbers associated with the sequence $(0,1,2,\dots)$.
Hence by Theorem \ref{th2.1}
\begin{gather*}
%\label{e2.6}
S(n,k)=\sum_{\substack{d_1+\dots+d_k=n-k\\ d_i\in\mathbb{N}}}1^{d_1}2^{d_2}
\cdots k^{d_k},\qquad\forall\ n,k\in\mathbb{N},\\
%\label{e2.7}
\sum_{n\geqslant0}S(n,k)x^n=\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)},\qquad
\forall\ k\in\mathbb{N},\\
\intertext{and}
%\label{e2.8}
x^n=\sum_{k=0}^nS(n,k)x^{\underbar{$\scriptstyle k$}},\qquad\forall\ n\in\mathbb{N},
\end{gather*}
where $x^{\underbar{$\scriptstyle0$}}:=1$ and $x^{\underbar{$\scriptstyle k$}}:=x(x-1)\cdots(x-k+1)$ for $k\in\mathbb{P}$.

The total number of partitions of $[n]$ is given by the {\em Bell number}
$B_n$, where
\begin{equation*}%\label{e2.9}
B_n=\sum_{k=0}^nS(n,k).
\end{equation*}
Clearly, $B_0=1$, and
\begin{equation*}%\label{e2.10}
B_{n+1}=\sum_{k=0}^n\binom nkB_k,
\end{equation*}
since
$\binom nkB_k$ enumerates those partitions of $[n+1]$ for which the size
of the block containing the element $n+1$ is $n-k+1$.

2.3 {\em Restricted Sums of Binomial Coefficients}. As we have already noted
in \S~\ref{sec1}, setting $q=1$ and $q=-1$ in \eqref{e1.2} yields the
well known result
\begin{equation*}%\label{e2.11}
\sum_{k\text{ even}}\binom nk=\sum_{k\text{ odd}}\binom nk=2^{n-1},\qquad
\forall\ n\in\mathbb{P}.
\end{equation*}
Here we recall a method for evaluating
sums such as
\begin{equation*}%\label{e2.12}
\sum_{k\equiv0\!\!\!\pmod3}\binom nk.
\end{equation*}
Let $\omega$ be either of the two complex cube roots of $1$, e.g., 
$\omega=(-1+i\sqrt3)/2$. Then
\begin{multline}\label{e2.13}
(1+x)^n+(1+\omega x)^n+(1+\omega^2x)^n=\sum_{k=0}^n\binom nkx^k\left(1+\omega^k+\omega^{2k}\right)\\
=3\sum_{k\equiv0\!\!\!\pmod3}\binom nkx^k,
\end{multline}
since $k\equiv0\pmod3$ implies that $1+\omega^k+\omega^{2k}=3$ and
$k\equiv1$ or $2$ $\pmod 3$ implies that $1+\omega^k+\omega^{2k}=1+\omega+\omega^2=0$.
Setting $x=1$ in \eqref{e2.13} yields
\begin{equation}\label{e2.14}
\sum_{k\equiv0\!\!\!\pmod3}\binom nk=\frac13\left(2^n+(1+\omega)^n+(1+\omega^2)^n\right).
\end{equation}

\section{Partition Statistics and $q$-Stirling Numbers}\label{sec3}

Let $\Pi(n,k)$ denote the set of all partitions of $[n]$ with $k$ blocks.
Given a partition $\pi\in\Pi(n,k)$, let $(E_1,\dots,E_k)$ be the unique
{\em ordered} partition of $[n]$ comprising the same blocks as $\pi$, 
arranged in increasing order of their smallest elements, and define
statistics $w^*$, $w$, and $\tilde w$ by
\begin{align*}
%\label{e3.1}
w^*(\pi) &amp;:= \sum_{i=1}^ki|E_i|,\\
%\label{e3.2}
w(\pi) &amp;:= \sum_{i=1}^k(i-1)|E_i|=w^*(\pi)-n,\\
\intertext{and}
%\label{e3.3}
\tilde w(\pi) &amp;:=\sum_{i=1}^k(i-1)(|E_i|-1)=w^*(\pi)-n-\binom k2.
\end{align*}
If elements of $[n]$ are regarded as labels on $n$ unit masses, then
$w^*(\pi)$ is the moment about $x=0$ of the mass configuration in which
the masses with labels in $E_i$ are placed at $x=i$. The statistics 
$w(\pi)$ and $\tilde w(\pi)$ admit of similar interpretations.

We wish to study the generating functions
\begin{align}
\label{e3.4}
S_q^*(n,k) &amp;:= \sum_{\pi\in\Pi(n,k)}q^{w^*(\pi)},\\
\label{e3.5}
S_q(n,k) &amp;:= \sum_{\pi\in\Pi(n,k)}q^{w(\pi)}=q^{-n}S_q^*(n,k),\\
\intertext{and}
\label{e3.6}
\tilde S_q(n,k) &amp;:= \sum_{\pi\in\Pi(n,k)}q^{\tilde w(\pi)}
=q^{-n-\binom k2}S_q^*(n,k).
\end{align}
Each of these polynomials furnishes a $q$-generalization of $S(n,k)$,
reducing to the latter when $q=1$. As closely related as these $q$-Stirling
numbers appear to be, it might be thought that one could carry out an
analysis of any one of them, chosen arbitrarily, with properties of
the others derived as easy corollaries.
Interestingly, it turns out that each is best suited for elucidating
a particular subset of their more or less common properties. We consider
first the matter of recursive formulas.

\begin{theorem}\label{th3.1}
The $q$-Stirling numbers $S_q^*(n,k)$ are generated by the recurrence
relation
\begin{equation}\label{e3.7}
S_q^*(n,k)=q^kS_q^*(n-1,k-1)+qk_qS_q^*(n-1,k),\qquad\forall\ n,k\in\mathbb{P},
\end{equation}
with $S_q^*(0,0)=1$ and $S_q^*(n,0)=S_q^*(0,k)=0$, $\forall$ $n,k\in
\mathbb{P}$.
\end{theorem}

\begin{proof}[\bf Proof]
The boundary conditions are obvious. To establish the recurrence \eqref{e3.7},
let
\[
c(n,k,t):=\left|\{\pi\in\Pi(n,k):\ w^*(\pi)=t\}\right|.
\]
Then,
\begin{equation}\label{e3.8}
c(n,k,t)=c(n-1,k-1,t-k)+\sum_{i=1}^kc(n-1,k,t-i),\qquad\forall\ n,k\in
\mathbb{P}.
\end{equation}
For if $w^*(\pi)=t$, with $(E_1,\dots,E_k)$ being the ordered partition
associated with $\pi$, then the number $n\in[n]$ is either (i)
in $E_k$ alone (there are clearly $c(n-1,k-1,t-k)$ such $\pi$'s)
or (ii) in some $E_i$, where $1\leqslant i\leqslant k$, with at least
one element of $[n-1]$ (there are clearly $c(n-1,k,t-i)$ such $\pi$'s).
From \eqref{e3.8} it follows that
\[
\begin{split}
S_q^*(n,k) &amp;= \sum_tc(n,k,t)q^t\\
&amp;= \sum_rc(n-1,k-1,r)q^{r+k}+\sum_{i=1}^kq^i\sum_rc(n-1,k,r)q^r\\
&amp;= q^kS_q^*(n-1,k-1)+qk_qS_q^*(n-1,k).
\end{split}
\]
\end{proof}

Recurrence relations for $S_q(n,k)$ and $\tilde S_q(n,k)$ follow immediately
from \eqref{e3.7}, along with \eqref{e3.5} and \eqref{e3.6},
respectively. We have
\begin{align}
\label{e3.9}
S_q(n,k)&amp;=q^{k-1}S_q(n-1,k-1)+k_qS_q(n-1,k),\qquad\forall\ n,k\in\mathbb{P},\\
\intertext{and}
\label{e3.10}
\tilde S_q(n,k) &amp;= \tilde S_q(n-1,k-1)+k_q\tilde S_q(n-1,k),\qquad\forall\ n,k\in\mathbb{P}.
\end{align}
By \eqref{e3.10}, the numbers $\tilde S_q(n,k)$ are the Comtet numbers 
associated with the sequence $(n_q)_{n\geqslant0}$. By Theorem \ref{th2.1}
it follows immediately that
\begin{gather}
\label{e3.11}
\tilde S_q(n,k)=\sum_{\substack{d_1+\dots+d_k=n-k\\ d_i\in\mathbb{N}}}
(1_q)^{d_1}(2_q)^{d_2}\cdots(k_q)^{d_k},\qquad\forall\ n,k\in\mathbb{N},\\
\label{e3.12}
\sum_{n\geqslant0}\tilde S_q(n,k)x^n=\frac{x^k}{(1-1_qx)(1-2_qx)\cdots
(1-k_qx)},\qquad\forall\ k\in\mathbb{N},\\
\intertext{and}
\label{e3.13}
x^n=\sum_{k=0}^n\tilde S_q(n,k)\phi_k(x),\qquad\forall\ n\in\mathbb{N},
\end{gather}
where $\phi_0(x):=1$ and $\phi_k(x):=x(x-1_q)\cdots(x-(k-1)_q)$,
$\forall$ $k\in\mathbb{P}$.

Variants of \eqref{e3.11}--\eqref{e3.13} that hold for $S_q(n,k)$ and
$S_q^*(n,k)$ follow immediately from the relations $S_q(n,k)=q^{\binom k2}
\tilde S_q(n,k)$ and $S_q^*(n,k)=q^nS_q(n,k)$. To cite a few examples,
we have
\begin{multline*}
%\label{e3.14}
\sum_{n\geqslant0}S^*(n,k)x^n=
\frac{q^{\binom{k+1}2}x^k}{(1-qx)(1-qx-q^2x)\cdots(1-qx-\dots-q^kx)},\\
%\qquad
\forall\ k\in\mathbb{N},
\end{multline*}
and
\begin{equation}
\label{e3.15}
x^n=\sum_{k=0}^nS_q(n,k)\psi_k(x)=\sum_{k=0}^nS_q^*(n,k)\psi_k\left(
\frac xq\right),
\end{equation}
where $\psi_k(x):=q^{-\binom k2}\phi_k(x)$.

Using the method of linear functionals \cite[pp. 89--90]{bRo} one can
derive from \eqref{e3.15} the recurrence \cite[Theorem 5.4]{bWa}
\begin{equation}\label{e3.16}
S_q(n+1,k)=\sum_{j=0}^n\binom njq^jS_q(j,k-1),\qquad
\forall\ n\in\mathbb{N},\ k\in\mathbb{P},
\end{equation}
from which the variant recurrences
\begin{align}
%\label{e3.17}
\notag
S_q^*(n+1,k) &amp;= q^{n+1}\sum_{j=0}^n\binom nj S_q^*(j,k-1),\qquad
\forall\ n\in\mathbb{N},\ k\in\mathbb{P},\\
\intertext{and}
\label{e3.18}
\tilde S_q(n+1,k) &amp;= \sum_{j=0}^n\binom nj q^{j-k+1}
\tilde S_q(j,k-1),\qquad\forall\ n\in\mathbb{N},\ k\in\mathbb{P}
\end{align}
follow immediately.

Summing the $q$-Stirling numbers $S_q^*(n,k)$, $S_q(n,k)$ and
$\tilde S_q(n,k)$ over $k$ yields the respective $q$-Bell numbers 
$B_q^*(n)$, $B_q(n)$, and $\tilde B_q(n)$. From \eqref{e3.16} it follows
that
\begin{equation}\label{e3.19}
B_q(n+1)=\sum_{j=0}^n\binom njq^jB_q(j),\qquad\forall\ n\in\mathbb{N}.
\end{equation}
Since $B_q^*(n)=q^nB_q(n)$, the recurrence \eqref{e3.19} yields
\begin{equation}\label{e3.20}
B_q^*(n+1)=q^{n+1}\sum_{j=0}^n\binom njB_q^*(j),\qquad\forall\ n\in
\mathbb{N}.
\end{equation}
Due to the factor $q^{-k}$ in \eqref{e3.18}, we do not get any
recurrence for $\tilde B_q(n)$ analogous to \eqref{e3.19} and
\eqref{e3.20}, this being the single exception to the general parallelism
between properties of the three $q$-Stirling numbers under consideration.
The uniqueness of $\tilde B_q(n)$ is further manifested when $q=-1$,
as we shall see in the next section.

\section{The Case $q=-1$}\label{sec4}

In this section we derive simple expressions for the foregoing $q$-Stirling
and $q$-Bell numbers
when $q=-1$.

\begin{theorem}\label{th4.1}
The number $\tilde S_{-1}(n,k)$ is given by the formula
\begin{equation}
\label{e4.1}
\tilde S_{-1}(n,k)=\binom{n-\left\lfloor
\frac k2\right\rfloor-1}{\left\lfloor\frac{k-1}2\right\rfloor},\qquad
1\leqslant k\leqslant n.
\end{equation}
\end{theorem}

\begin{proof}[\bf Proof]
Note that
\begin{equation*}%\label{e4.4}
\left.i_q\right|_{q=-1}=\omega_i:=
\begin{cases} 1, &amp;\text{if $i$ is odd};\\
0, &amp;\text{if $i$ is even}.
\end{cases}
\end{equation*}
Hence by \eqref{e3.11}, if $1\leqslant m\leqslant\lfloor n/2\rfloor$,
\begin{equation}\label{e4.5}
\tilde S_{-1}(n,2m)=\sum_{\substack{d_1+d_3+\dots+d_{2m-1}=n-2m\\
d_i\in\mathbb{N}}}1=\binom{n-m-1}{m-1},
\end{equation}
since  the number of sequences $(t_1,\dots,
t_m)$ of nonnegative integers summing to $s$ is
$\binom {s+m-1}{m-1}$ \cite[p. 15]{bSt}. Similarly, if
$0\leqslant m\leqslant\lfloor (n-1)/2\rfloor$,
\begin{equation}
\label{e4.2}
\tilde S_{-1}(n,2m+1)=\binom{n-m-1}m.
\end{equation}
Formula \eqref{e4.1} incorporates \eqref{e4.5} and \eqref{e4.2}.
\end{proof}

In tabulating the numbers $\tilde S_{-1}(n,k)$ it is of course more efficient to
use the recurrence 
\begin{equation*}%\label{e4.6}
\tilde S_{-1}(n,k)=\tilde S_{-1}(n-1,k-1)+\omega_k\tilde S_{-1}(n-1,k),
\end{equation*}
representing the case $q=-1$ of \eqref{e3.10}.

Let $F_0=F_1=1$, with $F_n=F_{n-1}+F_{n-2}$ if $n\geqslant2$. As is well
known,
\begin{equation}\label{eq4.6}
F_n=\sum_{m=0}^{\lfloor n/2\rfloor}\binom{n-m}m,\qquad
\forall n\in\mathbb{N}.
\end{equation}

\begin{theorem}\label{theo4.2}
For all $n\in\mathbb{N}$,
\begin{equation}\label{eq4.7}
\tilde B_{-1}(n):=\sum_{k=0}^n\tilde S_{-1}(n,k)=F_n.
\end{equation}
\end{theorem}

\begin{proof}[\bf Proof]
It is easy to check that \eqref{eq4.7} holds for $n=0,1$. If $n\geqslant2$,
then by \eqref{e4.5}, \eqref{e4.2}, and \eqref{eq4.6},
\[
\begin{split}
\tilde B_{-1}(n) &amp;= \sum_{m=0}^{\lfloor (n-1)/2\rfloor}\binom{n-m-1}m
+\sum_{m=1}^{\lfloor n/2\rfloor}\binom{n-m-1}{m-1}\\
&amp;= \sum_{m=0}^{\lfloor (n-1)/2\rfloor}\binom{(n-1)-m}m+
\sum_{m=0}^{\lfloor (n-2)/2\rfloor}\binom{(n-2)-m}m\\
&amp;= F_{n-1}+F_{n-2}=F_n.
\end{split}
\]
\end{proof}

From \eqref{e4.1} and the fact that
$S_q^*(n,k)=q^{\binom k2+n}\tilde S_q(n,k)$, we have
\begin{equation*}%\label{eq4.8}
S_{-1}^*(n,k)=(-1)^{\binom k2+n}\binom{n-\left\lfloor\frac k2\right\rfloor-1}%
{\left\lfloor\frac{k-1}2\right\rfloor},\qquad
1\leqslant k\leqslant n.
\end{equation*}
On the other hand, the Bell numbers $B_{-1}^*(n)$ are quite different
from the numbers $\tilde B_{-1}(n)$.

\begin{theorem}\label{th4.2}
For all $n\in\mathbb{N}$,
\begin{equation}\label{e4.9}
B_{-1}^*(n):=\sum_{k=0}^nS_{-1}^*(n,k)=\begin{cases}
1, &amp;\text{if\ \ }n\equiv0\pmod3;\\
-1, &amp;\text{if\ \ }n\equiv1\pmod3;\\
0, &amp;\text{if\ \ }n\equiv2\pmod3.
\end{cases}
\end{equation}
\end{theorem}

\begin{proof}[\bf Proof]
Noting that $B_{-1}^*(0)=1$, we prove \eqref{e4.9} by induction
on $n$. In what follows
\begin{equation*}%\label{e4.10}
b_r(n):=\sum_{j\equiv r\!\!\!\pmod3}\binom nj.
\end{equation*}
From \eqref{e3.20} with $q=-1$, we have
\begin{multline*}%\label{e4.11}
B_{-1}^*(n+1)=(-1)^{n+1}\sum_{j=0}^n\binom njB_{-1}^*(j)=(-1)^{n+1}
b_0(n)+(-1)^nb_1(n)\\
=(-1)^{n+1}b_0(n)+(-1)^nb_0(n-1)+(-1)^nb_1(n-1).
\end{multline*}
Similarly, $B_{-1}^*(n)=(-1)^nb_0(n-1)+(-1)^{n-1}b_1(n-1)$, and so
\begin{multline}\label{e4.12}
B_{-1}^*(n+1)=(-1)^{n+1}b_0(n)+2(-1)^nb_0(n-1)-B_{-1}^*(n)\\
=\frac13\left[\omega^{2n-1}-\omega^{2n-2}+\omega^{n+1}-\omega^{n-1}\right]
-B_{-1}^*(n),
\end{multline}
by \eqref{e2.14}, where $\omega$ is either of the two complex cube roots of $1$.
Taking $n+1=3m$, $3m+1$, and $3m+2$, respectively, in \eqref{e4.12} yields
\begin{align*}
%\label{e4.13}
B_{-1}^*(3m) &amp;= 1-B_{-1}^*(3m-1)=1,\\
%\label{e4.14}
B_{-1}^*(3m+1) &amp;= 0-B_{-1}^*(3m)=-1,\qquad\text{and}\\
%\label{e4.15}
B_{-1}^*(3m+2) &amp;= -1-B_{-1}^*(3m+1)=0.
\end{align*}
\end{proof}

It is easy to check that one can write \eqref{e4.9} more compactly as
\begin{equation*}%\label{e4.16}
B_{-1}^*(n)=
\frac1{1-\omega}\omega^n-\frac\omega{1-\omega}\omega^{2n},
\end{equation*}
from which we get the nice exponential
generating function
\begin{equation}\label{e4.17}
\sum_{n=0}^\infty B_{-1}^*(n)\frac{x^n}{n!}=\frac1{1-\omega}e^{\omega x}-
\frac \omega{1-\omega}e^{\omega^2x}.
\end{equation}

From \eqref{e4.1} and the fact that $S_q(n,k)=q^{\binom k2}\tilde S_q(n,k)$,
we have
\begin{equation*}%\label{eq4.18}
S_{-1}(n,k)=(-1)^{\binom k2}\binom{n-\left\lfloor\frac k2\right\rfloor-1}%
{\left\lfloor\frac{k-1}2\right\rfloor},\qquad
1\leqslant k\leqslant n.
\end{equation*}
By \eqref{e3.5},
\[
B_{-1}(n):=\sum_{k=0}^nS_{-1}(n,k)=(-1)^nB_{-1}^*(n),
\]
and so by \eqref{e4.9}
\begin{equation}\label{e4.18}
B_{-1}(n)=
\begin{cases}
(-1)^n, &amp;\text{if\ \ }n\equiv0\pmod3;\\
(-1)^{n+1}, &amp;\text{if\ \ }n\equiv1\pmod3;\\
0, &amp;\text{if\ \ }n\equiv2\pmod3,
\end{cases}
\end{equation}
and by \eqref{e4.17}
\begin{equation}\label{e4.19}
\sum_{n=0}^\infty B_{-1}(n)\frac{x^n}{n!}=\frac1{1-\omega}e^{-\omega x}-
\frac \omega{1-\omega}e^{-\omega^2x}.
\end{equation}

In a paper which showed how the numbers
$S_{-1}(n,k)$ and $B_{-1}(n)$ arise in the study of fermionic oscillators,
Schork \cite{bSc} posed the problem of finding a closed form and a
generating function for the numbers $B_{-1}(n)$. Formulas
\eqref{e4.18} and \eqref{e4.19} furnish solutions to Schork's problem.

To conclude this section we remark that our list of partition statistics
might have been rounded out to include
the statistic
\begin{equation*}%\label{e4.21}
\hat w(\pi):=\sum_{i=1}^k i(|E_i|-1)=\tilde w(\pi)+n-k,
\end{equation*}
with generating function
\begin{equation}\label{e4.22}
\hat S_q(n,k):=\sum_{\pi\in\Pi(n,k)}q^{\hat w(\pi)}=q^{(n-k)}\tilde S_q(n,k).
\end{equation}
Formula \eqref{e4.22} and Theorem \ref{th4.1} yield an easy evaluation of
$\hat S_{-1}(n,k)$. As for
\begin{equation*}%\label{e4.23}
\hat B_{-1}(n):=\sum_{k=0}^n\hat S_{-1}(n,k),
\end{equation*}
we have $\hat B_{-1}(0)=\hat B_{-1}(1)=1$, $\hat B_{-1}(2)=0$, and
\begin{equation}\label{e4.24}
\hat B_{-1}(n)=(-1)^{n-1}F_{n-3},\qquad \forall n\geqslant 3,
\end{equation}
the proof of which we leave to interested readers.

\section{Bijective Proofs}\label{sec5}

We conclude by returning to the opening theme of this paper. If
$G(I,\Delta;-1)\allowbreak=0$, then, as already noted, $|\Delta_0|=|\Delta_1|$, where
$\Delta_i=\{\delta\in\Delta:\ I(\delta)\equiv i\pmod 2\}$. 
One gains a deeper understanding (and bijective proof) of such results by identifying an
$I$-parity changing involution of
$\Delta$. For the statistic
$|S|$ in \eqref{e1.2}, the map
\[
S\mapsto\begin{cases}
S\cup\{1\}, &amp;\text{if }1\notin S;\\
S-\{1\}, &amp;\text{if }1\in S,
\end{cases}
\]
furnishes such an involution. For the statistic $i(\sigma)$ in
\eqref{e1.3}, switching positions of the elements $1$ and $2$ (or
of $k$ and $k+1$, for any fixed $k$) in a permutation furnishes such an
involution.

A similar task arises when \eqref{e1.4} is nonzero. Suppose, for example,
that $G(I,\Delta;-1)=c&gt;0$. Here one wishes to identify a subset
$\Delta^+$ of $\Delta_0$, with $|\Delta^+|=c$, and 
an $I$-parity changing
involution of $\Delta-\Delta^+$.

My student, Mark Shattuck, has recently succeeded in finding such
bijective proofs of formulas \eqref{e4.1}, \eqref{eq4.7}, \eqref{e4.9}, 
\eqref{e4.18},
and \eqref{e4.24}. Details will appear in a forthcoming paper.

\section{Tables}\label{sec6}

\noindent Table 1: The numbers $S_{-1}^*(n,k)$ for $1\leqslant k\leqslant n
\leqslant8$.
\begin{center}
\begin{tabular}{|r||r|r|r|r|r|r|r|r|}
\hline
        &amp; $k=1$ &amp; $2$  &amp; $3$  &amp; $4$  &amp; $5$  &amp; $6$  &amp; $7$  &amp; $8$  \\
\hline\hline
$n=1$   &amp; $-1$  &amp;      &amp;      &amp;      &amp;      &amp;      &amp;      &amp;      \\
\hline
$2$     &amp; $1$   &amp; $-1$ &amp;      &amp;      &amp;      &amp;      &amp;      &amp;      \\
\hline
$3$     &amp; $-1$  &amp; $1$  &amp; $1$  &amp;      &amp;      &amp;      &amp;      &amp;      \\
\hline
$4$     &amp; $1$   &amp; $-1$ &amp; $-2$ &amp;  $1$ &amp;      &amp;      &amp;      &amp;      \\
\hline
$5$     &amp; $-1$  &amp; $1$  &amp; $3$  &amp; $-2$ &amp; $-1$ &amp;      &amp;      &amp;      \\
\hline
$6$     &amp; $1$   &amp; $-1$ &amp; $-4$ &amp; $3$  &amp; $3$  &amp; $-1$ &amp;      &amp;      \\
\hline
$7$     &amp; $-1$  &amp; $1$  &amp; $5$  &amp; $-4$ &amp; $-6$ &amp; $3$  &amp; $1$  &amp; \hphantom{$-1$} \\
\hline
$8$     &amp; $1$   &amp; $-1$ &amp; $-6$ &amp; $5$  &amp; $10$ &amp; $-6$ &amp; $-4$ &amp; $1$  \\
\hline
\end{tabular}
\end{center}

\noindent Table 2: The numbers $S_{-1}(n,k)$ for $1\leqslant k\leqslant n
\leqslant8$.
\begin{center}
\begin{tabular}{|r||r|r|r|r|r|r|r|r|}
\hline
        &amp; $k=1$ &amp; $2$  &amp; $3$  &amp; $4$  &amp; $5$  &amp; $6$  &amp; $7$  &amp; $8$  \\
\hline\hline
$n=1$   &amp; $1$   &amp;      &amp;      &amp;      &amp;      &amp;      &amp;      &amp;      \\
\hline
$2$     &amp; $1$   &amp; $-1$ &amp;      &amp;      &amp;      &amp;      &amp;      &amp;      \\
\hline
$3$     &amp; $1$   &amp; $-1$ &amp; $-1$ &amp;\hphantom{$-1$}&amp;\hphantom{$-1$}&amp;      &amp;      &amp;      \\
\hline
$4$     &amp; $1$   &amp; $-1$ &amp; $-2$ &amp; $1$  &amp;      &amp;      &amp;      &amp;      \\
\hline
$5$     &amp; $1$   &amp; $-1$ &amp; $-3$ &amp; $2$  &amp; $1$  &amp;      &amp;      &amp;      \\
\hline
$6$     &amp; $1$   &amp; $-1$ &amp; $-4$ &amp; $3$  &amp; $3$  &amp; $-1$ &amp;      &amp;      \\
\hline
$7$     &amp; $1$   &amp; $-1$ &amp; $-5$ &amp; $4$  &amp; $6$  &amp; $-3$ &amp; $-1$ &amp; \hphantom{$-1$} \\
\hline
$8$     &amp; $1$   &amp; $-1$ &amp; $-6$ &amp; $5$  &amp; $10$ &amp; $-6$ &amp; $-4$ &amp; $1$  \\
\hline
\end{tabular}
\end{center}

\noindent Table 3: The numbers $\tilde S_{-1}(n,k)$ for $1\leqslant k
\leqslant n\leqslant 8$.
\begin{center}
\begin{tabular}{|r||r|r|r|r|r|r|r|r|}
\hline
        &amp; $k=1$ &amp; $2$  &amp; $3$  &amp; $4$  &amp; $5$  &amp; $6$  &amp; $7$  &amp; $8$  \\
\hline\hline
$n=1$   &amp; $1$   &amp;\hphantom{$-1$}&amp;\hphantom{$-1$}&amp;\hphantom{$-1$}&amp;\hphantom{$-1$}&amp;\hphantom{$-1$}&amp;\hphantom{$-1$}&amp;      \\
\hline
$2$     &amp; $1$   &amp; $1$  &amp;      &amp;      &amp;      &amp;      &amp;      &amp;      \\
\hline
$3$     &amp; $1$   &amp; $1$  &amp; $1$  &amp;      &amp;      &amp;      &amp;      &amp;      \\
\hline
$4$     &amp; $1$   &amp; $1$  &amp; $2$  &amp;  $1$ &amp;      &amp;      &amp;      &amp;      \\
\hline
$5$     &amp; $1$   &amp; $1$  &amp; $3$  &amp; $2$  &amp; $1$  &amp;      &amp;      &amp;      \\
\hline
$6$     &amp; $1$   &amp; $1$  &amp; $4$  &amp; $3$  &amp; $3$  &amp; $1$  &amp;      &amp;      \\
\hline
$7$     &amp; $1$   &amp; $1$  &amp; $5$  &amp; $4$  &amp; $6$  &amp; $3$  &amp; $1$  &amp; \hphantom{$-1$} \\
\hline
$8$     &amp; $1$   &amp; $1$  &amp; $6$  &amp; $5$  &amp; $10$ &amp; $6$  &amp; $4$  &amp; $1$  \\
\hline
\end{tabular}
\end{center}

\begin{thebibliography}{99}
\bibitem{bCa} L. Carlitz, {\rm Generalized Stirling numbers}, {\it Combinatorial
Analysis Notes}, Duke University (1968), 8-{}-15.
\bibitem{bCo} L. Comtet, {\rm Nombres de Stirling g\'en\'eraux et
fonctions symmetriques}, {\it C. R. Acad. Sci. Paris S\'erie A} {\bf 275} (1972),
747-{}-750.
\bibitem{bESW} P. Edelman, R. Simion, and D. White, {\rm Partition
statistics on permutations}, {\it Discrete Math.} {\bf 99} (1992), 62-{}-68.
\bibitem{bMi} S. Milne, {\rm A $q$-analogue of restricted growth
functions, Dobinski's equality, and Charlier polynomials},
{\it Trans. Amer. Math. Soc.} {\bf 245} (1978), 89-{}-118.
\bibitem{bRo} G.-C. Rota, {\rm The number of partitions of a set}, {\it Amer.
Math. Monthly} {\bf 71} (1964), 498-{}-504.
\bibitem{bSc} M. Schork, {\rm On the combinatorics of normal ordering
bosonic operators and deformations of it}, {\it J. Phys. A: Math. Gen.} {\bf 36}
(2003), 4651-{}-4665.
\bibitem{bSt} R. Stanley, {\it Enumerative Combinatorics, Vol.} I,
Wadsworth and Brooks/Cole, 1986.
\bibitem{bWa} C. Wagner, {\rm Generalized Stirling and Lah numbers},
{\it Discrete Math.} {\bf 160} (1996), 199-{}-218.
\bibitem{bWW} M. Wachs and D. White, {\rm $p,q$-Stirling numbers and 
partition statistics}, {\it J. Combin. Theory A} {\bf 56} (1991), 27-{}-46.
\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  August 1, 2003;
revised version received January 8, 2004. 
Published in {\it Journal of Integer Sequences}, February 9 2004.

\bigskip
\hrule
\bigskip

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


\end{document}

</pre></body></html>