Получить код ссылки
Внешний вид
Пример
УчебаМатематика

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

Подсчет числа перестановок, размещений и сочетаний
Timur2010-09-04 18:58:29

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

Элементы комбинаторики. Перестановки, размещения, сочетанияCreative Commons Attribution/Share-Alike License 3.0 (Unported)
 
 
 
 

Итак, есть множество из 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

Комментарии

 Все обсуждения
Защита от спама