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

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

(22.1)

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

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

.

или

(22.2)

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

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

,

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

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