- •2. Элементы комбинаторики
- •2.1. Основные понятия
- •2.2. Виды комбинаторных задач
- •2.3. Основные правила комбинаторики
- •Базис индукции
- •Решение
- •Решение
- •2.4. Размещения и сочетания
- •Определение
- •Рассмотрим примеры сочетаний
- •2.5. Разбиения множеств на части
- •2.6. Формула включений-исключений
- •Рассмотрим пример
- •Упражнение
- •3. Отношения
- •3.1. Определение и примеры отношений
- •3.2. Представление отношений
- •Табличное задание отношений
- •3.3. Операции над отношениями
- •Определение
- •3.4. Бинарные отношения на множестве
- •3.5. Отношения эквивалентности определение
- •Определение
- •Доказательство
- •Построение разбиения, порождаемого отношением .
- •3.6. Отношения порядка
- •Определение
- •Определение
Определение
Сочетанием из n элементов по m элементов n-элементного множества D называется всякая совокупность, состоящая из m элементов D.
Если множество D неизвестно или не уточняется, то говорят о размещениях из n по m.
Так же, как и для размещений, предполагается, что m 0. Если m = 0, то такое сочетание не содержит элементов, т.е. является пустым множеством.
Как следует из приведенного определения в сочетаниях, в отличие от размещений, важен только состав входящих в них элементов, которые в составе сочетания не различаются между собой.
Сочетания могут быть с повторениями и без них.
В сочетании без повторений все элементы совокупности являются разными. Для существования таких сочетаний необходимо выполнение дополнительного условия n m. Всякое такое сочетание может рассматриваться как подмножество того множества, из которого выбираются элементы сочетания. Поэтому множества всех сочетаний без повторений некоторого конечного множества и множество подмножеств этого множества равны.
Из приведенных определений следует, что в сочетании с повторениями могут содержаться одинаковые элементы. Поэтому сочетания без повторений одновременно являются и сочетаниями с повторениями.
Рассмотрим примеры сочетаний
Если покупатель оплачивает сделанную в магазине покупку, то совокупность передаваемых кассиру денег может рассматриваться как:
сочетание без повторений, если оплата осуществляется только банкнотами, каждая из которых имеет уникальный номер;
сочетание с повторениями, если оплата осуществляется монетами, среди которых могут встречаться неотличимые монеты одного достоинства.
Выведем формулы для определения числа сочетаний из n по m с повторениями и без повторений.
1.Число сочетаний без повторений из n по m.
Пусть D это некоторое множество, состоящее из n элементов. Рассмотрим все размещения без повторений из n по m, составленные из элементов этого множества. Число таких размещений равно .
Компоненты каждого такого размещения определяют некоторое сочетание без повторений из n по m, составленное из элементов этого размещения. При этом размещения, отличающиеся лишь порядком вхождения значений, образуют одно и то же сочетание.
Поскольку размещения, соответствующие одному и тому же сочетанию являются перестановками элементов этого сочетания, то всякое сочетание порождается m! различными размещениями. Обозначим число сочетаний из n по m без повторений как .
Поэтому имеет место равенство m! = .
Следовательно, справедлива следующая формула для числа сочетаний без повторений: = .
Пусть D это произвольное множество, содержащее n элементов. Тогда число mэлементных подмножеств этого множества равно . Значит число всех различных подмножеств данного множества равно + + ... + .
С другой стороны, поскольку число подмножеств nэлементного множества равно 2n, то для сочетаний без повторений справедливо равенство:
+ + ... + = 2n.
Упражнение
Используя комбинаторные доводы доказать справедливость равенств:
(1 - x)r = x0 + ... + (1)i xi+ ... + (1)r xr.
= .
2. Число сочетаний с повторениями из n по m .
Пусть D = {a1, ... , an} некоторое множество. Сочетания с повторениями, содержащие по m элементов этого множества, будем представлять двоичными последовательностями длины n + m 1, составленными из m нулей и n 1 единиц.
Двоичная последовательность, сопоставляемая отдельному сочетанию, состоит из n групп последовательно идущих нулей разделенных, n 1 единицами.
В i-й группе нулей, отсчитываемой слева направо, столько нулей, сколько экземпляров элемента ai входит в выбранное сочетание. Если некоторый элемент не входит в сочетание без повторений ни одного раза, то соответствующая ему группа нулей окажется пустой.
Например, если A = {a1, a2, a3, a4}, то сочетание с повторениями, содержащее 2 элемента a1, 3 элемента a2 и 2 элемента a4 представляется двоичным набором:
(0 0 1 0 0 0 1 1 0 0).
Покажем, что определенное ранее соотношение между сочетаниями с повторениями из n по m и двоичными последовательностями длины n + m 1, содержащими по m нулей, является биективным.
Всякая двоичная последовательность длины n + m 1, содержащая m нулей, разбивается входящими в неё единицами на n последовательно идущих групп нулей, определяющих количества вхождений элементов a1, ... , an в m элементное сочетание с повторениями. Следовательно, соотношение сочетаний с повторениями и двоичных последовательностей является сюрьективным.
Покажем, что если = 1, . . . , m+n1 и = 1, . . . , m+n1 две разные двоичные последовательности, то они представляют разные сочетания с повторениями. Пусть V1, . . . , Vn и W1, . . . , Wn последовательности групп нулей разделенных единицами в последовательностях и . Тогда найдется такое i, что Vi Wi. В противном случае и оказываются равными. Следовательно, соотношение сочетаний с повторениями и двоичных последовательностей является инъективным.
Поэтому, число сочетаний с повторениями из n по m равно числу рассматриваемых двоичных последовательностей.
Легко проверить, что последних ровно столько, сколько имеется различных способов выбора из n + m 1 позиций в двоичных последовательностях, таких n 1 позиций, в которые записываются единицы. В каждом случае остальные позиции последовательности заполняются нулями.
Число способов выбора различных n 1 позиций, если имеется n + m 1 разных позиций, равно: .
Для обозначения числа сочетаний с повторениями из n по m применяется запись . Поэтому справедлива формула:
= .
Рассмотрим несколько примеров задач, приводящих к использованию сочетаний с повторениями.
1. Определить число способов составления букета из 7 гвоздик, если имеются гвоздики трех цветов.
Очевидно, что букеты как комбинаторные объекты представляют собой сочетания с повторениями из 3 по 7. Поэтому число различных букетов равно .
2. Пусть имеется n одинаковых книг. Сколько может быть способов расстановки таких книг на шести полках книжного шкафа?
Очевидно, что всякая расстановка книг на полках соответствует сочетанию с повторениями из 6 элементов по n. В таком сочетании содержатся номера полок. Число вхождений номера некоторой полки в сочетание равно количеству книг, помещенных на эту полку.
Поэтому число указанных расстановок книг на полках равно .