Биномиальные тождества. 
Метод включений и исключений. 
Производящие функции

Как уже отмечали, числа имеют ряд важных свойств. Укажем некоторые из них:

; (2.1).

; (2.2).

; (2.3).

; (2.4).

. (2.5).

Известна также формула бинома Ньютона:

(2.6).

(2.7).

Коэффициенты формулы (6) называются биномиальными коэффициентами: -е слагаемое суммы (6) считаетсям членом разложения и обозначается через .

. (2.8).

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

• 1. Число биномиальных коэффициентов равно .
• 2. Коэффициенты членов, равноотстоящих от начала и конца бинома, равны между собой.
• 3. Сумма биномиальных коэффициентов равна .
• 4. Сумма биномиальных коэффициентов, стоящих на нечетных местах, равна сумме коэффициентов, стоящих на четных местах.

Задача 1. Найдите член разложения, не содержащий .

Решение. Согласно формуле (2.8) имеем. По условию задачи число должно удовлетворять уравнению где .

Таким образом, искомым будет второй член разложения:

.

В комбинаторном анализе существует целый ряд подходов для изучения комбинаторных объектов и чисел.

Теоретико-множественный подход

Этот подход связан с вычислением мощностей конечных множеств.

Пусть множество имеет элементов и одноместных отношений (свойств). Каждый из элементов может обладать или не обладать любым из этих свойств. Обозначим через число элементов, обладающих свойствами и может быть, некоторыми другими. Тогда число элементов, не обладающих ни одним из свойств, определяется по следующей формуле, называемой формулой включений и исключений:

(2.9).

где.

Обобщая формулу (2.9), получаем формулу, позволяющую вычислить число элементов, обладающих ровно свойствами ():

треугольник паскаль рекуррентный.

. (2.10).