Bertrand's ballot theorem
Let $N(p,q)$ be the number of sequences containing $p$ many A's and $q$ many B's, such that in every non-empty prefix, the number of A's strictly exceeds the number of B's. Clearly $N(p,q) = 0$ if $q \geq p$ and $q &gt; 0$. When $p = q = 0$ there are no non-empty prefixes, and so $N(p,q) = 1$.

Suppose therefore that $p &gt; q$, and consider any sequence satisfying the condition. If we remove the last element, we still get a sequence satisfying the condition. Conversely, whatever element we add, the resulting sequence will satisfy the condition, since $p &gt; q$. We conclude that
$$
N(p,q) = \begin{cases}
1 &amp; \text{ if } p=q=0, \\
0 &amp; \text{ if } q \geq p \text{ and } q &gt; 0, \\
N(p-1,q) + N(p,q-1) &amp; \text{ if } p &gt; q &gt; 0, \\
N(p-1,q) &amp; \text{ if } p &gt; q = 0.
\end{cases}
$$