Метод включений и исключений

Пусть множество А имеет N элементов и n одноместных отношений (свойств) Р₁,Р₂,…,Р_n. Каждый из N элементов может обладать или не обладать любым из этих свойств. Обозначим через N_{i1...i k} число элементов, обладающих свойствами Р_i1,...,P_{i k} и, может быть, некоторыми другими. Тогда число N(0) элементов, не обладающих ни одним из свойств Р₁,Р₂,…,Р_n, определяется по следующей формуле, называемой формулой включений и исключений:

Пример: Сколько положительных чисел от 1 до 500 делятся ровно на одно из чисел 3,5 или 7?

Обозначим свойства делимости на 3,5 и 7 соответственно через Р₁, Р₂ и Р₃. Тогда для N = 500 имеем , , . Так как N₁₂ – число общих кратных для чисел 3 и 5, наименьшее общее кратное которых равно 15, то N₁₂ совпадает с количеством чисел, которые делятся на 15, т.е. . Аналогично , , . По последней формуле находим искомое число чисел

-2(N₁₂ + N₁₃ + N₂₃) + 3N₁₂₃ = 166 +100 +71 -2(33+23+14) +3 4 =209.