Сочетания

В ряде комбинаторных задач требуется определить число k-элементных подмножеств множества из n элементов. В этом случае порядок следования компонентов несущественен, т.е. производится неупорядоченная выборка.
В результате получают так называемые сочетания без повторения.
Сочетаниями без повторений из n элементов по k называются отли-чающиеся друг от друга хотя бы одним элементом выборки длины k, со-ставленные из n элементного множества.
Число сочетаний без повторений из n элементов по k, обозначаемое как   определяется, исходя из числа размещений без повторений с учетом то-го, что различных неупорядоченных векторов (подмножеств исходного множества) будет меньше в число раз, соответствующее числу перестано-вок без повторений из k элементов:
.
Пример. Определить число двухэлементных подмножеств множества, состоящего из трех элементов. Перечисляем все двухэлементные подмно-жества множества Х={х1,х2,х3}:
{х1,х2},{х1,х3},{х2,х3}.
Здесь мы имеем дело с сочетаниями из 3-х по 2:
.
Это величина в 2! раза меньше, чем число размещений из  , посколь-ку компоненты двухэлементных векторов можно переставить Р2=2! спосо-бами.
Пример. Сколькими способами можно выбрать 3 различных комбайна из 5 имеющихся?
Число размещений из 5 по 3 без повторений:  =543=60.
Один и тот же набор комбайнов можно получить различными способа-ми, например, векторы (а,b,с) и (b,а,с) дают один и тот же набор. Посколь-ку три элемента можно переставить Р3=3!=6 способами, то число способов выбора различных 3 комбайнов равно
.
В ряде комбинаторных задач требуется подсчитывать число различных составов векторов длины k из n элементного множества. Такие векторы-составы называются сочетаниями с повторениями из n элементов по k.
Например, требуется составить механизированные бригады из 3 ком-плексов 2 типов и определить количество таких бригад. Порядок следова-ния комплексов в векторе бригады роли не играет, а каждая бригада зада-ется вектором длины 3 из 2 элементов, порядок компонент которого роли не играет.
Получаем сочетания с повторениями из 2 элементов по 3:
(m1,m1,m1),(m1,m2,m2),(m1,m1,m2),(m2,m2,m2),
где m означает тип комплекса.
Итак, возможно построить бригаду из трех комплексов первого типа, трех комплексов второго типа, двух комплексов второго типа и одного пер-вого и, наконец, двух комплексов первого типа и одного второго, т.е. че-тырьмя способами.
Определение числа сочетаний с повторениями можно произвести сле-дующим образом [24].
Каждому сочетанию с повторениями из 2 по 3 ставится в однозначное соответствие вектор длины n+k-1=2+3-1=4, состоящий из 3 нулей и n-1=1 единицы:
Количество ком-плексов 1-го типа Разделитель Количество комплексов 2-го типа Состав вектора бригады
000 1    (m1,m1,m1)
0 1 00 (m1,m2,m2)
00 1 0 (m1,m1,m2)
1 000 (m2,m2,m2)

В таком случае число сочетаний с повторениями, которое обозначается  , равно числу перестановок с повторениями данного состава (вектор имеет одну единицу и три нуля), т.е. Р(3,1)= =4.
В общем случае, это выражение имеет вид
,
что соответствует выражению
.
Например, требуется составить подразделения из 6 рабочих 4 специ-альностей и определить количество способов формирования таких подраз-делений.
Получаем сочетания с повторениями из 4-х элементов по 6:
.