Комбинаторика

Теория

Комбинаторика — раздел математики, который занимается задачами выбора и расположения элементов из некоторого множества в соответствии с заданными правилами. Пусть имеется множество ("алфавит") из n объектов. Для наглядности возьмём множество из трёх цифр: {1, 2, 3}. Формулы комбинаторики определяют количества возможных комбинаций этих элементов между собой.

Перестановки

Берутся все n элеметов исходного множества, меняется лишь порядок их следования друг за другом. В нашем случае — составляются "слова" из всех трёх элементов исходного множества: {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}.

Количество неповторяющихся вариантов перестановки в этом случае определяется формулой:

где ! — обозначение факториала (n! = 1 ∙ 2 ∙ 3 ∙ ... ∙ n). В нашем примере оно равно 3! = 6.

Размещения

Из исходного множества ("алфавита" из n элементов) берётся только m каких-то элементов, и выполняются различные перестановки только этого количества элементов. При этом рассматриваются все возможные способы выборки такого количества элементов из исходного множества.

Например, когда из исходного множества из n = 3 цифр: {1, 2, 3} берутся подмножества из m = 2 цифр: {1,2}, {1,3}, и {2,3}, получаем следующую подборку комбинаций: {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}.

Количество различных возможных вариантов таких комбинаций элементов вычисляется по формуле:

В нашем случае оно равно: 3! / (3 - 2)! = 3! / 1! = 6.

Сочетания

Из исходного множества n берётся m каких-то элементов, но в пределах каждого такого способа выборки никакие перестановки не производятся, т.е. нас интересуют не все возможные комбинации перестановок, а только лишь количество возможных подмножеств(порядок следования элементов в каждом подмножестве не важен).

Например, из исходного множества из n = 3 цифр: {1,2,3} берутся подмножества из m = 2 цифр: {1,2}, {1,3}, {2,3}. Варианты {2,1}, {3,1} и {3,2} считаются совпадающими с предыдущими.

Количество возможных таких сочетаний определяется по формуле:

В нашем случае оно равно: 3! / (3 - 2)! ∙ 2! = 3! / 2! = 3.

Перестановки с повторениями

Пусть исходное множество может, кроме уникальных, неповторяющихся, содержать какие-то одинаковые элементы, например: {1,1,2,2,2,3,3,3,3}.

Тогда при всех возможных перестановках будут возникать одинаковые варианты, в которых местами меняются только одинаковые элементы. Такие повторы необходимо исключить при подсчёте количества неповторяющихся комбинаций.

Формула количества возможных перестановок с повторениями:

где n = n1 + n2 + ... + nk.

Здесь n — общее количество элементов в исходном множестве (для нашего примера — 9), а n1, n2, n3 ... — количества элементов в каждой группе из одинаковых элементов(в примере имеется n1 = 2 элемента "1", n2 = 3 элемента "2", n3 = 4 элемента "3").

Если в исходном множестве есть неповторяющиеся (уникальные) элементы, то каждый из них считается входящим в группу из одного такого элемента. Далее можно применить ту же формулу. Однако, учитывая, что 1! = 1 и фактически уникальные элементы на результат расчётов никак не влияют, можно принять за основу следующее правило: в указанной формуле просто брать значение n равным общему количеству элементов множества (как уникальных, так и повторяющихся), а в качестве n1, n2, n3 ... брать численности групп из нескольких повторяющихся элементов.

В итоге количество перестановок с повторениями в нашем примере равно: 9! / 2! ∙ 3! ∙ 4! = 1260.

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

Пусть имеется исходное множество из различных элементов, из которого требуется выбрать k элементов и расставлять их на n местах, так что каждый элемент может использоваться несколько раз, а может не использоваться совсем.

Либо: имеется исходное множество из k элементов, при этом можно брать их все любое количество раз, расставляя в n знакоместах.

Формула:

Фактически же в данном случае можно считать, что рассматривается количество всех возможных n-значных чисел в системе счисления с основанием k.

Пример: {1,2,3,4,5,6,7} — имеются 4 нечётных и 3 чётных цифры. Требуется определить количество различных (неповторяющихся) комбинаций из трёх нечётных цифр. Получается: k = 4 (всего нечётных цифр в исходном множестве), n = 3 (берём любые три цифры из этого набора и расставляем на трёх позициях). Тогда количество возможных комбинаций равно 4^3 = 64.

Сочетания с повторениями

Имеется множество, в котором, возможно, есть одинаковые элементы n различных разновидностей. Из него берётся некоторое количество k элементов (как одной, так и разных разновидностей; возможно, что какой-то вид элементов в тех или иных комбинациях вообще не будет выбран). Требуется узнать количество возможных различных комбинаций (наборов) таких элементов.

Формула:

Пример: исходное множество {1,1,2,2,2,3,3,3,3}. Требуется найти количество различных наборов, получаемых из 5 любых выбранных из такого множества элементов. Здесь n = 3 (три возможных разновидности: "1", "2" и "3", при этом количества элементов каждой разновидности значения не имеют), а k = 5 (каждый набор состоит из 5 каких-то элементов.) Тогда количество различных наборов равно:

На этом основные формулы заканчиваются.