В ряде комбинаторных задач требуется определить число 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.17).

Таблица 1.17

Количество комплексов 1-го типа	Разделитель	Количество комплексов 2-го типа	Состав вектора бригада
000	1
00	1	0
0	1	00
	1	000

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

.

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

,

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

.

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

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

.

Пример  1

Вычислить: .

Решение

.

Пример 2

Упростить: .

Решение

.

Пример 3

Сколько двузначных чисел можно составить из пяти цифр 1, 2, 3, 4, 5 при условии, чтобы ни одна из них не повторилась?

Решение

Так как двузначные числа отличаются друг от друга или самими цифрами, или порядком их следования, то искомое количество двузначных чисел равно числу размещений  из пяти цифр (n = 5) по две (m = 2) в каждой комбинации:

.

Итак, можно составить 20 различных двузначных чисел из пяти цифр 1, 2, 3, 4, 5, так, чтобы они не повторялись в числах.

Пример 4

Сколькими способами можно заполнить билет лотереи «Спортлото 5 из 36»?

Решение

Так как варианты заполнения должны отличаться хотя бы одним числом, то искомое количество способов заполнения равно числу сочетаний из n = 36 чисел по m = 5 чисел в каждой комбинации (здесь порядок следования элементов, очевидно, не учитывается):

.