Тема 2. Элементы комбинаторики и применение

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

Комбинаторика имеет непосредственное отношение к теории вероятностей. Близость этих разделов обусловлена, прежде всего, классическим способом подсчёта вероятностей. Формула, гдечисло всех элементарных исходов опыта, ачисло исходов, благоприятных для, сводит вычисленияк нахождению отношения двух чисели; последняя задача во многих случаях носит явно комбинаторный характер. Кроме теории вероятностей, комбинаторика используется в теории вычислительных машин, теории автоматов, некоторых задачах экономики, биологии, генетики и т.д.

1. Правило суммы и произведения.

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

Правило суммы. Правило суммы выражает следующий вполне конкретный факт: если и- два непересекающихся конечных множества, то число элементов, содержащихся в объединении этих множеств, равно сумме чисел элементов в каждом из них. Действительно, если условимся обозначить число элементов конечного множества, то правило суммы запишется равенством. Это правило легко обобщается для любого числа непересекающихсямножеств: есликакие-то попарно непересекающиеся конечные множества, тогда их сумма определяется равенством:

_{Следует заметить, что задачи, которые можно решить применением только правила суммы, в основном несложные. Обычно правило суммы полезно использовать вместе с правилом произведения.}

Правило произведения.Пусть заданы последовательности данной длины:, состоящие из некоторых элементов(необязательно различных). Для краткости условимся называть такие последовательностимерными строками.Две строкиибудем считать различными в том и только в том случае, если хотя бы для одного номера(из совокупности 1, 2, … , k) элемент. Правило произведения формулируется следующим образом.

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

Это правило доказывается индукцией по . Пусть. Обозначим черезразличные значения дляСреди строкимеется ровнострок, начинающихся с, т.е. строки вида, ровностроки, начинающихся с, и т.д. Следовательно, число всех строкбудет:

;

число слагаемых равно .

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

Любую строку

(*)

можно рассматривать как строку из двух объектов: из строки и элемента. Первый объект, по предположению индукции, может быть выбранспособами; при любом из этих способов элементпо условию может быть выбранспособами. Далее, применяя уже доказанное правило для строк длиныполучим, что число различных строк вида (*) будет.

Рассмотрим следующий пример.Сколько можно составить пятизначных чисел так, чтобы любые две соседние цифры числа были различны?

Решение.Пятизначному числу с цифрамиможно сопоставить строку При этом выбор цифры(не нулевых) возможен 9 способами, есливыбрана, то для выбора(любая из цифр 0,1,2,…,9, отличное от) имеется тоже 9 возможностей, после выбора,дляснова имеется 9 (любая из цифр 0,1,2,…,9, отличное от) возможностей выбора и т.д.

Применяя правило произведения, находим, что искомое количество чисел есть .