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

UptoLike

Составители: 

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