# Polynomial multiplications and counting

I came across the following problem. Given a set of $$n$$ positive integers $$A$$ and an integer $$k$$. Let $$S$$ be the set of integers that are the sum of $$k$$ distinct integers in $$A$$. Mathematically speaking $$S = \{s ; \text{ there exists } P \in {A\choose k} \text{ such that } s = \sum_{a \in P} a\}.$$ The object of the problem is to compute $$S$$ and for each integer $$s \in S$$, we have to find how many subsets of $$A$$ of size $$k$$ there are that sum up to $$s$$.

The constraints: $$k$$ is very small (can be considered constant) and I am looking for something subquadratic in $$n$$.

I tried to formulate the problem as a polynomial multiplication problem and solve it using FFT. So I built the polynomial $$\rho$$ as follows. I started with $$\rho = 0$$ and For each element $$a \in A$$, I added $$x^a$$ to $$\rho$$. Now for each exponent $$r$$ in $$\rho^k$$, the coefficient represents the number of combinations of $$k$$ elements in $$A$$ that sum up to $$r$$. However, these combinations include using the same element more than one time and count reorderings of the same subset.

I have been trying the following ideas:

• Rebuilding my polynomial to count better.
• Build and multiply different polynomials each representing a part of the problem (with some kind of divide and conquer technique).
• Edit the polynomial resulting from the multiplication with some combinatorial argument (Subtract the numbers resulting from counting twice etc.). This helps when $$\rho^2$$ but could not make it work for higher values of $$k$$.

I appreciate any thoughts or hints about the problem :)

• You should be able to cancel out sums in which elements are used multiple times. This will require some case analysis, but sounds completely feasible. – Yuval Filmus Oct 27 '19 at 13:25
• It was easy for $k=2$ but I couldn't find a formula in general. maybe that is why $k$ is always small and I have to do it by hand. – narek Bojikian Oct 27 '19 at 13:36

You already explained what to do when $$k = 2$$. Let's see what to do when $$k = 3$$. Let $$P_i$$ be the polynomial corresponding to $$iS$$ (for example, the solution for $$k = 2$$ is $$(P_1^2 - P_2)/2$$).
We can construct the following table: $$\begin{array}{c|ccc} & aaa & aab & abc \\\hline P_1^3 & 1 & 1 & 1 \\ 3P_2 P_1 & 3 & 1 & 0\\ P_3 & 1 & 0 & 0 \end{array}$$ So the solution for $$k = 3$$ is $$(P_1^3 - 3P_2P_1 + 2P_3)/6$$.
More generally, the solution will involve terms corresponding to all partitions of $$k$$. The coefficients presumably appear in some change-of-basis formula for symmetric polynomials, and you can find formulas by browsing monographs on the subject.
• It seems to work with this formula $\rho_i = \frac{1}{i}\sum\limits_{j=1}^i -1^{j-1}\rho_{i-j} P_j$, where $\rho_i$ is the answer for $k = i$ – narek Bojikian Oct 27 '19 at 23:09