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

UptoLike

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

27
12. Пусть
1
r
отношение порядка на множестве
A
,
2
r
отношение
порядка на множестве
B
. Докажите, что отношение
(
)
(
)
(
)
(
)
(
)
(
)
{
}
2221112121
,,,:,,,
r
r
j
Î
Î
´
´
´
Î
=
bababbaa
B
A
B
A
есть отношение порядка.
13. Для следующего отношения порядка постройте диаграмму Хассе:
{
}
8,7,6,5,4,3,2,1
=
A
,
(
)
{
}
yxyx
£
´
Î
=
:,
A
A
r
.
2. КОМБИНАТОРИКА
2.1 Основные правила комбинаторики
Правило суммы
Правило суммы для двух объектов: Пусть объект a можно выбрать
m способами, объект b n способами, и существует k общих способов вы-
бора объектов a и b , тогда один из объектов «a или b» можно выбрать
m + n k способами.
Пример 1. Сколькими способами из 28 костей домино можно вы-
брать кость, на которой есть «2» или «.
Решение. Выбрать кость, содержащую «2», можно 7-ю способами, со-
держащую «5» тоже 7-ю способами, но среди этих способов есть один об-
щий это выбор кости «2 : 5». В соответствии с правилом суммы общее чис-
ло способов выбора нужной кости можно осуществить 7 + 7 1 = 13 спосо-
бами.
Правило суммы можно сформулировать для произвольного числа
объектов. Для этого достаточно использовать формулу для мощности объ-
единения конечного числа множеств. В случае трёх объектов формула
имеет вид:
|A CB
| = |A| + |B| + |C| |A
B| |A
C| |B
C| + |A
B
C|.
Правило суммы для 3-х объектов:
Если объект а можно выбрать n
1
способами, объект b n
2
способа-
ми, объект с n
3
способами, и известны n
12
общих способов выбора одного
из объектов а и b, n
13
общих способа выбора одного из объектов а и с, n
23
общих способа выбора одного из объектов b и с, а также известно n
123
общих способа выбора одного их объектов а, b и с , то число всех способов
выбора одного из объектов «а или b или с» вычисляется по формуле:
n
1
+ n
2
+ n
3
n
12
n
13
n
23
+ n
123.
(1)