2
$\begingroup$

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 :)

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 27 '19 at 13:25
  • $\begingroup$ 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. $\endgroup$ – narek Bojikian Oct 27 '19 at 13:36
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – narek Bojikian Oct 27 '19 at 23:09
  • $\begingroup$ It worked!! thank you :D $\endgroup$ – narek Bojikian Oct 27 '19 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.