Дискретная математика. Азарнова Т.В - 37 стр.

UptoLike

Комбинаторика
37
1
α
- первая пара враждующих рыцарей сидит рядом,
2
α
- вторая пара
враждующих рыцарей сидит рядом,
3
α
- третья пара враждующих рыцарей
сидит рядом,
4
α
- четвертая пара враждующих рыцарей сидит рядом. Теперь
наша задача найти число
0
Ν
ΝΝ
Ν
элементов в множестве
Χ
ΧΧ
Χ
, которые не
обладают ни одним из введенных свойств.
Число элементов
Ν
ΝΝ
Ν
в множестве
Χ
ΧΧ
Χ
равно числу перестановок без
повторений из 8 элементов !8
=
Ν
ΝΝ
Ν
. Для вычисления чисел
()
,
1
αΝ
ΝΝ
Ν
()
,
2
αΝ
ΝΝ
Ν
()
,
3
αΝ
ΝΝ
Ν
()
4
αΝ
ΝΝ
Ν
мы рассматриваем соответствующую пару
враждующих рыцарей как один объект и находим всевозможные
перестановки 7 объектов, учитывая при этом порядок рыцарей внутри
объединенной пары. Поэтому,
() () () ()
!72
4321
====
ααααΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
Ν
.
Числа
()
21
,
ααΝ
ΝΝ
Ν
,
()
31
,
ααΝ
ΝΝ
Ν
,
()
41
,
ααΝ
ΝΝ
Ν
,
()
32
,
ααΝ
ΝΝ
Ν
,
()
42
,
ααΝ
ΝΝ
Ν
,
()
43
,
ααΝ
ΝΝ
Ν
находятся аналогично. Объединяются в одно целое по две пары враждующих
рыцарей и находятся всевозможные перестановки из 6 объектов, при этом
учитывается порядок внутри объединенных пар:
(
)
jiji
ji
<==
,4,3,2,1,!622,
ααΝ
ΝΝ
Ν
.
Аналогично, при нахождении
()
,,,
321
αααΝ
ΝΝ
Ν
()
,,,
421
αααΝ
ΝΝ
Ν
()
,,,
431
αααΝ
ΝΝ
Ν
()
4332
,,
αααΝ
ΝΝ
Ν
объединяются в один объект по три пары враждующих
рыцарей и находятся всевозможные перестановки из пяти объектов с учетом
порядка внутри объединенных пар. Все эти величины равны между собой и
равны !5222
.
Последняя искомая величина
()
!42222,,,
4321
=
ααααΝ
ΝΝ
Ν
.
Итак,
() () () ()
=
43210
ααααΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
Ν
()()()()()()
++++++
434232413121
,,,,,,
ααααααααααααΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
Ν
()()()()
+
432431421321
,,,,,,,,
ααααααααααααΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
Ν
()
!42222!52224!6226!724!8,,,
4321
+=+
ααααΝ
ΝΝ
Ν
Задачи для самостоятельного решения
.
1. Доказать тождества:
a) ;0,2
0
=
=
nC
n
n
k
k
n
b) ;2
0
1
=
=
n
k
nk
n
nkC