Формула включения-исключения.

Пусть А - конечное непустое множество.

– система подмножеств множества А. Тогда:

Доказательство.

Возьмем произвольный элемент , может быть 2 случая:

1) принадлежит ровно k подмножествам (k=1, 2, …, n)

1=

…

2)

1 раз учитывать при подсчете левой части и 1 раз при подсчете правой части.

Пример.

Пересечение будем учитывать дважды, 1 раз нужно отнять.

Полиномиальная формула. Свойства полиномиальных коэффициентов.

Формула бинома Ньютона.

Полиномом называется выражение: (1).

Полиномиальной формулой называется формула для вычисления выражения типа (1), при любом m и n.

Теорема. Полиномиальная формула.

, где – разбиение числа

Доказательство.

(n раз) =

, где .

( штук), , …,

Свойства полиномиальных коэффициентов.

1)

2)