1
$\begingroup$

I am looking for a proof that the number of ballot paths of length $2n$ (from Bertrand's Ballot Problem) that are unchanged when reversed and complemented is $n \choose [n/2]$. I know that the total number of ballot paths for $(a,b)$ is ${a+b \choose a} - {a+b \choose a-1}$ since ${a+b \choose a}$ is the number of lattice paths from $(0,0)$ to $(a,b)$ and ${a+b \choose a-1}$ are the number of paths crossing the line $y=x$ which is an invalid ballot path. I am trying to use an approach by representing vertical steps with $1$ and horizontal steps with $0$. So a path would be something like $[0,0,1,0,1,1]$ and the reversed and complemented path in this example would be unchanged. I realize also that for a path $[s_0,s_1,...,s_{2n}]$ where each $s_i$ is a $1$ or $0$ must have the property that $s_i \neq s_{2n-i}$.

$\endgroup$
1
$\begingroup$

The second half of such a path is completely determined by the first half, so you’re really just counting the possible first halves. They are precisely the paths of length $n$ that never rise above the diagonal. Such paths can reach any of the points $\langle n-k,k\rangle$ such that $0\le k\le n-k$, so $0\le k\le\left\lfloor\frac{n}2\right\rfloor$, and the total number of such paths is

$$\begin{align*} \sum_{k=0}^{\lfloor n/2\rfloor}\left(\binom{n}{n-k}-\binom{n}{n-k-1}\right)&=\sum_{k=n-\lfloor n/2\rfloor}^n\left(\binom{n}k-\binom{n}{k+1}\right)\\ &=\binom{n}{n-\lfloor n/2\rfloor}-\binom{n}{n+1}\\ &=\binom{n}{n-\lfloor n/2\rfloor}\\ &=\binom{n}{\lceil n/2\rceil}\;, \end{align*}$$

since the second summation clearly telescopes.

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