Let $A=\{1,...,n\}$. Two subsets of $A$, not necessarily distinct, chosen uniformly at random. What is the probability that both subsets have the same sum? Alternatively, is there a known upper bound?
1
-
3$\begingroup$ Just to be sure, "subsets … chosen uniformly at random" means that each subset has probability $2^{-n}$ of being chosen (so that the question is really how many pairs of subsets have the same sum), right? $\endgroup$– LSpiceCommented Aug 16, 2020 at 23:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Assuming the two subsets are selected independently, the probability in question is $$p_n=a_n/2^{2n},$$ where $a_n$ the sum of the squares of the coefficients in the polynomial $$\prod_{k=1}^n (1+x^k).$$ The sequence $(a_n)$ is the sequence A047653, and its asymptotics, given on that page, is $$a_n\sim\frac{\sqrt{3/\pi}\,4^n}{n^{3/2}} \tag{1}$$ (as $n\to\infty$). So, $$p_n\sim\frac{\sqrt{3/\pi}}{n^{3/2}}.\tag{2}$$
For (1), A047653 refers to Vaclav Kotesovec, where I have been unable to find a link/reference to (1). However, the equivalent relation (2) was actually proved by van Lint. (I found a link to van Lint on the related OEIS page A000980.)
answered Aug 17, 2020 at 0:48
-
2
-
1$\begingroup$ @LSpice : Thank you for your comment. I am sorry for the confusion. I was hesitating between $s_n$ (for the sum of the squares) and $a_n$ (the notation used on the linked page). Now this typo is fixed. $\endgroup$ Commented Aug 17, 2020 at 2:37
-
$\begingroup$ The asymptotic comes from the integral $$4^n\int_{0}^{1} \left(\prod_{k=1}^{n} \cos^2(\pi kt) \right)dt$$. But how to calculate the integral? $\endgroup$ Commented Aug 17, 2020 at 2:43
-
$\begingroup$ @AlapanDas : I have added a response to your comment. $\endgroup$ Commented Aug 17, 2020 at 15:00