Составители:
Рубрика:
10
67
A=48
B=35
A
∩
B=27
Очевидно, что N = 67 – 48 – 35 + 27 = 11.
Главная теорема комбинаторики (Теорема о включениях и ис-
ключениях)
Пусть имеется множество из N объектов произвольной природы. На
этом множестве пусть задано n свойств. Каждый объект может обла-
дать либо не обладать некоторыми из этих свойств. Сами свойства обо-
значим: α
1
, α
2
, α
3
, ..., α
n
. Будем обозначать N(α
i
) – количество объек-
тов точно обладающих свойством α
i
и может быть какими-то другими,
а
(, )
ij
N αα
– число объектов не обладающих ни свойством α
i
, ни
свойством α
j
. Тогда число объектов, не обладающих ни одним из пере-
численных свойств:
()()()()
()()()()
()() ( )( )
() ( )
123 1 2 3
12 13 14
123 1123
123
, , ,..., ...
...
... ...
1 ,..., .
n
n
nnn
n
i
NNNNN
NN N N
NN N N
N
−
ααα α = − α − α − α
−α+αα+αα+αα+
+ αα + αα + + α α − ααα +
+− ααα α
( 6 )
Продолжение примера. Пусть теперь 20 человек знают французс-
кий, 12 – английский и французский, 11 – английский и немецкий и 5 – все
три языка.
Тогда в соответствии с теоремой количество человек, не знающих
ни одного из трех перечисленных языков (но может быть знающих ки-
тайский язык), равно N = 67 – 48 – 35 – 20 + 27 + 12 + 11 – 5 = 9.
Решето Эратосфена
Выпишем все числа от 1 до N. Сколько чисел делится на k? Очевид-
но, [N/k], где [x] обозначает целую часть числа x. Тогда, легко подсчи-
тать количество чисел, не делящихся в данном диапазоне на k
1
, k
2
, k
3
...
П р и м е р. Сколько чисел от 1до 100 не делятся на 5 и 7?
Воспользуемся теоремой о включениях и исключениях. Под первым
свойством чисел будем понимать делимость на 5, под вторым – делимость
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
