12. Сочетания

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

В результате получают так называемые сочетания без повторения.

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

Число сочетаний без повторений из n элементов по k, обозначаемое как определяется, исходя из числа размещений без повторений с учетом того, что различных неупорядоченных векторов (подмножеств исходного множества) будет меньше в число раз, соответствующее числу перестановок без повторений изk элементов:

.

Пример. Определить число двухэлементных подмножеств множества, состоящего из трех элементов. Перечисляем все двухэлементные подмножества множества Х={х₁,х₂,х₃}:

{х₁,х₂},{х₁,х₃},{х₂,х₃}.

Здесь мы имеем дело с сочетаниями из 3-х по 2:

.

Это величина в 2! раза меньше, чем число размещений из , поскольку компоненты двухэлементных векторов можно переставить Р₂=2! способами.

Пример. Сколькими способами можно выбрать 3 различных комбайна из 5 имеющихся?

Число размещений из 5 по 3 без повторений: =543=60.

Один и тот же набор комбайнов можно получить различными способами, например, векторы (а,b,с) и (b,а,с) дают один и тот же набор. Поскольку три элемента можно переставить Р₃=3!=6 способами, то число способов выбора различных 3 комбайнов равно

.

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

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

Получаем сочетания с повторениями из 2 элементов по 3:

(m₁,m₁,m₁),(m₁,m₂,m₂),(m₁,m₁,m₂),(m₂,m₂,m₂),

где m означает тип комплекса.

Итак, возможно построить бригаду из трех комплексов первого типа, трех комплексов второго типа, двух комплексов второго типа и одного первого и, наконец, двух комплексов первого типа и одного второго, т.е. четырьмя способами.

Определение числа сочетаний с повторениями можно произвести следующим образом [24].

Каждому сочетанию с повторениями из 2 по 3 ставится в однозначное соответствие вектор длины n+k-1=2+3-1=4, состоящий из 3 нулей и n-1=1 единицы:

В таком случае число сочетаний с повторениями, которое обозначается , равно числу перестановок с повторениями данного состава (вектор имеет одну единицу и три нуля), т.е. Р(3,1)==4.

В общем случае, это выражение имеет вид

,

что соответствует выражению

.

Например, требуется составить подразделения из 6 рабочих 4 специальностей и определить количество способов формирования таких подразделений.

Получаем сочетания с повторениями из 4-х элементов по 6:

.