4

The question I am really asking is, how many sequences $a_{n}$ satisfy the inequality for a given $N$. Clearly the number is even due to the symmetry of the problem. Also there is no solutions for $N\equiv 1 \mod 4$ or $N\equiv 2 \mod 4$ since the number of the first $N$ natural numbers is odd in these cases (you cannot halve the amount into a positive and negative set).

So for example:

$N=3\Longrightarrow$ $$1 + 2 - 3=0 \quad\quad -1 - 2 + 3=0$$ $N=4\Longrightarrow$ $$+1 - 2 - 3 +4=0 \quad\quad -1 + 2 + 3 -4=0$$ $N=5\Longrightarrow$ $$\text{No solutions.}$$ $N=6\Longrightarrow$ $$\text{No solutions.}$$ $N=7\Longrightarrow$ $$\geq 4 \,\,\text{cases, don't want to write them out.}$$

Mohammad Riazi-Kermani
  • 68,728
Joshua Farrell
  • 1,526
  • 2
    In fact, $N=7$ has exactly 4 cases. You might want to have a look at https://oeis.org/A058377 , which doesn't have a lot of great information about the sequence but has some good references. These sequences are loosely related to Golygons, and if you dig into those you should be able to find some information on generating functions and recurrence relations that might be adaptable to getting more information about these values. – Steven Stadnicki Apr 02 '18 at 21:47
  • 1
    Hmm, it would be the coefficient of $x^0$ in $(x+x^{-1}) (x^2+x^{-2}) \cdots (x^n+x^{-n})$ - not sure if that's of much use, though. – Daniel Schepler Apr 02 '18 at 21:50
  • @StevenStadnicki I suspect $N=7$ has $8$ cases, and the OEIS A058377 list is for those with $a_1=1$, so half those asked for here – Henry Apr 02 '18 at 22:02

1 Answers1

5

I assume that we let $a_n = \{0, 1\}$, or else the number of solutions is obviously infinite.

The number of different $a_n$ is equal to the number of different subsets of $\{1, \dots, n\}$ that sum to $\frac{1}{4}n(n+1)$. As you've noticed, this is only possible when $n \bmod 4 \in \{0, 3\}$.

This is also equivalent to the number of integer partitions of $\frac{1}{4}n(n+1)$ where each part is distinct and at most $n$. Luckily, this has a simple generating function form:

$$[z^{n(n+1)/4}]\prod_{k=1}^n(1 + z^k)$$ This gives initial values:

$$2, 2, 0, 0, 8, 14, 0, 0, 70, 124, 0, 0, 722, 1314$$

Which leads to the correct OEIS sequence: A063865.

orlp
  • 10,508