\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,amsthm}
\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 Parity Theorems for Statistics on Lattice  \\
\vskip .1in
Paths and Laguerre Configurations}

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

\vskip .2 in
\begin{abstract}
We examine the parity of some statistics on lattice paths
and Laguerre configurations, giving both algebraic and combinatorial
treatments. For the former, we evaluate $q$-generating functions
at $q=-1$; for the latter, we define appropriate parity-changing
involutions on the associated structures. In addition, we furnish
combinatorial proofs for a couple of related recurrences.
\end{abstract}

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

\newtheorem{theo}{Theorem}
\numberwithin{theo}{section}
\newtheorem{cori}{Corollary}
\numberwithin{cori}{theo}
\theoremstyle{definition}
\newtheorem*{rem}{Remark}

%\documentclass[12pt,tbtags]{article}

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

\numberwithin{equation}{section}
\numberwithin{table}{section}

%\theoremstyle{plain}

%\begin{document}

%\footnote{{\em Keywords:} Laguerre configuration, Lah numbers,
%lattice paths, $q$-binomial coefficient.}

\section{Introduction}\label{sec1}

To establish the familiar result that a finite nonempty set has equally
many subsets of odd and of even cardinality it suffices either to set
$q=-1$ in the generating function
\begin{equation}\label{e1.1}
\sum_{S\subseteq[n]}q^{|S|}=\sum_{k=0}^n\binom nkq^k=(1+q)^n,
\end{equation}
where $[n]:=\{1,\dots,n\}$, or to observe that the map
\begin{equation}\label{e1.2}
S\mapsto\begin{cases}
S\cup\{1\}, &\text{if }1\notin S;\\
S-\{1\}, &\text{if }1\in S,
\end{cases}
\end{equation}
is a parity changing involution of $2^{[n]}$.

With this simple example as a model, we analyze the parity of a well known
statistic on lattice paths, as well as two statistics on what Garsia and
Remmel \cite{b3} call {\em Laguerre configurations}, i.e., distributions
of labeled balls to unlabeled, contents-ordered boxes. These statistics have
in common the fact that their generating functions all involve
$q$-binomial coefficients.

In \S\ref{sec2} we evaluate such coefficients and their sums,
known as {\em Galois numbers}, when $q=-1$, giving both algebraic
and bijective proofs. We also give a bijective proof of a
recurrence for Galois numbers, furnishing an elementary
alternative to Goldman and Rota's proof by the method of linear
functionals \cite{b4}. In \S\ref{sec3} we carry out a similar
evaluation of the two types of $q$-Lah numbers that arise as
generating functions for the aforementioned Laguerre configuration
statistics. In addition, we supply a combinatorial proof of a
recurrence for sums of Lah numbers.

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}$.
If $q$ is an indeterminate, then $0_q:=0$,
$n_q:=1+q+\dots+q^{n-1}$ if $n\in\mathbb{P}$,
$0_q^{\textstyle!}:=1$, $n_q^{\textstyle!}:= 1_q2_q\cdots n_q$ if
$n\in\mathbb{P}$, and
\begin{equation}\label{e1.3}
\binom nk_q:=\begin{cases}
\frac{n_q^{\textstyle!}}{k_q^{\textstyle!}(n-k)_q^{\textstyle!}}, &\text{if $0\leq k\leq n$;}\\
0, &\text{if $k<0$ or $0\leq n<k$.}
\end{cases}
\end{equation}
Our notation in \eqref{e1.3} for the $q$-binomial coefficient,
which agrees with Knuth's \cite{b5}, has the advantage over the
traditional notation $n \brack k$ that it can be used to reflect
particular values of the parameter $q$.

\section{A Statistic on Lattice Paths}\label{sec2}

Let $\Lambda(n,k)$ denote the set of (minimal) lattice paths from
$(0,0)$ to $(k,n-k)$, where $0\leqslant k\leqslant n$. Each
$\lambda\in\Lambda(n,k)$ corresponds to a sequential arrangement
$t_1\cdots t_n$ of the multiset $\left\{1^k,2^{n-k}\right\}$, with
$1$ representing a horizontal and $2$ a vertical step. Hence,
$|\Lambda(n,k)|=\binom nk$. Moreover, since the area
$\alpha(\lambda)$ subtended by $\lambda$ is equal to the number of
inversions in the corresponding word (i.e., the number of ordered
pairs $(i,j)$ with $1\leqslant i<j\leqslant n$ such that
$t_i>t_j$), and since the $q$-binomial coefficient is the
generating function for the statistic that records the number of
inversions in such words \cite[Prop. 1.3.17]{b7}, it follows that
\begin{equation}\label{e2.1}
\sum_{\lambda\in\Lambda(n,k)}q^{\alpha(\lambda)}=\binom nk_q,
\end{equation}
a result that Berman and Fryer \cite[p. 218]{b1} attribute to Polya. With
\begin{equation}\label{e2.2}
\Lambda(n):=\bigcup_{0\leqslant k\leqslant n}\Lambda(n,k),
\end{equation}
it follows that
\begin{equation}\label{e2.3}
\sum_{\lambda\in\Lambda(n)}q^{\alpha(\lambda)}=G_q(n):=\sum_{k=0}^n
\binom nk_q.
\end{equation}
The polynomials $G_q(n)$ have been termed {\em Galois numbers} by
Goldman and Rota \cite{b4}.

Let $\Lambda_r(n):=\{\lambda\in\Lambda(n):\ \alpha(\lambda)\equiv r\pmod 2\}$,
and let $\Lambda_r(n,k):=\Lambda(n,k)\cap\Lambda_r(n)$. Clearly,
\begin{equation}\label{e2.5}
\binom nk_{-1}=|\Lambda_0(n,k)|-|\Lambda_1(n,k)|,
\end{equation}
and
\begin{equation}\label{e2.6}
G_{-1}(n)=|\Lambda_0(n)|-|\Lambda_1(n)|.
\end{equation}
In evaluating \eqref{e2.5} and \eqref{e2.6} we shall employ several alternative
characterizations of $\binom nk_q$, namely, the recurrence
\begin{equation}\label{e2.7}
\binom nk_q=\binom{n-1}{k-1}_q+q^k\binom{n-1}k_q,\qquad\forall n,k\in
\mathbb{P},
\end{equation}
with $\binom n0_q=\delta_{n,0}$ and $\binom 0k_q=\delta_{k,0}$,
$\forall$ $n,k\in\mathbb{N}$, the generating function
\begin{equation}\label{e2.8}
\sum_{n\geqslant0}\binom nk_qx^n=\frac{x^k}{(1-x)(1-qx)\cdots(1-q^kx)},
\qquad \forall k\in\mathbb{N},
\end{equation}
and the summation formula
\begin{equation}\label{e2.9}
\binom nk_q=\sum_{\substack{d_0+d_1+\dots+d_k=n-k\\ d_i\in\mathbb{N}}}
q^{d_1+2d_2+\dots+kd_k}.
\end{equation}
See \cite[pp. 201--202]{b8} for further details.

Setting $q=-1$ in \eqref{e2.8} and treating separately the
even and odd cases for $k$ yields

\begin{theo}\label{t2.1}
If $0\leqslant k\leqslant n$, then
\begin{equation}\label{e2.10}
\binom{n}{k}_{-1}=\begin{cases}
0, &\text{if $n$ is even and $k$ is odd;}\\
\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor},
&\text{otherwise.}
\end{cases}
\end{equation}
\end{theo}

\noindent A straightforward application of \eqref{e2.10} yields
\begin{cori}\label{c2.1.1}
For all $n\in\mathbb{N}$,
\begin{equation}\label{ne2.11}
G_{-1}(n)=2^{\lceil n/2\rceil}.
\end{equation}
\end{cori}

The above results are well known and apparently very old. But the
following bijective proofs of \eqref{e2.10} and \eqref{ne2.11},
which convey a more visceral understanding of these formulas, are,
so far as we know, new.\\\\

\newpage

{\emph{Bijective proofs of Theorem 2.1 and Corollary 2.1.1.}}\\

As above, we represent a lattice path $\lambda\in\Lambda(n)$ by a
word $t_1t_2\cdots t_n$ in the alphabet $\{1,2\}$, recalling that
$\alpha(\lambda)$ is equal to the number of inversions in this
word, which we also denote by $\alpha(\lambda)$. By \eqref{e2.6},
formula \eqref{ne2.11} asserts that
\begin{equation}\label{ne2.12}
|\Lambda_0(n)|-|\Lambda_1(n)|=2^{\lceil n/2\rceil}.
\end{equation}

Our strategy for proving \eqref{ne2.12} is to identify a
subset $\Lambda_0^+(n)$ of $\Lambda_0(n)$ having
cardinality $2^{\lceil n/2\rceil}$, along with an $\alpha$-parity
changing involution of $\Lambda(n)-\Lambda_0^+(n)$. Let
$\Lambda_0^+(n)$ comprise those words
$\lambda=t_1t_2\cdots t_n$ such that for $i=1,2,\dots,\lfloor n/2
\rfloor$,
\begin{equation}\label{ne2.13}
t_{2i-1}t_{2i}=11\text{ or }22.
\end{equation}
Clearly, $\Lambda_0^+(n)\subseteq\Lambda_0(n)$ and
$|\Lambda_0^+(n)|=2^{\lceil n/2\rceil}$. If
$\lambda\in\Lambda(n)-\Lambda_0^+(n)$, let $i_0$ be the smallest
index for which \eqref{ne2.13} fails to hold and let $\lambda'$ be
the result of switching $t_{2i_0-1}$ and $t_{2i_0}$ in $\lambda$.
The map $\lambda\mapsto\lambda'$ is clearly an $\alpha$-parity
changing involution of $\Lambda(n)-\Lambda_0^+(n)$, which proves
\eqref{ne2.12} and hence \eqref{ne2.11}.

By \eqref{e2.5}, formula \eqref{e2.10} asserts that
\begin{equation}\label{ne2.14}
|\Lambda_0(n,k)|-|\Lambda_1(n,k)|=\begin{cases}
0, &\text{if $n$ is even and $k$ is odd;}\\
\binom{\lfloor n/2\rfloor}{\lfloor k/2\rfloor},
&\text{otherwise.}
\end{cases}
\end{equation}
To show \eqref{ne2.14}, let $\Lambda_0^+(n,k)=\Lambda_0^+(n)
\cap\Lambda(n,k)$. The cardinality of $\Lambda_0^+(n,k)$ is given
by the right-hand side of \eqref{ne2.14}, and the restriction of
the above map to $\Lambda(n,k)-\Lambda_0^+(n,k)$ is again an
involution and inherits the parity changing property. This proves
\eqref{ne2.14}, and hence \eqref{e2.10}.
$\hfill\square$\\

In tabulating the numbers $\binom nk_{-1}$ it is of course more efficient
to use the recurrence
\begin{equation}\label{e2.11}
\binom nk_{-1}=\binom{n-1}{k-1}_{-1}+(-1)^k\binom{n-1}k_{-1},
\end{equation}
representing the case $q=-1$ of \eqref{e2.7}.

Comparison of \eqref{e2.10} with an evaluation of $\binom nk_{-1}$ based
on \eqref{e2.9} yields a pair of interesting identities.

\begin{cori}
If $1\leqslant m\leqslant\lfloor n/2\rfloor$, then
\begin{equation}\label{e2.12}
\sum_{j=0}^{n-2m}(-1)^j\binom{m+j-1}{m-1}\binom{n-m-j}m=
\binom{\lfloor n/2\rfloor}m,
\end{equation}
and if $0\leqslant m\leqslant\lfloor (n-1)/2\rfloor$, then
\begin{equation}\label{e2.13}
\sum_{j=0}^{n-2m-1}(-1)^j\binom{m+j}m\binom{n-m-j-1}m=
\begin{cases}
0, &\text{if $n$ is even;}\\
\binom{\lfloor n/2\rfloor}m, &\text{if $n$ is odd.}
\end{cases}
\end{equation}
\end{cori}
\begin{proof}
Setting $q=-1$ and $k=2m$ in \eqref{e2.9} yields
\[
\begin{split}
\binom{n}{2m}_{-1} &= \sum_{d_0+d_1+\dots+d_{2m}=n-2m}(-1)^{d_1+
d_3+\dots+d_{2m-1}}\\
&\underset{(j=d_1+d_3+\dots+d_{2m-1})}=\sum_{j=0}^{n-2m}(-1)^j
\binom{m+j-1}{m-1}\binom{n-m-j}m,
\end{split}
\]
which implies \eqref{e2.12} by \eqref{e2.10}, upon independently
choosing the $d_i$'s of even index, which sum to $n-2m-j$. Setting
$k=2m+1$ yields
\[
\begin{split}
\binom n{2m+1}_{-1} &= \sum_{d_0+d_1+\dots+d_{2m+1}=n-2m-1}(-1)^{d_1+d_3+
\dots+d_{2m+1}}\\
&\underset{(j=d_1+d_3+\dots+d_{2m+1})}=\sum_{j=0}^{n-2m-1}(-1)^j
\binom{m+j}m\binom{n-m-j-1}m,
\end{split}
\]
which implies \eqref{e2.13} by \eqref{e2.10}.
\end{proof}

Corollary~\ref{c2.1.1} above
can also be proved by induction from the case
$q=-1$ of the following recurrence for $G_q(n)$:

\begin{theo}\label{t2.2}
For all $n\in\mathbb{P}$,
\begin{equation}\label{e2.15}
G_q(n+1)=2G_q(n)+(q^n-1)G_q(n-1),
\end{equation}
where $G_q(0)=1$ and $G_q(1)=2$.
\end{theo}
\begin{proof}
Let $a(n,i):=|\{\lambda\in\Lambda(n):\ \alpha(\lambda)=i\}|$,
where $n\in\mathbb{N}$ and $a(n,i):=0$ if $i<0$. Showing
\eqref{e2.15} is equivalent to showing that
\begin{equation}\label{e2.16}
\begin{split}
a(n+1,i) &= 2a(n,i)+a(n-1,i-n)-a(n-1,i)\\
&= a(n,i)+(a(n,i)-a(n-1,i))+a(n-1,i-n)
\end{split}
\end{equation}
for all $i\in\mathbb{N}$. As above, we represent a lattice path
$\lambda\in\Lambda(n+1)$ by a word $t_1t_2\cdots t_{n+1}$ in the
alphabet $\{1,2\}$, recalling that $\alpha(\lambda)$ is equal to
the number of inversions in this word.

The term $a(n+1,i)$ thus counts all words of length $n+1$ with $i$ inversions.
The term $a(n,i)$ counts the subclass of such words for which $t_{n+1}=2$.
The term $a(n,i)-a(n-1,i)$ counts the subclass of such words for which
$t_1=t_{n+1}=1$. For deletion of $t_1$ is a bijection from this subclass
to the class of words $u_1u_2\cdots u_n$ with $i$ inversions and $u_n=1$,
and there are clearly $a(n,i)-a(n-1,i)$ words of the latter type. Finally,
the term $a(n-1,i-n)$ counts the subclass of words for which $t_1=2$ and
$t_{n+1}=1$. For deletion of $t_1$ and $t_{n+1}$ is a bijection from this
subclass to the class of words $v_1v_2\cdots v_{n-1}$ with $i-n$ inversions
(both classes being empty if $i<n$).
\end{proof}

The above proof provides an elementary alternative to Goldman and Rota's
proof of \eqref{e2.15} using the method of linear functionals \cite{b4}.

\section{Two Statistics on Laguerre Configurations}\label{sec3}

Let $\mathcal{L}(n,k)$ denote the set of distributions of $n$
balls, labeled $1,2,\dots,n$, among $k$ unlabeled, {\em
contents-ordered} boxes, with no box left empty. Garsia and Remmel
\cite{b3} term such distributions {\em Laguerre configurations}.
If $L(n,k):=|\mathcal{L}(n,k)|$, then $L(n,0)=\delta_{n,0}$,
$\forall$ $n\in\mathbb{N}$, $L(n,k)=0$ if $0\leqslant n<k$, and
\begin{equation}\label{e3.1}
L(n,k)=\frac{n!}{k!}\binom{n-1}{k-1},\qquad
1\leqslant k\leqslant n.
\end{equation}
The numbers $L(n,k)$ are called {\em Lah numbers}, after Ivo Lah
\cite{b6}, who introduced them as the connection constants in the
polynomial identities
\begin{equation}\label{e3.2}
x(x+1)\cdots(x+n-1)=\sum_{k=0}^n L(n,k)x(x-1)\cdots(x-k+1),\qquad
\forall n\in\mathbb{N}.
\end{equation}
From \eqref{e3.1} it follows that
\begin{equation}\label{e3.3}
\sum_{n\geqslant k}L(n,k)\frac{x^n}{n!}=\frac1{k!}\left(\frac{x}{1-x}\right)^k,
\qquad\forall k\in\mathbb{N}.
\end{equation}
The Lah numbers also satisfy the recurrence relations
\begin{equation}\label{e3.4}
L(n,k)=L(n-1,k-1)+(n+k-1)L(n-1,k),\qquad\forall n,k\in\mathbb{P},
\end{equation}
and
\begin{equation}\label{e3.5}
L(n,k)=\frac nkL(n-1,k-1)+nL(n-1,k),\qquad\forall n,k\in\mathbb{P}.
\end{equation}


%%%%%%%%%%mid page 7%%%%%%%%%%%%%%%%


The set $\mathcal{L}(n):=\bigcup_k\mathcal{L}(n,k)$ comprises  all distributions
of $n$ balls, labeled $1,2,\dots,n$, among $n$ unlabeled, contents-ordered
boxes. If $L(n):=|\mathcal{L}(n)|$, it follows from \eqref{e3.3} that
\begin{equation}\label{e3.6}
\sum_{n\geqslant0}L(n)\frac{x^n}{n!}=e^{x/(1-x)},
\end{equation}
and differentiating \eqref{e3.6} yields \cite[p. 171]{new6},
\cite[A000262]{new9}

\begin{theo}\label{t3.1}
For all $n\in\mathbb{P}$,
\begin{equation}\label{e3.7}
L(n+1)=(2n+1)L(n)-(n^2-n)L(n-1),\end{equation} where
$L(0)=L(1)=1$.\end{theo} \noindent \emph{Combinatorial proof of
Theorem
3.1.}\\

We'll argue that the cardinality of $\mathcal{L}(n+1)$ is given by
the right-hand side of \eqref{e3.7} when $n\geqslant1$. Let us
represent members of $\mathcal{L}(m)$ by partitions of $[m]$ in
which the elements of each block are ordered. As there are clearly
$L(n)$ members of $\mathcal{L}(n+1)$ in which the singleton
$\{n+1\}$ occurs, we need only show that the members of
$\mathcal{L}(n+1)$ in which the singleton $\{n+1\}$ doesn't occur
number $2nL(n)-n(n-1)L(n-1)$.

Suppose $\lambda\in\mathcal{L}(n)$ and consider the $2n$ members
of $\mathcal{L}(n+1)$ gotten from $\lambda$ by inserting $n+1$
either directly before or directly after an element of $[n]$
within $\lambda$. Then $2nL(n)$ double counts members of
$\mathcal{L}(n+1)$ for which $n+1$ is neither first nor last in
its block and counts once all other members of $\mathcal{L}(n+1)$
for which $n+1$ goes in a block with at least one element of
$[n]$. But there are $n(n-1)L(n-1)$ configurations of the former
type as seen upon choosing an element $j$ of $[n]$ to directly
follow $n+1$ and then inserting $n+1,j$ directly after an element
of $[n]-\{j\}$ in a Laguerre configuration of the set
$[n]-\{j\}$.\hspace{2in}$\hfill\square$\\

In what follows, we consider two statistics on Laguerre configurations.

\subsection{The Statistic $i$}

Given a distribution $\delta\in\mathcal{L}(n,k)$, let us represent the
ordered contents of each box by a word in $[n]$, and then arrange these
words in a sequence $W_1,\dots,W_k$ in decreasing order of their least
elements. Replacing the commas in this sequence by zeros and counting
inversions in the resulting single word yields the value $i(\delta)$,
i.e.,
\begin{equation}\label{e3.8}
i(\delta)=\text{ the number of inversions in }W_10W_20\cdots
0W_{k-1}0W_k.
\end{equation}
As an illustration, for the distribution $\delta\in\mathcal{L}(9,4)$ given
by
\begin{equation}\label{e3.9}
\begin{array}{|c|} 3,4,9\\ \hline\end{array}\quad
\begin{array}{|c|} 8,1\\ \hline\end{array}\quad
\begin{array}{|c|} 2,6\\ \hline\end{array}\quad
\begin{array}{|c|} 7,5\\ \hline\end{array}\ ,
\end{equation}
we have $i(\delta)=35$, the number of inversions in the word
$750349026081$.

The statistic $i$ is due to Garsia and Remmel \cite{b3}, who show that the
generating function
\begin{equation}\label{e3.10}
L_q(n,k):=\sum_{\delta\in\mathcal{L}(n,k)}q^{i(\delta)}=q^{k(k-1)}
\frac{n_q^{\textstyle!}}{k_q^{\textstyle!}}\binom{n-1}{k-1}_q,\quad
1\leqslant k\leqslant n.
\end{equation}
Generalizing \eqref{e3.4}, the $q$-Lah number $L_q(n,k)$
satisfies the recurrence
\begin{equation}
L_q(n,k)=q^{n+k-2}L_q(n-1,k-1)\\+(n+k-1)_qL_q(n-1,k),
\forall n,k\in\mathbb{P}.
\end{equation}
Garsia and Remmel also show that
\begin{equation}\label{e3.12}
x_q(x+1)_q\cdots(x+n-1)_q=\sum_{k=1}^nL_q(n,k)x_q(x-1)_q\cdots(x-k+1)_q,
\end{equation}
where $x_q:=\left.(q^x-1)\right/(q-1)$. It seems not to have been noted that
\eqref{e3.12} is equivalent to
\begin{equation}\label{e3.13}
x(qx+1_q)\cdots(q^{n-1}x+(n-1)_q) = \sum_{k=1}^nL_q(n,k)x
\left(\frac{x-1_q}q\right)\cdots\left(\frac{x-(k-1)_q}{q^{k-1}}\right),
\end{equation}
which generalizes \eqref{e3.2}.

\begin{theo}\label{t3.2}
If $1\leq k\leq n$, then
\begin{equation}\label{e3.14}L_{-1}(n,k)=\delta_{n,k}.
\end{equation}
\end{theo}
\begin{proof}
Formula \eqref{e3.14} is an immediate consequence of \eqref{e3.10}
and \eqref{e2.10}, upon considering even and odd cases for $n$, as
$j_{-1}=0$ if $j$ is even (cf. \cite{bn8}). For a bijective proof
of \eqref{e3.14}, first note that
$L_{-1}(n,k)=|\mathcal{L}_0(n,k)|-|\mathcal{L}_1(n,k)|$, where
$\mathcal{L}_r(n,k):=\left\{\delta\in\mathcal{L}(n,k) :\
i(\delta)\equiv r\pmod2\right\}$. Now $\mathcal{L}(n,n)$ consists
of a single distribution $\delta$, with $i(\delta)=n(n-1)=$ the
number of inversions in $n0(n-1)0\cdots0 201$, whence
$|\mathcal{L}_0(n,n)|=1$ and $|\mathcal{L}_1(n,n)|=0$. If
$1\leqslant k<n$ and $\delta\in\mathcal{L}(n,k)$ gives rise to the
sequence $W_1,\dots,W_k$, then locate the leftmost word $W_i$
containing at least two letters and interchange its first two
letters. The resulting map is a parity changing involution of
$\mathcal{L}(n,k)$, whence
$|\mathcal{L}_0(n,k)|-|\mathcal{L}_1(n,k)|=0$.
\end{proof}

\begin{rem}
Note that $\mathcal{L}(n,1)=\mathcal{S}_n$, the set of permutations of
$[n]$, and so \eqref{e3.10} is a generalization of the well known result
that
\begin{equation}\label{e3.15}
\sum_{\pi\in\mathcal{S}_n}q^{i(\pi)}=n_q^{\textstyle!},
\end{equation}
and \eqref{e3.14} a generalization of the fact that among the permutations
of $[n]$, if $n\geqslant2$, there are as many with an odd number of inversions
as there are with an even number of inversions.
\end{rem}

\subsection{The Statistic $\tilde w$}
As above, given $\delta\in\mathcal{L}(n,k)$, we represent the ordered contents
of each box by a word in $[n]$. Now, however, we arrange these words in a
sequence $W_1,\dots,W_k$ in increasing order of their initial elements,
defining $\tilde w(\delta)$ by the formula
\begin{equation}\label{e3.16}
\tilde w(\delta)=\sum_{i=1}^k(i-1)(|W_i|-1),
\end{equation}
where $|W_i|$ denotes the length of the word $W_i$. As an
illustration, for the distribution $\delta\in\mathcal{L}(9,4)$
given above by \eqref{e3.9}, we have $W_1$, $W_2$, $W_3$,
$W_4=26$, $349$, $75$, $81$ and $\tilde w(\delta)=7$. The
statistic $\tilde w$ is an analogue of a now well known partition
statistic first introduced by Carlitz \cite{b2} (see also
\cite{b8}).

\begin{theo}\label{t3.3}
The generating function
\begin{equation}\label{e3.17}
\tilde L_q(n,k):=\sum_{\delta\in\mathcal{L}(n,k)}q^{\tilde w(\delta)}=
\frac{n!}{k!}\binom{n-1}{k-1}_q,\qquad
1\leqslant k\leqslant n.
\end{equation}
\end{theo}
\begin{proof}
In running through $\delta\in\mathcal{L}(n,k)$, we are running through all
sequences of words $W_1,\dots,W_k$ whose initial elements form an increasing
sequence, and such that $|W_i|=n_i$, with $\sum n_i=n$. For fixed such
$n_1,\dots,n_k$, there are $\binom nk(n-k)!$ such sequences,
$\binom nk$ being the number of ways to choose and place the initial
elements, and $(n-k)!$ the number of ways to place the remaining elements.
By \eqref{e3.16} and \eqref{e2.9}, it follows that
\[
\begin{split}
\sum_{\delta\in\mathcal{L}(n,k)}q^{\tilde w(\delta)} &=\binom nk
(n-k)!\sum_{\substack{n_1+\dots+n_k=n\\ n_i\in\mathbb{P}}}
q^{0(n_1-1)+1(n_2-1)+\dots+(k-1)(n_k-1)}\\
&=\frac{n!}{k!}\binom{n-1}{k-1}_q.
\end{split}
\]
\end{proof}
From \eqref{e3.17} and \eqref{e2.8}, it follows that
\begin{equation}\label{e3.18}
\sum_{n\geqslant k}\tilde L_q(n,k)\frac{x^n}{n!}=\frac1{k!}
\frac{x^k}{\prod\limits_{0\leqslant j\leqslant k-1}(1-q^jx)},\quad
\forall k\in\mathbb{N},
\end{equation}
which generalizes \eqref{e3.3}. The $q$-Lah number $\tilde L_q(n,k)$ also
satisfies the recurrence
\begin{equation}\label{e3.19}
\tilde L_q(n,k)=\frac nk\tilde L_q(n-1,k-1)+nq^{k-1}\tilde L_q(n-1,k),
\end{equation}
which generalizes \eqref{e3.5}.

\begin{theo}\label{t3.4}
If $1\leq k\leq n$, then
\begin{equation}\label{e3.20} \tilde
L_{-1}(n,k)=\begin{cases}
0, &\text{if $n$ is odd and $k$ is even;}\\
\frac{n!}{k!}\binom{\lfloor (n-1)/2\rfloor}{\lfloor (k-1)/2\rfloor},
&\text{otherwise.}
\end{cases}
\end{equation}
\end{theo}
\begin{proof}
This follows immediately from \eqref{e3.17} and \eqref{e2.10}, but the
following bijective proof yields a deeper insight into this result:
with $\mathcal{L}_r(n,k):=\left\{\delta\in\mathcal{L}(n,k):\ %
\tilde w(\delta)\equiv r\pmod2\right\}$, we have
$\tilde L_{-1}(n,k)=|\mathcal{L}_0(n,k)|-|\mathcal{L}_1(n,k)|$.
To prove \eqref{e3.20} it thus suffices to identify a subset $\mathcal{L}_0^+
(n,k)$ of $\mathcal{L}_0(n,k)$ such that
\begin{equation}\label{e3.21}
|\mathcal{L}_0^+(n,k)|=\begin{cases}
0, &\text{if $n$ is odd and $k$ is even;}\\
\frac{n!}{k!}\binom{\lfloor (n-1)/2\rfloor}{\lfloor(k-1)/2\rfloor},
&\text{otherwise,}
\end{cases}
\end{equation}
along with a parity changing involution of $\mathcal{L}(n,k)-\mathcal{L}_0^+
(n,k)$.

The set $\mathcal{L}_0^+(n,k)$ consists of those distributions whose associated
sequences $W_1,W_2,\dots,W_k$ satisfy
\begin{equation}\label{e3.22}
|W_{2i-1}|\text{ is odd and }|W_{2i}|=1,\ 1\leqslant i\leqslant
\lfloor k/2\rfloor.
\end{equation}
Clearly, $\mathcal{L}_0^+(n,k)=\varnothing$ if $n$ is odd and $k$
is even. In the remaining cases, the factor $n!/k!$ arises as the
product $\binom nk(n-k)!$, just as it does in the proof of Theorem
\ref{t3.3}, and
\begin{multline}\label{e3.23}
\binom{\lfloor(n-1)/2\rfloor}{\lfloor(k-1)/2\rfloor}=\left|\left\{
(n_1,\dots,n_k):\ \sum n_i=n,\ n_{2i-1}\text{ is odd,}\right.\right.\\
\left.\left.\vphantom{\sum}\text{and }n_{2i}=1,\ 1\leqslant i
\leqslant\lfloor k/2\rfloor\right\}\right|,
\end{multline}upon halving
compositions of an integer whose parts are all even.

Suppose now that $\delta\in\mathcal{L}(n,k)-\mathcal{L}_0^+(n,k)$
is associated with the sequence $W_1,\dots,W_k$ and that $i_0$ is
the smallest index for which \eqref{e3.22} fails to hold. If
$|W_{2i_0-1}|$ is even, take the last member of $W_{2i_0-1}$ and
place it at the end of $W_{2i_0}$. If $|W_{2i_0-1}|$ is odd,
whence $|W_{2i_0}|\geqslant2$, take the last member of $W_{2i_0}$
and place it at the end of $W_{2i_0-1}$. The resulting map is a
parity changing involution of
$\mathcal{L}(n,k)-\mathcal{L}_0^+(n,k)$.
\end{proof}

In tabulating the numbers $\tilde L_{-1}(n,k)$ it is of course more efficient
to use the recurrence
\begin{equation}\label{e3.24}
\tilde L_{-1}(n,k)=\frac nk\tilde L_{-1}(n-1,k-1)+(-1)^{k-1}n
\tilde L_{-1}(n-1,k),
\end{equation}
representing the case $q=-1$ of \eqref{e3.19}. This yields the following
table for $0\leqslant k\leqslant n\leqslant 8$:

\begin{table}[h]
\caption{\label{tab3.1}The numbers $\tilde L_{-1}(n,k)$ for
$0\leqslant k\leqslant n\leqslant8$.}
\begin{center}
\begin{tabular}{|c||r|r|r|r|r|r|r|r|r|}
\hline
                 & $k=0$ & $\hphantom{k=}1$ & $\hphantom{k=}2$ &
         $\hphantom{k=}3$ & $\hphantom{k=}4$ & $\hphantom{k=}5$ &
         $\hphantom{k=}6$ & $\hphantom{k=}7$ & $\hphantom{k=}8$ \\
\hline\hline
$n=0$            & 1     &   &   &   &   &   &   &   &   \\
\hline
$\hphantom{n=}1$ & 0     & 1 &   &   &   &   &   &   &   \\
\hline
$\hphantom{n=}2$ & 0     & 2 & 1 &   &   &   &   &   &   \\
\hline
$\hphantom{n=}3$ & 0     & 6  & 0  & 1 &   &   &   &   &   \\
\hline
$\hphantom{n=}4$ & 0     & 24  & 12 & 4  & 1 &   &   &   &   \\
\hline
$\hphantom{n=}5$ & 0     & 120 & 0   & 40  & 0  & 1 &   &   &   \\
\hline
$\hphantom{n=}6$ & 0     & 720  & 360 & 240  & 60 & 6   & 1 &   &   \\
\hline
$\hphantom{n=}7$ & 0     & 5040  & 0     & 2520  & 0    & 126  & 0   & 1 &   \\
\hline
$\hphantom{n=}8$ & 0     & 40320 & 20160 & 20160 & 5040 & 1008 & 168 & 8 & 1 \\
\hline
\end{tabular}
\end{center}
\end{table}
The row sums of Table \ref{tab3.1} correspond to the quantities
$\tilde L_{-1}(n)$ \cite[A089656]{new9}, where
\begin{equation}\label{e3.25}
\tilde L_q(n):=\sum_{\delta\in\mathcal{L}(n)}q^{\tilde w(\delta)}=
\sum_k\tilde L_q(n,k).
\end{equation}
We have been unable to find a simple closed form or recurrence for
$\tilde L_{-1}(n)$. However, using the case $q=-1$ of formula \eqref{e3.18},
it is straightforward to show that
\begin{equation}\label{e3.26}
\sum_{n\geqslant0}\tilde L_{-1}(n)\frac{x^n}{n!}=\cosh\frac{x}{\sqrt{1-x^2}}
+\frac{\sqrt{1-x^2}}{1-x}\sinh\frac{x}{\sqrt{1-x^2}}.
\end{equation}
The values of $\tilde L_{-1}(n)$ for $0\leqslant n\leqslant 10$
are as follows: 1, 1, 3, 7, 41, 161, 1387, 7687, 86865, 623233,
8682131.

\section{Some Concluding Remarks}\label{sec4}

Reductions from $q$-binomial coefficients to ordinary binomial
coefficients similar to those seen when $q=-1$ occur with higher
roots of unity. For example, substituting
$q=\rho=\frac{-1+\sqrt{3}i}2$, a third root of unity, and $q=i$, a
fourth root of unity, into \eqref{e2.8} and considering cases for
$k$ mod $3$ and mod $4$ yields \begin{theo}\label{t4.1} If $0\leq
k\leq n$, then
\begin{align}
\label{e4.1} \binom{n}{k}_\rho &=
\begin{cases}
\vphantom{{\displaystyle\int}} \binom{\lfloor n/3\rfloor}{\lfloor
k/3\rfloor},
&\text{if }n\equiv k\!\!\pmod3\text{ or }k\equiv0\!\!\pmod3;\\
\vphantom{{\displaystyle\int}} -\rho^2\binom{\lfloor
n/3\rfloor}{\lfloor k/3\rfloor},
&\text{if }n\equiv2\!\!\pmod3\text{ and }k\equiv1\!\!\pmod3;~~~~\\
\vphantom{{\displaystyle\int}} 0, &\text{otherwise}.
\end{cases}\end{align}\end{theo}
\noindent and \begin{theo}\label{t4.2} If $0\leq k\leq n$, then
\begin{align}\label{e4.2} \binom{n}{k}_i &=
\begin{cases}
\vphantom{{\displaystyle\int}}
\binom{\lfloor n/4\rfloor}{\lfloor k/4\rfloor},
&\text{if }n\equiv k\!\!\pmod4\text{ or }k\equiv0\!\!\pmod4;\\
\vphantom{{\displaystyle\int}}
i\binom{\lfloor n/4\rfloor}{\lfloor k/4\rfloor},
&\text{if }n\equiv 3\!\!\pmod4\text{ and }k\equiv1,2\!\!\pmod4;\\
\vphantom{{\displaystyle\int}}
(1+i)\binom{\lfloor n/4\rfloor}{\lfloor k/4\rfloor},
&\text{if }n\equiv2\!\!\pmod4\text{ and }k\equiv1\!\!\pmod4;\\
\vphantom{{\displaystyle\int}}
0, &\text{otherwise}.
\end{cases}
\end{align}
\end{theo}
\noindent\emph{Bijective proof of Theorem 4.1.}\\

We modify the combinatorial argument used to establish
\eqref{e2.10}. Instead of pairing members of $\Lambda(n,k)$ of
opposite $\alpha$-parity, we partition a portion of $\Lambda(n,k)$
into tripletons each of whose members have different $\alpha$
values mod $3$. Each such tripleton contributes $0$ towards the
sum $\binom{n}{k}_\rho=\sum_{\lambda\in\Lambda(n,k)}\rho^{\alpha(
\lambda)}$ since $1+\rho+\rho^2=0$.

As before, we represent lattice paths by words in $\{1,2\}$. Let
$\Lambda'(n,k)$ consist of those words $\lambda=t_1t_2\cdots t_n$
in $\Lambda(n,k)$ satisfying
\begin{equation}\label{e4.3}
t_{3i-2}=t_{3i-1}=t_{3i},\qquad
1\leqslant i\leqslant\lfloor n/3\rfloor.
\end{equation}
In all cases, the right-hand side of \eqref{e4.1} above gives the
net contribution of $\Lambda'(n,k)$ towards $\binom{n}{k}_\rho$;
note that members
of $\Lambda'(n,k)$ may end in either $12$ or $21$ if $n\equiv2\pmod3$
and $k\equiv1\pmod3$, hence the $1+\rho=-\rho^2$ factor in this case.

Suppose now that $\lambda=t_1t_2\cdots
t_n\in\Lambda(n,k)-\Lambda'(n,k)$, with $i_0$ the smallest $i$ for
which \eqref{e4.3} fails to hold. Group the three members of
$\Lambda(n,k)-\Lambda'(n,k)$ gotten by circularly permuting
$t_{3i_0-2}$, $t_{3i_0-1}$, and $t_{3i_0}$ within
$\lambda=t_1t_2\cdots t_n$, leaving the rest of $\lambda$
undisturbed. Note that these three members of
$\Lambda(n,k)-\Lambda'(n,k)$ have different $\alpha$ values mod
$3$, which establishes \eqref{e4.1}.$\hfill{\square}$\\

A similar proof, which involves partitioning members of
$\Lambda(n,k)$ according to their \emph{inv} values mod 4, applies
to \eqref{e4.2}, the details of which we leave as an exercise for
interested readers.

If $m\in\mathbb{P}$ and $\omega=e^{2\pi i/m}$, a primitive
$m^{\text{th}}$ root of unity, examining \eqref{e2.8} when
$q=\omega$ reveals that $\binom{n}{k}_\omega$ is of the form
$\beta\binom{\lfloor n/m\rfloor}{\lfloor k/m\rfloor}$ for all $n$
and $k$, where $\beta$ is some complex number depending on the
values of $n$ and $k$ mod $m$. Even though $\beta$ can in general
be expressed in terms of symmetric functions of certain $m^{th}$
roots of unity, there does not appear to be a simple closed form
for $\binom{n}{k}_\omega$ which generalizes \eqref{e2.10},
\eqref{e4.1}, and \eqref{e4.2}. Some particular cases are easily
ascertained. For example, when $m$ divides $n$, we have from
\eqref{e2.8},
\begin{equation}\label{e4.4}
\binom nk_{\omega}=\begin{cases}\binom{n/m}{k/m},
&\text{if } m \text{ divides }k;\\
0, &\text{otherwise}.\end{cases}\end{equation} When $m$ is a
prime, the combinatorial argument used for \eqref{e4.1} readily
generalizes to \eqref{e4.4}.

\begin{thebibliography}{99}
\bibitem{b1}
G. Berman and K. Fryer, {\it Introduction to Combinatorics},
Academic Press, 1972.

\bibitem{b2}
L. Carlitz, {\it Combinatorial analysis notes}, Duke University
 (1968).

\bibitem{b3}
A. Garsia and J. Remmel, A combinatorial interpretation of
$q$-derangement and $q$-Laguerre numbers, {\it Europ. J.
Combinatorics} \textbf{1} (1980), 47--59.

\bibitem{b4}
J. Goldman and G.-C. Rota, The number of subspaces of a vector space, in:
W. Tutte, ed., {\it Recent Progress in Combinatorics},
Academic Press (1969), 75--83.

\bibitem{b5}
D. Knuth, Two notes on notation, {\it Amer. Math. Monthly}
\textbf{99} (1992), 403-422.

\bibitem{b6}
I. Lah, Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung
in der mathematischen Statistik, {\em Mitteilungsbl. Math.
Statist.} \textbf{7} (1955), 203--212.

\bibitem{new6}
T. S. Motzkin, Sorting numbers for cylinders and other
classification numbers, in: {\em Proc. Symp. Pure Math., Vol.}
{\it 19}, American Mathematical Society (1971), 167--176.

\bibitem{bn8}
M. Schork, Fermionic relatives of Stirling and Lah numbers, {\em
J. Phys. A: Math. Gen.} \textbf{36} (2003), 10391--10398.

\bibitem{new9}
N. J. A. Sloane, \href{http://www.research.att.com/~njas/sequences/}{On-Line Encyclopedia
of Integer Sequences}.

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

\bibitem{b8}
C. Wagner, Generalized Stirling and Lah numbers, {\it Discrete
Math.} \textbf{160} (1996), 199--218.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A99; Secondary 05A10 .

\noindent \emph{Keywords: } Laguerre configuration, Lah numbers, lattice
paths, $q$-binomial coefficient.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000262} and \seqnum{A089656}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 1 2005; 
revised version received October 18 2005.
Published in {\it Journal of Integer Sequences},
October 20 2005.

\bigskip
\hrule
\bigskip

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


\end{document}