I am practicing combinatorics problems and came across this problem:
How many sets of 10 distinct positive integers sum to at most 2021?
Here is my approach to get the answer: First, we consider the following: If $$\sum_{i=1}^{10}x_i = n$$ then the number of possible solutions(where order does not matter) is $$\frac{n+9 \choose n}{10!}$$.
The minimum $n$ is 55. ($\sum_{i=1}^{10} i$) . The maximum is 2021. Therefore, the total number of solutions is: $$ \sum_{n=55}^{2021}\frac{n+9 \choose n}{10!} $$
Is this correct? If not where is the mistake?
Supposing that we want $k$ distinct integers that sum to at most $n$ we first choose the minimum value
$$\frac{z}{1-z}$$
and then we choose $k-1$ differences between consecutive values
$$\left(\frac{z}{1-z}\right)^{k-1}.$$
The coefficient $[z^n]$ of the product
$$F(z) = \left(\frac{z}{1-z}\right)^k$$
then gives the number of sets of $k$ distinct positive integers with the largest element being $n.$ We want the sum however. Now the minimum value contributes $k$ times, the first difference $k-1$ and so on, the last difference contributes once.
This gives the product
$$G(z) = \prod_{q=0}^{k-1} \frac{z^{k-q}}{1-z^{k-q}} = \prod_{q=1}^k \frac{z^q}{1-z^q}.$$
This coefficient gives the set of $k$ distinct positive integers that sum to exactly $n.$ If we require at most $n$, we sum by multiplying by $1/(1-z)$ and obtain
$$H(z) = \frac{1}{1-z} \prod_{q=1}^k \frac{z^q}{1-z^q}$$
We may write
$$H(z) = \frac{z^{\frac{1}{2} k(k+1)}}{1-z} \prod_{q=1}^k \frac{1}{1-z^q} = z^{\frac{1}{2} k(k+1)} J(z)$$
so that
$$J(z) = \frac{1}{1-z} \prod_{q=1}^k \frac{1}{1-z^q} \quad\text{and}\quad H_{n,k} = J_{n-\frac{1}{2} k(k+1), k}.$$
The base case here is $H_{n,k} = 0$ if $n\lt \frac{1}{2} k(k+1)$ and $H_{\frac{1}{2} k(k+1), k} = 1.$
Differentiate to get
$$J'(z) = \frac{1}{1-z} \prod_{q=1}^k \frac{1}{1-z^q} \left[ \frac{1}{1-z} + \frac{1}{z} \sum_{q=1}^k \frac{q z^q}{1-z^q}\right].$$
Extract coefficients on $[z^{n-1}]$ to get
$$n J_{n,k} = \sum_{p=0}^{n-1} J_{p,k} + \sum_{q=1}^k q \sum_{p=1}^{\lfloor n/q \rfloor} J_{n-pq,k}.$$
We find the recurrence
$$\bbox[5px,border:2px solid #00A000]{ J_{n,k} = \frac{1}{n} \left[ \sum_{p=0}^{n-1} J_{p,k} + \sum_{q=1}^k q \sum_{p=1}^{\lfloor n/q \rfloor} J_{n-pq,k}\right]}$$
where $n\ge 1$ and $J_{0,k} = 1.$
We implement this as a memoized recurrence in our favorite CAS and obtain for the pair $(n,k) = (2021, 10)$
$$\bbox[5px,border:2px solid #00A000]{ H_{2021, 10} = 75434038103498084111.}$$
Seeing that we are in the eleventh month of the year $2022$ we also find
$$\bbox[5px,border:2px solid #00A000]{ H_{2022, 11} = 1212319110727843596031.}$$
Reply to comments, some time later. It was asked why we differentiate. Well if we have an equation for a generating function it defines the coefficients being the same on the LHS and the RHS. So that does not tell us about the relation between the coefficients. If we then differentiate however we obtain some type of relation between coefficients that often leads to a recurrence. So that's why. It was also asked why we extract coefficients. The coefficient gives us the desired number of sets that sum to at most $n$ so it is the quantity we are interested in. Finally, how do we extract coefficients, we get for example
$$[z^{n-1}] \frac{1}{z} \sum_{q=1}^k \frac{q z^q}{1-z^q} J(z) = [z^n] \sum_{q=1}^k \frac{q z^q}{1-z^q} J(z) \\ = [z^n] \sum_{q=1}^k q (z^q + z^{2q} + z^{3q} + \cdots) J(z) \\ = [z^n] \sum_{q=1}^k q (z^q + z^{2q} + z^{3q} + \cdots + z^{\lfloor n/q\rfloor q}) J(z) \\ = \sum_{q=1}^k q [z^n] \sum_{p=1}^{\lfloor n/q \rfloor} z^{pq} J(z) \\ = \sum_{q=1}^k q \sum_{p=1}^{\lfloor n/q \rfloor} [z^{n-pq}] J(z) = \sum_{q=1}^k q \sum_{p=1}^{\lfloor n/q \rfloor} J_{n-pq, k}.$$