Комбинаторика и вероятность

Федеральное агентство по образованию

Сибирский государственный аэрокосмический университет

имени академика М.Ф. Решетнёва

Новоселов О.В., Скиба Л.П.

КОМБИНАТОРИКА И ВЕРОЯТНОСТЬ

Учебное пособие для слушателей подготовительных курсов

Красноярск 2009

УДК 519

Рецензенты: Балашова О.Ю., канд. физ. - мат. наук, проф. каф. высшей математики СибГАУ

Пашковская О.В., канд. физ. - мат. наук, доц. каф. «Математика» КрИЖТ ИрГУПС

Печатается по решению методического совета ИИКТ

Новоселов Олег Вадимович

Скиба Людмила Петровна

Новоселов О.В. Комбинаторика и вероятность: учебн. пособие для слушателей подготовит. курсов / О. В. Новоселов, Л.П. Скиба. СибГАУ, Красноярск, 2009. - 78 с.

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

© Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнёва , 2009

ПРЕДИСЛОВИЕ

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

О необходимости изучения в школе элементов комбинаторики и теории вероятностей речь идет очень давно. Так ещё в 1899 году попечитель Московского учебного округа профессор П. А. Некрасов на совещании по вопросам о средней школе говорил об огромном значении в школьном образовании того, что сейчас принято называть стохастической линией в преподавании математики. Методические указания как раз и посвящены изложению тех понятий, фактов, задач и обстоятельств, с которых, собственно, берет свое начало эта самая стохастическая линия.

В школьном стандарте по математике перечисляются следующие вопросы комбинаторики и теории вероятностей.

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

Элементарные и сложные события. Рассмотрение случаев и вероятность суммы несовместных событий, вероятность противоположного события. Понятие о независимости событий. Вероятность и статистическая частота наступления события».

Цель указаний: дать некоторый минимум, доступный слушателям подготовительных курсов и достаточный для формирования у них первоначальных комбинаторно-вероятностных представлений (в рамках школьного стандарта).

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

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

ВВЕДЕНИЕ

Когда кончается игра в три кости,

То проигравший снова их берет

И мечет их один в унылой злости.

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

Комбинаторика - это раздел дискретной математики, посвященный решению задач выбора и расположения элементов в соответствии с каким-либо правилом. Например, сколькими способами можно выбрать 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 в. Это связано с бурным развитием кибернетики и дискретной математики и широким использованием ЭВМ. В этот период активизировался интерес и к классическим комбинаторным задачам. Быстро выросло число комбинаторных задач и их разнообразие. Во многих областях математики (теория графов, теория чисел, теория групп, кибернетика, вычислительная математика и др.) имеются задачи или группы задач, комбинаторный характер которых угадывается без особых усилий.

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

1.       ПРИНЦИП УМНОЖЕНИЯ

При решении комбинаторных задач используются два правила: принцип умножения и принцип сложения.

Принцип умножения. Если элемент А можно выбрать из некоторого множества m способами и если после каждого такого выбора элемент B можно выбрать n способами, то пара элементов (А,В) в указанном порядке может быть выбрана (m×n) способами.

Пример 1.1. Из пункта А в пункт В ведут 3 дороги, а из пункта В в пункт С - 4 дороги. Сколькими способами можно совершить поездку из А в С через В?

Решение. В пункте А есть 3 способа выбора дороги в пункт В, а в пункте В есть 4 способа попасть в пункт С. Согласно принципу умножения, существует 3×4=12 способов попасть из пункта А в пункт С.

Принцип умножения легко обобщается на случай выбора трех и более элементов.

Пример 1.2. Сколько четырехзначных чисел можно составить из цифр 1, 2, 3, 4 и 5, если: а) цифры не повторяются; б) повторение допустимо; в) числа должны быть нечетные и без повторения.

Решение. а) Первую цифру можно выбирать 5-ю способами. Так как в числе цифры не повторяются, то вторую цифру уже можно выбрать из четырех оставшихся 4-мя способами. Далее получаем, что третью цифру можно выбрать 3-мя способами и четвертую - двумя. Таким образом, число возможных четырехзначных чисел равно N=5×4×3×2=120.

б) Так как повторения допустимы, то каждую цифру можно выбирать каждый раз из 5 имеющихся цифр, т.е. пятью способами. Тогда число возможных чисел равно N=5×5×5×5=54=625.

в) У нечетного числа последняя цифра нечетная, т.е. в данном случае может быть либо 1, либо 3, либо 5. Поэтому на это место можно поставить любую из этих трех чисел. После этого на оставшиеся места можно поставить: четыре цифры, три цифры и две цифры, ибо никакие из пяти цифр нельзя использовать более одного раза. Таким образом, N=3×4×3×2=72.

Упражнения

.1. Имеется 5 видов конвертов без марок и 4 вида марки. Сколькими способами можно выбрать конверт и марку для посылки письма?

Ответ: .

.2. На вершину горы ведут пять дорог. Сколькими способами турист может подняться на гору и потом спуститься с неё? Решите ту же задачу при дополнительном условии, что подъём и спуск происходят по разным дорогам.

Ответ: ; .

.3. При составлении одного варианта письменной контрольной работы по математике преподаватель располагает 4 задачами по геометрии, 8 - по алгебре и 3 - по тригонометрии. Сколькими способами можно составить этот вариант, если в него должно войти по одной задаче из перечисленных разделов?

Ответ: .

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

Ответ: .

.5. В книге из 20 страниц на каких-либо трех страницах надо поместить по одной разной иллюстрации. Сколькими способами это можно сделать?

Ответ: .

.6. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Ответ: .

.7. Сколькими способами Чип и Дейл могут поделить между собой 5 разных орешков?

Ответ: .

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

Ответ: .

2.       ПРИНЦИП СЛОЖЕНИЯ

Принцип сложения. Если элемент А можно выбрать из некоторого множества m способами, а другой элемент B - n способами, причём выборы А и В таковы, что взаимно исключают друг друга и не могут быть выбраны одновременно, то выбор какого-либо одного из этих элементов (либо А, либо В) можно осуществить (m+n) способами.

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

Пример 2.1. Пусть из города A в город B можно добраться одним авиамаршрутом, двумя железнодорожными маршрутами и тремя автобусными маршрутами. Сколькими способами можно добраться из города A в город B?

Рассмотрим пример, иллюстрирующий различие принципов умножения и сложения.

Пример 2.2. В магазине электроники продаются три марки телевизоров и два вида видеомагнитофонов. У покупателя есть возможности приобрести либо телевизор, либо видеомагнитофон. Сколько способами он может совершить одну покупку? Сколько различных комплектов, содержащих телевизор и магнитофон, можно приобрести в этом магазине, если покупатель собирается приобрести в паре и телевизор, и видеомагнитофон?

Решение. Один телевизор можно выбрать тремя способами, а магнитофон - другими двумя способами. Тогда телевизор или магнитофон можно купить 3+2=5 способов.

Во втором случае один телевизор можно выбрать тремя способами, после этого видеомагнитофон можно выбрать двумя способами. Следовательно, в силу принципа умножения, купить телевизор и видеомагнитофон можно 3×2=6 способами.

Замечание. Обычно принцип сложения применяется в тех случаях, когда в задачах встречаются союзы «или», «либо, либо» (телевизор или видеомагнитофон), а принцип умножения - в задачах, содержащих союз «и» (телевизор и видеомагнитофон).

Рассмотрим теперь примеры, в которых применяются оба правила комбинаторики: и принцип умножения, и принцип сложения.

Пример 2.3. В корзине лежат 12 яблок и 10 апельсинов. Ваня выбирает либо яблоко, либо апельсин, после чего Надя выбирает из оставшихся фруктов и яблоко и апельсин. Сколько возможно таких выборов?

Решение. Ваня может выбрать яблоко 12 способами, апельсин - 10 способами. Если Ваня выбирает яблоко, то Надя может выбрать яблоко 11 способами, а апельсин - 10 способами. Если Ваня выбирает апельсин, то Надя может выбрать яблоко 12 способами, а апельсин - 9 способами. Таким образом, Ваня и Надя могут сделать свой выбор  способами.

Пример 2.4. Есть 3 письма, каждое из которых можно послать по 6 адресам. Сколькими способами это можно сделать?

Решение. В данной задаче мы должны рассмотреть три случая: а) все письма рассылаются по разным адресам, б) все письма посылаются по одному адресу, в) только два письма посылаются по одному адресу. Если все письма рассылаются по разным адресам, то число таких способов легко находится из принципа умножения: n1=6×5×4=120 способов. Если все письма посылаются по одному адресу, то таких способов будет n2=6. Таким образом, остается рассмотреть только третий случай, когда только 2 письма посылаются по одному адресу. Выбрать какое-либо письмо мы можем 3 способами и послать его по какому-либо выбранному адресу можем 6 способами. Оставшиеся два письма мы можем послать по оставшимся адресам 5 способами. Следовательно, послать только два письма по одному адресу мы можем n3=3×6×5=90 способами. Таким образом, разослать 3 письма по 6 адресам в соответствие с принципом сложения можно

1+n2+n3 = 120+6+90 = 216 способами.

Упражнения

.1. В урне содержится 3 синих, 5 красных и 2 белых шара. Сколькими способами можно вытащить из урны либо два белых шара, либо два цветных шара, из которых один синий, а другой - красный?

Ответ: Все шары различимы и порядок важен. Поэтому все способов .

.2. Имеется 6 различных конвертов без марок, 4 различные марки и 3 различных конверта с марками. Сколькими способами можно выбрать конверт с маркой для отправки письма?

Ответ: .

.3. Семья новоселов хочет приобрести письменный стол, книжный шкаф и диван. В мебельном магазине имеется 6 письменных столов, 4 книжных шкафа и 12 диванов, Кроме того, есть 2 гарнитура, содержащих письменный стол и диван, и 8 гарнитуров, содержащих книжный шкаф и письменный стол. Сколькими способами может быть сделана покупка?

Ответ: .

.4. В букинистическом магазине лежат 6 разных изданий романа И.С. Тургенева «Рудин», 3 издания его романа «Дворянское гнездо» и 4 издания романа «Отцы и дети». Кроме того, есть 5 разных сборников, в каждом из которых есть романы «Рудин» и «Дворянское гнездо», и 7 сборников с романами «Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать покупку, содержащую по одному экземпляру каждого из этих романов?

А если в магазине есть ещё 3 сборника, содержащие романы «Рудин» и «Отцы и дети», и 5 книг, содержащих все три романа?

Решение: Можно купить либо по экземпляру каждого романа, либо сборник, содержащий два романа, и экземпляр третьего романа. Из принципов сложения и умножения получаем  способа. Во втором случае можно купить ещё сборник, содержащий романы «Рудин» и «Отцы и дети», и один экземпляр «Дворянского гнезда», либо сразу все романы. Всего имеем  способов.

При решении комбинаторных задач важно уметь выделять случаи, где можно использовать те или иные формулы. Пусть имеется множество, состоящее из n элементов, например, урна, содержащая n различных шаров. Выборкой будем называть любую совокупность k элементов этого множества; другими словами, выбор k шаров из урны. Однако при постановке такого эксперимента должно быть строго оговорено, каким способом производится выбор и что понимается под различными выборками.

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

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

В результате получаются четыре различные постановки эксперимента по выбору k элементов из общего числа n элементов некоторого множества.

Без возвращений (без повторений)