Integer Partitions
                            ------------------

By an _integer partition_ of a natural number  n  we mean a nonincreasing
finite sequence  (a_1, ...  , a_m)  of natural numbers such that

                           n = a_1 + ... + a_m.

Given an integer partitions, we call the numbers a_i _parts_ of the partition.


 Note.  _Nonincreasing_ means that, for each i < m, we have each a_{i+1} less
 than or equal to  a_i .  One may also say _weakly decreasing sequence_ to
 mean the same thing.

 Note.  Alternatively, we could define an integer partition of  n  as
 a _set_ of natural numbers which sum to  n .  We can only order such
 a set to make a nonincreasing sequence in one way, so the two definitions
 amount to the same.

Given a natural number  n  , we may consider the set of *all* possible
integer partitions, or we may consider only partitions satisfying various
constraints whether on the size, the number or distribution of the parts.
A theorem in the theory of partitions could give a exact formula for the
cardinality of the set of partitions of  n  that satisfy a particular
constraint.  Failing an exact formula, a theorem might provide just an
asymptotic estimate or a bound.  Some theorems only give a relation
between cardinalities associated with different sets of constraints.

For us, the theory of partitions provides a testing ground for two major
techniques of combinatorics, _generating functions_ and bijections.

The method of generating functions turns combinatorial questions into
algebraic questions and vice-versa.  Often when can use generating function
to bring a problem to a successful resolution without much in the way of
creative insight.  Unfortunately, a solution by means of generating
functions often provides little in the way of combinatorial intuition.

The method of bijections seeks to provide combinatorial answers to
combinatorial questions.  The discovery of a bijective proof usually
requires insight, but once discovered, a bijection may provide an immediate
and elementary (but possibly complicated) explanation for a hitherto
mysterious phenomenon.


                             A Typical Theorem
                             -----------------

Euler discovered that the number of partitions of n into *odd* parts equals
the number of partitions of n into *distinct* part (meaning that, for i<m, we
have a_{i+1} < a_i).

The following table gives some idea what Euler's theorem says:

PARTITIONS INTO DISTINCT PARTS   n   PARTITIONS INTO ODD PARTS
------------------------------------------------------------------------
                             1 = 1 = 1
                             2 = 2 = 1+1
                     3 =   2+1 = 3 = 3   = 1+1+1
                     4 =   3+1 = 4 = 3+1 = 1+1+1+1
               5 = 4+1 =   3+2 = 5 = 5   = 3+1+1  = 1+1+1+1+1
         6 = 5+1 = 4+2 = 3+2+1 = 6 = 5+1 = 3+3    = 3+1+1+1  = 1+1+1+1+1+1

 Note: From this table it *might* appear that the number of partitions of  n  of either
 type grows quit slowly as a function of  n , but 100 has exactly 444,793 partitions
 of each type and 1000 has exactly 8,635,565,795,744,155,161,506 .  It certainly would
 not make sense to dismiss the coincide of numbers of that magnitude as accidental!


                           Generating Functions
                           --------------------

Let DISTINCT(n) equal the number of partitions of  n  into distinct parts; let
ODD(n)  equal the number of partitions of  n  into odd parts.  So Euler's theorem
says that for all  n , DISTINCT(n) = ODD(n).  Instead of having an infinite number
of equations, the method of generating functions folds all these into one equation
between power series:

  \sum_{n=0}^{infinity} DISTINCT(n) x^n  =  \sum_{n=0}^{infinity} ODD(n) x^n  .

We call the power series on the left _the generating function for partitions
into DISTINCT parts_, similarly for the one on the right.  These generating
function *look* like functions of  x , but we know little in advance about
what values of x make the series converge.  We skirt this issue and regard
the equation above as _purely formal_.  That means it says *just exactly* that
for all  n , DISTINCT(n) = ODD(n) .  ``Well then,'' you might ask, ``how does
the translating into the language of generating functions confer any advantage?''

                             Infinite Products
                             -----------------

First we claim that

 \sum_{n=0}^{infinity} DISTINCT(n) x^n = (1+x^1)(1+x^2)(1+x^3)(1+x^4)... .

Before we can prove this, first we must say how we want to make sense of the infinite
product on the left.

 Note: Had we regarded this expression as an honest function of x , for
 any particular value of  x  we'd have little choice but to *try* to make sense of
 it as a limit of a sequence, as follows:

 (1+x^1)(1+x^2)(1+x^3)(1+x^4)... = lim_{n -->infinite} (1+x^1)(1+x^2)(1+x^3)...(1+x^n) .

Since we *only* care about the _coefficients_ of the series, *not* its _values_
we consider the *coefficient* of x^n in the (finite) polynomials:

(1+x^1) , (1+x^1)(1+x^2) , (1+x^1)(1+x^2)(1+x^3) , (1+x^1)(1+x^2)(1+x^3)(1+x^4) , ...

This coefficient eventually stabilizes.  Specifically, all products past

                  (1+x^1)(1+x^2)(1+x^3)(1+x^4)...(1+x^n)

have x^n with the *same* coefficient.  After all, by the distributive law,
multiplying by 1 + x^q, with q>n  gives us the sum of what we have (from the 1)
plus terms with exponent at least q (from the x^q).

 Note. A nice way to think about this has us observing that we have all higher factors
 congruent to 1 modulo  x^(n+1), (where we regard any term divisible by x^(n+1) as 0).

Now the coefficient of x^m in

                  (1+x^1)(1+x^2)(1+x^3)(1+x^4)...(1+x^n)

equals the number of ways to express  m  as the sum of distinct parts less
than or equal to  n .  This follows immediately from a suitable
generalization of the distributive law (which we can prove using the
distributive law itself, and induction).


Here we give a specially adapted induction for just this claim.  Assume, accordingly,
that the coefficient of x^m in

                  (1+x^1)(1+x^2)(1+x^3)(1+x^4)...(1+x^(n-1))

equals the number of ways to express m as the sum of distinct parts less than or n-1.
By the distributive law, if we multiply by (1+x^n), then the new coefficient of x^m
equals the sum of the old coefficient of x^m  plus the old coefficient of x^(m-n).
One the other hand, when we write  m  as a sum of distinct parts less than or equal to n,
either wew use a part of size  n  or not.  If we don't, we just have a partition into
distinct parts of size n-1 or less -- the number of these equals the old coefficient of
x^n -- and if we do, we have apart of size n appended to a partition of m-n into parts
of size n-1 or less -- the number of these equals the old coefficient of x^{n-m}.

(YOU SHOULD STUDY THE LAST PARAGRAPH CAREFULLY.  WE HAVE AND WE WILL USE THIS SORT
OF REASONING OVER AND OVER WITHOUT SPELLING OUT THE DETAILS AS WE HAVE DONE HERE.)

We also claim that

 \sum_{n=0}^{infinity} ODD(n) x^n = (1+x^1+x^2+x^3+... )(1+x^3+x^6+x^9+...)(1+x^5+x^10+x^15+...)...

EXERCISE:  Justify this by an induction modeled on the preceding argument.

Perhaps it helps think of the first factor as (1+x^{1}+x^{1+1}+x^{1+1+1}+... ) ,
the second as (1+x^{3}+x^{3+3}+x^{3+3+3}+... ) , the third as (1+x^{5}+x^{5+5}+x^{5+5+5}+... ) ,
and so forth.

 Note: Each factor represents the generating function for the number of ways
 to express a number as the sum of parts *all* equal to a fixed odd number and used
 as often as we please.  Of course the coefficients of these generating functions
 consist entirely of 0s and 1s.


                             Doing the Algebra
                             -----------------

Now we can make our goal the proof of the identity

(1+x^1)(1+x^2)(1+x^3)(1+x^4)... = (1+x^1+x^2+x^3+... )(1+x^3+x^6+x^9+...)(1+x^5+x^10+x^15+...)... .

The glory here consist of leaving behind the combinatorial interpretation and finishing
the proof with algebraic manipulation alone.  The right hand side equals


                                     1
                        ---------------------------
                          (1-x)(1-x^3)(1-x^5)...


because each factor amounts to a geometric progression.

 Note: In every case, we just use the formula 1/(1-x) = 1 + x^1 + x^2 + x^3 + ...
 and substitution.  We could justify this formula by cross multiplication,
 by Taylor series, by long division, or by considering (1-x^j)/(1-x) and
 taking a limit.  MAKE SURE YOU UNDERSTAND THIS COMPLETELY!).

Thus it suffices to prove the identity

         (1+x^1)(1+x^2)(1+x^3)(1+x^4)...(1-x)(1-x^3)(1-x^5)... = 1 .

In real and complex analysis rearranging terms of an infinite sum or product can
turn into a delicate affair.  In our case, the coefficient of any particular x^m
when we expand the product depends only on finitely many factors, so we can
rearrange to our hearts content.  Consider the arrangement

(1-x)(1+x)(1+x^2)(1+x^4)(1+x^8)..