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

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

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

.

Пример 1

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

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

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

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

Пример 2

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

Число размещений из пяти по три без повторений:

.

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

.

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

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

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

,

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

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

Определение числа сочетаний с повторениями можно произ­вести следующим образом. Каждому сочетанию с повторениями из двух по 3 ставится в однозначное соответствие вектор длины , состоящий из трех нулей и  единицы, так как  (табл. 1.12).

Таблица 1.12 Определение числа сочетаний с повторениями

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

.

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

,

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

.

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

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

.