Partitions and pentagonal number theorem

Revision en6, by adamant, 2022-06-28 23:47:55

Hi everyone!

In today's blog I'd like to write about the theorem that allows to efficiently solve the following problems:

  • What is the number of partitions of a non-negative number $$$n$$$ for $$$n \leq 10^5$$$?
  • What is the number of partitions of a non-negative number $$$n$$$ for $$$n \leq 10^5$$$, so that no summand repeats $$$d$$$ or more times?
  • What is the number of partitions of a non-negative number $$$n$$$ for $$$n \leq 10^5$$$, so that no summand is divisible by $$$d$$$?
  • HackerEarth — Perfect Permutations: What is the number of permutations of length $$$n$$$ with $$$k$$$ inversions for $$$k \leq n \leq 10^5$$$?
  • 102354E - Decimal Expansion: Let $$$\phi = \frac{9}{10} \cdot \frac{99}{100} \cdot \frac{999}{1000} \cdot \dots$$$, what is the $$$k$$$-th digit of $$$\phi$$$ for $$$k \leq 10^{18}$$$?
  • SNSS-2018 Round 5 — Investment Portfolio: You have $$$2n$$$ dollars and there are $$$n$$$ types of products in the market. There are $$$a_i$$$ instances of the $$$i$$$-th product, costing $$$i$$$ dollars each, such that $$$a_i > a_j$$$ when $$$i > j$$$. Besides that, there are also $$$m$$$ individual offers, $$$j$$$-th of them costing $$$b_j$$$. How many ways are there to spend all $$$2n$$$ dollars, while taking exactly one individual offer for $$$n, m \leq 10^5$$$?

The core fact that allows us to solve these problems efficiently is the pentagonal number theorem:

$$$ \large \boxed{\prod\limits_{k=1}^\infty (1-x^k) = 1 + \sum\limits_{k=1}^\infty (-1)^k\left(x^{\frac{k(3k+1)}{2}} + x^{\frac{k(3k-1)}{2}}\right)} $$$

Prerequisites

  • Familiarity with generating functions, formal power series and operations on them.
  • Basic notion of combinatorics.
  • Basic notion of number theory.

Motivational examples

General partitions

Let $$$n$$$ be a non-negative number. A partition is a way of writing it as a sum of positive integers. For example,

$$$\begin{align} 4 & = 4 \\ &= 3 + 1 \\ &= 2 + 2 \\ &= 2 + 1 + 1 \\ &= 1 + 1 + 1 + 1. \end{align}$$$

Let $$$p(n)$$$ be the partition function meaning that $$$p(n)$$$ is the number of partitions of $$$n$$$. Let $$$P(x)$$$ be such that

$$$ P(x) = \sum\limits_{n=0}^\infty p(n) x^n, $$$

that is $$$P(x)$$$ is the ordinary generating function of the partition sequence. It can be expressed as an infinite product

$$$ P(x) = (1+x+x^2+x^3+\dots)(1+x^2+x^4+x^6+\dots)(1+x^3+x^6+x^9+\dots)\dots $$$

Indeed, after expanding the expression into a sum of monomials, $$$k$$$-th multiplier will contribute with $$$x^{kt}$$$ for some $$$t \geq 0$$$, which may be interpreted as $$$t$$$ summands in the partition that are equal to $$$k$$$. Than the contributions are summed up to

$$$ 1 \cdot t_1 + 2 \cdot t_2 + 3 \cdot t_3 + \dots = n, $$$

making one of possible partitions of the number $$$n$$$.

On the other hand, $$$1+x^k + x^{2k} + x^{3k} + \dots = \frac{1}{1-x^k}$$$ is the sum of geometric progression, so $$$P(x)$$$ may be expressed as

$$$ P(x) = \frac{1}{1-x} \frac{1}{1-x^2} \frac{1}{1-x^3} \dots = \prod\limits_{k=1}^\infty \frac{1}{1-x^k}. $$$

Conveniently, if we only need to compute the number of partitions of numbers up to $$$n$$$, we may consider only first $$$n$$$ multipliers discarding the remaining part of the infinite product. Now, to compute it, we may find the multiplicative inverse of the denominator after computing it. But how to compute the denominator? There are several approaches.

Square root decomposition

The solution below is borrowed from ABalobanov's comment

Solution

Exp and Log of power series

Solution

Although this approach is a bit more complicated than the one with the pentagonal number theorem, it generalizes to compute

$$$ (1-x)(1-x^2) \dots (1-x^n) \pmod{x^k}, $$$

or even

$$$ (1-x^{a_1})(1-x^{a_2}) \dots (1-x^{a_n}) \pmod{x^k} $$$

for arbitrary $$$k$$$ in $$$O(k \log k)$$$, including the case $$$k > n$$$, for which pentagonal number theorem fails if applied directly.

Pentagonal number theorem

Solution

Pentagonal number theorem allows to compute the number of partitions faster than $$$O(n \sqrt n)$$$, while also not involving complicated operations like computing polynomial logarithms and exponents.

Note that the pentagonal number theorem also allows for a simpler $$$O(n \sqrt n)$$$ solution, using the recurrence

$$$ p(n) = \sum\limits_{k=1}^{\dots} (-1)^{k-1} \left[ p\left(n - \frac{k(3k+1)}{2}\right) + p\left(n - \frac{k(3k-1)}{2}\right)\right], $$$

as only first $$$O(\sqrt n)$$$ values of $$$k$$$ are of interest for it.

Distinct partitions, odd partitions

What if we additionally ask the partition to only have distinct summands? Or only odd summands?

Nore generally, that each summand appears less than $$$d$$$ times? That each summand is not divisible by $$$d$$$?

Solution

The result shown in the solution is known as Glaisher's theorem.

102354E - Decimal Expansion

Find the $$$k$$$-th ($$$k \leq 10^{18}$$$) digit of the decimal expansion of the constant

$$$ \phi = \frac{9}{10} \frac{99}{100} \frac{999}{1000} \dots = \prod\limits_{k=1}^\infty (1-10^{-k}) $$$
Solution

Enumerating permutations by inversions

What is the number of permutations of length $$$n$$$ with $$$k$$$ inversions for $$$k \leq \min(n, 10^5)$$$ and $$$n \leq 10^9$$$?

Solution

SNSS-2018 Round 5 — Investment Portfolio

You have $$$2n$$$ dollars and there are $$$n$$$ types of products in the market. There are $$$a_i$$$ instances of the $$$i$$$-th product, costing $$$i$$$ dollars each, such that $$$a_i > a_j$$$ when $$$i > j$$$. Besides that, there are also $$$m$$$ individual offers, $$$j$$$-th of them costing $$$b_j$$$. How many ways are there to spend all $$$2n$$$ dollars, while taking exactly one individual offer for $$$n, m \leq 10^5$$$?

Solution

Explanation of the theorem

The expansion of $$$(1-x)(1-x^2)(1-x^3) \dots$$$ was first discovered by Euler. He derived the formula

$$$ P(x) = \prod\limits_{k=1}^\infty \frac{1}{1-x^k} $$$

and then tried to expand the denominator. As a result, he saw that

$$$ (1-x)(1-x^2)(1-x^3) \dots = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - x^{35} - x^{40} + \dots $$$

First mention of the theorem was in Euler's letter to Bernoulli in 1741. Although he mentioned the formula several more times in his correspondence, only in 1750 Euler derived a complete proof to it, as follows from his letter to Goldbach.

Franklin's proof

In modern time, most common proof to be taught is due to Hungarian born American mathematician Fabian Franklin, first published in 1881. The proof inteprets the series $$$(1-x)(1-x^2)(1-x^3) \dots$$$ as a generating function for strict partitions (i.e. partitions in which all summands are distinct), such that every partition is weighted by $$$(-1)^k$$$, where $$$k$$$ is the number of partition elements. In other words,

$$$ (1-x)(1-x^2)(1-x^3) \dots = \sum\limits_{k=0}^\infty [d_e(k) - d_o(k)] x^k, $$$

where $$$d_e(k)$$$ and $$$d_o(k)$$$ are the numbers of partitions of $$$k$$$ into distinct summands such that the amount of summands is even for $$$d_e(k)$$$ and odd for $$$d_o(k)$$$. As it turns out, $$$d_e(k) = d_o(k)$$$ for vast majority of numbers $$$k$$$.

Franklin discovered that in most times it is possible to pair up partitions with odd number of summands and partitions with even number of summands. To understand how the pairing is obtained, we may represent a partition as a pattern of dots.

$$$\large \begin{matrix} \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \color{royalblue} \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet & \color{royalblue} \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \color{red} \bullet & \color{red} \bullet & \color{red} \bullet \end{matrix} \iff \begin{matrix} \bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \color{red} \bullet & \color{red} \bullet & \color{red} \bullet \\ \color{royalblue} \bullet & \color{royalblue} \bullet \\ \end{matrix} $$$

Franklin's idea was, considering the last row and the last diagonal, to either move the last diagonal below the last row, or to move the last row after the last diagonal. In this way, $$$7+6+4+3$$$ is paired with $$$6+5+4+3+2$$$.

The pairing works most of the times. Except when last row and last diagonal share a dot and the size of the last row is either same as the size of the last diagonal or larger than it by exactly $$$1$$$:

$$$\begin{gather}\large \begin{matrix} \bullet & \bullet & \bullet & \bullet & \color{royalblue} \bullet \\ \bullet & \bullet & \bullet & \color{royalblue} \bullet \\ \color{red} \bullet & \color{red} \bullet & \color{orchid} \bullet \end{matrix} & \large ~ & \large \begin{matrix} \bullet & \bullet & \bullet & \bullet & \bullet & \color{royalblue} \bullet \\ \bullet & \bullet & \bullet & \bullet & \color{royalblue} \bullet \\ \color{red} \bullet & \color{red} \bullet & \color{red} \bullet & \color{orchid} \bullet \end{matrix} \end{gather}$$$

In the first case, moving the diagonal or the row would make an invalid diagram, as the last row would be of larger size than the one above it. In the second case, moving diagonal would make a valid partition, but last two elements of the partition would both be equal (in the picture above to the number $$$3$$$), meaning that the partition is not strict, as needed for the bijection.

Let $$$k$$$ be the number of summands in the partition. The first case yields a sum of

$$$ k^2 + \frac{k(k-1)}{2} = \frac{k(3k-1)}{2}, $$$

and the second case yields a sum of

$$$ k^2 + \frac{k(k+1)}{2} = \frac{k(3k+1)}{2}, $$$

which proves the theorem:

$$$ \large \boxed{\prod\limits_{k=1}^\infty (1-x^k) = 1 + \sum\limits_{k=1}^\infty (-1)^k\left(x^{\frac{k(3k+1)}{2}} + x^{\frac{k(3k-1)}{2}}\right)} $$$

Why pentagonal?

Because the numbers appear in a construction of dotted pentagons, which is similar to triangular numbers and square numbers.

Further reading

Tags tutorial, generating function, pentagonal numbers, euler, partitions

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English adamant 2022-06-29 12:50:04 18
en6 English adamant 2022-06-28 23:47:55 2
en5 English adamant 2022-06-28 23:05:30 15
en4 English adamant 2022-06-28 20:27:18 92
en3 English adamant 2022-06-28 20:23:43 9
en2 English adamant 2022-06-28 20:22:11 332
en1 English adamant 2022-06-28 20:15:45 17167 Initial revision (published)