Distinct and Odd Partitions

Euler’s Partition Theorem:

The number of distinct partitions of an integer, \(n\), is equal to the number of odd partitions of that integer :

\(D(n) = O(n)\), for all \(n\).

Euler gave us a proof which is delightful in its simplicity; he multiplied by one (the multiplicative identity).


 

A distinct partition of an integer is one such that there is no repetition of parts.

An odd partition of an integer is one such that all the parts are odd and repetition is allowed.

Using the integer \(8\) as an example which has a total of \(22\) partitions, \(p(8) = 22\),

\(D(8) = O(8) = 6 \)

These are :

Distinct :

\( 8 \\
7 + 1 \\
6 + 2 \\
5 + 3 \\
5 + 2 + 1 \\
4 + 3 + 1 \)

Odd :

\(7 + 1 \\
5 + 3 \\
5 + 1 + 1 + 1 \\
3 + 3 + 1 + 1 \\
3 + 1 + 1 + 1 + 1 + 1 \\
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 \)

 

Consider the following infinite product :

\((1 + x)(1 + x^2)(1 + x^3)(1 + x^4)(1 + x^5)(1 + x^6)(1 + x^7)(1 + x^8) … \)

Expanding this up to the term in \(x^8\) gives :

\(1 + x + x^2 + 2x^3 + 2x^4 + 3x^5 + 4x^6 + 5x^7 + 6x^8 + … + x^{15} \)

With this infinite sum we are interested in the coefficients of the terms.

Note that when we reach the point where the number of factors is equal to the exponent of the term, then the coefficient of that term no longer increases.

Multiplying out the above product for the terms in \(x^8\), we have :

\( \begin{align} x^8 & = x \times 1 \times x^3 \times x^4 \times 1 … = x^{1+3+4} \\
& = x \times x^2 \times 1 \times 1 \times x^5 \times 1 … = x^{1+2+5} \\
& = 1 \times 1 \times x^3 \times 1 \times x^5 \times 1 … = x^{3+5} \\
& = 1 \times x^2 \times 1 \times 1 \times 1 \times x^6 \times 1 … = x^{2+6} \\
& = x \times 1 \times 1 \times 1 \times 1 \times 1 \times x^7 \times 1 … = x^{1+7} \\
& = 1 \times 1 \times 1 \times 1 \times 1 \times 1 \times 1 \times x^8 \times 1 … = x^8 \end{align}\)

Thus we see that the term \(x^8\) can be calculated in six different ways where the parts are distinct and therefore takes a coefficient of six.

The above infinite product is written as :

\( \displaystyle \prod_{n=1}^∞ (1 + x^n) \)

and is the generating function for the resulting infinite polynomial.

This polynomial can be summed and written as :

\( \displaystyle 1 + \sum_{n=1}^∞ D(n) x^n \)

Hence :

\( \displaystyle \begin{align}
\prod_{n=1}^∞ (1 + x^n) & = (1 + x)(1 + x^2)(1 + x^3)(1 + x^4) … \\
& = 1 + x + x^2 + 2x^3 + 2x^4 + 3x^5 + 4x^6 + … \\
& = 1 + \sum_{n=1}^∞ D(n) x^n \end{align} \)

 

Now consider the following infinite product :

\( \displaystyle \frac {1}{(1-x)(1-x^3)(1-x^5)(1-x^7)(1-x^9)(1-x^{11})} … \)

Using a standard result for a geometric series :

\(a + ar + ar^2 + ar^3 + ar^4 + … = \frac {a}{1-r} \),

for first term \(a\) and common ratio \(r\).

When \(a = 1\), this is simplified to :

\(1 + r + r^2 + r^3 + r^4 + … = \frac {1}{1-r} \)

We substitute this into the above product :

\( \displaystyle \frac {1}{(1 + x + x^2 + x^3 + …)(1 + x^3 + x^6 + x^9 + …)(1 + x^5 + x^{10} + x^{15} + …)} … \)

Rewriting, we have :

\( \displaystyle \frac {1}{(1 + x + x^{1+1} + x^{1+1+1} + …)(1 + x^3 + x^{3+3} + x^{3+3+3} + …)(1 + x^5 + x^{5+5} + x^{5+5+5} + …)} … \)

Multiplying out and omitting the ones, we have :

\( \begin{align} x^8 & = x^{1+1+1+1+1+1+1+1} \\
& = x^{1+1+1+1+1}\cdot x^3 & = x^{3+1+1+1+1+1} \\
& = x^{1+1}\cdot x^{3+3} & = x^{3+3+1+1} \\
& = x^{1+1+1}\cdot x^5 & = x^{5+1+1+1} \\
& = x^3\cdot x^5 & = x^{5+3} \\
& = x\cdot x^7 & = x^{7+1} \end{align} \)

Thus we see that the term \(x^8\) can be calculated in six different ways having odd parts.

This shows that \(D(8) = O(8) = 6\) but we have not proved that it is true for all \(n\).

 


 

Euler’s Proof : 

Multiply each factor in the first infinite product by one, the multiplicative identity.

He expresses one in infinitely many ways :

\(1 = \frac {(1-x)}{(1-x)}, \frac {(1-x^2)}{(1-x^2)}, \frac {(1-x^3)}{(1-x^3)}, … \)

So:

\((1 + x)(1 + x^2)(1 + x^3)(1 + x^4)(1 + x^5)(1 + x^6) … \)

multiplied by one equals :

OldTrout, Going Postal

A difference of squares can be factored :

\(1-x^2 = (1 + x)(1-x) \)

We start cancelling :

OldTrout, Going Postal

We continue cancelling infinitely many times  since :

\(1-x^4 = (1 + x^2)(1-x^2) \\
1-x^6 = (1 + x^3)(1-x^3) \\
1-x^8 = (1 + x^4)(1-x^4) \\
. \\
. \\
. \\ \)

Leading to :

\( \displaystyle \frac {1}{(1-x)(1-x^3)(1-x^5)(1-x^7)(1-x^9)(1-x^{11})} … \)

Then :

\(\displaystyle \begin{align} 1 + \sum_{n=1}^∞ D(n)x^n \\
& = (1 + x)(1 + x^2)(1 + x^3)(1 + x^4) … \\
& = \frac {1}{(1-x)(1-x^3)(1-x^5)(1-x^7)} … \\
& = 1 + \sum_{n=1}^∞ O(n) x^n \end{align}\)

Thus :

\(D(n) = O(n)\), for all \(n\),

which proves the theorem.
 

© OldTrout \(2019\)
 

No Audio file – Does not translate well