2
$\begingroup$

For any positive integer $n$ (using integer division only), let $P(n)$ denote the number of ways in which the integer $(n^2+n)/4$ can be expressed as a sum of exactly $n /2$ distinct elements of the set $\{1,2,3,\dots, n\}$.

What is $P(n)$ in terms of n? Specifically, how exponential is it? Is this less than $2^{n/2}$?

  • 2
    It's zero if $n$ is not a multiple of 4. Have you run any experiments? like, calculating $P(n)$ for a few small values of $n$?2012-08-24
  • 0
    In this case, I mean integer division. I care about this in cases when n is large.2012-08-24
  • 0
    If you mean integer division, you should edit your question so that it says what you mean instead of saying something different. And small values often give insight into large ones.2012-08-25
  • 2
    So one is meant to interpret \ as a symbol for integer division? Is that a standard notation?2012-08-25
  • 2
    If $n\equiv 0\pmod 4$, it is the constant term of the expression $$\prod_{i=1}^n (xz^{i}+x^{-1}z^{-i})$$ Not sure if that helps any2012-08-25
  • 0
    Here's a heuristic: (I will consider the case n a multiple of 4 for simplicity) If you take the sum of $\frac{n}{2}$ randomly chosen distinct elements from ${1,2,\cdots n}$, you will get an expected value of $\frac{n+n^2}{4},$ but you can get anywhere within a range of $\frac{n^2}{2}.$ I suspect that the expected value will be the most likely value of the sum in this range (and I suspect that this can be proven with a bit of combinatorics), which would imply that $P(n)$ would be at least $\frac{2\binom{n}{n/2}}{n^2}$, and as $\binom{n}{n/2}$ is $\Theta(\frac{2^n}{\sqrt{n}}),$ $P(n)$ should be2012-08-25
  • 0
    (continued) $\Omega(\frac{2^n}{n^{2.5}})$, in particular larger than $2^{\frac{n}{2}}$ for large n.2012-08-25

1 Answers 1