\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
\usepackage{pstricks,pstcol,multido}

%\input{psfig}

%
% Labelling theorems, lemmas, etc... 
%
\newtheorem{theorem}{Theorem}
\newtheorem{maintheorem}[theorem]{Main Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{mainlemma}[theorem]{Main Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}


%
% Margins
%
%\addtolength{\textwidth}{1.50in}
%\addtolength{\textheight}{1.00in}
%\addtolength{\evensidemargin}{-0.75in}
%\addtolength{\oddsidemargin}{-0.75in}
%\addtolength{\topmargin}{-.50in}


%
% New Commands
%
%q-binomial coefficient
\newcommand{\qbin}[2]{\left[{#1 \atop #2}\right]}
%a_n a_{n+1} \ cdots a_m
\newcommand{\abar}[3]{a_{#1}a_{#2}\cdots a_{#3}}
%(a)_V_{k,i}(x;q)
\newcommand{\aVki}[2]{{{}_{\mbox{\rm \tiny(}a\mbox{\rm \tiny)}}\hskip-2.0pt V_{#1}(#2;q)}}
%V_{k,i}(x;q)
\newcommand{\Vki}[2]{{V_{#1}(#2;q)}}
%lambda
\newcommand{\la}[1]{\lambda_{#1}}


%
% Numbering Sections, Equations, Theorems, etc...
%
\renewcommand{\theequation}{\thesection.\arabic{equation}}
\renewcommand{\thetheorem}{\thesection.\arabic{theorem}}
\makeatletter
\renewcommand{\section}{\@startsection
	{section}
	{1}
	{-0mm}
	{-\baselineskip}
	{0.1\baselineskip}
	{\setcounter{equation}{0}\setcounter{theorem}{0}\bf}}
\makeatother
\renewcommand{\thefootnote}{\fnsymbol{footnote}}


%
% Drawing Ferrers diagrams
%
\newcommand{\mybox}[1]{
    \moveto#1
    \rlineto(1,0)
    \rlineto(0,1)
    \rlineto(-1,0)
    \closepath
    \fill
}

%\mylabelledrow{color}{scale}{col}{row}{#cols}{celllabel}{startpoint}
\newcommand{\mylabelledrow}[7]{
    \psset{unit=.33cm}
    \pscustom[linewidth=.5pt,fillstyle=solid,fillcolor=#1]{
         \multido{\i=#3+1}{#5}{\mybox{(\i,#4)}}
    }
    \psset{unit=1cm}
    \multirput[Bl]#7(#2,0){#5}{\sffamily \bfseries \scriptsize #6}
    \psset{unit=.33cm}
}
%\myrow{color}{col}{row}{#cols}
\newcommand{\myrow}[4]{
    \pscustom[linewidth=.5pt,fillstyle=solid,fillcolor=#1]{
         \multido{\i=#2+1}{#4}{\mybox{(\i,#3)}}
    }
}




%
% Document
%
\begin{document}
\vspace{20pt}
\begin{center}
\large
\textbf{AN EXTENSION OF FRANKLIN'S BIJECTION}
\\
\normalsize
\vspace{12pt}
\textsc{BY DAVID P. LITTLE}
\footnote{Research carried out under NSF grant support}\\
University of California, San Diego\\
\today
\end{center}

\vspace{20pt}

\begin{abstract}
We are dealing here with the power series expansion of the product 
$F_m(q)=\prod_{n> m} (1-q^n)$. This expansion may be readily obtained from an
identity of Sylvester and the latter, in turn, may be given a relatively
simple combinatorial proof. Nevertheless, the problem remains to give a
combinatorial explanation for the massive cancellations which produce the
final result. The case $m=0$ is clearly  explained by Franklin's proof of the
Euler Pentagonal Number Theorem. Efforts to extend the same mechanism of proof
to the general case $m>0$ have led to the discovery of an extension
of the Franklin involution which explains all the components of
the final expansion.
\end{abstract}

\vspace{12pt}

\section{Introduction}


Sylvester \cite[p. 281]{Syl82} used Durfee squares to prove the following result.

\begin{theorem}
\begin{equation}
\label{SYLVESTER}
\prod_{n\geq1}(1+zq^n)=1+\sum_{n\geq1} z^n q^{\frac{3n^2-n}{2}}(1+zq^{2n})(-zq)_{n-1}/(q)_n
\end{equation}
\end{theorem}
where $(z)_n=(1-z)(1-zq)\cdots (1-zq^{n-1}).$  Multiplying the above equation 
by $1+z$ and then setting $z=-q^{m+1}$ for any $m \geq 0$ yields

\begin{equation}
\label{GENERALFORMULA}
\prod_{n>m}(1-q^n)=\sum_{n\geq0}(-1)^n \qbin{n+m}{m} q^{\frac{3n^2+n}{2}+nm}(1-q^{2n+m+1})
\end{equation}
where
\begin{equation}
\label{GAUSSIAN}
\qbin{n+m}{m}=\frac{(q)_{n+m}}{(q)_n(q)_m}
\end{equation}
is the usual $q$-analog of the binomial coefficients.  When $m=0$,
formula (\ref{GENERALFORMULA}) is none other than Euler's Pentagonal Number
Theorem,  

\begin{eqnarray}
\label{PENTAGONAL}
\prod_{n>0}(1-q^n)&=&\sum_{n\geq0}(-1)^nq^{\frac{3n^2+n}{2}}(1-q^{2n+1}).
\end{eqnarray}
Of course, in the process of setting $z=-q^{m+1}$, we invite a tremendous 
amount of cancelation to occur, none of which is explained by Sylvester's
proof of (\ref{SYLVESTER}), which has been included in the following section
for the sake of completeness.  However, Franklin's proof of (\ref{PENTAGONAL})
does exactly that, and in fact, offers an explanation for {\em every} single
cancelation which occurs.  It would be of historical interest to extend
Franklin's ideas to explain as many of the cancelations as possible in
(\ref{GENERALFORMULA}) for any $m\geq 1$.  This will be the focus of the
remainder of the paper.

\section{Sylvester's Proof of Theorem \ref{SYLVESTER}}

The left-hand side of (\ref{SYLVESTER}) can be thought of as the generating 
function for partitions $\la{}$, with $k$ distinct parts $>0$ weighted by
$z^kq^{|\la{}|}$, where $|\la{}|=\la{1}+\la{2}+\cdots +\la{k}$.  To prove
Sylvester's identity, we need to show that the right-hand side of (\ref{SYLVESTER})
enumerates the exact same objects.

We begin by noting that the Durfee square associated with $\la{}$, $\mathcal{D}(\la{})$, is the largest square contained in the Ferrers diagram \cite[p. 7]{And76} of $\la{}$.  The dimension, $d(\la{})$, of this square can be defined as the maximum $i$ such that $\la{i} \geq i$.  Using the Durfee square to classify these partitions, we see that $\la{}$ can fall into one of two distinct categories.  The first category is comprised of partitions $\la{}$ such that $\la{n+1}<n$, where for convenience we have set $n=d(\la{})$.  A typical partition in this category might look like the diagram below.


\begin{center}
\begin{pspicture}(0,0)(4,2)
\psset{unit=.33cm}
\pscustom[linewidth=.5pt,fillstyle=solid,fillcolor=white]{
    \pspolygon(0,0) (12,0) (12,1) (9,1) (9,2) (6,2) (6,3) (5,3) (5,4) (3,4) (3,5) (1,5) (1,6) (0,6)
    \pspolygon(0,0) (4,0) (4,4) (0,4)
}
\rput(2,2){$\mathcal{D}(\la{})$}
\end{pspicture}
\end{center}

%$$\psfig{figure=images/fig2.ps}$$

Directly above $\mathcal{D}(\la{})$ can be any partition with distinct parts $<n$. 
These partitions are generated by $(-zq)_{n-1}$.  Directly to the right of
$\mathcal{D}(\la{})$ can be any partition with exactly $n$ distinct parts $\geq0$. 
The generating function for these partitions is $z^nq^{n \choose 2}/(q)_n$.  Putting
this all together, any partition falling into this category can be accounted for in
the following term

\begin{equation}
\label{TYPE1}
z^nq^{n^2+{n \choose 2}}(-zq)_{n-1}/(q)_n.
\end{equation}


The second category is comprised of partitions $\la{}$ such that $\la{n+1}=n$.  
Note that this is the only other possibility since $\la{n+1}$ cannot be $\geq
n+1$ by the definition of $d(\la{})$.  In this case, $\la{}$ must be of the
following form.


\begin{center}
\begin{pspicture}(0,0)(4.5,2.7)
\psset{unit=.33cm}
\pscustom[linewidth=.5pt,fillstyle=solid,fillcolor=white]{
    \pspolygon(0,0) (13,0) (13,1) (10,1) (10,2) (7,2) (7,3) (6,3) (6,4) (4,4) (4,5) (3,5) (3,6) (1,6) (1,7) (0,7)
    \pspolygon(0,0) (5,0) (5,4) (0,4)
    \pspolygon(0,0) (4,0) (4,5) (0,5)
}
\psset{unit=1cm}
\rput(.7,.7){$\mathcal{D}(\la{})$}
\rput(-.1,1.5){1}
\rput(1.5,-.2){1}
\end{pspicture}
\end{center}

%$$\psfig{figure=images/fig3.ps}$$

Directly above $\mathcal{D}(\la{})$ can be any partition with distinct parts $\leq n$
and largest part equal to $n$.  Directly to the right of $\mathcal{D}(\la{})$ can be any
partition with exactly $n$ distinct parts $>0$.  The following term accounts for 
any partition falling into this category.  

\begin{equation}
\label{TYPE2}
z^{n+1}q^{n^2+{n \choose 2}+2n}(-zq)_{n-1}/(q)_n.
\end{equation}

Combining (\ref{TYPE1}) and (\ref{TYPE2}), we get the summand in the 
right-hand side of (\ref{SYLVESTER}), and summing over all values of $n\geq1$
completes the proof.

\section{Extending Franklin's Bijection}
Franklin's proof \cite[p. 10]{And76} of Euler's Pentagonal Number Theorem begins by
defining two sets of cells contained in the Ferrers diagram associated with a fixed
partition.  For our purposes we will need to extend these definitions as well as
further classify the cells involved.

Fix $m\geq0$ and $\la{}$, a partition with $n$ distinct parts $>m$.  Define a 
{\em stair} to be a cell in the Ferrers diagram associated with $\la{}$ at the end of
a row or the top of one of the $\la{n}-m-1$ left-most columns.  Of the remaining
cells, define a {\em landing} to be any cell that does not have another cell above
it.  The {\em m-landing staircase} is the sequence of neighboring stairs and
landings, starting with the stair at the end of the first row, with exactly $m$
landings, using as many stairs occuring at the end of a row as possible.  Let
$\mathcal{S}_m(\la{})$ refer to the cells in the {\em m}-landing staircase, with
$s_m(\la{})$ defined to be $|\mathcal{S}_m(\la{})|$, and let $\mathcal{T}(\la{})$
refer to the cells in the top row of $\la{}$, with $t(\la{})$ defined to be
$|\mathcal{T}(\la{})|=\la{n}$.  Lastly, we define the weight of $\la{}$, $w(\la{})$,
to be $(-1)^nq^{|\la{}|}$.  

For example, let $m=3$ and $\la{}=(14,11,9,8,6)$, then the Ferrers diagram would be 
labelled as in the figure below, with stairs and landings denoted by S's and L's,
respectively and cells belonging to $\mathcal{S}_3(\la{})$ shaded.


\begin{center}
\begin{pspicture}(0,0)(5,1.7)
%Label row 1
    \mylabelledrow{yellow}{.33}{0}{0}{15}{S}{(.08,.06)}
    \mylabelledrow{yellow}{.33}{0}{0}{13}{L}{(.08,.06)}
    \mylabelledrow{white}{.33}{0}{0}{11}{ }{(0,0)}
%Label row 2
    \mylabelledrow{yellow}{.33}{0}{1}{11}{S}{(.08,.39)}
    \mylabelledrow{yellow}{.33}{0}{1}{10}{L}{(.08,.39)}
    \mylabelledrow{white}{.33}{0}{1}{9}{ }{(0,0)}
%Label row 3
    \mylabelledrow{yellow}{.33}{0}{2}{9}{S}{(.08,.72)}
    \mylabelledrow{white}{.33}{0}{2}{8}{ }{(0,0)}
%Label row 4
    \mylabelledrow{yellow}{.33}{0}{3}{8}{S}{(.08,1.05)}
    \mylabelledrow{white}{.33}{0}{3}{7}{L}{(.08,1.05)}
    \mylabelledrow{white}{.33}{0}{3}{6}{ }{(0,0)}
%Label row 5
    \mylabelledrow{white}{.33}{0}{4}{6}{S}{(.08,1.38)}
    \mylabelledrow{white}{.33}{0}{4}{5}{L}{(.08,1.38)}
    \mylabelledrow{white}{.33}{0}{4}{2}{S}{(.08,1.38)}

\end{pspicture}
\end{center}

%$$\psfig{figure=images/stairland.ps}$$

By definition, an {\em m}-landing staircase must have exactly $m$ landings and can
have anywhere from $1$ to $n$ stairs.  Since it will be an extremely useful fact for
proving \ref{GENERALFORMULA}, we shall restate this in the following form

\begin{lemma}
\label{s_mLEMMA}
Let $\la{}$ be a partition with $n$ distinct parts $>m$.  Then the
following inequalities must hold.
\begin{equation}
m+1 \leq s_m(\la{}) \leq m+n
\end{equation}
\end{lemma}


Armed with these definitions and the above lemma, we are now in a position 
to prove the following


\begin{lemma}
\label{LEMMAM=1}
\begin{equation}
\prod_{n>1}(1-q^n)=\sum_{n\geq0}(-1)^nq^{\frac{3n^2+n}{2}}(1+q+q^2+\cdots+q^{2n}).
\end{equation}
\end{lemma}

Although its validity can be readily checked by dividing both sides of 
(\ref{PENTAGONAL}) by $(1-q)$, it will prove more insightful to obtain
(\ref{LEMMAM=1}) through a combinatorial means which can be easily extended to
prove (\ref{GENERALFORMULA}).

\vspace{12pt}
\noindent \textbf{Proof of Lemma \ref{LEMMAM=1}} \newline
Notice that the left-hand side of (\ref{LEMMAM=1}) can be written in the form 
\begin{equation}
\label{EXPANDLHS}
\sum_{n\geq 0}\sum_{\la{}=(\la{1}>\cdots >\la{n})}w(\la{})
\end{equation}
We will proceed by defining a bijection, $I$, that pairs off a partition, 
$\la{}$, with  $I(\la{})$, in such a way that $w(I(\la{}))=-w(\la{})$ whenever
$\la{} \ne I(\la{})$.  This will allow us to reduce the inner summation of
(\ref{EXPANDLHS}) to a finite sum that accounts only for the fixed points of
$I$.  The idea is to use 1-landing staircases in a manner similar to the way
Franklin used staircases (i.e. 0-landing staircases) to prove
(\ref{PENTAGONAL}) .  The basic principle of the involution is this,
 
\begin{enumerate}
  \item If $t(\la{})\leq s_1(\la{})$, move $\mathcal{T}(\la{})$, if possible, to the outside of $\mathcal{S}_1(\la{})$ so that $s_1(I(\la{}))=t(\la{})$ and
  \item If $t(\la{})> s_1(\la{})$, move $\mathcal{S}_1(\la{})$, if possible, to the empty row above $\mathcal{T}(\la{})$.
\end{enumerate}
The best way to see what is meant by ``if possible", is to break up the
definition of $I$ into two cases.  Case 1 is when $s_1(\la{})<1+n$, which
means that $\mathcal{S}_1(\la{})$ {\em cannot} reach the top row of $\la{}$, and thus
it will always be possible to move either $\mathcal{T}(\la{})$ or
$\mathcal{S}_1(\la{})$.  In the event that $t(\la{})\leq s_1(\la{})$, move the landing
in $\mathcal{T}(\la{})$ so that it is directly above the landing in the first
$t(\la{})-2$ rows.  If there is no landing in these rows, then place the landing at
the end of the first row.  Now move the stairs in $\mathcal{T}(\la{})$ by placing one
at the end of the first $t(\la{})-1$ rows.  Moving $\mathcal{T}(\la{})$ in this
manner will guarantee that $s_1(I(\la{}))=t(\la{})$, as required.  This procedure is
illustrated in the following example.

\begin{center}
\begin{equation}
\label{CASE11}
\begin{pspicture}(0,0)(11,1)
\psset{unit=.3cm}
    \myrow{white}{0}{0}{10}
    \myrow{white}{0}{1}{8}
    \myrow{white}{0}{2}{7}
    \myrow{white}{0}{3}{5}
    \myrow{yellow}{0}{4}{4}
\psline{->}(10.33,3)(12,3)
    \myrow{white}{13}{0}{10}
    \myrow{yellow}{13}{1}{9}
    \myrow{white}{13}{1}{8}
    \myrow{white}{13}{2}{7}
    \myrow{white}{13}{3}{5}
    \myrow{yellow}{13}{4}{2}
    \myrow{yellow}{16}{4}{1}
\psline{->}(23.33,3)(25,3)
    \myrow{yellow}{26}{0}{11}
    \myrow{white}{26}{0}{10}
    \myrow{yellow}{26}{1}{10}
    \myrow{white}{26}{1}{8}
    \myrow{yellow}{26}{2}{8}
    \myrow{white}{26}{2}{7}
    \myrow{white}{26}{3}{5}
\end{pspicture}
\end{equation}
\end{center}
%\psfig{figure=images/case11.ps}
In the event that $t(\la{})> s_1(\la{})$, move $\mathcal{S}_1(\la{})$ to the top 
row, as in the diagram below.

\begin{center}
\begin{equation}
\label{CASE12}
\begin{pspicture}(0,0)(8.66,1.2)
\psset{unit=.33cm}
    \myrow{yellow}{0}{0}{11}
    \myrow{white}{0}{0}{10}
    \myrow{yellow}{0}{1}{10}
    \myrow{white}{0}{1}{8}
    \myrow{yellow}{0}{2}{8}
    \myrow{white}{0}{2}{7}
    \myrow{white}{0}{3}{5}
\psline{->}(12,3)(14.4,3)
    \myrow{white}{16}{0}{10}
    \myrow{white}{16}{1}{8}
    \myrow{white}{16}{2}{7}
    \myrow{white}{16}{3}{5}
    \myrow{yellow}{16}{4}{4}
\end{pspicture}
\end{equation}
\end{center}
%\psfig{figure=images/case12.ps}
Notice that this operation will not result in a partition with a part $<2$, 
since $t(I(\la{}))=s_1(\la{})\geq2$, by Lemma \ref{s_mLEMMA}.

Case 2 of the involution is when $s_1(\la{})=1+n$.  In this case, 
$\mathcal{S}_1(\la{})$ {\em must} reach the top row of $\la{}$, and thus it might not
be possible to move either $\mathcal{T}(\la{})$ or $\mathcal{S}_1(\la{})$.  In other
words, $\mathcal{S}_1(\la{})$ shares at least one cell with $\mathcal{T}(\la{})$ and
possibly two, if the landing in $\mathcal{S}_1(\la{})$ occurs in the last row of
$\la{}$.  For this reason, we'll denote the row of $\la{}$ in which the landing
occurs by  $r(\la{})$.  For Case 2a, we will assume that $r(\la{})<n$.  If $t(\la{})
\leq s_1(\la{})-1$, move $\mathcal{T}(\la{})$ in a similar manner to (\ref{CASE11})

\begin{center}
\begin{equation}
\label{CASE21}
\begin{pspicture}(0,0)(8.33,1.2)
\psset{unit=.33cm}
    \myrow{white}{0}{0}{9}
    \myrow{white}{0}{1}{8}
    \myrow{white}{0}{2}{7}
    \myrow{white}{0}{3}{5}
    \myrow{yellow}{0}{4}{4}
\psline{->}(10,3)(12.4,3)
    \myrow{yellow}{14}{0}{11}
    \myrow{white}{14}{0}{9}
    \myrow{yellow}{14}{1}{9}
    \myrow{white}{14}{1}{8}
    \myrow{yellow}{14}{2}{8}
    \myrow{white}{14}{2}{7}
    \myrow{white}{14}{3}{5}
\end{pspicture}
\end{equation}
\end{center}
%\psfig{figure=images/case21.ps}
and if $t(\la{})-1>s_1(\la{})$, move $\mathcal{S}_1(\la{})$ in a similar manner 
to (\ref{CASE12}).

\begin{center}
\begin{equation}
\label{CASE22}
\begin{pspicture}(0,0)(8.66,1.2)
\psset{unit=.33cm}
    \myrow{yellow}{0}{0}{11}
    \myrow{white}{0}{0}{10}
    \myrow{yellow}{0}{1}{10}
    \myrow{white}{0}{1}{9}
    \myrow{yellow}{0}{2}{9}
    \myrow{white}{0}{2}{7}
    \myrow{yellow}{0}{3}{7}
    \myrow{white}{0}{3}{6}
\psline{->}(12,3)(14.4,3)
    \myrow{white}{16}{0}{10}
    \myrow{white}{16}{1}{9}
    \myrow{white}{16}{2}{7}
    \myrow{white}{16}{3}{6}
    \myrow{yellow}{16}{4}{5}
\end{pspicture}
\end{equation}
\end{center}
%\psfig{figure=images/case22.ps}
For Case 2b, we will assume that $r(\la{})=n$.  If $t(\la{}) \leq s_1(\la{})-1$, 
then the involution is performed just as in (\ref{CASE11}) and (\ref{CASE21}).


\begin{center}
\begin{pspicture}(0,0)(8.33,1.6)
\psset{unit=.33cm}
    \myrow{white}{0}{0}{9}
    \myrow{white}{0}{1}{8}
    \myrow{white}{0}{2}{7}
    \myrow{white}{0}{3}{6}
    \myrow{yellow}{0}{4}{5}
\psline{->}(10,3)(12.4,3)
    \myrow{yellow}{14}{0}{11}
    \myrow{white}{14}{0}{9}
    \myrow{yellow}{14}{1}{9}
    \myrow{white}{14}{1}{8}
    \myrow{yellow}{14}{2}{8}
    \myrow{white}{14}{2}{7}
    \myrow{yellow}{14}{3}{7}
    \myrow{white}{14}{3}{6}
\end{pspicture}
\end{center}

%\psfig{figure=images/case23.ps}
Notice that the above example was previously a fixed point of Franklin's involution. 
 And finally, if $t(\la{})-2>s_1(\la{})$, then the involution is similar to
(\ref{CASE12}) and (\ref{CASE22}).

\begin{center}
\begin{pspicture}(0,0)(8.66,1.6)
\psset{unit=.33cm}
    \myrow{yellow}{0}{0}{11}
    \myrow{white}{0}{0}{10}
    \myrow{yellow}{0}{1}{10}
    \myrow{white}{0}{1}{9}
    \myrow{yellow}{0}{2}{9}
    \myrow{white}{0}{2}{8}
    \myrow{yellow}{0}{3}{8}
    \myrow{white}{0}{3}{6}
\psline{->}(12,3)(14.4,3)
    \myrow{white}{16}{0}{10}
    \myrow{white}{16}{1}{9}
    \myrow{white}{16}{2}{8}
    \myrow{white}{16}{3}{6}
    \myrow{yellow}{16}{4}{5}
\end{pspicture}
\end{center}
%\psfig{figure=images/case24.ps}

In the event that $\la{}$ does not fit into one of the above categories, 
simply define $I(\la{})=\la{}$.  For example, moving $\mathcal{T}(\la{})$
could shorten $\mathcal{S}_1(\la{})$ to the point that $\mathcal{T}(\la{})$ is
too big to move, as in (\ref{FIXED}a).  Similarly, moving
$\mathcal{S}_1(\la{})$ could shorten $\mathcal{T}(\la{})$ to the point where
$\mathcal{S}_1(\la{})$ is also too big, as in (\ref{FIXED}b).

\begin{center}
\begin{equation}
\label{FIXED}
\begin{pspicture}(0,0)(8,1)
\psset{unit=.33cm}
\rput(-1,2){a)}
    \myrow{white}{0}{0}{9}
    \myrow{white}{0}{1}{7}
    \myrow{white}{0}{2}{6}
    \myrow{yellow}{0}{3}{5}
\rput(12.6,2){b)}
    \myrow{yellow}{14}{0}{10}
    \myrow{white}{14}{0}{9}
    \myrow{yellow}{14}{1}{9}
    \myrow{white}{14}{1}{7}
    \myrow{yellow}{14}{2}{7}
    \myrow{white}{14}{2}{6}
    \myrow{yellow}{14}{3}{6}
    \myrow{white}{14}{3}{5}
\end{pspicture}
\end{equation}
\end{center}

%\psfig{figure=images/fixed.ps}

\noindent The following table summarizes the fixed points of $I$.

\begin{center}
\begin{tabular}{|c|c|c|l|}
\hline
$s_1(\la{})$ & $t(\la{})$ & $r(\la{})$ & $|\la{}|$ \\
\hline
$n+1$ & $n+1$ & $\{1,2,\dots,n-1\}$ & $n^2 + {n+1\choose 2} + r(\la{})$ \\
$n+1$ & $n+2$ & $\{1,2,\dots,n-1\}$ & $n^2 + {n+1\choose 2} + n + r(\la{})$ \\
$n+1$ & $n+1$ & $n$ & $n^2 + {n+1\choose 2}$ \\
$n+1$ & $n+2$ & $n$ & $n^2 + {n+1\choose 2} + n$ \\
$n+1$ & $n+3$ & $n$ & $n^2 + {n+1\choose 2} + 2n$ \\
\hline
\end{tabular}
\end{center}

\noindent We can now replace the inner summation in (\ref{EXPANDLHS}) with 
$$
\sum_{\la{}=I(\la{})} w(\la{})
=(-1)^n q^{\frac{3n^2+n}{2}}(1+q+q^2+\cdots+q^{2n})
$$
which completes our proof.

\vspace{20pt}
We are now in possession of a mechanism that can be easily generalized to prove formula (\ref{GENERALFORMULA}).  However, we must first formalize the definition of our involution for a fixed $m\geq 1$.   Having done that, a simple observation regarding $m$-landing staircases will provide the key to determining a necessary and sufficient characteristic of fixed points.
\vspace{20pt}

\noindent \textbf{Proof of Theorem \ref{GENERALFORMULA}} \newline
Let $\la{}$ be a partition with $n$ distinct parts $>m$.  Let $\tau(\la{})$ be the result of moving $\mathcal{T}(\la{})$ to the outside of $\mathcal{S}_m(\la{})$.  This is accomplished by placing a landing from $\mathcal{T}(\la{})$ on top of each landing in the $t(\la{})-m-1$ bottommost rows of $\mathcal{S}_m(\la{})$.  Any landings still remaining in $\mathcal{T}(\la{})$ should be placed at the end of the first row.  Next, place the stairs from $\mathcal{T}(\la{})$ at the ends of the $t(\la{})-m$ bottommost rows.  This process will insure that $s_m(\tau(\la{}))=t(\la{})$, which is necessary in order to reverse the process.  Let $\sigma(\la{})$ be the result of moving $\mathcal{S}_m(\la{})$ to the empty row above $\mathcal{T}(\la{})$.  Notice that we cannot apply $\tau$ and $\sigma$ to just any partition $\la{}$ with parts $>m$, so to make up for this, we define $I$ as follows.

$$
I(\la{})=
\left\{
\begin{array}{cl}
  \tau(\la{})& \mbox{\rm if $t(\la{})\leq s_m(\la{})$ \quad \& \quad
$t(\la{})<m+n$,}\\
  \sigma(\la{})& \mbox{\rm if $t(\la{})-|\mathcal{T}(\la{}) \cap
\mathcal{S}_m(\la{})|>s_m(\la{})$,}\\
  \la{}& \mbox{\rm otherwise.}
\end{array}
\right.
$$
$I$ is an involution since $\tau$ and $\sigma$ are inverses of each other and if
$\mu=\tau(\la{})$, then

$$
t(\mu)-|\mathcal{T}(\mu) \cap \mathcal{S}_m(\mu)| = \la{n-1}
> \la{n} = t(\la{}) = s_m(\mu)
$$
and if $\mu=\sigma(\la{})$, then

$$
t(\mu)=s_m(\la{})\leq s_m(\mu) \quad \& \quad t(\mu)=s_m(\la{})\leq m+n.
$$

Notice that if $\la{}$ is a fixed point, then $t(\la{})\geq m+n$ and $s_m(\la{})=m+n$.
This means that the partition $\la{}^*=(2n-1+m,2n-2+m,\ldots ,n+m)$ is the smallest
fixed point of $I$ with exactly $n$ parts.  The weight of $\la{}^*$ is given by

\begin{equation}
w(\la{}^*)=(-1)^nq^{|\la{}^*|}=(-1)^nq^{\frac{3n^2-n}{2}+nm}.
\end{equation}
Unfortunately, it is not enough for $t(\la{})\geq m+n$ and $s_m(\la{})=m+n$.  In
order to come up with a necessary and sufficient condition for $\la{}$ to be a fixed
point, we need the following observation. 

\begin{center}
 If $s_m(\la{})=m+n$ then $\mathcal{S}_m(\la{})$ will start and finish at\\
opposite corners of an $n\times m+n$ rectangle.
\end{center}
Of course this is none other than a simple fact regarding taxicab distances, but
using this observation, we can prove the following crucial lemma.

\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{\rm \theenumi)}
\begin{lemma}
Let $\la{}=(\mu_1+2n-1+m,\mu_2+2n-2+m,\ldots ,\mu_n+n+m)$ where 
$\mu_1\geq \mu_2 \geq \cdots \geq \mu_n \geq 0$.  Then
$\la{}$ is a fixed point if and only if 
$$
\mu_1\leq m  \qquad \mbox{\rm or} \qquad \mu_1=m+1 \;\; \& \;\; \mu_n\geq 1.
$$

\end{lemma}


\noindent \textbf{Proof} \newline
Let us start by assuming that $\la{}$ is a fixed point.  In particular, this means
that $s_m(\la{})=m+n$ and that $\mathcal{S}_m(\la{})$ cannot be moved, or
symbolically,

\begin{equation}
\label{CANTMOVESM}
t(\la{})-|\mathcal{T}(\la{}) \cap \mathcal{S}_m(\la{})| \leq m+n.
\end{equation}
Notice that the observation we made above allows us to compute the left-hand side of
(\ref{CANTMOVESM}) exactly.

\begin{equation}
\label{TMINUSS}
t(\la{})-|\mathcal{T}(\la{}) \cap \mathcal{S}_m(\la{})| = \mu_1+n-1
\end{equation}
Therefore, $\mu_1 \leq m+1$.  If $\mu_1 \leq m$, then we are done.  If $\mu_1
= m+1$, then using the observation again, the left-most cell of
$\mathcal{S}_m(\la{})$ ocurrs in the top row of $\mu$, and thus we must
also have that $\mu_n \geq 1$.  

Now we need to show that this condition is sufficient.  If $\mu_1 \leq m$,
then one of the stairs in $\mathcal{S}_m(\la{}^*)$ will be used as a landing
in $\mathcal{S}_m(\la{})$.  This insures that $s_m(\la{})=m+n$.  It also
allows us to use equation (\ref{TMINUSS}) again to see that

$$
t(\la{})-|\mathcal{T}(\la{}) \cap \mathcal{S}_m(\la{})| = \mu_1+n-1
\leq m+n-1,
$$
which means that $I(\la{})=\la{}$.  

In the event that $\mu_1 = m+1$ and $\mu_n \geq 1$, one of the cells in
the first column of $\mu$ will be used as a landing, insuring that
$s_m(\la{})=m+n$.  Again we see that  

$$
t(\la{})-|\mathcal{T}(\la{}) \cap \mathcal{S}_m(\la{})| = \mu_1+n-1 = m+n,
$$
which means that $I(\la{})=\la{}$ in this case as well.

\vspace{20pt}

Using this lemma, we see that any partition $\mu$ that fits in an $n \times
m$ box will lead to a fixed point, as will any partition $\tilde{\mu}$ that
fits in an $n \times m+1$ box with $\tilde{\mu}_1=m+1$ and $\tilde{\mu}_n\geq
1$. Therefore, the weights of all fixed points with exactly $n$ parts are accounted
for in

\begin{equation}
\label{ALLFIXED}
w(\la{}^*)\left(\qbin{n+m}{m}+q^{n+m}\qbin{n+m-1}{m}\right).
\end{equation}
Summing (\ref{ALLFIXED}) over all values of $n\geq 0$, we see that

\begin{equation}
\label{FINAL}
\prod_{n>m}(1-q^n)=\sum_{n\geq0}(-1)^n 
q^{\frac{3n^2-n}{2}+nm}\qbin{n+m-1}{m-1}\frac{1-q^{2n+m}}{1-q^m}.
\end{equation}
Multiplying both sides of equation (\ref{FINAL}) by $(1-q^m)$ and making a change of
variable
$m\rightarrow m+1$ yields (\ref{GENERALFORMULA}).
\vspace{20pt}

One property of Franklin's bijection is that it accounts for all of the cancelation
occurring in the left-hand side of equation (\ref{GENERALFORMULA}). 
Unfortunately, this is not always the case for $I$.  In fact, as soon as $m=3$ there
is some unexplained cancelation.  For example, the two partitions $(14,13,12,11)$ and
$(12,11,10,9,8)$ are both partitions of 50 and both are fixed points of $I$.  On the
other hand, there are 31,571,191 partitions of 250 with parts $>10$.  Of those
31,571,191 partitions, 3,537 are fixed points of $I$.  Of those 3,537 fixed points,
just 47 have a positive sign associated with them, and can therefore be cancelled out.


\begin{thebibliography}{99}

\bibitem{And76} G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Vol. 2, G.-C. Rota ed., Addison-Wesley, Reading, 1976

\bibitem{Syl82} J. J. Sylvester, {\em A Constructive theory of Partitions, arranged in three Acts, an Interact and an Exodion}, American Journal of Mathematics, Vol. 5 (1882), pp. 251-330.

\end{thebibliography}

\end{document}





