\input lmacros
\documentstyle[12pt]{article}
\headheight 0in
\headsep 0in
\evensidemargin 1in
\oddsidemargin \evensidemargin
\textwidth 6.5in
\topmargin 1.25in
\textheight 8.7in
\begin{document}
\pagestyle{empty}

%%% MACROS
%
\setlength\unitlength{0.1em}
\savebox0{\rule[-2\unitlength]{0pt}{10\unitlength}%
\begin{picture}(10,10)(0,2)
\put(0,0){\line(0,1){10}}
\put(0,10){\line(1,0){10}}
\put(10,0){\line(0,1){10}}
\put(0,0){\line(1,0){10}}
\end{picture}}
\savebox1{\rule[-2\unitlength]{0pt}{10\unitlength}%
\begin{picture}(10,10)(0,2)
\put(0,10){\line(1,0){10}}
\put(10,0){\line(0,1){10}}
\put(0,10){\line(1,-1){10}}
\end{picture}}
\newcommand\sq{\;\usebox0\;}
\newcommand\ssq{\;\usebox1\;}
\newcommand\sssq{\;\makebox[0pt][l]{\usebox0}\usebox1\;}
\newcommand\mixarrow{\stackrel{\rm m}{\leftarrow}}
\newcommand\lrarrow{\stackrel{\rm l.r.}{\longleftarrow}}
\newcommand\worlarrow{\stackrel{\rm WS}{\longleftarrow}}
\newcommand\ev{\mbox{\rm ev}}
\newcommand\sh{\mbox{\rm sh}}
\newcommand\R{\mbox{\rm R}}
\newcommand\trunc{\mbox{\rm trunc}}
\newcommand\T{{\bf t}}
\newcommand\cir[1]{{\mbox{}^\bigcirc\! {#1}}}
\renewcommand\emptyset{\mbox{\sc \O}}
\newlength\cellsize \setlength\cellsize{18\unitlength}
\savebox2{%
\begin{picture}(18,18)
\put(0,0){\line(1,0){18}}
\put(0,0){\line(0,1){18}}
\put(18,0){\line(0,1){18}}
\put(0,18){\line(1,0){18}}
\end{picture}}
\newcommand\cellify[1]{\def\thearg{#1}\def\nothing{}%
\ifx\thearg\nothing
\vrule width0pt height\cellsize depth0pt\else
\hbox to 0pt{\usebox2\hss}\fi%
\vbox to 18\unitlength{
\vss
\hbox to 18\unitlength{\hss$#1$\hss}
\vss}}
\newcommand\tableau[1]{\vtop{\let\\=\cr
\setlength\baselineskip{-16000pt}
\setlength\lineskiplimit{16000pt}
\setlength\lineskip{0pt}
\halign{&\cellify{##}\cr#1\crcr}}}
\savebox3{%
\begin{picture}(15,15)
\put(0,0){\line(1,0){15}}
\put(0,0){\line(0,1){15}}
\put(15,0){\line(0,1){15}}
\put(0,15){\line(1,0){15}}
\end{picture}}
\newcommand\expath[1]{%
\hbox to 0pt{\usebox3\hss}%
\vbox to 15\unitlength{
\vss
\hbox to 15\unitlength{\hss$#1$\hss}
\vss}}
%
%%%


\begin{center}
{\bf Notes:  Partitions and their generating functions.}
\end{center}

\noindent 1.  Partitions of $n$: basic definitions.

\medskip

In these notes we are concerned with partitions of a number $n$,
as opposed to partitions of a set.
A partition of $n$ is a combination (unordered, with repetitions allowed)
of positive integers, called the {\it parts}, that add up to
$n$.

The usual practice is to write the parts of a partition in
descending order, and to use the notation $\lambda \vdash n$
to mean $\lambda $ is a partition of $n$.  Thus for example,
$$ (7,5,2,2)\vdash 16 $$
is a partition of 16 into 4 parts.

We use the following notation for the numbers of partitions:
$$ p_{k}(n) = \mbox{{\rm number of partitions of $n$ with $k$ parts}} $$
$$ p(n) = \mbox{{\rm total number of partitions of $n$}} $$
$$ q_{k}(n) = p_{1}(n)+\cdots +p_{k}(n) = \mbox{{\rm number of
partitions of $n$ with at most $k$ parts }} $$

For example, the partitions of $5$ are $(5)$, $(4, 1)$, $(3,2)$,
$(3,1,1)$, $(2,2,1)$, $(2,1,1,1)$, and $(1,1,1,1,1)$.  Thus $p(5) =
7$, $p_{1}(5) = 1$, $p_{2}(5) = 2$, $p_{3}(5) = 2$, $p_{4}(5) = 1$,
$p_{5}(5)$ = 1.

\bigskip

\noindent 2.  Ferrers diagram and conjugate partition.

\medskip

The {\it Ferrers diagram} of a partition $\lambda \vdash n$ is a rectangular
array of $n$ boxes, or cells, with one row of length $j$ for each part
$j$ of $\lambda $.

For example, the diagram of $(7,5,2,2)$ is
$$ \tableau{
{}&{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}\\
{}&{}\\
{}&{}}. $$

The {\it conjugate} of a partition $\lambda\vdash n $ is the partition
of $n$ whose diagram you get by reflecting the diagram of $\lambda $
about the diagonal so that rows become columns and columns become
rows.  We use the notation $\lambda '$ for the conjugate of $\lambda
$.  In our example above, with $\lambda  = (7,5,2,2)$, the diagram of
$\lambda '$ is
$$ \tableau{
{}&{}&{}&{}\\
{}&{}&{}&{}\\
{}&{}\\
{}&{}\\
{}&{}\\
{}\\
{}\\} $$
and so we see that $\lambda ' = (7,5,2,2)' = (4,4,2,2,2,1,1)$.

A couple of obvious but useful facts about $\lambda '$: (1) $(\lambda
')' = \lambda $, that is, the conjugate of the conjugate is the
original partition; (2) the number of parts of $\lambda $ equals the
largest part of $\lambda '$.  As a consequence, we see that
$p_{k}(n)$, the number of partitions of $n$ with $k$ parts, is also
the number of partitions of $n$ with largest part $k$.  Look again at
the list of partitions of $5$ in the previous section for an example.

The conjugate $\lambda '$ can be described mathematically without drawing
the Ferrers diagrams.  Write $\lambda $ as $(\lambda _{1},\lambda
_{2},\ldots,\lambda _{l})$.  Let the conjugate be $\lambda ' =
(\lambda _{1}',\lambda _{2}',\ldots,\lambda _{m}')$.  Notice that $l
= \lambda _{1}'$ and $m = \lambda _{1}$.  Now $\lambda _{i}'$ is the
length of column $i$ in the diagram of $\lambda $, and there is one
cell in this column for every row of length at least $i$.  Therefore
$\lambda _{i}'$ equals the number of parts $\geq i$ in $\lambda $,
or equivalently the largest $j$ such that $\lambda _{j}\geq i$.

For example, we compute
$$ (6,6,5,3,3,3,2,1,1)' = (9,7,6,3,3,2) $$
because $\lambda _{9}$ is the last $1$, $\lambda _{7}$ is the last $2$,
$\lambda _{6}$ is the last 3, $\lambda _{3}$ is the last part $\geq 4$
and also the last $5$, and $\lambda _{2}$ is the
 last $6$ in $\lambda $.

A partition $\lambda $ is called {\it self-conjugate} if $\lambda'  =
\lambda $.  This means its Ferrers diagram is symmetric, as in for
example $\lambda  = (5,5,3,2,2)$:
$$ \tableau{
{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}\\
{}&{}&{}\\
{}&{}\\
{}&{}\\}. $$

We define 
$$ k(n) = \mbox{{\rm number of self-conjugate partitions of $n$}}. $$
This number turns up fairly often in partition theory.  One
interesting fact about $k(n)$ is given by the following theorem:

\medskip

\noindent {\it Theorem:} $k(n)$ is also the number of partitions of
$n$ into {\it distinct, odd} parts.

\noindent {\it Proof:}  We'll give a bijection $\phi $ from $\{$self-conjugate
$\lambda \vdash n \}$ to $\{\lambda \vdash n$ with distinct odd parts$
\}$.

\medskip

Given a self-conjugate $\lambda $, define $\phi (\lambda )$ to be the
partition whose parts are the ``hooks'' in the diagram of $\lambda $,
as illustrated below:
$$  \tableau{
{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}\\
{}&{}&{}\\
{}&{}\\
{}&{}\\} = \tableau{
{}&{}&{}&{}&{}\\
{}\\
{}\\
{}\\
{}\\} + \tableau{
&&&&\\
&{}&{}&{}&{}\\
&{}&\\
&{}\\
&{}\\} + \tableau{
&&&&\\
&&&&\\
&&{}\\
&\\
&\\}, $$
so that $\phi ((5,5,3,2,2)) = (9,7,1)$

Each hook has odd size because it is symmetric about the middle, and each
hook is strictly larger than the next one, which nests inside it.
Therefore $\phi (\lambda )$ has distinct odd parts.  On the other
hand, given distinct odd numbers, we can form corresponding symmetric
hooks and nest them together into a diagram.  This operation clearly
defines $\phi ^{-1}$ and thus shows we have a bijection.

\bigskip

\noindent 3.  Generating functions for partitions.

\medskip

We begin with the generating function $P(x) = \sum p(n)x^{n}$ which
counts all partitions of all numbers $n$, with weight $x^{n}$ for a
partition of $n$.

To choose an arbitrary partition $\lambda $ of unrestricted $n$, we
can decide independently for each positive integer $i$ how many times
to include $i$ as a part of $\lambda $.

Each use of $i$ as a part contributes $i$ to the total size $n$, so
the generating function for one instance of $i$ is $x^{i}$.  By the
repetition principle, the generating function for the choice of any
number of repetitions of the part $i$ is $1/(1-x^{i}) = 1 + x^{i} +
x^{2i}+\cdots $.  Multiplying for all $i$ we get
$$ P(x) = \sum_{n} p(n)x^{n} = \prod _{i=1}^{\infty }\frac{1}{1-x^{i}}
= \frac{1}{(1-x)(1-x^{2})(1-x^{3})\cdots }. $$
This infinite product need not disturb us.  If we want a particular
coefficient $p(n)$ we need only multiply out those factors involving
$x$ to a power $n$ or less, and these are a finite number of terms.
Thus the infinite product makes sense since only a finite number of
the factors contribute to any given term.

Do this exercise to convince yourself this all makes sense:  multiply
out the product 
$$
\frac{1}{1-x}\frac{1}{1-x^{2}}\frac{1}{1-x^{3}}\frac{1}{1-x^{4}}\frac{1}{1-x^{5}}\cdots
,$$
keeping track only of terms up to degree $x^{5}$.  Then compare the
coefficients with the values of $p(0)$ through $p(5)$ which you
compute by actually listing all partitions of $n$ for $n = 0$ to $5$.

The strategy we used to write down $P(x)$ lends itself to endless
variations.  Here are some examples.

(1)  To count partitions whose parts are $\leq k$, use only the
factors for $i = 1,2,\ldots,k$ to get 
$$ Q_{k}(x) = \prod _{i=1}^{k}\frac{1}{1-x^{i}} =
\frac{1}{(1-x)(1-x^{2})\cdots (1-x^{k})}. $$
Taking the conjugate partition gives a bijection between partitions of
$n$ with parts $\leq k$ and partitions of $n$ with at most $k$ parts.
Therefore $Q_{k}(x)$ also counts partitions with at most $k$ parts,
which is to say, $Q_{k}(x)$ is the generating function for $q_{k}(n)$:
$$ Q_{k}(x) = \sum _{n}q_{k}(n)x^{n}. $$

(2)  To count partitions with largest part equal to $k$, we proceed as
in example (1) with the difference that the factor for $i = k$ must change.
Namely, we may use $k$ as a part $1$ or more times, but not zero
times.  Thus the generating function for this choice will be
$x^{k}/(1-x^{k}) = x^{k}+ x^{2k}+\cdots $ instead of $1/(1-x^{k}) =
1+x^{k}+x^{2k}+\cdots $.  As a result, the generating function for
partitions with largest part equal to $k$ is 
$$ P_{k}(x) = x^{k}Q_{k}(x) = \frac{x^{k}}{(1-x)(1-x^{2})\cdots (1-x^{k})}. $$
An in example (1) we can use conjugation to get a bijection between
partitions of $n$ with largest part equal to $k$ and partitions of $n$
with exactly $k$ parts.  Therefore $P_{k}(x)$ is also the generating
function for partitions with exactly $k$ parts:
$$ P_{k}(x) = \sum_{n} p_{k}(n)x^{n}. $$
Note that the relation $P_{k}(x) = x^{k}Q_{k}(x)$ is equivalent to
$p_{k}(n) = q_{k}(n-k)$, a fact which can also be proven directly.

(3) To count partitions with odd parts, we use only the factors for
odd values of $i$ to get the generating function
$$ O(x)  = \prod _{i\;\mbox{{\rm odd}}}\frac{1}{1-x^{i}} =
\frac{1}{(1-x)(1-x^{3})(1-x^{5})\cdots }.$$

(4)  To count partitions with distinct parts, we must choose for each
$i$ whether to use the part $i$ once, or not at all.  Thus the
repetition generating function $1/(1-x^{i})$ in $P(x)$ must be
replaced by $(1+x^{i})$, giving the generating function
$$ D(x) = \prod _{i=1}^{\infty }(1+x^{i}) =
(1+x)(1+x^{2})(1+x^{3})\cdots . $$

(5) To count partitions with distinct, odd parts, we combine the
methods of examples (3) and (4) to get the generating function
$$ K(x) = \prod _{i\;\mbox{{\rm odd}}} (1+x^{i}) =
(1+x)(1+x^{3})(1+x^{5})\cdots. $$
According to the theorem in the previous section, this is also the
generating function counting self-conjugate partitions:
$$ K(x) = \sum _{n} k(n)x^{n}. $$

(6) Another way to get a generating function for $p_{k}(n)$ is to use
a two-variable generating function for all partitions, in which we
count each partition $\lambda = (\lambda _{1},\lambda
_{2},\ldots,\lambda _{k})\vdash n$ with weight $y^{k}x^{n}$, where $n$
is the size and $k$ is the number of parts.  The generating function
for the contribution of a part $i$ now become $yx^{i}$ (one to the
part count, $i$ to the size) instead of just $x^{i}$ and accordingly
we get the generating function
$$ P(x,y) = \sum _{n,k}p_{k}(n) y^{k}x^{n} = \prod _{i=1}^{\infty
}\frac{1}{1-yx^{i}} = \frac{1}{(1-yx)(1-yx^{2})(1-yx^{3})\cdots }. $$
Setting $y=1$ gets us back to our original generating function $P(x)$.

\bigskip

\noindent 4.  Partition identities.

\medskip

In the last section we counted $p_{k}(n)$ in two essentially different
ways.  One was direct, using the 2-variable generating fucntion
$$ P(x,y) = \sum _{n,k}p_{k}(n) y^{k}x^{n} = \prod _{i=1}^{\infty
}\frac{1}{1-yx^{i}}. $$
The other was indirect, using conjugation to get
$$ P_{k}(x) = \sum _{n}p_{k}(n)x^{n} = \frac{x^{k}}{(1-x)\cdots (1-x^{k})}. $$
We can make this last equation into a 2-variable generating function
by summing with a factor $y^{k}$ for all $k$:
$$ P(x,y) = \sum _{n,k}p_{k}(n)y^{k}x^{n} = \sum _{k}P_{k}(x)y^{k} =
\sum _{k}\frac{x^{k}y^{k}}{(1-x)\cdots (1-x^{k})}. $$
As a result we arrive at a {\it partition identity}
$$ \prod _{i=1}^{\infty }\frac{1}{1-yx^{i}} = \sum _{k=0}^{\infty
}\frac{x^{k}y^{k}}{(1-x)\cdots (1-x^{k})} $$ 
expanding an infinite product as an infinite sum.  Though we derived
it combinatorially, this is a purely algebraic identity.  One theme in
modern combinatorics is to find combinatorial explanations for
algebraic identities like this, often ones which were discovered in
entirely different contexts.

Other identities can be found by analyzing Ferrers diagrams
combinatorially.
We'll do an example.  Define the Durfee square of $\lambda $ to be the
largest square array that fits in the upper left corner of $\lambda
$'s Ferrers diagram.  Here are examples, with the Durfee square marked
with $*$'s:
$$ \tableau{
*&a&a&a\\
l\\
l\\
}\quad 
\tableau{
*&*&a\\
*&*&a\\
l&l\\
l
}\quad 
\tableau{
*&*&*&a&a&a\\
*&*&*&a&a\\
*&*&*\\
l\\
l
}. $$
If the Durfee square is $c$ by $c$, we call $c$ the {\it Durfee
number} of $\lambda $.  The rest of the diagram of $\lambda $ consists
of two parts, which we call the {\it arm} (marked above with $a$'s)
and the {\it leg} (marked with $l$'s).  The arm and the leg are
diagrams themselves.  Obviously the arm can be any partition with at
most $c$ parts, and the leg any partition with parts at most $c$.

Suppose we wish to choose a partition (of unrestricted $n$) with
Durfee number $c$.  We can start with the Durfee square and choose the
arm and leg independently.  The Durfee square contributes $c^{2}$ to
the total size $n$.  The generating function for the choice of an arm
is $Q_{c}(x)$, and the generating function for the choice of a leg is
the same.  Multiplying, we find the generating function for partitions
with Durfee number $c$ to be
$$ x^{c^{2}}Q_{c}(x)^{2} =
\frac{x^{c^{2}}}{(1-x)^{2}(1-x^{2})^{2}\cdots (1-x^{c})^{2}}. $$
Summing for all values of $c$ gives $P(x)$ by the addition principle,
leading to the identity
$$ \prod _{i=1}^{\infty }\frac{1}{1-x^{i}} = \sum _{c =0}^{\infty
}\frac{x^{c^{2}}}{(1-x)^{2}(1-x^{2})^{2}\cdots (1-x^{c})^{2}}$$
$$ = 1 +
\frac{x}{(1-x)^{2}}+\frac{x^{4}}{(1-x)^{2}(1-x^{2})^{2}}
+\frac{x^{9}}{(1-x)^{2}(1-x^{2})^{2}(1-x^{3})^{2}}+\cdots . $$ 

The connection between partition combinatorics and algebraic
identities can also be applied in reverse, to get surprising
combinatorial facts.

As an example, consider the generating functions found in the last
section for partitions with distinct parts, 
$$ D(x) = (1+x)(1+x^{2})(1+x^{3})\cdots , $$
and for partitions with odd parts,
$$ O(x) = \frac{1}{(1-x)(1-x^{3})(1-x^{5})\cdots }. $$
Let's multiply $O(x)$ by 1, in the form 
$$ 1 = \frac{(1-x^{2})(1-x^{4})(1-x^{6})}
{(1-x^{2})(1-x^{4})(1-x^{6})}\cdots . $$
We get 
$$ O(x) =
\frac{(1-x^{2})(1-x^{4})(1-x^{6})\cdots }{(1-x)(1-x^{2})(1-x^{3})\cdots } $$
$$  = \left(\frac{1-x^{2}}{1-x} \right)\left(\frac{1-x^{4}}{1-x^{2}}
\right) \left(\frac{1-x^{6}}{1-x^{3}} \right)\cdots  $$
$$ = (1+x) (1+x^{2}) (1 +x^{3})\cdots  = D(x)$$
Amazingly, we find that $O(x) = D(x)$ by pure algebra, and thus we
have proved:

\medskip

\noindent {\it Theorem:}  For each $n$, the number of partitions of
$n$ into odd parts is equal to the number of partitions of $n$ into
distinct parts.

\medskip

Exercise (not very easy): find a bijective proof of the above theorem.

\bigskip

5. Euler's identity.

\medskip

The following wonderful partition identity was discovered by Euler:
$$ \prod _{i=1}^{\infty }(1-x^{i}) = 1+\sum _{k=1}^{\infty
}(-1)^{k}(x^{(3k^{2}-k)/2} + x^{(3k^{2}+k)/2}). $$
This looks a little forbidding but actually the right hand side is
very simple.  It describes a power series in which most terms are zero
and the others have coefficient $\pm 1$; they occur for those
exponents $x^{n}$ where $n$ is of the form $(3k^{2}\pm k)/2$.  Writing
out some terms should make this clearer: the identity reads
$$ (1-x)(1-x^{2})(1-x^{3})\cdots =
1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}- \cdots.  $$

We shall interpret Euler's identity combinatorially and prove it by
means of a bijection.  By the methods of section 3 we see that 
$$ D(x,y) = \prod _{i=1}^{\infty }(1+yx^{i}) $$
is the generating function for partitions into distinct parts, counted
with weight $y^{k}x^{n}$ for a partition $\lambda \vdash n$ with $k$
parts.

  From now on, let's use the notation $\lambda \models n$ to
mean that $\lambda $ is a partition of $n$ into distinct parts.

  Setting $y=-1$ in $D(x,y)$, each partition into distinct parts will count
with weight $x^{n}$ if it has an even number of parts and $-x^{n}$ if
it has an odd number of parts.  Thus the coefficient of $x^{n}$ in
$D(x,-1)$ is the difference $|\{\lambda \models n$, even \# of parts$
\}|-|\{\lambda \models n$, odd \# of parts$ \}|$.  Now $D(x,-1)$ is
just the left-hand side of Euler's identity, so to prove the identity
we must show that the difference $|\{\lambda \models n$, even \# of parts$
\}|-|\{\lambda \models n$, odd \# of parts$ \}|$ is also counted by
the right hand side.

In other words, we are to show that except when $n = (3k^{2}\pm k)/2$,
there are exactly as many $\lambda \models n$ with an even number of
parts as $\lambda \models n$ with an odd number of parts.  When $n =
(3k^{2}\pm k)/2$ we want there to be one extra partition $\lambda $
with an even number of parts if $k$ is even, and one extra with an odd
number of parts if $k$ is odd.  In fact we will 
arrange for the extra partition to have $k$ parts, which will
surely do.

The partitions we exclude are going to be the {\it wedge}-shaped partitions
$(2k-1,2k-2,\ldots,k)$ and $(2k,2k-1,\ldots,k+1)$, for every $k$.  For
$k = 4$ they look like this:
$$ \tableau{
{}&{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}\\
{}&{}&{}&{}\\
}\;,\quad \tableau{
{}&{}&{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}\\
}\;. $$
You should check for yourself that the first wedge is a partition of
$(3k^{2}-k)/2$ and the second is a partition of $(3k^{2}+k)/2$.  Also
check this fact:  the wedges are precisely those partitions $\lambda
\models n$ with the properties (i) all the parts are consecutive, and
(ii) the last part is either equal to or one more than the number of parts.

To prove the theorem we now construct a bijection 
$$ \{\mbox{{\rm non-wedge }}\lambda \models n,\;\mbox{{\rm even \# of
parts}} \} \leftrightarrow \{\mbox{{\rm non-wedge }}\lambda \models
n,\;\mbox{{\rm odd \# of parts}} \}. $$

We'll define the bijection by means of an operation $S$ on all
non-wedge partitions with
distinct parts.  It will change the number of parts by 1, so
$S(\lambda )$ will always have 1 more or less part than $\lambda $.
It will also be an involution, meaning $S(S(\lambda )) = \lambda $.
Thus $S$ applied to odd partitions will give even ones, $S$ applied to
even partitions will give odd ones, and these two applications of $S$
will be inverse to each other and therefore bijections.

To define $S$, we use two numbers describing the diagram of $\lambda
\models n$.  We define $i(\lambda )$ to be the smallest part of
$\lambda $.  This is the length of the last row in the diagram.  We
define $j(\lambda )$ to be the number of consecutive parts starting
with the largest part.  This is the length of the diagonal of cells
leading down and to the left from the last cell in the first row of
the diagram.

For example, if we take $\lambda  = (7,6,5,3,2)$ then $i(\lambda )=2$
and $j(\lambda ) = 3$ because the first 3 parts $7,6,5$ are
consecutive.  The diagram looks like this:
$$ \tableau{
{}&{}&{}&{}&{}&{}&{j}\\
{}&{}&{}&{}&{}&{j}\\
{}&{}&{}&{}&{j}\\
{}&{}&{}\\
{i}&{i}\\
} $$

The operation $S$ either transfers the ``$i$'' cells up to the ``$j$''
position or vice versa, depending which one makes sense.  There are
two cases:

Case 1.  $i\leq j$.  In this case, remove the last row of $\lambda $
and extend each of the first $i$ rows by one cell.  For example
$$ \tableau{
{}&{}&{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}\\
{*}&{*}&{*}\\
}\quad \rightarrow \quad \tableau{
{}&{}&{}&{}&{}&{}&{}&{}&{*}\\
{}&{}&{}&{}&{}&{}&{}&{*}\\
{}&{}&{}&{}&{}&{}&{*}\\
{}&{}&{}&{}\\
} $$
This makes sense provided the last row (to be removed) is not also
among the first $i$ rows (to be extended).  But that could only happen
if $j\leq i$, hence $j=i$, which would make $\lambda $ a wedge of the
first type, and we excluded those.  Notice that after applying $S$ in
case 1, $j$ for the new partition $S(\lambda )$ is $i$ for the old
partition $\lambda $.  Also $i$ for the new partition $S(\lambda )$ is
the length of the (possibly extended) next to last row of $\lambda $,
so is greater than $i(\lambda )$.

Case 2.  $i>j$.  In this case, remove 1 cell from each of the first
$j$ rows and add a new last row of length $j$.  For example,
$$ \tableau{
{}&{}&{}&{}&{}&{}&{}&{}&{*}\\
{}&{}&{}&{}&{}&{}&{}&{*}\\
{}&{}&{}&{}&{}&{}&{*}\\
{}&{}&{}&{}\\
}\quad \rightarrow \quad \tableau{
{}&{}&{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}&{}&{}\\
{}&{}&{}&{}\\
{*}&{*}&{*}\\
} $$
This makes sense provided the new row we are trying to add is smaller
than the old last row, so that we still get distinct parts.  But the
old last row has length $i$, or possibly $i-1$ if it was one of the
first $j$ rows.  By definition $i>j$ in case 2, so the only bad
possibility is that $i = j+1$ and the $j$ rows include the last row.
But that would mean our partition is a wedge of the second type, which
we excluded.  Notice that in case 2, $i$ for the new partition
$S(\lambda )$ is $j$ for the old one $\lambda $.  Also, after removing
1 from each of the first $j$ rows they are still consecutive, so $j$
for the partition $S(\lambda )$ is at least $j(\lambda )$.

Obviously, $S$ changes the number of parts by 1 in both cases, as we
said it would.  What remains to check is that $S$ is an involution.
But the remarks made in each case show that applying $S$ in case 1
give $S(\lambda )$ belonging to case 2 and vice versa.  Since the
operations in case 1 and case 2 undo each other, we conclude that
$S(S(\lambda )) = \lambda $ in either case.  This completes the proof
of Euler's identity.


\bigskip

6. MacMahon's recurrence.

Proving Euler's identity is worth the work because it is not only
beautiful but also useful.  MacMahon observed that it can be used to
get an efficient recurrence for the partition numbers $p(n)$.  The
left hand side of Euler's identity is $1/P(x)$, so we have the
generating function identity
$$ (1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}- \cdots)P(x) = 1. $$
Considering the coefficient of $x^{n}$ in this identity, we see that
$$ p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)-p(n-12)-p(n-15)+\cdots  = 0, $$
or
$$ p(n) = p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-\cdots. $$
This is of course not an infinite sum; for each $n$ it just continues
as long as the terms are $p(j)$ for $j\geq 0$.  The starting point is
$p(0) = 1.$

How many terms are actually in the recurrence for $p(n)$?  Since the
terms are $p(j)$ with $j = n-(3k^{2}\pm k)/2$, the last term
corresponds to the largest $k$ for which $(3k^{2}-k)/2\leq n$.  This
will be approximately $\sqrt{2n/3}$, so the recurrence involves only
about $2\sqrt{2n/3}$ terms.  Thus to compute $p(1000)$, say, we need
to use only 50 previous values.

On the next page is a computer program to compute $p(0)$ through
$p(49)$ using MacMahon's recurrence, together with its output.


\end{document}
