3
$\begingroup$

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!

  • 0
    Ok, and if so - how do I start?2012-01-02

4 Answers 4

3

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:

Catalan-type picture

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?

  • 0
    I$f$ I $r$eflect 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?2012-01-02
2

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.

  • 0
    @Didier: Nice coincidence -- I've been reading *Analytic Combinatorics* by Flajolet and Sedgewick over the holidays in order to give a better answer to [this question](http://math.stackexchange.com/questions/93906/how-many-weakly-connected-digraphs-of-n-vertices-are-there-without-loops-and-who/93962#comment221206_93962). So I'm aware of their approach (though I wasn't two weeks ago), and that's probably why I came up with squaring the generating function -- but it seemed to me that the question asked for a bijective proof; that's what I was missing in the hint and wanted to provide.2012-01-02
1

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.

0

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}$

  • 0
    Yup you're right, I interpreted the question wrongly I guess haha2012-03-26