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

UptoLike

Решение. Зашифруем каждый выбор книг последовательностью из
нулей и единиц следующим образом : каждой оставленной книге сопоста -
вим 0, а каждой взятой 1. В результате получим последовательность из 5
единиц и 7 нулей, причём в последовательности не будет двух подряд
идущих единиц (так как нельзя по условию брать две рядом стоящие кни-
ги ). Имеем неупорядоченную 5-выборку из 8 (см . пример 18). Следова -
тельно, всего будет
5
8
C
= 56 (способов).
Пример 20. Найти число способов разбиения n одинаковых предме-
тов по m урнам.
Решение. Перенумеруем урны, расположив их в ряд . Между ними
будет (m-1) промежуток. Поставим в соответствие каждому разбиению
предметов по урнам последовательность из нулей и единиц следующим
образом : сначала последовательность имеет группу из нулей, число кото-
рых равно числу предметов в первой урне, затем ставим 1 (перегородку );
далее столько нулей, сколько предметов во второй урне и опять ставим 1;
затем столько нулей, сколько в третьей урне и т. д . Заканчивается последо-
вательность группой нулей; их столько, сколько предметов в последней
урне. Следовательно, в последовательности будет n нулей и (m-1) единиц,
всего (n+m-1) цифр. Тогда всего способов разбиения будет равно
1
1
−+
m
mn
C
.
Заметим, что
1
1
−+
m
mn
C
=
n
m
H
(уметь доказать).
Пример 21. Комиссия состоит из 9 человек. Документы хранятся в
сейфе. Сколько замков должен иметь сейф , сколько ключей для них нужно
изготовить и как их распределить между членами комиссии, чтобы доступ
к сейфу был возможен тогда и только тогда, когда соберутся вместе не ме-
нее 6 человек комиссии?
Решение. Какие бы 5 членов комиссии не собрались, должен найтись
замок, который они не могут открыть, но ключ от этого замка имеется у
каждого из 4 остальных членов комиссии (появление кого - нибудь из кото-
рых даёт возможность открыть сейф ). Следовательно, число замков равно
5
9
C
=126; число ключей равно
5
9
C
×
4=504.
Замечание. В общем случае число замков равно
1m
n
C
; число ключей
к этим замкам равно (n-m+1)
1m
n
C
, где n число членов комиссии, m
наименьшее число членов, при которых возможен доступ к сейфу, при ус-
ловии m
n + 1.
Пример 22. Сколькими способами можно расставить в шеренгу 5
львов и 4 тигра так, чтобы никакие два тигра не шли друг за другом ?