Page 187 - 4496

об'єктів, що не володіють жодною з перерахованих
властивостей:

N  1 , 2 , 3 ,..., n  N  N   Na   a 2
1
 N   Na    Na  a  a 2 
n
3
1
 N a  a 3  ... N a  a n  N a  a 3  ... (5.6)
2
1
1
 N a n 1 a  n  N a  a 2 a  3 
1
 ...   1  n N a  a  a  ... a i 
1
3
2
Продовження прикладу. Хай тепер 20 чоловік знають
французьку, 12 - англійську і французьку, 11 - англійську і
німецьку і 5 - всі три мови.
Тоді відповідно до теореми кількість людей, які не
знаючих жодної з трьох перерахованих мов (але може бути
знаючих китайську мову), рівне N = 67 - 48 - - 35 - 20 + 27
+12+11- 5 = 9.
Решето Ератосфена. Випишемо всі числа від 1 до N.
Скільки чисел ділиться на k? Очевидно, [N/k], де [х] позначає
цілу частину числа х. Тоді, легко підрахувати кількість чисел,
що не діляться в даному діапазоні на k1, k2, k3, …
Приклад. Скільки чисел від 1до 100 не діляться на 5 і 7?
Скористаємося теоремою про включення і виключення.
Під першою властивістю чисел розумітимемо подільність на
5, під другим – подільність на 7. На 5 діляться 20 чисел. На 7
діляться 14 чисел. На 35 діляться 2 числа. Отже, не діляться на
5 і 7: 100 - 20 - 14 + 2 = 68 чисел.

5.7 Поєднання без повторень
Якщо вимагається вибрати k предметів з п, і при цьому
порядок вибираних предметів байдужий, то маємо

! n
k
C  (5.7)
n
k  ! n  k !
Формула (5.7) може бути одержана таким чином.
Виберемо по черзі k предметів з n. Число варіантів буде рівне
184