Формула включений-исключений и ее применения к комбинаторике и теории чисел. Бином Ньютона

Теорема 22.1. (формула включений-исключений) Если и конечные подмножества некоторого множества, – число элементов множества , – число элементов множества , число элементов множества , то

(22.1)

Установим общую формулу для определения числа элементов объединения конечного числа конечных множеств.

Теорема 22.2. Если конечные подмножества множества, то

.

или

(22.2)

где есть сумма чисел по всем возможным пересечениям ровно различных множеств из множеств .

Бином Ньютона (полиномиальная формула) - это формула, выражающая выражение в виде многочлена. Эта формула имеет вид:

,

- число сочетаний из элементов по k.

Широко известные формулы сокращенного умножения квадрата суммы и разности, куба суммы и разности являются частными случаями бинома Ньютона.