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

Рассмотрим некоторые понятия комбинаторики. Набор элементов, взятых из множества и выписанных в строчку называется выборкой r элементов из n. Выборка называется упорядоченной, если порядок следования элементов в ее записи задан, т. е. две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются разными. Две неупорядоченные выборки считаются равными тогда и только тогда, когда состоят из одних и тех же элементов.

Размещением из n по r называется упорядоченная выборка объема r из n различных элементов. Например, все размещения из четырех элементов А,В,С и D по два:

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC.

Число всех различных размещений из n по r обозначается .

Ясно, что

Отсюда,

Перестановкой n-ной степени называется размещение из n по n, т.е. иными словами любое взаимное расположение n элементов. Число всех различных перестановок n-ой степени обозначается через .

Тогда

В новых обозначениях

Сочетанием из n по rназывается неупорядоченная выборка объема r из n элементов, т.е. любое подмножество, состоящее из r элементов, взятых из множества, состоящего из n элементов. Число всех различных сочетаний из n по r обозначается через . Ясно, что

Достаточно очевидно свойство симметрии: . Действительно, отбор r из n элементов равносилен выбору n-r элементов, которые не входят в число отобранных.

Теорема. (формула Паскаля).

Доказательство. Все сочетания разобьем на два класса: класс сочетаний, не содержащих фиксированный элемент, и класс сочетаний, содержащих этот фиксированный элемент. В первом классе – сочетаний (выбираем те же r из n-1 элементов), а во втором – (добавляем к фиксированному элементу r-1 из n-1 элемента). В сумме эти два числа дают число всех сочетаний.

Методом полной математической индукции по n и r с помощью формулы Паскаля можно получить рабочую формулу для вычисления числа всех сочетаний

Можно провести следующее рассуждение. Одно сочетание из n по r порождает r! размещений из n по r, а сочетаний, соответственно, порождают размещений. С другой стороны, все сочетания из n по r порождают все размещения из n по r, а их Отсюда,

■

Числа называют биномиальными коэффициентами, так как они входят в качестве коэффициентов в слагаемые формулы бинома Ньютона