Задача на комбинации с ограничениями

[Antalas]

Здравствуйте, уважаемые форумчане.

Пожалуйста, помогите понять как считать сочетания в этой задаче из Виленкина "Комбинаторика", M., 1969 г.
Подходил к ней уже несколько раз.

Дана очередь в кассу из $m+k$ человек. У $m$ человек в руке рубль, у $k$ 50 коп. Билет стоит 50 коп. У кассира изначально денег нет.
Сколькими способами можно переставить очередь так, чтобы она не застревала?
Люди в очереди не уникальны. Очередь застревает, если у кассира не оказывается сдачи. $k \geqslant m>0$

Как предлагает решать автор (изложено моими словами):
Обозначим за $1$ обладателя рубля, а за $0$ обладателя 50 коп. Тогда любую расстановку $m+k$ человек можно записать ввиде строки из $0$ и $1$. Полагаем, что очередь начинается слева и оканчивается справа.

Далее переберём все "запрещённые" перестановки, в которых очередь застревает.
Каждая запрещённая перестановка характерна тем, что количество $0$ и $1$ слева одинаково и огорожено от остальной части строки "отравленной" $1$-ей (на ней очередь встаёт, т.к. у кассира не хватает сдачи). Например $001110110$ - запрещённая, с "отравленной" $1$-ей на пятой позиции.

Чтобы их сосчитать, построим вспомогательное множество по такому правилу:

• для каждой запрещённой перестановки добавим $0$ в начало строки
• инвертируем от нового начала строки до "отравленной" $1$-цы включительно

При этом получится строка, в которой количество $0$ и $1$ будет гарантированно одинаково вплоть до определённой позиции.

Правило работает в обе стороны:

1. каждую запрещённую перестановку отображает во вспомогательное множество
2. каждый элемент вспомогательного множества отображает на уникальную запрещённую перестановку

Первое верно из свойства запрещённых перестановок и из правила отображения.
Второе верно из-за того, каждая строка вспомогательного множества гарантированно имеет одинаковое количество $0$ и $1$ слева.

Как тогда посчитать количество элементов вспомогательного множества?
Первый знак для всех них будет одинаковый и его можно исключить из рассмотрения.

Не понимаю, почему автор утверждает, что это будет $\binom{m+k}{m-1}$

[DeBill]

Antalas в сообщении #1128758 писал(а):

Первый знак для всех них будет одинаковый и его можно исключить из рассмотрения.

Остается $m+k$ мест. На этих местах надо произвольно расставить $m-1$ единиц и $k+1$ нулей. Это можно сделать ровно таким кол-вом способов...

[Antalas]

Я не пойму, почему можно расставлять произвольно. Когда выписываю в столбик первые несколько строк из вспомогательного множества, создаётся впечатление, что нули и единицы не могут вставать на определённые места:

• $10......$
• $1100......$
• $111000......$
• $110100......$
• и т.д.

[DeBill]

Antalas в сообщении #1128872 писал(а):

не могут вставать

Да почему же?

Antalas в сообщении #1128872 писал(а):

создаётся впечатление, что нули и единицы не могут вставать на определённые места:

Укажите в своих примерах - где конкретно - проблемы (я их не вижу).
Фишка в том, что, для нашей вспомогательной последовательности, начинающейся с 1, нулей больше, чем единиц. Поэтому, как бы их не ставили, равенство кол-в нулей и единиц на некотором начальном отрезке всегда будет .

[Antalas]

Всё, понял, надо было просто расписать вспомогательное множество для какого-нибудь простого случая (я взял $m=3$, $k=3$).

А как такой метод вообще может придти в голову? Вот я расписал все 15 строк оригинального множества, смотрю на них и не знаю как сосчитать. Что можно попробовать? Способ с инвертированием единственный?

[Sinoid]

Antalas в сообщении #1131949 писал(а):

Способ с инвертированием единственный?

Не знаю, то ли это, что нужно вам, но такая задача решается геометрически в книге Гнеденко Курс теории вероятностей.

[Antalas]

Спасибо, посмотрю