Размещения, перестановки, сочетания

Основные понятия комбинаторики. Множества. Перестановки. Сочетания. Размещения. Разбиения. Понятие алгоритма и сложность алгоритмов.

Два основных правила комбинаторики

Для строгого вывода всех формул используются два основных правила комбинаторики:
Правило умножения (правило «и»). Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару A и B можно выбрать n·m способами.
Это правило обобщается на произвольную длину последовательности.
Правило сложения (правило «или»). Оно утверждает, что, если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами.
Эти правила нужны и для решения задач.

Понятие факториал также рапространяется на ноль: 0! = 1, так как считается, что пустое множество можно упорядочить единственным способом.

Размещения, перестановки, сочетания

Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два? .

Определение. Размещениями множества из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются либо самими элементами, либо порядком элементов.

Размещениями из n элементов по m (мест) называются такие выборки, которые имея по m элементов, выбранных из числа данных n элементов, отличаются одна от другой либо составом элементов, либо порядком их расположения.

Число размещений из n по m обозначается A_n^m и определяется по формуле
A_n^m =n·(n− 1)·(n− 2)·...·(n−m+ 1) =n!/(n − m)!

Число всех размещений множества из элементов по элементов обозначается через (от начальной буквы французского слова “arrangement”, что означает размещение), где и .

Теорема. Число размещений множества из элементов по элементов равно

Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.

Так, все различные перестановки множества из трех элементов — это

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

Число всех перестановок из элементов обозначается (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле