Задача по комбинаторике

[Whitaker]

Здравствуйте! Помогите пожалуйста разобраться со следующей задачей.

На книжной полке стоит $n$ книг. Сколькими способами можно выбрать из них $k$ книг так, чтобы между любыми двумя выбранными книгами, равно как и после $k$-й выбранной книги, было не менее $s$ книг?
Приведу решение из книги: Учтем, что за каждой выбранной книгой надо оставить следующие за ней $s$ книг. Тогда нам надо будет выбрать $k$ предметов из $n-ks$. Это можно сделать $C_{n-ks}^{k}$ способами.

У меня следующий вопрос: Почему они удаляют ровно следующие $s$ книг? А не удаляют например $s+1$ или $s+2$ книг, ведь сказано что надо оставить не менее $s$ книг. Ведь тогда бы получился совсем другой ответ.
Объясните пожалуйста.

[gris]

$s+1$ или $s+2$ не меньше, чем $s$, но $s$ не не меньше, чем $s+1$.
Приклеивание к книге ещё $s$ штук вовсе не исключает того, что при отборе за ней не окажется гораздо больше (вот меньше не будет).
А вообще такие задачи становятся более понятными, если попробовать частные случаи.
Я бы в ответе ещё написал о существовании решения. Или $C^{<0}_{<0}=0$ по определению? Не помню

[Whitaker]

Пусть $s=1$. Тогда задача формулируется следующим образом: Надо взять $k$ книг из имеющихся $n$ книг, так чтобы никакие две книги не стояли рядом. Но данная задача эквивалентна следующей: Сколько существует последовательностей длины $n$, где $k$ единиц и $(n-k)$ нулей, где единицы не должны стоять рядом.
Решаем это таким образом. Выпишем $(n-k)$ нулей. Для единиц получается ровно $(n-k)$ мест, одно место впереди и $(n-k-1)$ мест в промежутках между нулями. По условию задачи последний элемент в последовательности всегда должен быть нулем. И нам нужно определить сколькими способами можно выбрать $k$ позиций из $(n-k)$, а это быть сделано C_{n-k}^{k}$ способами.

Пусть теперь $s=2$. Теперь задача формулируется так: Надо взять $k$ книг из имеющихся $n$ книг, так чтобы между любыми соседними книгами было не менее 2 книг. Но данная задача эквивалентна следующей: Сколько существует последовательностей длины $n$, где $k$ единиц и $(n-k)$ нулей, где между любыми соседними книгами должно быть не менее двух нулей. Хотелось бы это тоже разобрать как и для случая $s=1$, но я что-то не догадываюсь как расставить нули и получить ответ C_{n-2k}^{k}$.

Объясните пожалуйста кто-нибудь как расставить нули для случая $s=2$ и если можно для случая $s=3$.

[TOTAL]

Whitaker в сообщении #472738 писал(а):

Объясните пожалуйста кто-нибудь как расставить нули для случая $s=2$

$100$ - вот такой набор обозначьте $X$
Теперь осталось найти количество различных расстановок из $k$ штук $X$ и $n-3k$ штук нулей.

[gris]

Всю ночь снились книги...
Но меня данная задача навела на некоторые размышления. Я притянул её к чисто практической задаче. Ведь вся эта комбинаторика нужна для определения вероятности появления случайной выборки определённого типа, эта вероятность нужна для разных критериев при анализе некоторой статистики и т.п. Короче, эти вещи полезны про планировании или компьютерном моделировании.
Скажем, я в течение месяца должен проработать ровно 5 дней, чтобы после каждого дня работы было не меньше 4 дней отдыха. Это ровно такая же задача про книги. Как мне составить расписание случайным образом?
Я определяю число дней необходимого отдыха. Их 20. Вычитаю из 30. Получаю 10. Из 10 первых натуральных чисел выбираю 5. Предположим: 3,4,6,8,10. Теперь прибавляю начиная со второго номера 4,8,12,16: 3, 8, 14, 20, 26. Это есть расписание моей работы. Оно удовлетворяет требованиям задачи. И таких расписаний может быть $C^5_{30-5\cdot3=10}$
Если представить себе алгоритм получения случайной выборки, то решение придёт само собой. Ведь задачу можно усложнить: количество дней отдыха, например, не должно превышать 6.

[PAV]

gris

красивая формулировка!

[gris]

Это исключительно летние настроения
На самом деле часто приходится слышать, что какой-де практический смысл в этих урнах с шарами, монетках, токарных станках, бойцах с винтовками и прочем ТВ-шном классическом реквизите.
Не лучше ли облекать задачи в современную форму.

Для медиков: предположим, планируется провести испытания нового лекарства. В течение $n$ дней надо сделать $k$ инъекций при $s+$ днях дополнительной релаксации после каждого дня назначения. Надо спланировать серию испытаний со случайным расписанием инъекций. Пределить необходимое число серий для получения необходимого уровня надёжности бла-бла-бла.

Для разведчиков: радистке Кэт надо с 20 апреля до 9 мая три раза выйти в эфир с не менее, чем 2 днями радиомолчания после каждого выхода. Помоги Штирлицу составить расписание и оценить вероятность перехвата передачи, если Мюллер 3 дня в неделю сидит на пеленгаторе.

Алгоритм первичен. Количество вариантов вторично.

[Whitaker]

Спасибо Вам большое TOTAL и gris!