6.1. Комбинаторные задачи
Комбинаторика – одна из самых древних отраслей математики. Несколько тысяч лет назад в Юго-восточной Азии из чисел и других знаков составлялись различные последовательности и таблицы с заданными свойствами. Определялись способы положения и перестановок элементов в данных структурах. В Древней Греции подсчитывали количество различных комбинаций сочетаний слов в словосочетаниях, способы построений геометрических фигур из заданных элементов. В Средние века в Европе предпринимались попытки вывода математических законов для существующих в то время азартных игр с использованием монет, игральных костей, карт, домино и т.д.
Научное обоснование комбинаторика получает в XVI-XVII веках, как приложение для решения задач из области теории вероятностей. Развитие комбинаторики обусловлено было необходимостью расчета количества возможных вариантов наступления того или иного события, комбинаций выбора предметов или иных действий, выполняемых случайным образом. В это время элементы комбинаторных расчетов появились в работах итальянских ученых Николо Тартальи (1499–1557), Джероламо Кардано (1501–1576), Галилео Галилея (1564–1642), и французских математиков Блеза Паскаля
(1623–1662) и Пьера Ферма (1601–1665).
Понятие «комбинаторика» введено, как термин, немецким математиком Готфридом Вильгельмом Лейбницем (1646 - 1716). В работе «Рассуждения о комбинаторном искусстве» (1666). Лейбниц, впервые опубликовал формулы сочетаний без повторений из k элементов по n, ввел специальные символы для определения количества конфигураций, высказывался о приложениях комбинаторики в различных сферах человеческой деятельности.
Развитием методов решения комбинаторных задач также занимались выдающиеся математики: Якоб Бернулли (1654–1705) и Леонард Эйлер (1707– 1783). В работах этих ученых рассматривались методы определения числа перестановок, сочетаний и размещений, как без повторений, так и с
91
повторениями, исследовались возможности использования комбинаторики в алгебре, аналитической геометрии, теории вероятности, математической статистике.
В XIX веке изучением геометрических конфигураций занимался известный немецкий математик Теодор Карл Рейе (1838–1892), а в работах американского ученого Элиакима Гастингса Мура (1862–1932) рассматривались тактические конфигурации. В XX веке с помощью
перечислительной комбинаторики известных математиков Дж.-К. Рота и Ричарда Стенли изучались свойства упорядоченных множеств, различных алгебраических структур, специальных алгебраических функций. В настоящее время комбинаторных методов исследования широко востребованы и интегрированы в современной математике и других науках.
6.3. Правила умножения и сложения.
Комбинаторными принято называть задачи, в которых необходимо подсчитать, сколькими способами можно осуществить то или иное требование, выполнить какое-либо условие, сделать тот или иной выбор. Такие способы построения некоторой конструкции из элементов исходного множества называются комбинаторными конфигурациями.
Рассмотрим задачи комбинаторики, описывающие наиболее общие и простые комбинаторные конфигурации. Многие такие задачи решаются с помощью основных теорем комбинаторики – правила сложения и правила умножения.
Правило сложения. Пусть некоторое множество А состоит из k элементов: А1, А2, А3, ..., Аk. Тогда, если элемент А1 может быть выбран n1 способами, элемент А2 – n2 способами, элемент А3 – n3 способами, ..., элемент Аk – nk способами, отличными от первых k – 1 способов, то выбор одного из элементов: или А1, или А2, …, или Аk может быть осуществлен n = n1 + n2 + n3 + … + nk способами.
Данное правило можно сформулировать иначе. Пусть имеется k различных групп А1, А2, А3, ..., Аk, причем каждая i-ая группа содержит ni
92
элементов. Если один элемент из группы Ai можно выбрать ni способами, и при этом любые две группы Ai и Aj не имеют общих элементов, то выбор одного элемента или из A1, или из A2, ..., или из Ak можно осуществить n = n1 + n2 + n3 + … + nk способами.
Решим комбинаторные задачи, используя правило сложения.
Пример. В ящиках имеется 140 обычных, 30 трассирующих и 65 холостых патронов. Сколько существует способов извлечения из ящиков либо одного обычного, либо одного трассирующего, либо одного холостого патрона?
Решение. Так как количество способов выбора одного обычного патрона n1 = 140, количество способов выбора одного трассирующего патрона n2 = 30, а количество способов выбора одного трассирующего патрона n3 = 65, то согласно правилу сложения количество способов извлечения из ящиков обычного или трассирующего или холостого патрона n = n1 + n2 + n3= 140 + 30 + 65 = 21.
Пример. В подразделении имеются три легковых автомобиля и два микроавтобуса. Для перевозки семи сотрудников к месту патрулирования можно выбрать либо два легковых автомобиля, либо один микроавтобус. Сколькими способами это можно сделать?
Решение. Снова будем использовать правило сложения. Легко рассчитать, что количество способов выбора двух легковых автомобилей из трех n1 = 3. На самом деле, первый способ – можно взять первый и второй автомобили, второй способ – берем первый и третий автомобили, третий способ – выбрали второй и третий автомобили. Количество способов выбора одного микроавтобуса из двух, естественно, равно n2 = 2. Тогда количество всех способов выбора транспортных средств для перевозки личного состава равно n = n1 + n2 = 3 + 2 = 5.
Правило умножения. Пусть некоторое множество А состоит из k
элементов: А1, А2, А3, ..., Аk. Если элемент А1 может быть выбран n1 способами, после каждого такого выбора элемент А2 может быть выбран n2 способами, …, после каждого k – 1 выбора элемент Аk может быть выбран nk
93
способами, то выбор всех элементов А1, А2,…, Аk в указанном порядке может быть осуществлен n = n1 n2 n3 … nk способами.
Cформулируем это правило по-другому. Пусть имеется k групп А1, А2, А3,
..., Аk, причем i-ая группа содержит ni элементов. Тогда общее число n способов, которыми можно получить упорядоченную совокупность (a1, a2, a3,..., ak), где ai Ai (т.е. выбрать по одному элементу из каждой группы и расставить их в определенном порядке), равно n = n1 n2 n3 … nk.
Пример. В учебной группе 17 курсантов. Сколько способов может быть при назначении заместителя командира взвода и двух командиров отделений при условии, что каждый учащийся может быть выбран только на одну из этих должностей?
Решение. Пусть сначала назначается заместитель командира взвода, это может сделать одним из 17 способами; командира первого отделения можно выбрать из оставшихся курсантов 16-ю способами, а затем остается 15 вариантов назначения командира второго отделения. Используя правило произведения, найдем количество способов одновременного назначения заместителя командира взвода и двух командиров отделений: n = n1 n2 n3 = 17 16 15 =4080.
Пример. Два почтальона должны разнести 10 писем,15 газет и 2 бандероли по 12 адресам. Сколькими способами они могут распределить свою работу, учитывая, что двум почтальонам ходить по одному адресу нецелесообразно?
Решение. Первый адрес имеет n1=2 альтернативы – либо к адресату идет первый почтальон, либо второй. Для второго адресата также есть n2=2 альтернативы и т.д., т.е. n1=n2=…=n12=2. Следовательно, в силу правила умножения общее число способов распределений доставки корреспонденции между двумя почтальонами равно n = n1 n2 n3 … n12 =212 = 4096.
6.2.Комбинаторные конфигурации без повторений
Вкомбинаторных задачах часто определяется количество всех подмножеств данного множества, удовлетворяющих определенным условиям.
94
Однако, в одних конфигурациях рассматриваются подмножества, отличающиеся не только элементами, но и установленным порядком следования элементов, в других порядок следования элементов не важен и подмножества, отличающиеся только расположением в них элементов, не считаются различными. Кроме того, в одних случаях исследуемые подмножества могут содержать неограниченное количество повторений выбранных элементов, а в других эти элементы могут браться только однократно. Все эти обстоятельства необходимо учитывать при решении комбинаторных задач.
Способы построения некоторой конструкции из элементов исходного множества, в которых все выбранные элементы представлены только по одному разу, называются конфигурациями без повторений.
Размещения без повторений
Определение размещения без повторений. Пусть имеется множество,
содержащее n элементов. Каждое его упорядоченное подмножество, состоящее из k элементов, называется размещением (размещением без повторений) из n элементов по k элементов.
Можно привести другую формулировку определения размещения без повторений.
Размещение из n элементов по k – это все k-элементные подмножества, отличающиеся составом элементов или порядком их следования.
Для обозначения числа размещений принят специальный математический символ: Ank (число размещений из n элементов по k). Рассчитать количество размещений можно, используя следующую теорему.
Теорема. Количество размещений из n элементов по k элементов равно произведению k последовательных натуральных чисел от n до n – k + 1 включительно, т. е.
Ank n(n 1)(n 2)...(n k 1), k 0.
95