Сочетания

Рассмотрим наборы, в записи которых порядок следования элементов не имеет значения. В комбинаторике такие наборы называются сочетаниями.

Определения и примеры

Неупорядоченная комбинация, содержащая т элементов, выбранных из л-элементного множества, называется сочетанием из п элементов по т элементов (или, сокращенно, сочетанием из п по т).

Если выбираются попарно различные элементы, то комбинация называется сочетанием без повторений. Если при составлении наборов допускается повторение элементов, то говорят, что рассматривается сочетание с повторениями.

Так как порядок элементов в наборе не имеет значения, то сочетания отличаются только составом элементов. Например, сочетание 2,2,4 имеет следующий состав: две цифры 2 и одна цифра 4. Поэтому набор 2,4,2 определяет то же самое сочетание. Набор 2,4,4 определяет другое сочетание (его состав: одна цифра 2 и две цифры 4).

Пример 11.1.1. Дано множество S= {2,3,4}. Запишем все сочетания с повторениями из 3 по 3.

• 2,2,2
• 2.2.3 2,2,4
• 2.3.3 2,3,4 2,4,4
• 3.3.3 3,3,4 3,4,4 4,4,4

В первой строке записаны все сочетания, в которых цифра 2 встречается три раза, во второй строке - сочетания, в которых цифра 2 встречается 2 раза и т. д.

Среди всех комбинаций имеется только одно сочетание без повторений - 2,3,4 (каждая цифра записана по одному разу). •

Пусть дано множество S. Рассмотрим его произвольное сочетание без повторений, то есть неупорядоченный набор различных элементов множества S. Такой набор однозначно определяет некоторое подмножество множества S. И наоборот, любое подмножество в S может быть рассмотрено как сочетание.

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

Очень часто вместо слов «сочетание без повторений» говорят просто «сочетание».

Пример 11.1.2. Пусть S- {1,2,3,4,5}. Найдем все сочетания (без повторений) из 5 по 3. Для этою составим всевозможные трехэлементные подмножества.

Подмножество можно представить в виде комбинации цифр, записанных в порядке возрастания, так как изменение порядка следования элементов не изменит подмножество. Организуем перебор:

• 1.2.3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5
• 2.3.4 2,3,5 2,4,5
• 3.4.5

Имеем 10 сочетаний. •