Формула числа размещений без повторений.

Размещения из m по одному. Очевидно, что их число: А =m

Составим размещения по 2:

              -размещений (m-1)

  m-строк

       Итого: А =m(m-1)

Размещения по 3: В каждой строке будет (m-2) размещений

 

А ²_m  -строк

Ясно, что    А = А (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. Десять человек могут выйти Ậ ₈ ¹⁰ = 8 .

Таким образом, так как каждый элемент попадает в комбинацию m способами, где n комбинаций, то

                                                  Ậ = .