I have a subset $S=\{x_1, x_2, x_3, ... x_m\}$ with $m$ elements in it. Each of these elements is between $1$ and $m^2$. Given an instance of this problem and a sum, $y$, I want to place an upper bound on the number of subsets of $S$ that can sum up to $y$. Any crude polynomial upper bound would work for me. (I need this upper bound for some proof I am constructing for a cryptography problem).
Number of subsets that add up to a given number
5
$\begingroup$
combinatorics
-
0I mean polynomial upper bound for a general instance – 2011-05-10
1 Answers
4
If all elements are equal to $1$ and $y = m/2$ then the number of subsets is $\binom{m}{m/2} = \Theta\left(\frac{2^m}{\sqrt{m}}\right).$
Here's an example with all elements different. Let $S = \{1,\ldots,m\}$ and $y = (m+1)m/4$. The number of subsets is at least $\binom{m/2}{m/4} = \Theta\left(\frac{2^{m/2}}{\sqrt{m}}\right).$
-
0Right, thanks. Also now i see that since the size of the domain is $2^m$ and the size of the range is $m^3$ (the elements can only sum up to at most $m^3$) the average number of preimages is also exponential. – 2011-05-10