Четыре лекции по комбинаторике. Семенов А.С. - 6 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

8
булевых или двоичных функций от m двоичных аргументов равно .2
2
m
Теорема 3 (принцип сложения)
Если некоторое действие №1 можно осуществить
1
m
способами, а действие
№2 --
2
m способами, то осуществить "либо действие №1, либо действие №2" можно
2
1
mm + способами.
Справедливость теоремы очевидна. Например, если студенту необходимо по-
пасть в лекционный корпус, к которому можно подъехать либо на одном из трех ав-
тобусных маршрутов, либо на одном из четырех трамвайных, то студент обязатель-
но окажется около корпуса, воспользовавшись одним из семи маршрутов городского
транспорта.
Пример 5. Сколькими способами из 28 костей домино можно выбрать две кости од-
ну за другой так, чтобы вторую можно было приложить к первой ?
Решение. Если первой костью является дубль
)7(
1
=
n
, то вторую можно приложить
к первой 6
2
=n способами. Если первая кость не дубль )21(
'
1
=n , то вторую можно
приложить к первой 12
'
2
=n способами. Теперь, последовательно применяя прин-
цип умножения и принцип сложения, для искомого числа получаем
.294122167
'
2
'
12121
=⋅+⋅=⋅+⋅=+= nnnnmmm
§ 3. Число элементов объединения конечного числа конечных множеств
Теорема 4.
Если
A
и
B
конечные подмножества некоторого универсального
множества ,
I
то
).()()()( BANBNANBAN IU
−
+
= (8)
Доказательство. Применим метод полной индукции. Рассмотрим последовательно
все пять различных случаев "взаимного расположения" двух множеств
A
и .
B
1. ,
B
A
= тогда
ABAABA
=
= IU ,
и формула (8) дает
−
+= )()()(
A
N
A
N
A
N
),()(
A
N
A
N
=− т.е. верное равенство.
2. ,
B
A
⊂ тогда ABABBA
=
= IU , и формула (8) дает
−
+= )()()(
B
N
A
N
B
N
),()(
B
N
A
N
=− т.е. верное равенство.
3.
B
A
⊃ (аналогично случаю 2).
4.
=BA I Ø, тогда
0)( =BAN I
и формула дает верное равенство
).()()( BNANBAN +=U
5. ≠BA I Ø, тогда ),()()()( BANBANBNAN IU
+
=
+ так как в левой части
последнего равенства число общих элементов
)( BAN I
будут перечислены дваж-
ды. Отсюда и следует равенство (8). Теорема 4 доказана.
Установим общую формулу для определения числа элементов объединения
конечного числа конечных множеств.
Теорема 5.
Если
),...,2,1( niA
i
= конечные подмножества универсального множества ,
I
то −++= )(...)()...(
1
2
1 nn
ANANAAAN UUU +)({
21
AAN I
)}(..)(
131 nn
AANAAN II
−
+
++ + ++ )()({
4213
2
1
AAANAAAN IIII

Страницы