Задача
COM-B2-M03-P014 Баллотировка
#14
★★★★☆ Уровень 4 из 5
Пусть \(p>q\). Сколько слов из \(p\) букв \(A\) и \(q\) букв \(B\) имеют свойство: в каждом начальном отрезке букв \(A\) строго больше, чем букв \(B\)?
Начните слово с \(A\), затем примените отражение к плохим словам.
Всего слов \(\binom{p+q}{q}\). Классическая отражательная биекция показывает, что число плохих слов равно \(\binom{p+q}{q-1}\): плохое слово впервые достигает равенства после начального преимущества \(A\), и отражение соответствующей начальной части меняет один \(A\) в лишний \(B\). Поэтому хороших слов
\[\binom{p+q}{q}-\binom{p+q}{q-1}=\frac{p-q}{p+q}\binom{p+q}{q}.\]
Сложный пример; можно давать после Catalan-отражения.