Problem
COM-B2-M03-P014 Ballot Count
#14
★★★★☆ Level 4 of 5
Let \(p>q\). How many words with \(p\) letters \(A\) and \(q\) letters \(B\) have the property that in every initial segment, the number of \(A\)'s is strictly greater than the number of \(B\)'s?
Start with \(A\), then apply reflection to bad words.
There are \(\binom{p+q}{q}\) words in total. The classical reflection bijection shows that the number of bad words is \(\binom{p+q}{q-1}\): a bad word first reaches equality after an initial \(A\)-lead, and reflecting the corresponding initial segment changes one \(A\) into an extra \(B\). Hence the number of good words is
\[\binom{p+q}{q}-\binom{p+q}{q-1}=\frac{p-q}{p+q}\binom{p+q}{q}.\]
A difficult example; give it after Catalan reflection.