Count number of ballot paths of length $2n$ that are unchanged when reversed and complemented 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}$.

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.