Partitions and the Partition Function

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 = q1a1q2a2…qrar where qiai are the distinct prime factors are n, then f(n) = f(q1a1)f(q2a2)…f(qrar).

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 1x0 + 1x1 + 2x2 + 3x3 + 5x4 + … 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 + x2 + x3 + x4 + x5 + …

The geometric series $\frac{1}{1-x^2}$ = 1 + x2 + x4 + x6 + …

The geometric series $\frac{1}{1-x^3}$ = 1 + x3 + x6 + x9 + …

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 + x1 + x2 + x3 + x4 + x5 + …)(1 + x2 + x4 + x6 + x8 + …)(1 + x3 + x6 + x9 + …)(1 + x4 + x8 + …)(1 + x5 + …)(1 + x6 + …)…

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

$\prod_{n=1}^{\infty} \frac{1}{1-x^n}$ = (1 + x1 + x1+1 + x1+1+1 + x1+1+1+1 + x1+1+1+1+1 + …)(1 + x2 + x2+2 + x2+2+2 + x2+2+2+2 + …)(1 + x3 + x3+3 + x3+3+3 + …)(1 + x4 + x4+4 + …)(1 + x5 + …)(1 + x6 + …)…

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

1 + x1 + 2x2 + 3x3 + x1+1+1+1 + x1+1+2 + x1+3 + x2+2 + x4 + 7x5 + 11x6

which is the same as

1 + x1 + 2x2 + 3x3 + 5x4 + 7x5 + 11x6

Restricted Partitions

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

Definition: pd(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 pd(8) = 6

5?

5

4 + 1

3 + 2

So there are 3 ways to partition 5 into distinct parts, so pd(5) = 3

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

Definition: podd(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 podd(8) = 6

5?

5

3 + 1 + 1

1 + 1 + 1 + 1 + 1

So there are 3 ways to partition 5 into odd parts, so podd(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 pd(n) = podd(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 + x1 + x1+1 + x1+1+1 + x1+1+1+1 + x1+1+1+1+1 + …)(1 + x2 + x2+2 + x2+2+2 + x2+2+2+2 + …)(1 + x3 + x3+3 + x3+3+3 + …)(1 + x4 + x4+4 + …)(1 + x5 + …)(1 + x6 + …)

so we get

(1 + x)(1 + x2)(1 + x3)(1 + x4)(1 + x5)(1 + x6) = 1 + x + x2 + 2x3 + 2x4 + 3x5 + 4x6

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

(1 + x1 + x1+1 + x1+1+1 + x1+1+1+1 + x1+1+1+1+1 + …)(1 + x2 + x2+2 + x2+2+2 + x2+2+2+2 + …)(1 + x3 + x3+3 + x3+3+3 + …)(1 + x4 + x4+4 + …)(1 + x5 + …)(1 + x6 + …)

so we get

(1 + x2 + x3 + x4 + x5 + x6)(1 + x3 + x6)(1 + x5) = 1 + x + x2 + 2x3 + 2x4 + 3x5 + 4x6

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 x6 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!!