Let $x^2=y^2=1$ and $xy\neq yx$. There are $\binom{2n}{n}$ expressions of length $2n$ in $x$ and $y$ that are equal to $1$. This question is motivated by this link.  The statement is as follows.  (Edit: Even if there are already two great answers, I would love to have a couple more answers.  Especially, I would like to see another, hopefully more combinatorial, proof of the bonus question below.)

Question.  Let $x$ and $y$ be noncommuting variables such that $x^2=y^2=1$.  Multiplication is associative.  Prove that, for each positive integer $n$, there are exactly $\displaystyle\binom{2n}{n}$ expressions of length $2n$ in $x$ and $y$ that are equal to $1$.  For example, when $n=1$, there are $2$ such expressions: $xx$ and $yy$.  When $n=2$, there are $6$ such expressions: $xxxx$, $xxyy$, $xyyx$, $yxxy$, $yyxx$, and $yyyy$.

For a technical clarification, consider the free product $G:=C_2*C_2$, where $C_2$ is the cyclic group of order $2$.  Then, $G$ has the following presentation: $G=\langle x,y\,|\,x^2=y^2=1\rangle$.  We want to find the number of strings of length $2n$ formed by $x$ and $y$ that can be reduced to $1$.
I would like to see how to prove this statement using a combinatorial argument, such as constructing a bijection, finding a generating function, etc.  However, any proof that is different from the proofs below is welcome.  (If you can visit the referred link and give it a combinatorial proof, that would be most appreciated.)
Bonus.  Let $s$ be a reduced word in $x$ and $y$ (that is, it can no longer be reduced using the rules $x^2=y^2=1$).  If $s$ has length $k$, then show that, for any integer $n\geq 0$, there are exactly $\displaystyle\binom{n+2k}{n}$ words in $x$ and $y$ of length $k+2n$ that can be reduced to $s$.

Elementary Proof
We work in $R:=\mathbb{Z}[x,y]$.  Note that
$$x+y=x+xxy=x(1+xy)$$
and
$$(x+y)^2=\big(x(1+xy)\big)^2=x(1+xy)\,x(1+xy)\,.$$
Because
$$(1+xy)x=x+xyx=x(1+yx)\,,$$
we have
$$(x+y)^2=xx(1+yx)(1+xy)=yx(1+xy)^2=(xy)^{-1}(1+xy)^2\,.$$
Therefore,
$$(x+y)^{2n}=\Big((xy)^{-1}(1+xy)^2\Big)^n=(xy)^{-n}(1+xy)^{2n}\,.$$
Thus, there are $\displaystyle\binom{2n}{n}$ expressions of length $2n$ that are equal to $1$.

Algebraic Proof
Here is another approach borrowing the idea from Julian Rosen.  Let $R$ denote the unital $\mathbb{Z}$-algebra generated by $x$ and $y$ (i.e. $R=\mathbb{Z}[G]$).  Then, the $\mathbb{Z}$-algebra homomorphism $$\varphi:R\to\text{Mat}_{2\times2}\big(\mathbb{Z}[t,t^{-1}]\big)$$ defined by sending
$$x\mapsto\begin{bmatrix}0&1\\1&0\end{bmatrix}\text{ and }y\mapsto\begin{bmatrix}0&t^{-1}\\t&0\end{bmatrix}$$
is injective.  We can easily see that
$$\varphi\big((x+y)^2\big)=t^{-1}(1+t)^2\,I\,,$$
where $I$ is the $2$-by-$2$ identity matrix.  Hence,
$$\varphi\big((x+y)^{2n}\big)=t^{-n}(1+t)^{2n}\,I\,,$$
and the assertion follows immediately.

Geometric Proof
Using the notations from the geometric proof in my answer here, recall that $x=\sigma_\alpha$ and $y=\sigma_\beta$.  Thus,
$$(x+y)^2=2+\sigma_\alpha\sigma_\beta+\sigma_\beta\sigma_\alpha=2+\rho_{2\alpha-2\beta}+\rho_{2\beta-2\alpha}\,.$$
(It can also be proven that
$$\sigma_{\theta_1}+\sigma_{\theta_2}=2\,\cos(\theta_1-\theta_2)\,\sigma_{\frac{\theta_1+\theta_2}{2}}$$
for all $\theta_1,\theta_2\in\mathbb{R}$.)  Note that
$$\rho_{+\theta}+\rho_{-\theta}=2\,\cos(\theta)$$
for all $\theta\in\mathbb{R}$.  Hence,
$$(x+y)^2=2\,\big(1+\cos(2\alpha-2\beta)\big)=2^2\,\big(\cos(\alpha-\beta)\big)^2\,.$$
Then, the number of expressions of length $2n$ that are equal to $1$ is given by
$$\begin{align}\frac{1}{(2\pi)^2}\,\int_0^{2\pi}\,\int_0^{2\pi}\,(x+y)^{2n}\,\text{d}\beta\,\text{d}\alpha&=\frac{1}{(2\pi)^2}\,\int_0^{2\pi}\,\int_0^{2\pi}\,2^{2n}\,\big(\cos(\alpha-\beta)\big)^{2n}\,\text{d}\beta\,\text{d}\alpha
\\&=\frac{1}{(2\pi)^2}\,2^{2n}\,\frac{\pi}{2^{2n-1}}\,\binom{2n}{n}\,(2\pi)=\binom{2n}{n}\,.
\end{align}$$

We can note that a necessary condition for an expression to evaluate to $1$ is that the number of $x$ (or $y$) occurrences in odd position be equal to the number of $x$ (or $y$, respectively) occurrences in even position, because every $x$ or $y$ must have its "companion", and the inner variables between each couple can be simplified only if their number is even.
We need to show that that condition is also sufficient.
For every expression with the condition above there are always two adjacent $x$ or two adjacent $y$. Suppose that is false: suppose one variable ($x$ or $y$) is at position $1$, then the other variable must be at position $2$, then the same variable at position $1$ must be at position $3$ and so on, thus one variable is on all odd positions and one variable on all even positions, which contradicts the original assumption about the above condition. Once we have eliminated the two adjacent equal variables, we can repeat again and again the process till we simplify the expression to $1$.
Finally we need to count all expressions that satisfy the condition. We have $n$ odd positions and $n$ even positions; the number of expressions with $2k$ $x$ in it is:
$${n \choose k}{n \choose k}$$
because we first choose $k$ $x$ in odd position and then $k$ $x$ in even position.
So the whole number of wanted expressions is:
$$\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}$$
which is well known and follows from Vandermonde's identity, which in turn has a combinatorial proof.
