3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Set up a recurrence perhaps. $\endgroup$ – paw88789 Dec 29 '18 at 16:35
  • $\begingroup$ do you mean n each or a total of n? $\endgroup$ – player100 Dec 29 '18 at 16:45
  • $\begingroup$ Sorry I meant that in total, the number of 0's, 1's and -1's is n $\endgroup$ – Lucio Tanzini Dec 29 '18 at 16:59
  • $\begingroup$ @MJD Thsnks for pointing out that I'd missed the $n$. I've deleted the answer! $\endgroup$ – timtfj Dec 29 '18 at 17:11
  • $\begingroup$ 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.. $\endgroup$ – timtfj Dec 29 '18 at 17:25
4
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ 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)!$. $\endgroup$ – timtfj Dec 29 '18 at 19:07
  • $\begingroup$ Whoops yeah I forgot a term $\endgroup$ – Zachary Hunter Dec 29 '18 at 19:12
  • $\begingroup$ Yes, I got the same formula. Do you think It can be simplified into a closed formula? $\endgroup$ – Lucio Tanzini Dec 29 '18 at 19:31
  • $\begingroup$ @LucioTanzini nothing immediately comes to mind without getting my hands dirty, but I’m thinking on it. $\endgroup$ – Zachary Hunter Dec 29 '18 at 19:37
  • $\begingroup$ Update: found closed form. $\endgroup$ – Zachary Hunter Dec 29 '18 at 20:43
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.