11
$\begingroup$

In how many ways can the integers $1,2,\ldots,n$ be divided into two groups with the same sum?

I have tried calculating some of these values for small $n$, but cannot seem to find a pattern.

Any help is appreciated! :)

$\endgroup$
4
  • 4
    $\begingroup$ Sometimes none, when $n$ is of shape $4k+1$ or $4k+2$. $\endgroup$ May 24, 2015 at 7:47
  • $\begingroup$ I don't think I can help, but what exactly is your question? Given a sum, how many subsets of size two of $\{1...n\}$ give this sum? Or is it how many distinct sums are given from grouping two of each of the first $n$ integers (including 1?)? $\endgroup$
    – Jared
    May 24, 2015 at 7:54
  • $\begingroup$ I don't know if I can make it more clear, but I can provide an example: for $n=7$ I am trying to determine in how many ways the intergers $1,2,\ldots,7$ can be divided in two groups with the same sum (here $14$). So one way to do that is $1+6+7 = 14 = 2+3+4+5$ $\endgroup$
    – user114158
    May 24, 2015 at 7:57
  • 6
    $\begingroup$ A search on the Online Encyclopedia of Integer Sequences yields entry oeis.org/A063865 , which tells you various ways to compute this number as well as an asymptotic formula for it. $\endgroup$ May 24, 2015 at 8:05

1 Answer 1

1
$\begingroup$

Obviously $1+2+\ldots+n = \frac{n(n+1)}{2}$ has to be an even number (hence that is possible only for $n\in\{0,3\}\pmod{4}$) and in such a case the answer is given by half the coefficient of $x^{\frac{n(n+1)}{4}}$ in the product $$ \prod_{k=1}^{n}\left(1+x^k\right). $$ See partition function and this article. In the case $n=7$, the answer is just $\color{red}{4}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .