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

идущих единиц (так как нельзя по условию брать две рядом стоящие кни-
ги). Имеем неупорядоченную 5-выборку из 8 (см. пример 18). Следова-
                      5
тельно, всего будет C 8 = 56 (способов).

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

      Пример 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 тигра так, чтобы никакие два тигра не шли друг за другом?
      Решение. Расставим сначала всех львов, оставив между каждыми
двумя львами промежуток. Это можно сделать P5 способами. Теперь для
расстановки тигров имеется 6 мест (либо одно впереди всех львов, либо

                                               46