p> Тут, як часто буває в комбінаторних задачах, вигідніше шукати число В«несприятливихВ» випадків, тобто випадків, коли черга затримується. Якщо ми знайдемо це число, то, віднявши його з числа Р (к, т) = C. всіх перестановок т рублів і k полтиника (загального число ламаних), отримаємо відповідь для нашої задачі.
Значить, вийшла завдання про відшукання числа ламаних, що перетинають пряму х = -1 . Але якщо ламана L перетинає пряму х = -1 , то її можна перетворити таким чином: взяти найвищу точку перетину і частина ламаної L вище цієї точки симетрично відобразити в прямій х = - 1. Таке перетворення ламаної L в L? показано на рис. 2. При цьому перетворенні точка A (k - m; k + т), лежача праворуч від прямої х = -1, переходить у симетричну їй точку А '(т - до - 2; до + m), що лежить зліва від прямої х = -1. Таким чином, кожній колії з О в А, перетинає пряму х = -1, відповідає шлях з О в А '. Назад, якщо ламана L? веде з О в А ', то вона по дорозі повинна хоча б один раз перетнути пряму. X = -1 і, отже, може бути отримана описом вище чином з ламаної, що з'єднує Про з А і перетинає зазначену пряму.
Отже, число ламаних, що з'єднують Про з А і перетинають пряму х = -1 , дорівнює числу ламаних, що ведуть з Про в А '.
Порахувати ж число ламаних, що ведуть з Про в А ', зовсім легко - координати точки А' дорівнюють т - до - 2 і до + т, a тому у такий ламаної має бути до + 1 ланок, спрямованих вліво, і т - 1 ланок, спрямованих вправо. Значить, загальне число цих ламаних одно P (k +1, m - 1). Число ж ламаних, що не перетинають пряму х = -1, виражається формулою
(1)
Отже, кількість черг, при яких не відбувається затримки, одно, де k-число полтиника, т - число рублів. Зокрема, якщо k = т, то черга пройде без затримки у випадках і затримається у випадках. При великих k = т чергу найчастіше затримається. Наше завдання повністю вирішена. p> Розглянемо тепер деякий узагальнення цього завдання.
Касир був завбачливий і на початку продажу квитків у касі вже лежало q полтиника. У скількох випадках пройде без затримки чергу, складається з т володарів рублів і до володарів полтиника?
Геометричне уявлення цього завдання буде майже таким же. Тільки забороненою прямий тепер буде пряма х = - q - 1 (наявність q полтиника в касі дозволяє ламаної ухилитися на q одиниць вліво без затримки черги, а ухилитися на q + 1 одиниць воно вже не має права). Тому тепер А '(т - до - 2q - 2; до + т), у L? ланок вліво до + q + 1, ланок вправо т...
