#### Partition

Definition: A **partition** of a positive integer n is a way of writing n as a sum of positive integers.

Definition: An addend in a partition is called a **part**.

Example:

Partitions of 4:

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

Partitions of 6:

6

5 + 1

4 + 2

4 + 1 + 1

3 + 3

3 + 2 +1

3 + 1 + 1 + 1

2 + 2 + 2

2 + 2 + 1 + 1

2 + 1 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1 + 1

#### Partition function

The partition function p(n) represents the number of possible partitions of a natural number n.

Example:

*p*(4) = 4

*p*(6) = 11

By convention:

*p*(0) = 1

*p*(n) = 0 for n negative

#### Is the partition function Multiplicative?

What is the first question we always ask ourselves when we are given a new arithmetic function?

Is our function multiplicative?

Well, let’s find out! Let’s remind ourselves what it means if a function is multiplicative. If f(n) is multiplicative and n = q_{1}^{a1}q_{2}^{a2}…q_{r}^{ar} where q_{i}^{ai} are the distinct prime factors are n, then f(n) = f(q_{1}^{a1})f(q_{2}^{a2})…f(q_{r}^{ar}).

Does *p*(6) = *p*(3)*p*(2)?

*p*(6) = 11

*p*(3):

3

2 + 1

1 + 1 + 1

p(2):

2

1 + 1

Does 11 = 3 x 2?

NO! So our partition function is NOT multiplicative!

#### Intermediate Function

The intermediate function gives a different way of partitioning an integer n. This function is written in the form *p*(k,n) where n is the number you are partitioning, and k is the least value of a part. So for *p*(k,n), the partitions counted by this function either have the smallest addend ≥ k

Some examples:

*p*(1, 4) = 5

*p*(2, 8) = 7

*p*(3, 12) = 9

*p*(4, 16) = 11

*p*(2, 8) = 7 (why do we skip 7?)

8

6 + 2

5 + 3

4 + 4

4 + 2 + 2

3 + 3 + 2

2 + 2 + 2 + 2

What is the original partition *p*(n) function written as the intermediate function?

*p*(1,n)

#### Generating Function

What’s the second thing we always want to know when we are given an arithmetic function?

As Lance would say, is there a “fun” formula to figure out how many partitions of a number there is?

Sadly, there is not necessarily a “fun” formula that works for partitions of any n. However, we are going to give you something else to work with.

Definition: a **generating function** for an arithmetic function f(k) is the infinite polynomial $\sum_{k=0}^{\infty} f(k)x^{k}$

For instance, the generating function for *p*(n) starts 1x^{0} + 1x^{1} + 2x^{2} + 3x^{3} + 5x^{4} + … where the coefficients of each x term is the number of partitions of the exponent.

Now, would the above polynomial really help us if we had to figure out what the coefficient was based off the number of partitions? NO! Because then it wouldn't be a generating function since we are generating the polynomial ourselves.

So, here is the generating function for *p*(n):

$\sum_{n=0}^{\infty} p(n)x^{n} = \prod_{n=1}^{\infty} \frac{1}{1-x^n}$

What does this mean?

The geometric series $\frac{1}{1-x}$ = 1 + x^{2} + x^{3} + x^{4} + x^{5} + …

The geometric series $\frac{1}{1-x^2}$ = 1 + x^{2} + x^{4} + x^{6} + …

The geometric series $\frac{1}{1-x^3}$ = 1 + x^{3} + x^{6} + x^{9} + …

See the pattern? The exponents go up by the original exponent of x in the denominator for each term of the polynomial expansion.

Now, we see that the generating function for *p*(n) is the product of geometric series since $\frac{1}{1-x^n}$ is a geometric series.

That means, that our generating function $\prod_{n=1}^{\infty} \frac{1}{1-x^n}$ = (1 + x^{1} + x^{2} + x^{3} + x^{4} + x^{5} + …)(1 + x^{2} + x^{4} + x^{6} + x^{8} + …)(1 + x^{3} + x^{6} + x^{9} + …)(1 + x^{4} + x^{8} + …)(1 + x^{5} + …)(1 + x^{6} + …)…

To understand it better, we ended up rewriting it as:

$\prod_{n=1}^{\infty} \frac{1}{1-x^n}$ = (1 + x^{1} + x^{1+1} + x^{1+1+1} + x^{1+1+1+1} + x^{1+1+1+1+1} + …)(1 + x^{2} + x^{2+2} + x^{2+2+2} + x^{2+2+2+2} + …)(1 + x^{3} + x^{3+3} + x^{3+3+3} + …)(1 + x^{4} + x^{4+4} + …)(1 + x^{5} + …)(1 + x^{6} + …)…

Then what do you get when you multiply out the polynomial?

1 + x^{1} + 2x^{2} + 3x^{3} + x^{1+1+1+1} + x^{1+1+2} + x^{1+3} + x^{2+2} + x^{4} + 7x^{5} + 11x^{6}…

which is the same as

1 + x^{1} + 2x^{2} + 3x^{3} + 5x^{4} + 7x^{5} + 11x^{6}…

#### Restricted Partitions

How many ways can you partition a number into distinct parts?

Definition: *p*_{d}(n) is the number of possible partitions of a natural number n that can be split into **distinct (non-repeating) parts**

Example: 8?

8

7 + 1

6 + 2

5 + 3

5 + 2 + 1

4 + 3 + 1

So there are 6 ways to partition 8 into distinct parts, so *p*_{d}(8) = 6

5?

5

4 + 1

3 + 2

So there are 3 ways to partition 5 into distinct parts, so *p*_{d}(5) = 3

How many ways can you partition a number into odd parts?

Definition: *p*_{odd}(n) is the number of possible partitions of a natural number n that can be split into **odd** parts.

Example: 8?

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

So there are 6 ways to partition 8 into odd parts, so *p*_{odd}(8) = 6

5?

5

3 + 1 + 1

1 + 1 + 1 + 1 + 1

So there are 3 ways to partition 5 into odd parts, so *p*_{odd}(5) = 3

Anyone notice anything?

It is true that for all positive numbers n that the number of partitions with odd parts ALWAYS equals the number of partitions with distinct parts! COOL!!

Theorem: If n is any positive integer then *p*_{d}(n) = *p*_{odd}(n).

Let’s look at our generating function and see why this is true:

For n = 6, the number of distinct partitions **(no repetition of exponents)** is

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

so we get

(1 + x)(1 + x^{2})(1 + x^{3})(1 + x^{4})(1 + x^{5})(1 + x^{6}) = 1 + x + x^{2} + 2x^{3} + 2x^{4} + 3x^{5} + 4x^{6}

For n = 6, the number of odd partitions **(no even parts)** is

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

so we get

(1 + x^{2} + x^{3} + x^{4} + x^{5} + x^{6})(1 + x^{3} + x^{6})(1 + x^{5}) = 1 + x + x^{2} + 2x^{3} + 2x^{4} + 3x^{5} + 4x^{6}

So we see that these are the same as stated in our theorem.

Looking at our function, how many odd/distinct partitions of 6 are there?

By looking at the coefficient of x^{6} we can see there are 4!

#### Congruences

Mathematician Srinivasa Ramanugan (who by the way is like the coolest man ever – if you want to feel bad about your life, he came from an impoverished family with basically no education, was handed a trig book at age 10, and had memorized all of the book memorized and had derived a bunch of theorems by the age of 13) ANYWAY – he came up with something pretty sweet.

He discovered that a congruence exists in the number of partitions that exist for integers ending in 4 or 9.

Basically, he figured out that the number of partitions of an integer n of the form 5k + 4 (or in other words, an integer ending in 4 or 9), will be divisible by 5.

As a congruence this is written as:

$p(5k + 4) \equiv 0 \mod{5}$

He ALSO discovered congruences related to 7 and 11

$p(7k + 5) \equiv 0 \mod{7}$

AND

$p(11k + 6) \equiv 0 \mod{11}$

In the 1960’s, A.O.L. Atkin of UIC found another congruence for some small prime moduli. For example:

$p(17303k + 237) \equiv 0 \mod{13}$

Actually, Ken Ono, in 2002 (from University of Wisconsin) proved that there are such congruences for every prime modulus! AWESOME!

A couple years later, together with Ono, Scott Ahlgren, of the U of I (who Andy knows!! Cool!) proved that there are partition congruences modulo every integer relatively prime to 6. This should make you all very very excited.

WOOHOO!!