Дискретная математика. Элементы теории, задачи и упражнения. Часть 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» или «5».
Решение. Выбрать кость, содержащую «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) 
     12. Пусть �1 – отношение порядка на множестве � , � 2 – отношение
порядка на множестве � . Докажите, что отношение
       � � ��a1 , a 2 �, �b1 , b2 � � �� � � � � �� � � � : �a1 , b1 � � �1 , �a 2 , b2 � � � 2 �
есть отношение порядка.
      13. Для следующего отношения порядка постройте диаграмму Хассе:
               � � �1,2,3,4,5,6,7,8�, � � �� x, y � � � � � : x � y�.



                                  2. КОМБИНАТОРИКА

                     2.1 Основные правила комбинаторики

                            Правило суммы
      Правило суммы для двух объектов: Пусть объект a можно выбрать
m способами, объект b – n способами, и существует k общих способов вы-
бора объектов a и b , тогда один из объектов «a или b» можно выбрать
m + n – k способами.

      Пример 1. Сколькими способами из 28 костей домино можно вы-
брать кость, на которой есть «2» или «5».
      Решение. Выбрать кость, содержащую «2», можно 7-ю способами, со-
держащую «5» – тоже 7-ю способами, но среди этих способов есть один об-
щий – это выбор кости «2 : 5». В соответствии с правилом суммы общее чис-
ло способов выбора нужной кости можно осуществить 7 + 7 – 1 = 13 спосо-
бами.
      Правило суммы можно сформулировать для произвольного числа
объектов. Для этого достаточно использовать формулу для мощности объ-
единения конечного числа множеств. В случае трёх объектов формула
имеет вид:
      |A � B � C | = |A| + |B| + |C| – |A � B| – |A � C| – |B � C| + |A � B � C|.
      Правило суммы для 3-х объектов:
      Если объект а можно выбрать n1 способами, объект b – n2 способа-
ми, объект с – n3 способами, и известны n12 общих способов выбора одного
из объектов а и b, n13 общих способа выбора одного из объектов а и с, n23
общих способа выбора одного из объектов b и с, а также известно n123
общих способа выбора одного их объектов а, b и с , то число всех способов
выбора одного из объектов «а или b или с» вычисляется по формуле:
                          n1 + n2 + n3 – n12 – n13 – n23 + n123.              (1)



                                                  27

Страницы