Using the Catalan numbers Here's a question we got for homework:

A soccer match between team A and team B ends with a 9-9 tie. It is
  know that at some point of the game team A had the lead and that later on it was
  team B who had it. How many series's of 18 goals can represent the
  course of the game?
Hint: use the double-reflection technique.

So, this hint doesn't really help me as I don't understand what a double-reflection is.
Other than that: I thought about counting all possible series's which is the Catalan number C9, and then subtract all series's where B scored the first goal, but it's a little vague in my mind.
Any hints that would get me started would be great. Thanks!
 A: Hint: it's probably easier to count the ways that the condition can fail: that is, the number of series where B is winning/tied up to a certain turning point, and then A is winning/tied for the rest of the tournament.
Here's a canonical Catalan-type picture demonstrating this:

The red-and-yellow marked point is the turning point here. Now, how can you use the reflection technique on this to get a Catalan graph where the black line is always above the diagonal? Can you use this to finish the problem?
A: I wasn't able to solve the problem based only on Lopsy's hint, so here's a bit more.
First, it's all well and good to apply nifty reflection tricks, but they're a lot easier to find if you already know the result you're aiming for; so let's first mechanically derive the result using generating functions and then think about how to get it more elegantly.
The sequences that don't fulfill the requirement consist of a segment (possibly empty) in which $B$ is in the lead, followed by a segment (possibly empty) in which $A$ is in the lead.  Such segments where the lead doesn't change are counted by the Catalan numbers, so these invalid sequences are counted by a convolution of the Catalan numbers with themselves (with the sum running over the point where the lead changes). In terms of generating functions, that means that the generating function $G$ of the invalid sequences is the square of the generating function $C$ of the Catalan numbers. With
$$C(x)=\frac{1-\sqrt{1-4x}}{2x}\;,$$
that yields
$$G(x)=C(x)^2=\frac1x\left(\frac{1-\sqrt{1-4x}}x-1\right)=\frac{C(x)-1}x\;.$$
Thus, $G$ is just $C$ with the constant term removed and shifted down by one, that is, $G_n=C_{n+1}$.
Knowing the result, it's a bit easier to see how to apply reflection. The problem in pursuing Lopsy's hint is that it's not obvious how to get a bijection – it's easy to reflect the part below the diagonal upward, but it's not clear what bijection that establishes. Knowing that we want to end up with the Catalan numbers one higher, we can use the extra slot to make the reflected sequence unique: By inserting an up-step before the reflected segment and a down-step after it, we get a bijection from the invalid sequences to the diagonal-avoiding sequences with two more steps, since the turning point is now uniquely marked as the last intersection with the diagonal in the new sequence.
A: This follows closely Lopsy's suggestion and Joriki's answer. I copy here my answer to a problem from sci.math.

Question: Suppose there are $n$ '$-1$' and $n$ '$+1$'. What is the recurrence relation for the permutations where all the subtotals beginning from the left is non-negative?
Answer: Let us call an arrangement of $n$ '$+1$'s and $n$ '$-1$'s a walk of type $n$. Let us also call a walk that has no negative partial sum a unilateral walk.
Let $w(n)$ be the number of unilateral walks of type $n$.  Let us classify these walks by the type of their smallest initial subwalk.  Those whose smallest initial subwalk is of type $k$ look like this:
$$
+1<\text{a unilateral walk of type }k{-}1>-1<\text{a unilateral walk of type }n{-}k>
$$
By considering all possible types of initial subwalk, we get the following recusive relation:
$$
w(n) = w(0)w(n-1) + w(1)w(n-2) + w(2)w(n-3) + \dots + w(n-1)w(0)\tag{1}
$$
with the initial condition that $w(0) = 1$.
Now that we have the recursive relation, let's try to find a closed form. The best way is to look at the generating function:
$$
f(x) = w(0) + w(1)x + w(2)x^2 + w(3)x^3 + \dots\tag{2}
$$
The recursive relation $(1)$ gives $f(x) = 1 + xf(x)^2$.  Solving this with the quadratic formula gives $f(x) = \frac{1 - \sqrt{1-4x}}{2x}$.  We can use the binomial theorem to get the power series for $\sqrt{1-4x}$, subtract that from $1$, and divide by $2x$.  This gives
$$
   f(x) = 1 + x + 2x^2 + 5x^3 + 14x^4 + \dots + \frac{1}{n+1}\binom{2n}{n} x^n + \dots\tag{3}
$$
And equating the coefficients of $(2)$ and $(3)$ we get $w(n) = \frac{1}{n+1}\binom{2n}{n}$.

Answer to the Misread Question
At first, I misread the question as looking for the number of tied games where each side had the lead at some point. In case this answers some future query, I leave this solution, but note that it does not answer the question asked.
Since there are $\binom{2n}{n}$ walks of type $n$, subtracting the unilateral walks on both sides, there are
$$
\binom{2n}{n}-2C_n=\frac{n-1}{n+1}\binom{2n}{n}\tag{4}
$$
walks of type $n$ whose partial sums are both positive and negative.

Answer to the Question Asked
The question asks for the number of tie games where A has the lead at some point and B has the lead at a later point. The negation of this condition is a tie game where any lead B has is before any lead A has. So the number of games that we don't want to count is
$$
\sum_{k=0}^n\overbrace{\frac1{k+1}\binom{2k}{k}}^{\text{B leads}}\overbrace{\frac1{n-k+1}\binom{2n-2k}{n-k}}^{\text{A leads}}\tag5
$$
which is the convolution of the Catalan Numbers with themselves, whose generating function is the product of the generating functions for the Catalan Numbers. So the generating function for $(5)$ is $f(x)^2$, which by the relation above, $f(x)=1+xf(x)^2$, is
$$
\frac{f(x)-1}{x}\tag6
$$
That is, the number of tie games we don't want to count is $C_{n+1}$. Thus, the number of tie games we want to count is $\binom{2n}{n}-C_{n+1}$
$$
\binom{2n}{n}-C_{n+1}=\frac{n(n-1)}{(n+2)(n+1)}\binom{2n}{n}\tag7
$$
A: I don't understand what the above posters are talking about but I think this problem is straightforward. Basically A is in the lead for $r$ goals and then B takes the lead for the other $18-r$ goals.
So the answer is just:
$\sum_{r=1}^{17} C_r C_{18-r}$ where $C_n$ is the Catalan number $\frac{1}{n+1}{2n \choose n}$
A: In this case, it's actually much easier to apply the double reflection in the question hint than the generating function approach in the answers. If you reflect once (about y=1 where y is the goal deficit between A and B), you get the paths where A was in the lead at least once. This gives you ${2n \choose n-1}$, the term we subtract from the total paths to get the Catalan numbers. But, we want paths where A was in the lead and later, B was in the lead. So, we need to reflect one more time, this time about the line y=-1. When we do this, we get ${2n \choose n-2}$. Plug $n=9$ here and there's your answer. See the answer here: Paths on a grid that don't go below $0$ or above $l$ before reaching their target. for another demonstration of this "multiple reflection" trick in action.
