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

UptoLike

Комбинаторика
36
20
321
=++
xxx
,
0,10,1
321
xxx
,
число
()
3
αΝ
ΝΝ
Ν
- с числом наборов
()
321
,,
xxx
, для которых
20
321
=++
xxx
,
10,0,1
321
xxx
,
число
()
21
,
ααΝ
ΝΝ
Ν
- с числом наборов
()
321
,,
xxx
, для которых
20
321
=++
xxx
,
0,10,10
321
xxx
,
число
()
31
,
ααΝ
ΝΝ
Ν
- с числом наборов
()
321
,,
xxx
, для которых
20
321
=++
xxx
,
10,0,10
321
xxx
,
число
()
32
,
ααΝ
ΝΝ
Ν
- с числом наборов
()
321
,,
xxx
, для которых
20
321
=++
xxx
,
10,10,1
321
xxx
,
число
()
321
,,
αααΝ
ΝΝ
Ν
- с числом наборов
()
321
,,
xxx
, для которых
20
321
=++
xxx
,
10,10,10
321
xxx
.
Используя подходящие замены переменных и формулу для числа
сочетаний с повторениями, найдем
()
66
!2!10
!12
10
12
10
1310
1020
3
1
=====
+
CCC
αΝ
ΝΝ
Ν
,
()
55
!2!9
!11
9
11
9
139
1120
3
2
=====
+
CCC
αΝ
ΝΝ
Ν
,
()
55
!2!9
!11
9
11
9
139
1120
3
3
=====
+
CCC
αΝ
ΝΝ
Ν
,
()
1,
2020
3
21
==
C
ααΝ
ΝΝ
Ν
,
()
1,
2020
3
31
==
C
ααΝ
ΝΝ
Ν
,
()
0,
2120
3
32
==
C
ααΝ
ΝΝ
Ν
,
()
0,,
321
=
αααΝ
ΝΝ
Ν
.
Итак,
() () () ( ) ( ) ( )
+++=
3231213210
,,,
αααααααααΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
Ν
()
3611555566210,,
321
=++=
αααΝ
ΝΝ
Ν
.
Задача 3
. К обеду за круглым столом приглашены 4 пары враждующих
рыцарей. Сколькими способами их можно разместить за столом так, чтобы
никакие из двух враждующих рыцарей не сидели рядом?
Решение. Обозначим через
Χ
ΧΧ
Χ
множество всевозможных размещений
рыцарей за столом и введем три свойства для элементов данного множества: