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

UptoLike

ВУЗ: 

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

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

Рубрика: 

18
разложения: достаточно найти полиномиальные коэффициенты для таких разбиений
числа ,...
1 k
rrn ++= что ,...
21 k
rrr ≥≥≥ а потом переставлять показатели
всеми возможными способами.
ЛЕКЦИЯ 4
§ 12. Понятие о методе включения и исключения
Рассмотрим некоторое конечное универсальное множество
I
, причем
m
I
N
=)( . Пусть элементы этого универсального множества либо не обладают ни
одним из свойств ,,...,
1 n
α
α
либо обладают одним или несколькими свойствами из
указанных. Пусть теперь
−
= ),...,2,1( niA
i
подмножество, элементы которого об-
ладают хотя бы свойством .
i
α
Тогда
U
n
i
i
A
1=
− множество, элементы которого обла-
дают хотя бы одним из свойств .,...,
1 n
α
α
Следовательно, разность
U
n
i
i
ANIN
1
)()(
=
− определит число элементов
N
универсального множества, кото-
рые не обладают ни одним из свойств .,...,
1 n
α
α
Воспользовавшись формулой (10),
получаем
∑∑
==
+++−=−−=
n
k
n
i
ink
k
AANANINAASINN
11
211
...)(()()(),..,()1()( I
+
+
+
+
+
−
−−−
...))(...)(())(
123211 nnnnn
AAANAAANAAN IIIII
+ )....()1(
21 n
n
AAAN III− (24)
Формулу (24) называют формулой включений и исключений, ибо сначала ис-
ключаются все элементы, обладающие хотя бы одним из свойств, потом включаются
элементы, обладающие по крайней мере двумя из свойств, исключаются элементы,
обладающие по крайней мере тремя свойствами и т.д.
Метод решения комбинаторных задач на основе формул (10) и (24) называет-
ся методом включения и исключения.
Пример 16. Сколько чисел
N
в первой сотне натуральных чисел не делится ни на
одно из чисел 2,3,5.?
Решение. В этом случае }.100,...,2,1{,100)(
=
= IIN Пусть −
321
,, AAA подмно-
жества
I
, элементы которых делятся соответственно на 2,3,5. Тогда
[]
]
]
,205100)(,333100)(,502100)(
321
=
=
=
=
== ANANAN
[]
[
]
,1010100)(,166100)(
3121
=
=
=
=
AANAAN II
[]
]
,330100)(,615100)(
32132
=
=
== AAANAAN III где
[]
−x наибольшее
целое число, не превосходящее
x
. Воспользовавшись формулой (24) при ,3
=
n
получаем
.263)61016()203350(100 =−+++++−=N

Страницы