Partitions and Generating Functions

I asked Gemini to explain the statement:

“It’s long been known that you can associate

a polynomial equation to any partition.”

Here's what it came up with.

The statement refers to the relationship between an integer partition and a generating function, which is a way of encoding an infinite sequence of numbers as the coefficients of a formal power series. In this context, the "polynomial equation" is more accurately a generating function, which can be represented as a polynomial-like expression.

A partition of a positive integer \(n\) is a way of writing \(n\) as a sum of positive integers. The order of the addends (the parts of the partition) does not matter. For example, the partitions of the number 4 are:

• 4

• 3 + 1

• 2 + 2

• 2 + 1 + 1

• 1 + 1 + 1 + 1

The statement means that for any given integer, we can construct a polynomial-like expression (a generating function) that "encodes" all of its possible partitions.

How the Association Works

The connection is established through the concept of generating functions. The generating function for the number of partitions of an integer \(n\), denoted as \( p(n) \), can be expressed as an infinite product:$$P(x) = \sum_{n=0}^{\infty} p(n)x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$$Let's break down this formula:

• \( p(n) \) This represents the number of partitions for an integer \(n\)

• \( \displaystyle\sum_{n=0}^{\infty} p(n)x^n \) This is the power series where the coefficient of \(x^n\) is the number of partitions of \(n\).

• \(\displaystyle\prod_{k=1}^{\infty} \dfrac{1}{1-x^k}\) This is the infinite product that generates these coefficients.

Each term in the product \( \dfrac{1}{1-x^k} \) can be expanded as a geometric series:

• \(\dfrac{1}{1-x} = 1 + x + x^2 + x^3 + \dots \) This represents using the number 1 as a part in the partition

• \(\dfrac{1}{1-x^2} = 1 + x^2 + x^4 + x^6 + \dots\) This represents using the number 2 as a part

• \( \dfrac{1}{1-x^3} = 1 + x^3 + x^6 + x^9 + \dots \) This represents using the number 3 as a part

• And so on for all integers \(k\).

When you multiply these series together, the coefficient of \(x^n\) in the resulting series will be the total number of ways to form \(n\) by adding these parts.

Examples

Let's find the partitions for the number 3. The partitions are:

• 3

• 2 + 1

• 1 + 1 + 1

There are 3 partitions of 3.

Now, let's see how the generating function gives us this result. We look at the expansion of the product:$$(1 + x + x^2 + x^3 + \dots)(1 + x^2 + x^4 + \dots)(1 + x^3 + x^6 + \dots) \dots$$To get the term \(x^3\), we can combine terms from these expansions in the following ways:

• From the first factor, take \(x^3\). This corresponds to the partition 1 + 1 + 1.

• From the first factor, take \(x^1\), and from the second factor, take \(x^2\). This corresponds to the partition 1 + 2.

• From the third factor, take \(x^3\). This corresponds to the partition 3.

The coefficient of \(x^3\) is therefore 3, which matches the number of partitions.

Here is another example for the partitions of 4, which we know is 5.

To find the coefficient of \(x^4\), we would consider combinations like:

• \(x^4\) from the first factor: 1 + 1 + 1 + 1

• \(x^2\) from the first factor and \(x^2\) from the second: 1 + 1 + 2

• \(x^1\) from the first factor and \(x^3\) from the third: 1 + 3

• \(x^4\) from the second factor: 2 + 2

• \(x^4\) from the fourth factor: 4

The total number of ways to get \(x^4\) is 5, so the coefficient is 5.

In essence, the "polynomial" or generating function provides a systematic way to count the number of partitions for any integer by looking at the coefficients of the series expansion.