Определение 10: Конечные неупорядоченные множества называются сочетаниями.

Таким образом, сочетания – это такая выборка элементов, при которой их порядок совершенно не важен.

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

Теорема 4: Число сочетаний находится по следующей формуле:

. (4)

Доказательство. Если из произвольного -элементного множества выбраны элементов, то их можно пронумеровать номерами числом способов, равным . Оставшиеся элементов можно занумеровать номерами , , …, всего способами. Кроме того, сам отбор элементов из элементов можно осуществить способами. Таким образом, мы получили вариантов нумерации полного множества из элементов, которых всего . Поэтому имеем , откуда получаем:

.

Теорема доказана.

Замечание: Дробь, стоящая в правой части (4), может быть сокращена до целого числа.

Из формулы числа сочетаний следует:

, , .

Формула (4) может быть преобразована к виду: . Отсюда видно, что число размещений в раз больше числа соответствующих сочетаний . Другими словами, чтобы посчитать все сочетания , нужно исключить из всех размещений подмножества, отличающиеся порядком (их будет штук), т.е. делят на .

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

Решение. Порядок выбора красок не важен. Важно только какие краски выбраны. Поэтому количество вариантов равно: .

Пример 6: Сколькими способами можно пошить трехцветные полосатые флаги, если имеется материал пяти различных цветов.

Решение. Порядок выбора полос важен, поэтому количество таких флагов равно: .