Введение

Когда кончается игра в три кости, То проигравший снова их берет И мечет их один в унылой злости.

Данте «Божественная комедия»

Комбинаторика – это раздел дискретной математики, посвященный решению задач выбора и расположения элементов в соответствии с каким-либо правилом. Например, сколькими способами можно выбрать 6 карт из колоды, состоящей из 36 карт; или сколькими способами можно составить очередь, состоящей из10 человек и т.д. Каждое правило в комбинаторике определяет способ построения некоторой конструкции, составленной из элементов исходного множества и называемой комбинацией. Основная цель комбинаторики состоит в подсчете количества комбинаций, которые можно составить из элементов исходного множества в соответствии с заданным правилом. Простейшими примерами комбинаторных конструкций являются перестановки, размещения и сочетания.

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

Теория вероятностей – это раздел математики, изучающий закономерности, присущие случайным явлениям. Казалось бы, «закономерность» и «случай» – противоположности. Закономерное – то, что в какой-то мере можно предсказать, случай же – как раз нечто непредсказуемое. Тем не менее, и случайным явлениям, не предсказуемым в полной мере, оказывается, могут быть присущи определенные закономерности, касающиеся большого числа однотипных случайных явлений, выполняющиеся приблизительно, в среднем.

В повседневной речи мы часто употребляем слова: «случайность», «случай» и другие. Например, мы говорим, что «это была случайность, что я завалил экзамен»; или «только случай помог кораблю вернуться в порт приписки после долгих странствий». В обыденном представлении случай противопоставляется закономерности, является чем-то, что нарушает ход событий. Но так ли это на самом деле? Если выучить только 5 вопросов из 25, то будет ли случайностью двойка на экзамене? Скорее закономерностью, хотя вероятность сдачи все-таки есть. Поэтому случайные события также подчиняются своим закономерностям. Изучение этих закономерностей и занимается наука о случайном – теория вероятностей.

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

Систематические исследования в области комбинаторики и теории вероятностей началось в XVI в. В жизни привилегированных слоёв тогдашнего общества большое место занимали азартные игры, широко были распространены всевозможные лотереи. В связи с этим, первые комбинаторные и вероятностные задачи касались в основном азартных игр – вопросов, сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей в данной карточной игре, каковы шансы выиграть в той или иной ситуации. Но они навсегда остались бы салонными играми, если бы и в практической деятельности (например, в статистике населения) не пришлось решать схожих задач.

Возникновение теории вероятностей и комбинаторики как науки относится в середине XVII в. и связано с исследованиями Б. Паскаля (1623-1662), П. Ферма (1601-1665) и Х. Гюйгенса (1629-1695) в области теории азартных игр. В этих работах постепенно формировались такие важные понятия, как вероятность и математическое ожидание; были установлены свойства и приёмы их вычисления. Особенно большую роль здесь сыграла задача о разделе ставки, которую предложил Паскалю его друг шевалье де Мере, страстный игрок. Проблема состояла в следующем: «матч» в орлянку ведётся до шести выигранных партий; он был прерван, когда один игрок выиграл 5 партий, а другой – 4; как разделить ставку? Было ясно, что раздел в отношении 5:4 несправедлив. Применив методы комбинаторики, Паскаль решил эту задачу. Он рассуждал так:

«Предположим, что ставка каждого игрока составляет 32 червонца и что первому не хватает одной партии до выигрыша, а второму двух. Им предстоит сыграть еще одну партию. Если ее выиграет первый, он получит всю сумму, то есть 64 червонца; если второй, у каждого будет по две победы, шансы обоих станут равны, и в случае прекращения игры каждому, очевидно, надо дать поровну. Итак, если выиграет первый, он получит 64 червонца. Если выиграет второй, то первый получит лишь 32. Поэтому, если оба согласны не играть предстоящей партии, то первый вправе сказать: 32 червонца я получу во всяком случае, даже если я проиграю предстоящую партию, которую мы согласились признать последней. Стало быть, 32 червонца мои. Что касается остальных 32 – может быть, их выиграю я, может быть, и вы; поэтому разделим эту сомнительную сумму пополам. Итак, если игроки разойдутся, не сыграв последней партии, то первому надо дать 48 червонцев, или же 3/4 всей суммы, второму 16 червонцев, или 1/4, из чего видно, что шансы первого из них на выигрыш втрое больше, чем второго (а не вдвое, как можно было бы подумать при поверхностном рассуждении).»

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

Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (1646-1716) в его диссертации «Комбинаторное искусство» (1666), где, по-видимому, впервые появился термин «комбинаторный». Большое значение для становления теории вероятностей и комбинаторики имела работа Я. Бернулли (1654-1706) «Искусство предположений» (1713), посвященная основным понятиям теории вероятностей, где обстоятельно изложен также и ряд комбинаторных понятий и указаны их применения для вычисления вероятностей. Можно считать, что с появлением работ Г. Лейбница и Я. Бернулли комбинаторные методы выделись в самостоятельную часть математики. С работы Бернулли по существу начинается становление теории вероятностей как науки. Доказанная им теорема, получившая впоследствии название «закона больших чисел», была первым теоретическим обоснованием накопленных ранее фактов.

Выдающаяся роль в развитии теории вероятностей принадлежит знаменитому математику П. Лаплас (1749-1827). Он впервые дал стройное и систематическое изложение основ теории вероятностей: «Аналитическая теория вероятностей» (1812). Он дал доказательство одной из форм центральной предельной теоремы (теоремы Муавра-Лапласа) и развил ряд замечательных приложений теории вероятностей к вопросам практики, в частности к анализу ошибок наблюдений и измерений.

В развитии теории вероятностей приняло участие огромное число замечательных учёных. Однако становление теории вероятностей как строгой математической науки, основанной на аксиоматическом методе, связано в первую очередь с выдающимся советским математиком А.Н. Колмогоровым (1903-1987). В 1933 г. вышла книга Колмогорова «Основные понятия теории вероятностей», в которой была предложена аксиоматика, получившая всеобщее признание и позволившая охватить не только все классические разделы теории вероятностей, но и дать строгую основу для развития её новых разделов, вызванных запросами естествознания.

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

В данных методических указаниях разбираются классические задачи и методы комбинаторики и теории вероятностей.