During a Stochastic Process lecture, one course mate asked me a question, which he thought to be related to the Gambler's Ruin Problem. Despite the fact that up till now he hasn't found the right formalism to make this connection, the question itself intrigued me, and I deemed it an important and interesting question. It goes as follows,
Suppose that we have $2n$ balls, of which $n$ are red (non-identical), and the other $n$ are blue (non-identical). We arrange them into a sequence, according to the rule below,
For any integer $1\le i\le 2n$, the first $i$ balls always have more or equal number of red ones compared with blue ones.
The question is, how many such arrangements are possible?
Please any help or hint would be appreciated, thanks!
Let denote a red ball with $1$ and a blue ball with $0$. Now writing the sequence of the $2n$ balls will give us a binary sequence. We want to count the number of binary sequence in which any initial sequence has at least the same number of red ball as blue balls. This is exactly the number of Dyck words of length $2n$ and it's given by the Catalan Number:
$$C_n = \frac1{n+1}\binom{2n}{n}$$
The wikipedia page about Catalan Numbers has a good explanation how the Catalan Numbers and Dyck Words are connected.