Sum of Product of Min, which is related to the Pentagonal number theorem.

Question

The title looks a little bit weird. The problem comes from the Atcoder Beginner Contest 279-Ex: Sum of Prod of Min:

Problem: You are given positive integers $n$ and $m$. Here, it is guaranteed that $n \leq m \leq 2n$.

Calculate the sum of the following value over all sequences of positive integers $S=(S_1, S_2, ..., S_n)$ such that $\sum\limits_{i=1}^n S_i=m$. Calculate $f(n, m)$, which is defined as the sum of $\prod\limits_{i=1}^n \min(i, S_i)$:

$f(n, m) := \sum\limits_{S}\prod\limits_{i=1}^n \min(i, S_i)\tag{1}$

The original problem has a modulo $200003$. The purpose of the modulo is to prevent integer overflow. $200003 × 200003$ is inside the range of C++ type long long. However, since MathStackexchange is a math forum, I omit it. Formula (1) might look a little bit abstract. Let me give two examples.

Example 1: $n=2, m=3$. $S$ could be $(1, 2)$ or $(2, 1)$.

If $S = (1, 2)$, then $\prod_{i=1}^n\min(S_i, i) = \min(1, 1) × \min(2, 2) = 2$.

If $S = (2, 1)$, then $\prod_{i=1}^n\min(S_i, i) = \min(2, 1) × \min(1, 2） = 1$.

So $f(2, 3) = 2+1 = 3$. Please note that you cannot take arrays like $(-1, 4)$ into consideration, as $S$ has to be an array of positive integers.

Example 2 is taken from the original problem. To make the problem more self-contained, I copy it here:

$n = 3, m = 5$. There are $6$ sequences $S$ that satisfy the condition: $S=(1,1,3)$, $S=(1,2,2)$, $S=(1,3,1)$, $S=(2,1,2)$, $S=(2,2,1)$, $S=(3,1,1)$.

for each of those S is as follows.

$S=(1,1,3)$: $\min(1, 1)×\min(1, 2)×\min(3, 3)=3$.

$S=(1,2,2)$: $\min(1, 1)×\min(2, 2)×\min(2, 3)=4$.

$S=(1,3,1)$: $\min(1, 1)×\min(3, 2)×\min(1, 3)=2$.

$S=(2,1,2)$: $\min(2, 1)×\min(1, 2)×\min(2, 3)=2$.

$S=(2,2,1)$: $\min(1, 1)×\min(2, 2)×\min(1, 3)=2$

$S=(3,1,1)$: $\min(1, 1)×\min(1, 2)×\min(1, 3)=1$.

Thus, the algorithm should print their sum: $f(3, 5)=3+4+2+2+2+1=14$.

================

My attempts: Obviously you cannot enumerate all $S$, otherwise the complexity blows up. I actually have no idea about it at all. After searching for accepted solutions, I find that:

$f(n, m) = [x^{m-n}](1-x)^{-2n}\prod_{k=1}^\infty(1-x^k) \tag{2}$.

For example when $n=2, m=3$, the coefficient of $x$ is $3$, which is related to the Pentagonal number theorem.

However, if $n=2, m=5$, the coefficient of $x^3$ is $6$ while $f(2, 5)=7$. It fails to work. $\{1, [x], [x^2], [x^3]\}(1+x+x^2+x^3)^{4\text{(because 2*n=2*2=4)}} = \{1, 4, 10, 20\}$.

$\{1, [x], [x^2], [x^3]\}(1-x)(1-x^2)(1-x^3) = \{1, -1, -1, 0\}$.

So the coefficient of $x^3$ is $20-10-4=6$.

The below python script might be helpful:

from sympy import *
x = Symbol('x')
expr = expand((1+x+x**2+x**3)**4)
print(expr)

My questions are:

1. Why does formula (2) work?
2. How to handle the min operator in formula (1)?
3. Why should $m \leq 2n$?
4. Is this problem somehow related to the modular forms?

Answer 1

Note: The solution below is slightly expanded from the official editorial, in Japanese.

---

We will use generating function to solve the problem. The value we want can be found by $$\left[x^m\right] \prod_{i=1}^n (1x^1 + 2x^2 + 3x^3 + \cdots + ix^i + ix^{i+1} + ix^{i+2} + \cdots)$$ where $[x^k] p(x)$ denotes the coefficient of the $x^k$ term of $p(x)$. Note that if the original problem used $S_i$ instead of $\min(i, S_i)$, then we would use $(1x^1 + 2x^2 + 3x^3 + \cdots)$ in the expression above instead of $(1x^1 + 2x^2 + 3x^3 + \cdots + ix^i + ix^{i+1} + ix^{i+2} + \cdots)$.

We can simplify the product above: \begin{align*} & \prod_{i=1}^n (1x^1 + 2x^2 + 3x^3 + \cdots + ix^i + ix^{i+1} + ix^{i+2} + \cdots) \\ =\: & \prod_{i=1}^{n} \Big((1x^1 + 2x^2 + 3x^3 + \cdots) - (1x^{i+1} + 2x^{i+2} + 3x^{i+3} + \cdots)\Big) \\ =\: & x^n \prod_{i=1}^{n} \Big((1x^0 + 2x^1 + 3x^2 + \cdots) - (1x^{i} + 2x^{i+1} + 3x^{i+2} + \cdots)\Big) \\ =\: & x^n \prod_{i=1}^{n} \left(\frac{1}{(1-x)^2} - \frac{x^i}{(1-x)^2}\right) \\ =\: & x^n \prod_{i=1}^{n} \left(\frac{1-x^i}{(1-x)^2}\right) \\ =\: & \frac{x^n}{(1-x)^{2n}} \prod_{i=1}^{n} (1-x^i). \end{align*}

So, we want to find the value of $$\left[x^{m-n}\right] \frac{\prod_{i=1}^{n} (1-x^i)}{(1-x)^{2n}}.$$

Using the assumption that $m-n \leq n$, we can change the upper bound of the product; the value above is equal to $$\left[x^{m-n}\right] \frac{\prod_{i=1}^{\infty} (1-x^i)}{(1-x)^{2n}}.$$

(Why? Because we are only interested in the coefficient of the $x^{m-n}$ term. Hence, the terms $(1-x^{n+1})$, $(1-x^{n+2})$, $\dots$ would never affect the coefficient of the $x^{m-n}$ term when we are under the assumption that $m-n \leq n$.)

Finally, we can now use the pentagonal number theorem which states that $$\prod_{i=1}^{\infty} (1-x^i) = \sum_{j = -\infty}^{\infty} (-1)^j x^{j(3j-1)/2}.$$ We can also write $$\left(\frac{1}{1-x}\right)^{2n} = \left(1 + x + x^2 + \cdots\right)^{2n}.$$

It should be trivial to find the coefficient of $x^{m-n}$ from the product of the two expressions above. First, we find all terms of $ \sum_{j = -\infty}^{\infty} (-1)^j x^{j(3j-1)/2}$ with degree at most $m-n$. Let these terms be $a_1 x^{e_1}$, $a_2 x^{e_2}$, $\dots$, $a_K x^{e_K}$. Then our answer is \begin{align*} & \left[x^{m-n}\right] \left((a_1 x^{e_1} + a_2 x^{e_2} + \cdots + a_K x^{e_K})(1+x+x^2+\cdots)^{2n}\right) \\ =\: & \left[x^{m-n}\right] \left(\sum_{i=1}^K a_i x^{e_i} (1+x+x^2+\cdots)^{2n}\right) \\ =\: & \sum_{i=1}^K a_i \cdot \left( \left[x^{m-n-e_i}\right](1+x+x^2+\cdots)^{2n}\right) \\ =\: & \sum_{i=1}^K a_i \binom{(m-n-e_i) + (2n-1)}{2n-1} \\ =\: & \sum_{i=1}^K a_i \binom{m+n-e_i-1}{2n-1}. \end{align*}