Элементы комбинаторики. Перестановки, размещения, сочетания

Подсчет числа перестановок, размещений и сочетаний.

Ниже калькулятор, подсчитывающий число перестановок, размещений и сочетаний. Под ним, как водится, ликбез, если кто подзабыл.

PLANETCALC, Элементы комбинаторики. Перестановки, размещения, сочетания

Элементы комбинаторики. Перестановки, размещения, сочетания

Число перестановок из n
 
Число размещений из n по m
 
Число размещений из n по m с повторениями
 
Число сочетаний из n по m
 

Итак, есть множество из n элементов.

Вариант упорядочивания данного множества называется перестановкой (permutation).
Например, есть множество, состоящее из 3 элементов - А, В, и С. Пример перестановки — СВА. Число всех перестановок из n элементов:
P_n = n!

Пример: Для случая А, В, С число всех перестановок 3! = 6. Перестановки: АВС, АСВ, ВАС, ВСА, САВ, СВА

Если из множества n элементов выбирают m в определенном порядке, это называется размещением (arrangement).
Пример размещения из 3 по 2: АВ или ВА — это два разных размещения. Число всех размещений из n по m
A_{n}^m=\frac{n!}{(n-m)!}

Пример: Для случая А, В, С число всех размещений из 3 по 2 равно 3!/1! = 6. Размещения: АВ, ВА, АС, СА, ВС, СВ

Также бывают размещения с повторениями, как ясно из названия, элементы на определенных позициях могут повторяться.
Число всех размещений из n по m с повторениями:
A_{n}^{'m}=n^m

Пример: Для случая А, В, С число всех размещений из 3 по 2 с повторениями равно 3*3 = 9. Размещения: AA, АВ, АС, ВА, BB, ВС, СА, СВ, CC

Если из множества n элементов выбирают m, и порядок не имеет значения, это называется сочетанием (combination).
Пример сочетания из 3 по 2: АВ. Число всех сочетаний из n по m
C_{n}^m=\frac{n!}{m!(n-m)!}

Пример: Для случая А, В, С число всех сочетаний из 3 по 2 равно 3!/(2!*1!) = 3. Сочетания: АВ, АС, СВ

Приведем до кучи формулу соотношения между перестановками, размещениями и сочетаниями:
C_{n}^m=\frac{A_{n}^m}{P_m}
Обратите внимание, что внизу P_m

Ссылка скопирована в буфер обмена
PLANETCALC, Элементы комбинаторики. Перестановки, размещения, сочетания

Комментарии