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
SolutionIn every partition of $$$n$$$, either the number of summands or the smallest summand is smaller than $$$\sqrt n$$$. Let $$$f(n, i)$$$ be the number of partitions of $$$n$$$ having all summands greater or equal than $$$i$$$ and $$$g(n, j)$$$ be the number of partitions of $$$n$$$ having $$$j$$$ summands.
The following formulas stand:
$$$\begin{align} f(n, i) &= f(n - i, i) + f(n, i + 1), \\ g(n, j) &= g(n - j, j) + g(n - 1, j - 1). \end{align}$$$For the first sum, we either use $$$i$$$ as a summand, or fallback to the larger summand. For $$$g(n, j)$$$, we either decrease each summand by $$$1$$$ when they're all greater than $$$1$$$, or decrease the number of summands by $$$1$$$ and decrese $$$n$$$ by $$$1$$$, if there is a summand that equals $$$1$$$.
Using the recurrence above, it is possible to compute $$$g(a, b)$$$ for all $$$a \leq n$$$ and $$$b \leq \sqrt n$$$. Let $$$p = \lfloor \sqrt n \rfloor$$$, then
$$$ f(a, p) = \sum\limits_{j=1}^{\lfloor a / (p-1) \rfloor} g(a - (p - 1) \cdot j, j). $$$Here, we used the fact that each summand is greater or equal than $$$p$$$, thus we may decrease each summand by $$$p-1$$$ and the target value $$$a$$$ by $$$(p-1) \cdot j$$$. Then, having $$$f(a, p)$$$ we may as well compute $$$f(a, b)$$$ for all $$$b \leq \sqrt n$$$, including $$$p(n) = f(n, 1)$$$. The total running time of the described algorithm is $$$O(n \sqrt n)$$$.
Although this method has worse complexity than two methods described below, it still seems practical, as
Exp and Log of power series
SolutionLet's take the logarithm of the RHS taken modulo $$$x^{n+1}$$$:
$$$ \log \prod\limits_{k=1}^{n} \frac{1}{1-x^k} \equiv \sum\limits_{k=1}^n \log\frac{1}{1-x^k} \equiv \sum\limits_{k=1}^n \sum\limits_{j=1}^{\lfloor n/k \rfloor} \frac{x^{kj}}{j} \pmod{x^{n+1}}. $$$The logarithm can be computed in $$$O(n \log n)$$$, then one may use another $$$O(n \log n)$$$ operations to compute its exponent.
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
SolutionAs written above, the denominator may be computed explicitly in $$$O(n)$$$ with the following formula:
$$$ \large \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). $$$Numbers $$$\frac{k(3k+1)}{2}$$$ and $$$\frac{k(3k-1)}{2}$$$ are called pentagonal numbers for reasons that will be explained further below, as well as the proof of the formula. After the denominator is computed, its inverse may be found in $$$O(n \log n)$$$.
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$$$?
SolutionAssume that we want to compute partitions in which all the summands are distinct. The generating function of such parittions is
$$$ D(x) = (1+x)(1+x^2)(1+x^3) \dots = \prod\limits_{k=1}^\infty (1+x^k). $$$A seemingly unrelated task is to compute partitions in which all summands are odd. The generating function of such partitions is
$$$ (1+x+x^2+x^3+\dots)(1+x^3+x^6+x^9+\dots)(1+x^5+x^{10}+x^{15}+\dots)\dots = \prod\limits_{k=1}^\infty \frac{1}{1-x^{2k-1}}. $$$However, for distinct partitions we may note that $$$1+x^k = \frac{1-x^{2k}}{1-x^k}$$$, therefore
$$$ D(x) = \prod\limits_{k=1}^\infty \frac{1-x^{2k}}{1-x^k} = \frac{P(x^2)}{P(x)}. $$$At the same time, $$$\frac{P(x^2)}{P(x)}$$$ may be interpreted in such way that all even multipliers are cancelled out from the product of $$$\frac{1}{1-x^k}$$$, leaving it as
$$$ \frac{P(x^2)}{P(x)} = \prod\limits_{k=1}^\infty \frac{1}{1-x^{2k-1}}. $$$Thus, we proved that the number of partitions into odd summands equals the number of partitions into distinct summands.
This result can be generalized a bit if you consider
$$$ \frac{P(x^d)}{P(x)} = (1+x+x^2+\dots+x^{d-1})(1+x^2+x^4+\dots+x^{2(d-1)})(1+x^3+x^6+\dots+x^{3(d-1)}) \dots, $$$as it can be intepreted as generating functions for
- partitions such that each summand is not divisible by $$$d$$$;
- partitions such that each summand occurs less than $$$d$$$ times.
The result shown in the solution is known as Glaisher's theorem.
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}) $$$ SolutionThe constant evaluates numerically as
$$$ \phi = 0.\;8\;9\;00\;1\;00\;9999\;8\;999\;000000\;1\;0000\;99999999\;8\;99999\;0000000000\;1\;0 \dots $$$That is, it only has digits $$$0$$$, $$$1$$$, $$$8$$$ and $$$9$$$ in its decimal representation, which seemingly form some patterns.
This comes as no surpise if instead of infinite product you represent it as an infinite sum
$$$ \large \phi = 1 + \sum\limits_{k=1}^\infty (-1)^k\left(10^{-\frac{k(3k+1)}{2}} + 10^{-\frac{k(3k-1)}{2}}\right), $$$which also allows to formally explain patterns in the decimal expansion of the number.
What is the number of permutations of length $$$n$$$ with $$$k$$$ inversions for $$$k \leq \min(n, 10^5)$$$ and $$$n \leq 10^9$$$?
SolutionLet $$$\operatorname{inv} p$$$ be the number of inversions of the permutation $$$p$$$. If the ($$$0$$$-indexed) position of the number $$$n$$$ in the permutation is $$$i$$$, the the number of inversions can be represented as $$$\operatorname{inv} p = i + \operatorname{inv} q$$$, where $$$q$$$ is a permutation obtained by removing $$$n$$$ from the permutation.
Thus, the generating function for permutations of length $$$n$$$ can be constructed as
$$$ F_n(x) = \sum\limits_{p \in S_n} x^{\operatorname{inv} p} = \sum\limits_{i=0}^{n-1} \sum\limits_{q \in S_{n-1}} x^{i + \operatorname{inv} q} = \sum\limits_{i=0}^{n-1} x^i F_{n-1}. $$$The later can be expanded as
$$$ F_n(x) = (1 + x + \dots + x^{n-1}) F_{n-1}(x) = \frac{1-x^n}{1-x} F_{n-1}(x) = \prod\limits_{i=1}^n \frac{1-x^i}{1-x}, $$$so to find $$$[x^k]F_n(x)$$$ for $$$k \leq n$$$, we may expand the numerator with the pentagonal number theorem.
$$$ (1-x)(1-x^2) \dots (1-x^n) \equiv \prod\limits_{i=1}^\infty (1-x^i) \pmod{x^{n+1}}. $$$Note that, unfortunately, it is not the case for $$$k > n$$$, as LHS doesn't contain multiples with $$$1-x^i$$$ for $$$i > n$$$.
However, exp-log approach should still be applicable.
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$$$?
SolutionThe generating function of the answer is
$$$ G(x) = (x^{b_1} + \dots + x^{b_m}) (1 + x + x^2 + \dots + x^{a_1})(1+x^2 + x^4 + \dots + x^{2a_2}) \dots (1 + x^n + \dots + x^{n a_n}). $$$We need to compute
$$$ [x^{2n}] G(x) = \sum\limits_{j=1}^m [x^{2n-b_j}] \prod\limits_{i=1}^n \frac{1-x^{i a_i + 1}}{1-x^i}. $$$To solve the problem, it is sufficient to compute first $$$2n$$$ coefficients of both the numerator and the denominator. For the numerator, $$$a_i$$$ is strictly increasing, and we're only interested in $$$i \cdot a_i \leq 2n$$$, so so we only need first $$$O(\sqrt n)$$$ terms.
Thus the numerator may be computed in $$$O(n \sqrt n)$$$. Note that it can be computed in $$$O(n \log n)$$$, using the exp-log approach, which solves the problem also for not necessarily increasing $$$a_i$$$.
As for the denominator, we may represent it as
$$$ \prod\limits_{i=1}^n \frac{1}{1-x^i} = \frac{(1-x^{n+1})(1-x^{n+2})\dots(1-x^{2n})}{(1-x)(1-x^2)\dots(1-x^{2n})} \pmod{x^{2n}}. $$$First $$$2n$$$ terms of the denominator are obtained from the pentagonal number theorem. As for the numerator, it holds that
$$$ (1-x^{n+1}) \dots (1-x^{2n}) \equiv 1 - x^{n+1} - x^{n+2} - \dots - x^{2n} \pmod{x^{2n}}, $$$because sum of any two non-zero powers after expansion will exceed $$$2n$$$, so this part may be computed in $$$O(n \log n)$$$.
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