Balanced ternary: combinatorial sum I was working on the following problem:

In balanced ternary, how many numbers with $2n$ digits can be expressed using the same number of $+1$ and $-1$ digits, where $n$ is an integer?

After some combinatorial shenanigans, I ended up with this sum as my answer:
$$\sum_{k=0}^{n-1} \binom{2n-1}{2k}\binom{2n-2k-1}{n-k}$$
But I cannot figure out how to evaluate it. It does not seem to telescope, and WA would not give me a formula.
Does anybody know how to evaluate this sum?
 A: Here we show OPs binomial sum is closely related to central trinomial coefficients which do not have a representation in closed form.

In the following we use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write e.g.
  \begin{align*}
[z^n](1+z)^k=\binom{n}{k}
\end{align*}
We obtain
  \begin{align*}
\color{blue}{\sum_{k=0}^{n-1}}&\color{blue}{\binom{2n-1}{2k}\binom{2n-2k-1}{n-k}}\tag{1}\\
&=\sum_{k=0}^{n-1}\frac{(2n-1)!}{(2k)!(2n-2k-1)!}\cdot\frac{(2n-2k-1)!}{(n-k)!(n-k-1)!}\\
&=\sum_{k=0}^{n-1}\frac{(2n-1)!}{(n-k-1)!(n+k)!}\cdot\frac{(n+k)!}{(2k)!(n-k)!}\\
&=\sum_{k=0}^{n-1}\binom{2n-1}{n+k}\binom{n+k}{n-k}\\
&=\sum_{k=0}^{\infty}[z^{n+k}](1+z)^{2n-1}[t^{n-k}](1+t)^{n+k}\tag{2}\\
&=[t^n](1+t)^n\sum_{k=0}^{n-1}\left(t(1+t)\right)^k[z^k]\frac{(1+z)^{2n-1}}{z^n}\tag{3}\\
&=[t^n](1+t)^n\frac{(1+t(1+t))^{2n-1}}{(t(1+t))^n}\tag{4}\\
&=\color{blue}{[t^{2n}](1+t+t^2)^{2n-1}}\tag{5}
\end{align*}

Comment:


*

*In (2) we apply the coefficient of operator twice and set the upper limit of the sum to $\infty$ without changing anything, since we are adding zeros only.

*In (3) we use the linearity of the coefficient of operator, do some rearrangements and use the rule
\begin{align*}
[z^{p-q}]A(z)=[z^p]z^qA(z)
\end{align*}

*In (4) we apply the substitution rule of the coefficient of operator with $z:=t(1+t)$
\begin{align*}
A(t)=\sum_{k=0}^\infty a_k t^k=\sum_{k=0}^\infty a^k [z^k]A(z)
\end{align*}

*In (5) we do some simplifications and use the same rule as in (3).

We observe the binomial sum (1) represents essentially central trinomial coefficients
  \begin{align*}
[t^n](1+t+t^2)^n
\end{align*}
  for which there is no closed form available. In fact we obtain the central trinomial coefficients $[t^{2n}]$ by multiplying (5) with $1+t+t^2$. 

Notes from the experts:

D.E. Knuth gives in Concrete Mathematics, Appendix A 7.56 the following representation of a more general expression
\begin{align*}
[t^n](a+bt+ct^2)^n=[t^n]\frac{1}{\sqrt{1-2bt+(b^2-4ac)t^2}}
\end{align*}
He states that according to the paper Hypergeometric Solutions of Linear Recurrences with Polynomial Coeffcients by Marko Petkovšek there exists a closed form (more precisely: a closed form solution as a finite sum of hypergeometric terms) if and only if
  $$\color{blue}{abc(b^2-4ac)=0}$$
In case of central trinomial coefficients we have $a=b=c=1$. Since then the expression $abc(b^2-4ac)=-3\ne 0$
  there is no such closed form in particular for the central trinomial coefficients.

A: What  follows  is   more  of  a  comment  on  the   formula  cited  by
@MarkusScheuer, which we  can actually prove. Observe  that when $a=0$
we get
$$[t^n] (a+bt+ct^2)^n = [t^n] t^n (b+ct)^n = b^n$$
so we may suppose that $a\ne 0.$
We start from
$$[t^n] (a+bt+ct^2)^n =
\frac{1}{2\pi i}
\int_{|t|=\epsilon}
\frac{1}{t^{n+1}} (a+bt+ct^2)^n 
\; dt.$$
We put
$$w = \frac{t}{a+bt+ct^2} = \frac{1}{a} t + \cdots$$
The series  tells us  that the  circle $|t|=\epsilon$  is mapped  to a
closed circle in  $w$ (one turn) of dominant  radius $\epsilon/a$ plus
lower order fluctuations, which we may deform to a circle $|w|=\gamma$ 
inside said contour, where the map is also analytic in $w.$ This means
that from the two branches
$$t = \frac{1-bw\pm \sqrt{(b^2-4ac)w^2-2bw+1}}{2cw}$$
we must choose the branch
$$t = \frac{1-bw-\sqrt{(b^2-4ac)w^2-2bw+1}}{2cw}
= aw + \cdots$$
(the  other one  has  a  singularity at  the  origin). This  converges
(distance to the nearest singularity)  either with radius $1/2/b$ when
$b^2-4ac=0$ or the distance from the origin to whichever of
$$\frac{-b\pm 2\sqrt{ac}}{4ac-b^2}$$
is  closer. We  take  $\gamma$  so that  $|w|=\gamma$  is inside  this
region. With
$$dt = \frac{(a+bt+ct^2)^2}{a-ct^2} \; dw
= \frac{t^2/w^2}{a-ct^2} \; dw.$$ 
we thus finally obtain the integral
$$\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^n} \frac{1}{t} \frac{t^2/w^2}{a-ct^2}
\; dw
= \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{n+1}} \frac{t/w}{a-ct^2}
\; dw.$$
We claim that
$$\frac{t/w}{a-ct^2} = \frac{1}{1-bw-2ctw}.$$
This is equivalent to
$$t(1-bw-2ctw) = w (a-ct^2)$$
or
$$t = w (a + bt + 2ct^2 - ct^2)
= w \times t / w$$
which holds by inspection. Now
$$\frac{1}{1-bw-2ctw}
= \frac{1}{\sqrt{(b^2-4ac)w^2-2bw+1}}$$
and we have shown that
$$\bbox[5px,border:2px solid #00A000]{
[t^n] (a+bt+ct^2)^n
= [w^n] \frac{1}{\sqrt{(b^2-4ac)w^2-2bw+1}}.}$$
A: In balanced ternary, all permutations of $n$ each of $+1$ and $-1$ digits are fair game since the leading digit being non-zero is the only requirement. Therefore the count of expressible numbers is the number of ways to choose $n$ positions for the $+1$ or $-1$ digits, which is $\binom{2n}n$ – the central binomial coefficients.
