3
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ Well-researched answer: (+1). $\endgroup$ – Marko Riedel Jul 17 '17 at 21:22
  • $\begingroup$ @MarkoRiedel: Thanks, Marko! :-) $\endgroup$ – Markus Scheuer Jul 17 '17 at 22:03
  • 2
    $\begingroup$ 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). $\endgroup$ – Marko Riedel Jul 17 '17 at 22:07
  • $\begingroup$ I proved the formula you cite by way of enrichment of the page. $\endgroup$ – Marko Riedel Jul 18 '17 at 4:09
  • $\begingroup$ @MarkusScheuer Beautiful answer, thank you! $\endgroup$ – Frpzzd Jul 24 '17 at 13:56
1
$\begingroup$

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

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

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.

$\endgroup$

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.