# In how many ways can I write $0$ as a sum of $n\; 0s, 1s \;\text{and}\; -1s?$

In how many ways can I write $$0$$ as a sum of $$n\; 0s, 1s \;\text{or}\; -1s?$$ (Taking the order into account). I suspect there is no closed formula to express the result, but I'd like someone to confirm it, or deny it.

Edit:
e.g., if $$n=3$$
\begin{aligned}0&=\;\;\;0+0+0,\\ 0&=\;\;\;1-1+0,\\ 0&=\;\;\;1+0-1,\\ 0&=\;\;\;0+1-1,\\ 0&=-1+1+0,\\ 0&=-1+0+1,\\ 0&=\;\;\;0-1+1.\end{aligned} So for $$n=3\;$$ there are $$7$$ ways.

• Set up a recurrence perhaps. – paw88789 Dec 29 '18 at 16:35
• do you mean n each or a total of n? – player100 Dec 29 '18 at 16:45
• Sorry I meant that in total, the number of 0's, 1's and -1's is n – Lucio Tanzini Dec 29 '18 at 16:59
• @MJD Thsnks for pointing out that I'd missed the $n$. I've deleted the answer! – timtfj Dec 29 '18 at 17:11
• I'd start here: for each $n$, we can choose how many times $0$ occurs ,and how many times $1$ occurs. $-1$ then has to match $1$. So if $0$ is used $r$ times and $1$ is used $s$ times, $r=n-2s$.Then for each choice of $r$ and $s$ you've got a defined permutation problem, with $r, s$ and $s$ items.. – timtfj Dec 29 '18 at 17:25

## 2 Answers

$$s(n) = \sum_{k=0}^{n/2} \binom{n}{n-2k} \cdot \binom{2k}{k}$$ The first term is the number of ways to arrange the zeroes, and then the second term arranges the parities. Now, we can simplify further:

$$s(n) = \sum_{k=0}^{n/2} \frac{2k!}{2k!} \cdot \frac{n!}{(n-2k)!(k!)(k!)} = \sum_{k=0}^{n/2} \frac{n!}{(n-2k)!(k!)(k!)}$$

Edit: put a few values into the OIES and came across trinomial coeffecients. In particular, s(n) is the n-th central trinomial coefficient, which has several closed forms, which you can find in the second link.

• This looks wrong to me. There are $k$ $1$'s, $k$ $(-1)$'s and $n-2k$ zeroes, so the denominator should be $(k!)^2(n-2k)!$. – timtfj Dec 29 '18 at 19:07
• Whoops yeah I forgot a term – Zachary Hunter Dec 29 '18 at 19:12
• Yes, I got the same formula. Do you think It can be simplified into a closed formula? – Lucio Tanzini Dec 29 '18 at 19:31
• @LucioTanzini nothing immediately comes to mind without getting my hands dirty, but I’m thinking on it. – Zachary Hunter Dec 29 '18 at 19:37
• Update: found closed form. – Zachary Hunter Dec 29 '18 at 20:43

The number of $$0s, 1s$$ and $$-1s$$ possible for a particular $$n$$ can be seen by the number of solutions to:

$$2p+q=n| p,q \in \Bbb Z^+$$

This can be done in $$\frac{n+1}{2}$$ ways for odd $$n$$ and $$\frac{n+2}{2}$$ ways for even $$n$$

You'll just need to account for positioning after this.

• Yes, but I'm afraid positioning is the main problem Indeed – Lucio Tanzini Dec 29 '18 at 17:34