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:
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,
Let $$$p(n)$$$ be the partition function meaning that $$$p(n)$$$ is the number of partitions of $$$n$$$. Let $$$P(x)$$$ be such that
that is $$$P(x)$$$ is the ordinary generating function of the partition sequence. It can be expressed as an infinite product
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
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
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
Exp and Log of power series
Although this approach is a bit more complicated than the one with the pentagonal number theorem, it generalizes to compute
or even
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
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
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$$$?
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
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$$$?
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$$$?
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
and then tried to expand the denominator. As a result, he saw that
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,
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 (Ferrers diagram).
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$$$:
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
and the second case yields a sum of
which proves the theorem:
Why pentagonal?
Because the numbers appear in a construction of dotted pentagons, which is similar to triangular numbers and square numbers.
