Recurrence relation: Flip a coin 2n times with n heads and n tails where, at all times, the number of heads is never less than the number of tails.

Question

I need to find a recurrence relation to count the different outcomes. I'm not sure how to do this, recursively or not. This is for an undergraduate class in combinatorics. I recently learned what the Catalan Numbers are but I don't see a connection.

Answer 1

How do you know Catalan numbers? Assuming you're familiar with the definition associated with lattice paths from $(0,0)$ to $(n,n)$ that never goes above the diagonal, just think of the horizontal steps as heads and the vertical steps as tails.

If you want to find a recurrence relation, consider this: at some point from the beginning to our last coin flip, we will have at least one point where the number of heads equals the number of tails (there's always the beginning, when we have $0$ heads and $0$ tails). Consider the last time this happens (besides the end, when we have $n$ heads and $n$ tails), when we have $i$ heads and $i$ tails for some $i$ such that $0\leq i<n$. Then the first $2i$ flips corresponds with one of these sequences.

Now what about the last $2n-2i$ flips? Note that the $2i+1$-th flip must be heads, otherwise we have $i+1$ tails and $i$ heads after the flip, and the last flip must be tails, otherwise we would have $2i$ tails and $2i-1$ heads before the flip. What can you say about the sequence of coin flips from $i+1$ heads and $i$ tails to $2i$ heads and $2i-1$ tails, then?