Комбинаторика. Очередь за спичками.

[Katmandu]

Такая задачка:

Очередь из 18 человек стоит за спичками. Один коробок спичек стоит 50 копеек. У девяти человек есть 50 копеек, а у остальных — только рубль. У продавца изначально нет денег. Сколькими способами можно расставить людей в очереди, чтобы все могли получить сдачу?
Люди не различаются между собой.

Никак не получается придти к ответу.
Представил данную задачу в виде последовательности нулей и единиц. $0 $ - $50 $ коп, $1$ - $1 $ руб.
$010101010101010101$
Вот нужно найти все такие последовательности. И если мы идем по такой последовательности слева направо, считая единицы и нули, то количество единиц не должно превышать количество нулей.

Дальше я думал составить рекуррентную формулу.
Рассмотреть последовательности из двух человек, из четырех и т.д. до 18. Но как такового правила не выходит.

я знаю, что ответ получается если посчитать так: $\frac{\binom{18}{9}}{10} = 4862$

[Brukvalub]

Это классическая комбинаторная задача, она много где разбирается. Обычно для ее решения используется геометрическая интерпретация расположения людей в очереди в виде ломаной и сначала подсчитывают число неправильных расположений- его подсчитать легче. Рекурсия здесь не особо нужна.

[Katmandu]

Странно, если она классическая, то почему я ее никогда не встречал.

Я пробовал считать число неправильных расположений. Но эта задача так или иначе упирается в поиск правильных расположений:
последовательности, которые имеют неправильные расположение имеют вид:
1...
01 1...
0101 1...
0011 1... (вот тут еще легко, а дальше я должен знать правильные расположения для 6 человек: трое с 50 коп, трое с рублем)
010101 1...
010011 1...
001101 1...
000111 1...
001011 1...

Пытался решить представив задачу в следующем виде:
$x_1 + ... + x_9 = 9, x_i \leq i, i \in [1,9]; x_i > 0$

Еще можно представить, что есть девять коробок и 9 шаров. В первую коробку помещается только 9 шаров, во вторую только 8. и т.д.
Тут тоже ничего не получилось.

Пытался рисовать бинарное дерево, в котором по порядку добавлял человека с рублем, либо с 50 копейками, но уже когда людей шестеро все становится печально

В виде ломаных только рисовал следующее. Выделил квадрат 9 на 9. И проводил возможные ломаные, которые соответствуют верным расположениям. Но ломанных там целая куча.

Вообще мне кажется, что задача должна решаться в уме, просто я чего-то не знаю.
В каких учебниках разбирается подобная тема? Эта задача итак уже убила кучу времени.

[Brukvalub]

См., например, Виленкин "Комбинаторика" задача "Очередь в кассу".

[Someone]

Katmandu в сообщении #1011429 писал(а):

В каких учебниках разбирается подобная тема?

В. Феллер. Введение в теорию вероятностей и ее приложения. Том 1. Москва, "Мир", 1984. Глава III.

[Katmandu]

Классная книжка, Виленкин "Комбинаторика". Спасибо.

Вообще мне стоило заметить что задача сводится к задаче о количестве правильных скобочных последовательностей длины 2k. В моем случае 18.
А решение этой задачки мне было известно: это числа Каталана. Жаль сразу не заметил.