Размещения из 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 комбинаций, то
Ậ = .