# 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?

• Can you do $n=2$ for us ? $++--,+-+-,+--+,-++-,-+-+,--++$ ? – Donald Splutterwit Jul 17 '17 at 1:13

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.

• Well-researched answer: (+1). – Marko Riedel Jul 17 '17 at 21:22
• @MarkoRiedel: Thanks, Marko! :-) – Markus Scheuer Jul 17 '17 at 22:03
• Yes I just read the material from Concrete Math and the Petkovsek paper. I have the first edition of CM and seeing your link I figure I should probably upgrade to the most recent one. Your reference also applies to the first edition (same numbering). – Marko Riedel Jul 17 '17 at 22:07
• I proved the formula you cite by way of enrichment of the page. – Marko Riedel Jul 18 '17 at 4:09
• @MarkusScheuer Beautiful answer, thank you! – Frpzzd Jul 24 '17 at 13:56

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

• Very nice and instructive! (+1) – Markus Scheuer Jul 18 '17 at 6:14
• Thanks! Did you see the following MSE post? – Marko Riedel Jul 24 '17 at 20:58
• I was just working on it. Answer added. :-) – Markus Scheuer Jul 24 '17 at 21:20
• I propose an additional proof at the cited link. – Marko Riedel Jul 24 '17 at 23:18

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.