Using the Catalan numbers

Solution 1:

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?

Solution 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.

Solution 3:

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