Дискретная математика (стр. 10 )

Спросил меня голос в пустыне дикой:

– Много ли в море растет земляники?

– Столько же, сколько селедок соленых

Растет на березах и елках зеленых.

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

Некоторые комбинаторные задачи решались еще в Древнем Китае, а позднее – в Римской империи. Однако как наука комбинаторика возникла в XVI веке. Первоначально применения комбинаторики были в основном ограничены азартными играми. Сначала – карточные игры и игра в кости, затем прибавилась игра в рулетку. Игроки хотели заранее знать свои шансы на выигрыш, а для этого нужно было уметь подсчитывать число различных возможных комбинаций в данной игре. Одним из первых, кто обратился к решению этих задач, был итальянский математик Николо Тарталья (Tartaglia, ок. 1499–1557). Позднее, в 1494 году итальянский математик Лука Пачиоли (Pacioli, ок. 1445–1514)

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

Задача. Два игрока договорились играть в кости до того момента, когда одному из них удастся выиграть m партий. Но игра была прервана после того, как первый выиграл a (a < m), а второй – b (b < m) партий. Как справедливо разделить ставку?

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

Спустя без малого пятьдесят лет другой итальянский математик Джероламо Кардано (Cardano, 1501–1576) подверг рассуждения Пачиоли справедливой критике, но и сам предложил ошибочное решение.

Дальнейшие исследования комбинаторных задач были предприняты спустя 100 с лишним лет, в XVII веке (1654 г.) французскими учеными Блезом Паскалем (Pascal, 1623–1662) и Пьером Ферма (Fermat, 1601–1665), в работах которых были также заложены основные понятия комбинаторики и теории вероятности.

Позже голландский математик Христиан Гюйгенс (Huygens, 1629–1695) в 1657 г. опубликовал первый трактат по теории вероятностей «О расчетах при азартных играх». Следует особо отметить работы Якоба Бернулли (Bernoulli, 1654–1705), который комбинаторными методами доказал первую содержательную теорему теории вероятностей – закон больших чисел (этот результат не потерял своего значения и в наши дни), а также работы Готтфрида Вильгеьма Лейбница (Leibniz, 1646–1716) и (позднее) Леонарда Эйлера (Euler, 1707–1783), впервые сформулировавшего задачу построения латинских квадратов, которая была решена лишь в 1959 году с помощью ЭВМ. В девятнадцатом веке методы комбинаторики получили окончательную «прописку» в теории вероятностей, став тем аппаратом, с помощью которого удалось получить многие серьезные результаты в этой области математики. И хотя аппарат современной теории вероятностей чрезвычайно расширился и усложнился по сравнению с аппаратом теории вероятностей XIX века, комбинаторные методы сохраняют свое значение для этой науки и сегодня. В последнее время, в связи с повышением интереса к проблемам дискретной математики, комбинаторика переживает период весьма бурного развития.

В каждой комбинаторной задаче требуется дать ответ на один и тот же вопрос: сколько различных комбинаций, подчиняющихся тем или иным условиям, можно составить из данного множества объектов? Вместо слова «комбинация» в математической литературе чаще используется слово «расстановка» (если в комбинацию входят k объектов, то говорят о k-расстановках). Термин «расстановка» представляется предпочтительнее термина «комбинация», поскольку в нем содержатся указания на то, как именно получается та или иная комбинация: нужно расположить, расставить в определенном порядке некото-

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

Имеется некоторое конечное множество, содержащее n различных объектов. Из него последовательно выбираются k объектов, при этом выбранный объект может быть как возвращен во множество (и, следовательно, выбран повторно – тогда говорят о выборе с возвращением, приводящем к расстановкам с повторениями), так и не возвращен (тогда говорят о выборе без возвращения – при таком способе выбора получаются расстановки без повторений). Если используется схема выбора, то вместо термина «k-расстановка» обычно используется термин «выборка объема k». Итак, в комбинаторных задачах мы имеем дело с выборками некоторого фиксированного объема. При этом, в соответствии с условием задачи, порядок следования в выборке объектов, или, как говорят, элементов, может как иметь, так и не иметь значение. В первом случае говорят об упорядоченных выборках, во втором – о неупорядоченных выборках.

3.2 Соединения комбинаторики

3.2.1  Размещения и перестановки

Определение. Всякая упорядоченная выборка объема k из множества, состоящего из n различных объектов, полученная в схеме выбора без возвращения, называется размещением из n элементов по k элементов.

Из определения выбора без возвращения следует, что k удовлетворяет неравенствам – читается: «а из n по k» (А – первая буква французского слова arragement, что означает «размещение, приведение в порядок»). Для числа размещений (или, как будем говорить, размещений) справедлива формула

где

Замечание. Число множителей в правой части формулы равно числу k.

Пример. Число размещений из 10 по 3 равно: . Из 5 по 3 равно: . Из 7 по 2 равно: .

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

Решение. Флаги будут различными, если хотя бы один из взятых трех цветов другой или порядок их другой. Следовательно, это будут размещения из семи по три, и их количество равно . То есть, используя семь цветов радуги, можно обеспечить различными трехцветными флагами 210 государств.

Особый интерес представляет собой случай k = n.

Определение. Размещения из n элементов по n называется перестановками из n элементов.

Так как каждая перестановка содержит n элементов рассматриваемого множества, то различные перестановки отличаются друг от друга только порядком элементов в выборке. Число всех перестановок из n элементов принято обозначать Pn (от французского слова permutation – «перестановка»). Очевидно, что , т. е. Рn равно произведению всех натуральных чисел от 1 до n. Следовательно,

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

Решение. Это число перестановок из пяти, т. е. . Следовательно, существует 120 вариантов расставить пять книг на полке, различаются варианты порядком следования книг. (Попробуйте это проверить?!)

Используя обозначение n!, можно формулу для числа размещений (при k<n) преобразовать следующим образом:

,

т. е.

.

Учитывая теперь, что по определению: 0!=1, из данной формулы получаем значение и при k = n:

3.2.2  Размещения и перестановки c повторениями

Определение. Пусть имеется k групп элементов, причем в первой группе n1 неразличимых элементов, во второй группе n2 неразличимых элементов, …, в k-й группе – nk неразличимых элементов. Элементы из разных групп различимы. Таким образом, имеется всего элементов. Рассмотрим все возможные упорядоченные наборы из этих элементов. Число различных таких наборов называется перестановками с повторением и обозначается символом . Число перестановок с повторениями равно: