Размещения из m по одному. Очевидно, что их число: А 
=m
Составим размещения по 2:
-размещений (m-1)
m-строк 
Итого: А 
=m(m-1)
Размещения по 3: В каждой строке будет (m-2) размещений
А 2m-строк 
Ясно, что А 
= А (m-2)=m(m-1)(m-2)
А 
= m(m-1)(m-2)(m-3)
………………………………
А 
= m(m-1)(m-2)….(m-(n-1)) (*)
Пример:
В группе 21 студент. Требуется выбрать старосту, профорга и физорга. Сколькими способами это можно сделать?
Решение:
Каждая тройка студентов может отличаться от другой тройки или распределением обязанностей, или хотя бы одним из студентов, то есть мы должны вычислить число размещений из 21 по 3:
m=21, n=3.
А 
=21*20*19=7980.
Другой вид формулы числа размещений.
Умножим числитель и знаменатель формулы (*) на (m-n)! Получим
А = 
, или
А = 
Каждое размещение содержит одно и то же количество элементов, взятых из данных m.
Перестановки.
Размещения из n-элементов по n, каждое из которых отличается друг от друга только порядком элементов, называются перестановками.
Их число обозначается 
:
= А 
=n*(n-1)*(n-2)…..2*1, то есть = n!
Пример:
Сколькими способами могут сесть 6 человек на 6-местную лавочку?
Решение:
В данном случае каждое расположение лиц на лавочке отличается от другого расположения только порядком. Поэтому мы имеем дело с перестановками:
=6!=720.
Сочетания.
Сочетания - это размещения, каждое из которых отличается от других хотя бы одним элементом.
Другими словами: Сочетания - это соединения, содержащие n элементов из данных m, отличающиеся хотя бы одним элементом.
Число сочетаний С . Если мы имеем m- элементов, и из них составим всевозможные сочетания по n и внутри каждого произведем перестановку, то получим размещения.
С * = А отсюда
С = 
= 
Пример:
В группе 20 студентов. Требуется выбрать 5 делегатов на конференцию. Сколькими способами это можно сделать?
Решение:
Так как внутри каждой пятерки делегатов перестановки дают одну и ту же пятерку, то каждая пятерка должна отличаться от других хотя бы одним делегатом. В данном случае мы должны посчитать число сочетаний из 20 по 5:
С 
= 
= 15504.
Свойства сочетаний.
1) С = С 
, достаточно выписать формулы левой и правой части равенства.
2) С 
= 
, т.к. по определению 0!=1
3) С 
= 
, т.к. по определению 1!=1
4) С 
= С 
+ С 
Доказательство:
С + С = 
+ 
= 
= 
= 
= 
= С
Что и требовалось доказать.
4) С = С 
* 
Доказательство:
= 
= , следовательно, С = С * .
Что и требовалось доказать.
Размещения с повторениями.
До сих пор мы рассматривали комбинации элементов, которые в каждой комбинации не повторялись. Рассмотрим размещения из m-элементов по n, в которых каждый элемент может повторяться. Такие размещения называются размещениями с повторениями: Ậ .
Рассмотрим задачу.
В лифт 9 этажного дома на 1-ом этаже вошло 10 человек, каждый из которых может выйти на любом этаже, начиная со второго. Сколькими способами они могут выйти из лифта?
Решение:
Каждый из пассажиров может выйти 8 способами. Два пассажира могут выйти Ậ 
= 8*8=8 
=64. Десять человек могут выйти Ậ810 = 8 
.
Таким образом, так как каждый элемент попадает в комбинацию m способами, где n комбинаций, то
Ậ = 
.