Глава 3. Структуры на множестве. Комбинаторика

Встречаются задачи, которые имеют несколько различных вариантов решений. Чтобы выбрать правильный из них, надо перебрать все возможные варианты. Задачи, требующие такого решения, называют комбинаторными. Раздел математики, в котором исследуются различные задачи на перебор, называется комбинаторикой.

Комбинаторика – это раздел математики, в котором для конечных множеств рассматриваются различные соединения элементов: перестановки, размещения, сочетания. В задачах, связанных с выборкой элементов множества, необходимо подсчитать количество различных комбинаций этих элементов. С теоретико-множественной точки зрения решение комбинаторных задач связано с выбором из некоторого множества подмножеств, обладающих определенными свойствами, и упорядочением множеств. Комбинаторика возникла в ХVI веке. В ней рассматривались задачи, связанные в основном с азартными играми. В процессе изучения таких задач были выработаны некоторые общие подходы к их решению, получены формулы для подсчёта числа различных комбинаций.

В настоящее время комбинаторика является одним из важных разделов математики. Её методы широко используются для решения практических и теоретических задач. Установлены связи комбинаторики с другими разделами математики. Появились направления в математике, в основу которых положена комбинаторика: перечислительная комбинаторика, комбинаторная теория, популярная комбинаторика, комбинаторный анализ, прикладная комбинаторная математика, комбинаторные методы дискретной математики, вероятностные методы в комбинаторике и т.д.

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

3.1. Перестановки

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

Определение 1: Перестановкаминазывают комбинации, состоящие из одних и тех же n – различных элементов и отличающиеся только порядком их расположения.

Рn= n! = 1×2×3×…×n.

(3.1)

где: Р_n– количество перестановок;

n! = 1 · 2 · 3· … · (n - 1) · n – произведение всех натуральных чисел от 1 до n включительно есть «n-факториал».

Необходимо учитывать, что факториал нуля равен единице: 0! = 1.

Пример 1.

Определить количество трехзначных чисел, которые можно составить из трех цифр: 3, 5, 7, с учётом использования каждой цифры в числе строго по одному разу.

Решение.

Количество трехзначных чисел в данном примере определяется по формуле перестановок (3.1) и равно: Р₃= 1×2×3=6.

Пример 2.

Подсчитать количество способов расстановки на полке 5 разных книг.

Решение.

На первое место можно поставить любую из 5 книг, для каждого варианта первой книги на второе место может быть поставлена любая из оставшихся 4 книг. Итак, число перестановок из 5 книг равно:

5! = 54321= 120.