Введение.
В этой лекции будут рассмотрены следующие 4 вопроса.
1. Размещения.
2. Перестановки.
3. Сочетания.
4. Бином Ньютона.
Комбинаторика, или дискретная математика, изучает конечные множества для подсчета количества элементов, обладающих заданными свойствами. В настоящее время получила мощное развитие в связи с применением в теории автоматов.
Цель занятия: знать и уметь использовать бином Ньютона.
1. Размещения
Определение 1. Группы, составленные из каких-либо предметов, называются соединениями.
Определение 2. Размещениями из n элементов по p называются такие соединения, из которых каждое содержит p элементов, взятых из числа данных n элементов, и которые отличаются друг от друга либо самими элементами (хотя бы одним), либо лишь порядком их расположения.
Примеры.
Из одного элемента можно составить лишь одно размещение.
Из двух элементов а и b можно составить два размещения по одному элементу и два размещения по два элемента ab и ba.
Из трех элементов а, b и c можно составить три размещения по одному элементу; шесть размещения по два элемента ab, ba, ac, bc, ca, cb; шесть размещений по три элемента abc, bac, acb, bca, cab, cba и т.д.
Число размещений из n элементов по p в каждом будем обозначать символом 
.
Пусть имеется n элементов a, b, c, …,h, k, l. Очевидно, что размещений из n элементов по одному будет n.
. (1)
Составим размещения по два.
ab; ac; …..ah; ak; al;
ba; bc; …..bh; bk; bl;
ca; cb; …..ch; ck; cl;
……………………..
……………………..
la; lb; …...lh; lk.
Число размещений в каждой строке равно n-1, а число всех строк n. Следовательно,
(2)
Число размещений по три будет равно
(3)
Пользуясь методом математической индукции можно показать справедливость формулы
|
|
|
(3)
Предположим, что формула (3) выполняется, докажем, что тогда будет выполняться и равенство
Возьмем одно из размещений (3) k-го порядка и станем присоединять к нему по очереди каждый из оставшихся 
элементов, не вошедших во взятое нами размещение. Тогда мы получим размещений 
порядка.
Таким способом из каждого размещения k-го порядка можно образовать размещений -го порядка.
Но число всех размещений k-го порядка по нашему предположению равно произведению
Следовательно, из всех размещений k-го порядка можно составить указанным способом столько размещений -го порядка, сколько единиц окажется в произведении
Легко понять, что изложенным способом получим все размещения -го порядка, взятые только по одному разу. Поэтому окажется, что
.
Таким образом, из предположения, что формула (3) верна для p=k, мы пришли к тому, что формула оказывается верной при p=k+1. Но поскольку формула (3) верна при p=1, то значит она верна всегда, т.е. при любом натуральном значении p, меньшем или равном n.
Примеры.
;
;
;
.
Из последних двух формул следует, что
.
2. Перестановки
Определение 3. Перестановками из n элементов называются такие соединения, из которых каждое содержит все n элементов и которые отличаются друг от друга лишь порядком расположения элементов.
Из одного элемента можно составить лишь одну перестановку.
Из двух элементов а и b можно составить две перестановки ab и ba.
|
|
|
Из трех элементов а, b и c можно составить шесть перестановок abc, bac, acb, bca, cab, cba и т.д.
Число перестановок из n элементов обозначается символом 
.
Число перестановок из n элементов – это то же самое, что число размещений из n элементов по n в каждом. Поэтому
,
или
. (4)
Пример.
Сколькими различными способами могут разместиться на скамейке 10 человек?
Произведение n натуральных чисел обозначается сокращенно n!, т.е.
! (читается n факториал)
Формулу числа перестановок теперь можно записать так:
!
Умножив и разделив произведение
на !, получим:
.
Принимается, что 0!=1
3. Сочетания
Определение 4. Сочетаниями из n элементов по p называются такие соединения, из которых каждое содержит p элементов, взятых из числа данных n элементов, и которые отличаются друг от друга по крайней мере одним элементом.
Примеры.
Из одного элемента можно составить лишь одно сочетание.
Из двух элементов a, b можно составить два сочетания по одному элементу и лишь одно сочетание по два элемента ab.
Из ьрех элементов a, b, c можно составить:
3 сочетания по одному элементу:
A, b, c
3 сочетания по два элемента:
Ab, bc, ac
одно сочетание по три элемента:
Abc.
И т. д.
Число сочетаний из n элементов по p обозначается символом 
.
Если в каждом сочетании из n элементов по p сделать всевозможные перестановки, тот образуются всевозможные размещения из n элементов по p. Поэтому
|
|
|
Отсюда
или
(5)
Пример. Сколькими способами можно выбрать три лица на три одинаковые должности из десяти кандидатов.
.
Умножим числитель и знаменатель правой части формулы (5) на произведение 
. Тогда получим
или
или
(6)
Первое свойство сочетаний:
.
Доказательство:
и 
.
Отсюда
.
Второе свойство сочетаний:
Доказательство:
4. Бином Ньютона.
Очевидно, что
, так как 
;
, так как 
; 
Пусть верна формула
(7)
Умножим обе части этого равенства на 
.
Тогда получим:
=
,
т.е.
Пользуясь формулой
и приняв во внимание, что
и 
получим окончательно
Из предположения, что формула верна при n, пришли к выводу, что формула верна при n+1.
Возьмем
или
(8)
Свойства биномиальных коэффициентов.
1.Биномиальные коэффициенты, равноудаленные от начала и конца разложения равны между собой.
.
2. 
полагая в равенстве (8) a=b=1, получаем искомое равенство
3. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах.
Полагая в равенстве (8) a=b= -1, получаем искомый результат
Биномиальные коэффициенты можно получить из треугольника Паскаля
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
……………………………………………….
…………………………………………………….
- я строка этой таблицы дает биномиальные коэффициенты разложения n-ой степени бинома.
Контрольные вопросы по теме занятия:
1. Что называется размещениями?
2. Что называется перестановками?
3. Дайте пример применения бинома Ньютона.
Заключение.
Представим содержание лекции в виде следующей схемы.
Важнейшей формулой математики является бином Ньютона, для закрепления которой необходимо самостоятельно проверить его для нескольких невысоких показателей.
