dm_tema_2

Биномиальные коэффициенты входят в формулу, которая получила название формулы бинома Ньютона.

Теорема (Формула бинома Ньютона)

n

X

(a + b)n = Cnk ak bn k : k=0

Формулу бинома Ньютона получим как следствие полиномиальной формулы.

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

X

(x1 + + xm)n = Cnk1;:::;km x1k1 : : : xmkm

k1+ +km=n k1;:::;km 0

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

Рассматриваемое выражение запишем в виде произведения n скобок

(x1 + + xm)n = (x1 + + xm) (x1 + + xm):

При раскрытии скобок получим mn слагаемых следующего вида

xi1 : : : xin , которые могут содержать повторяющиеся переменные. Пусть число повторений переменных x1; : : : ; xm

k1; : : : ; km. Тогда

xi1 : : : xin = x1k1 : : : xmkm ; k1 + + km = n:

Число таких слагаемых равно числу перестановок с повторениями

Pk1;:::;km = Cnk1;:::km :

Ïðè m = 2 полиномиальная формула принимает вид формулы бинома

Ньютона.

Как следствие формулы бинома Ньютона получим

Пример

Записать функцию (x + 1)5 в виде полинома. Применим формулу бинома Ньютона. Получим

5

X

(x + 1)5 = Cnk xk = 1 + 5x + 10x2 + 10x3 + 5x4 + x5:

k=0

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

Метод основан на формуле включений и исключений.

Теорема

Пусть A конечное множество и jAj = n. Пусть заданы некоторые свойства p1; : : : ; pm элементов множества A. Обозначим число

элементов множества A, обладающих свойствами pi1 ; : : : ; pik , через n(pi1 ; : : : ; pik ). Тогда число элементов множества A, не обладающих ни одним из свойств p1; : : : ; pm, равно

+( 1)m 1n(p1; : : : ; pm)):

Пример

В компании производителя программного обеспечения работают 50 человек. Из числа сотрудников компании 20 ведут разработки на языке программирования C++, 19 на языке Java, 16 на языке PHP, 12 на C++ и Java, 8 на C++ и PHP, 10 на Java и PHP, 5 на C++, Java и PHP. Сколько сотрудников не используют в своей работе ни один из указанных языков программирования?

Обозначим свойства сотрудников:

p1 сотрудник использует в своей работе язык программирования C++;

p2 сотрудник использует в своей работе язык программирования Java;

p3 сотрудник использует в своей работе язык программирования PHP.

По методу включений и исключений

n(p1; p2; p3) =n (n(p1) + n(p2) + n(p3)

n(p1; p2) n(p1; p3) n(p2; p3) + n(p1; p2; p3)) = =50 (20 + 19 + 16 12 8 10 + 5) = 20:

Пример

Сколько натуральных чисел от 1 до 100 не делятся одновременно на 2, 3 и 5?

Обозначим свойства чисел: p1 число делится на 2;

p2 число делится на 3;

p3 число делится на 5.

Пусть [a] есть целая часть числа. Тогда

Следовательно,

n(p1; p2; p3) =n (n(p1) + n(p2) + n(p3)

n(p1; p2) n(p1; p3) n(p2; p3) + n(p1; p2; p3)) = =100 (50 + 33 + 20 16 10 6 + 3) = 26:

2.5 Число функций

Теорема

Пусть jAj = m, jBj = n. Число всех функций f : A ! B равно nm.

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

Каждая функция есть упорядоченная выборка с повторениями из элементов множества B. Длина выборки равна m. Следовательно,

число функций равно

Теорема

Пусть jAj = jBj = n. Число всех биекций f : A ! B равно n!.

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

Каждая биекция есть перестановка элементов множества B. Следовательно, число биекций равно n!.