Дискретная математика. Ерош И.Л - 76 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

76
ри короля из 5 рыцарей, причем таких, которые не сидели рядом за
круглым столом.
Множество всех рыцарей разбиваем на два подмножества в зависи
мости от того, входит ли в команду спасателей конкретный рыцарь,
например Ланселот. Ответ: 15 + 21 = 36. При n рыцарях и составе ко
манды спасателей из k рыцарей решение имеет вид
1
1
.
kk
nk nk
СC1
(4.10)
Упражнения.
1. Определите соотношение между n и k, при которых задачи a), b)
и c) имеют решения.
2. Найдите все восьмиразрядные двоичные коды, содержащие по 5
единиц, в которых не встречаются подряд два нуля.
4.2.2. «Задачи о смещениях (о беспорядках)»
Рассмотрим задачу. Имеется 5 различных предметов, например букв
A, B, C, D, E. Сколько существует различных перестановок этих пред
метов, в которых ни один предмет не находится на своем месте? Эту
задачу можно решить с помощью теоремы о включениях и исключени
ях. Под объектами теоремы будем понимать различные перестановки
предметов (их число равно 5! = 120). Будем считать, что перестановка
обладает первым свойством, если первый предмет находится на своем
месте, а остальные – на любых. Будем считать, что перестановка об
ладает вторым свойством, если второй предмет находится на своем ме
сте, а остальные – на любых и т. д. Всего имеем пять свойств. Реше
ние имеет вид
1
2
1235
5555
55!4!3!1!0!44.N CCCC34 5 4 4 3
В некоторых случаях количество объектов, обладающих определен
ным набором свойств, зависит только от количества свойств, а не от са
мого набора. Тогда формула для подсчета числа объектов, не обладаю
щих ни одним из выделенных свойств, упрощается. Так, при решении
только что приведенной задачи количество перестановок, в которых не
который предмет оказывался на своем месте, не зависело от того, какой
конкретно предмет или предметы находились на своем месте, а зависело
только от числа этих предметов. При произвольном n имеем
12 1 2 1 2 1 2
12
!– 1 ! 2 ! ... 1 0! .
n
n
nn nn
Nn n C n C n С D34544543
(4.11)
Полученное значение D
n
иногда называют формулой полного беспо
рядка или субфакториалом. Субфакториал можно представить и так:

Страницы