- q - 1, число несприятливих перестановок буде P (k + q + 1, т - q - 1), а число сприятливих одно
(2)
Якщо при цьому т? q, то черга напевно пройде без затримки - полтиника, які були в касі з самого початку, вистачить, щоб задовольнити всіх власників рублів.
Якщо ж т> k + q, то черга напевно затримається - загального числа полтиника в касі і в черзі не вистачить, щоб дати здачу всім власникам рублів.
У процесі проходження черги могли бути моменти, коли в касі не залишалося жодного півгривні, і черга не зупинялася лише тому, що купував у цей момент квиток був якраз володарем півгривні. Підрахуємо число розстановок, при яких жодного разу не буде такого критичного моменту. Іншими словами, вирішимо таку задачу. p> Скількома способами можна розставити володарів т рублів і k полтиника так, щоб у будь-який момент (крім, можливо, початковий і кінцевий) в касі був хоча б один полтинник?
Це завдання теж вирішується методом підрахунку ламаних. Але тепер треба шукати ламані, що перетинають пряму х = 0 лише на початку координат і (за т = k) в точці А (0; 2k). Оскільки з умови задачі ясно, що попереду повинні стояти два володаря півгривні, то першого з них можна відвести убік, і тоді отримаємо вирішену вище завдання, але для випадку, коли на т рублів припадає k - 1 полтинник. Тому число сприятливих розстановок при т дорівнює
В
Якщо ж m = k, то треба відвести убік і замикаючого чергу володаря рубля. Ми отримаємо відповідь. p> Важливе слідство. Позначимо через T n число показує, у скількох випадках проходить без затримки чергу з володарів п рублів і п полтиника. Ми доведемо зараз, що ці числа задовольняють рекурентному співвідношенню
Т = Т 0 Т n-1 + Т 1 Т n-2 + ... + Т s-1 Т ns + ... + Т n- 1 Т 0 (3)
Для доказу розіб'ємо всі варіанти на класи, віднісши до s-му класу черги, в яких лише після того, як пройдуть 2s покупців, в перший раз виявляють відсутність у касі полтиника. У цьому випадку серед перших 2s покупців мається s людина з полтинник і s людина з рублями, а число способів розстановки, при яких в касі на перших 2s - 1 кроках був хоча б один полтинник, одно, як ми бачили,. Серед решти 2п - 2s людей у ​​ п - s рублі і у п - s полтиники. Розставити їх так, щоб черга і потім пройшла благополучно, можна Т ns способами. p> Всього за правилом твори отримуємо, що в s-му класі буде Ts-1Tn-s розстановок. А так як загальне число благополучних розстановок одно Т , то виконується рівність (3). При цьому Т 0 = 1. p> Співвідношення (3) зустрічається в...
