# 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!

-
The reflection principle is explained here. (Regarding your third paragraph, note that the first goal may be scored by B.) – Did Jan 2 '12 at 14:47
I understand the reflection principle, but what does double reflection means? Its probably a question for my TA but still... Also - the way I understand the question A must score the first goal – yotamoo Jan 2 '12 at 14:51
I don't think there's an implication that team A must score the first goal. They had the lead at some point. – joriki Jan 2 '12 at 14:52
Ok, and if so - how do I start? – yotamoo Jan 2 '12 at 15:06

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?

-
If I reflect from the marked point and on, then I count all series where B is winning/tied (or A never lead). Is that all the ways for the condition to fail? What about a series where B never leads? Should I double the number I find to include both options? – yotamoo Jan 2 '12 at 16:32

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.

-
The convolution of Catalan numbers which yields $G=C^2$ in your answer corresponds to @Lopsy's decomposition of each (in)admissible path into a path from (0,0) to some (x+1,x) which stays above the diagonal except at its endpoint, and a path from (x,x) to (9,10) which stays below the diagonal except at its endpoint. – Did Jan 2 '12 at 21:00
@Didier: a) I don't understand why you're including an additional segment in the paths -- wouldn't it be more straightforward to say that the decomposition is into a path from (0,0) to (x,x) and one from (x,x) to (9,9)? b) I agree that this decomposition corresponds to the convolution; but I don't see how this gives a hint how to use reflection to set up a bijection. – joriki Jan 2 '12 at 21:27
Re (a), adding these elementary segments is not needed, but I mentioned the point (x+1,x) (and the corresponding one (9,10)) to make clear the reason why the decompoosition is bijective: one does not cut the global path at the first hitting of the diagonal but at its first crossing of the diagonal. Re (b), I guess the idea is to reflect the second portion so as to have two similar paths in succession. Here again I agree with you that this is not needed. – Did Jan 2 '12 at 21:39
@Didier: Sorry, I might be being a bit dense, but I don't understand. I understand that the path is cut at the first crossing, not at the first hit, but once it's reflected, how does one decide which of the hits to turn into a crossing to get back to the original and make the mapping bijective? Or are you somehow using these additional segments in a similar way as I did in my answer to prevent any further hits in the reflected part? (I took Lopsy's hint to mean that one should simply reflect at the diagonal.) – joriki Jan 2 '12 at 22:05
Of course there is no bijection with the set of paths of length 18 entirely above the diagonal! (Otherwise one would have G=C.) Each such path p corresponds to as many admissible paths as the number n(p) of times it hits the diagonal. Surely true combinatorists know by heart that the generating function C^2 enumerates the collection of the paths p weighted by n(p)... – Did Jan 2 '12 at 22:40

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?

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

Since there are $\binom{2n}{n}$ walks of type $n$, subtracting the unilateral walks on both sides, there are $$\frac{n-1}{n+1}\binom{2n}{n}\tag{4}$$ walks of type $n$ whose partial sums are both positive and negative.

-

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.

$\sum_{r=1}^{17} C_r C_{18-r}$ where $C_n$ is the Catalan number $\frac{1}{n+1}{2n \choose n}$
This only works if you assume that after $B$ has taken the lead, $A$ never takes the lead anymore... – TMM Mar 25 '12 at 17:59