билеты в кино стоят 50 рублей. в очереди стоят n человек с купюрами п 50 рублей и n человек с купюрами по 100 рублей. сначала у кассира нет денег. сколько существует различных порядков в очереди так чтобы кассир всегда смог отдать сдачу? задан 8 Июл '13 17:57 денис |
Последовательность людей в очереди удовлетворяет условию тогда и только тогда, когда среди любых первых $%k$% людей число людей со 100р не больше числа людей с 50р, а всего их поровну, то есть если заменить 50 на (, 100 на ) получится правильная скобочная последовательность. И искомое число равно числу Каталана от $%n$%. отвечен 8 Июл '13 18:39 dmg3 |