Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 45 стр.

      Решение. Зашифруем каждый выбор книг последовательностью из
нулей и единиц следующим образом : каждой оставленной книге сопоста-
вим 0, а каждой взятой – 1. В результате получим последовательность из 5
единиц и 7 нулей, причём в последовательности не будет двух подряд
идущих единиц (так как нельзя по условию брать две рядом стоящие кни-
ги). Имеем неупорядоченную 5-выборку из 8 (см. пример 18). Следова-
                      5
тельно, всего будет C 8 = 56 (способов).

      Пример 20. Найти число способов разбиения n одинаковых предме-
тов по m урнам.
      Решение. Перенумеруем урны, расположив их в ряд. Между ними
будет (m-1) промежуток. Поставим в соответствие каждому разбиению
предметов по урнам последовательность из нулей и единиц следующим
образом: сначала последовательность имеет группу из нулей, число кото-
рых равно числу предметов в первой урне, затем ставим 1 (перегородку);
далее – столько нулей, сколько предметов во второй урне и опять ставим 1;
затем столько нулей, сколько в третьей урне и т. д. Заканчивается последо-
вательность группой нулей; их столько, сколько предметов в последней
урне. Следовательно, в последовательности будет n нулей и (m-1) единиц,
всего (n+m-1) цифр. Тогда всего способов разбиения будет равно     Cnm+−m1−1 .
               m−1     n
Заметим, что Cn+m−1 = H m (уметь доказать).

      Пример 21. Комиссия состоит из 9 человек. Документы хранятся в
сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно
изготовить и как их распределить между членами комиссии, чтобы доступ
к сейфу был возможен тогда и только тогда, когда соберутся вместе не ме-
нее 6 человек комиссии?
      Решение. Какие бы 5 членов комиссии не собрались, должен найтись
замок, который они не могут открыть, но ключ от этого замка имеется у
каждого из 4 остальных членов комиссии (появление кого-нибудь из кото-
рых даёт возможность открыть сейф). Следовательно, число замков равно
C 95 =126; число ключей равно C 95 × 4=504.

     Замечание. В общем случае число замков равно     Cnm−1 ; число ключей
                                 m−1
к этим замкам равно (n-m+1) Cn , где n – число членов комиссии, m –
наименьшее число членов, при которых возможен доступ к сейфу, при ус-
ловии m ≤ n + 1.

      Пример 22. Сколькими способами можно расставить в шеренгу 5
львов и 4 тигра так, чтобы никакие два тигра не шли друг за другом?