1.1 История комбинаторики

Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. индейцы умели вычислять числа, которые сейчас называют «сочетания». В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. Предполагают, что индейские ученые изучали соединения в связи с применением их в поэтике - науке о структуре стиха и поэтических произведений.

В жизни общества большое место занимали азартные игры, карты, кости и т. д. Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю зарождавшейся теории вероятностей вошла переписка заядлого игрока Антуана Гомбо (так же известного как шевалье де Мерэ) с Пьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии - как для разработки шифров, так и для их взлома.

Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики. Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше), так же он использовал и термин «размещение» (arrangement). Следует подчеркнуть, что исходным пунктом их исследований тоже были проблемы азартных игр.

Усилиями Лейбнеца и Бернули комбинаторика сформировалась как отдельная дисциплина. Современная символика сочетаний была предложена авторами учебных руководств только в XIX в.

1.2 Основные понятия комбинаторики

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

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

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

Основными типичными операциями и связанными с ними задачами комбинаторики, является следующее:

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

2. Образование подмножеств, состоящее в выделении из данного множества некоторой части его элементов, составление сочетаний.

3. Образование упорядоченных подмножеств, составление размещений.

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

1.3 Формулы комбинаторики

Комбинаторные задачи бывают самых разных видов. Однако большинство задач решается с помощью двух основных правил - правила суммы и правила произведения.

Правило суммы. Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m + n) способами.

При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В. Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k ) способов выбора, где k - число совпадений.

Пример 1. В ящике 200 деталей, причём 130 из них первого сорта, 20 - второго, а остальные - третьего сорта. Сколькими способами можно извлечь из ящика одну деталь первого или второго сорта?

Решение. Деталь первого сорта может быть извлечена m=130 способами, второго сорта n=20 способами. По правилу суммы существует

m + n=130 + 20 =150

способов извлечения одной детали первого или второго сорта.

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

При этом число способов выбора второго объекта не зависит от того, как именно выбран первый объект.

Пример 2. Из пункта А в пункт В ведут 5 дорог, а из пункта В в пункт С ведут 3 дороги. Сколько путей, проходящих через пункт В, ведут из пункта А в пункт С?

Решение. Переезд из А в В можно осуществить пятью способами, то есть m=5, а из В в С оставшимися тремя способами, то есть n=3. Последовательное выполнение первого и второго действий - это переезд из А в С через В. По правилу произведения получаем

mn = 5 • 3 = 15

путей ведущих из пункта А в пункт С, через пункт В.

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

n! = 1 · 2 · 3 · 4 · … · (n-2) · (n-1) · n

Случай 0! определен и имеет значение 0!=1, соответствующее комбинаторной интерпретации комбинации нуля объектов, другими словами, есть единственная комбинация нуля элементов, а именно: пустое множество.

Ниже приведены значения факториалов от 0 до 10.

0! = 1

1! = 1

2! = 1 · 2 = 2

3! = 1 · 2 · 3 = 6

4! = 1 · 2 · 3 · 4 = 24

5! = 1 · 2 · 3 · 4 · 5 = 120

6! = 1 · 2 · 3 · 4 · 5 · 6 = 720

7! = 1 · 2 · 3 · 4 · 5 · 6 · 7 = 5040

8! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 = 40320

9! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 = 362880

10! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 = 3628800

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

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

Решение. Имеем перестановки из 5 элементов.

пятизначных чисел можно составить из данных цифр.

Перестановки с повторениями. Рассмотрим задачу совокупности из n объектов, но при этом какие-то группы объектов из этой совокупности мы будем брать одинаковые. Пусть

Число всех перестановок с повторениями совокупности из n объектов обозначается P_n (k₁, k₂, k₃, …, k_m) и вычисляется по формуле

Пример 4. Найдем количество перестановок всех букв в слове КОМБИНАТОРИКА.

Решение. В этом слове две буквы «к», две буквы «о», одна буква «м», одна буква «б», две буквы «и», одна буква «н», две буквы «а», одна буква «т» и одна буква «р». Таким образом, число перестановок букв этого слова равно

количество перестановок букв в слове КОМБИНАТОРИКА.

Размещение без повторений. Размещение без повторений из m объектов по n объектов, называется всякая упорядоченная выборка, содержащая m объектов выбранная из n объектов. Число данных размещений обозначается и вычисляется по формуле

Пример 5. Из группы в 25 человек требуется выбрать старосту, заместителя старосты и профорга. Сколько вариантов выбора руководящего состава группы?

Решение. Старосту выбрать можно одним из 25 способов. Поскольку выбранный староста не может быть своим заместителем, то для выбора заместителя старосты остается 24 варианта. Профорга выбирают одним из 23 способов. Таким образом получаем

вариантов выбора актива группы.

Размещение с повторением. Размещение с повторением это такие упорядоченные выборки из n объектов, которые содержат m объектов, но при этом некоторые объекты могут повторяться. Число данных размещений обозначается и вычисляется по формуле

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

Решение. Мы из трех данных цифр, то есть n=3, находим все возможные варианты двузначных чисел, то есть m=2, тогда применив формулу размещения с повторением получаем

двузначных чисел можно составить из трех цифр.

Сочетание без повторений. Сочетание без повторений из n объектов по m объектов, называется всякий неупорядоченный выбор m объектов из совокупности n объектов. То есть данные сочетания отличаются друг от друга только самими объектами, порядок роли не играет. Число таких сочетаний обозначается и вычисляется по формуле

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

Решение. Электриков можно выбрать

способами.

Сочетание с повторениями. Сочетание с повторениями из n объектов по m, называется неупорядоченная выборка из n объектов, содержащая m объектов, причем некоторые из них могут повторяться. Число таких сочетаний обозначается и вычисляется по формуле

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

Решение. Из четырех возможных видов пирожных, то есть n=4, нам нужно купить 7 пирожных, значит m=7. Воспользовавшись формулой, сочетание с повторениями получаем

вариантов покупки 7 пирожных из 4 видов.

1.4 Вероятность

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

Событием называется результат некоторого испытания (опыта, наблюдения и т.п.).

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

Пример 1. Случайными являются события:

A - «при бросании игрального кубика выпало 2 очка»;

B - «при бросании монеты появился герб»;

C - «при выстреле стрелок попал в цель»

Событие называется достоверным, если оно обязательно произойдет при осуществлении данного испытания.

Событие называется невозможным, если оно не может произойти при осуществлении данного испытания.

Пример 2. Событие A - «при бросании игрального кубика выпало 7 очков» является невозможным, а событие B - «при бросании игрального кубика выпало меньше 7 очков» является достоверным.

Два события называются несовместными, если появление одного из них исключает появление другого в одном и том же испытании.

Пример 3. Брошена монета. События A - «появился герб» и B - «появилась цифра» несовместны, так как при однократном бросании монеты появление герба исключает появление цифры.

Несколько событий называются несовместными, если они попарно несовместны.

Два события называются совместными, если появление одного из них не исключает появление другого в одном и том же испытании.

Пример 4. Монета брошена два раза. События A - «появился герб при первом бросании» и B - «появился герб при втором бросании» являются совместными.

Несколько событий образуют полную группу событий, если в результате испытания обязательно появится хотя бы одно из них.

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

Пусть события по отношению к некоторому испытанию:

1) образуют полную группу событий;

2) являются несовместными;

3) являются равновозможными.

Такие события называются элементарными событиями для данного испытания или элементарными исходами данного испытания.

Элементарное событие называется благоприятствующим событию , если появление события влечет за собой появление события .

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

где m- число элементарных исходов, благоприятствующих , n - число всех возможных элементарных исходов испытания.

Из определения вероятности следует, что вероятность любого события удовлетворяет двойному неравенству

,

при этом вероятность достоверного события равна 1, а вероятность невозможного события равна 0.

Пример 5. Брошен игральный кубик. Найти вероятности следующих событий: А - «выпало четное число очков», В - «выпало 3 очка», С - «выпало более 4 очков».

Решение. Рассмотрим события: А₁ - «выпало 1 очко», А₂ - «выпало 2 очка», А₃ - «выпало 3 очка», А₄ - «выпало 4 очка», А₅ - «выпало 5 очков», А₆ - «выпало 6 очков». Очевидно, что эти события равновозможные, несовместные и образуют полную группу событий. Следовательно, события А₁, А₂, …, А₆ - являются элементарными исходами данного испытания (бросания игрального кубика). Таким образом, число всех элементарных исходов испытания равно 6.

Благоприятствующими событию А являются три элементарных исхода - А₂, А₄, А₆. Следовательно, по определению вероятности, получаем

Событию В благоприятствует только один элементарный исход А₃, значит

Благоприятствующими событию C являются два элементарных исхода - A₅ и A₆ . Следовательно

ГЛАВА 2. ПРИМЕНЕНИЕ ФОРМУЛ КОМБИНАТОРИКИ К ПОДСЧЕТУ ВЕРОЯТНОСТИ

Задача 1. Сколькими способами можно рассадить 5 человек за столом?

Решение: используем формулу количества перестановок:

Ответ: 120 способами.

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

Задача 2. Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9?

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

Решение: найдём количество всех возможных перестановок 4 карточек:

Когда карточка с нулём располагается на 1-м месте, то число становится трёхзначным, поэтому данные комбинации следует исключить. Пусть ноль находится на 1-м месте, тогда оставшиеся 3 цифры в младших разрядах можно переставить способами

Примечание: т.к. карточек немного, то здесь несложно перечислить все такие варианты:

0579

0597

0759

0795

0957

0975

Таким образом, из предложенного набора можно составить: 24 - 6 = 18 четырёхзначных чисел

Ответ: 18

Задача 3. В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?

Решение: прежде всего, снова обращаем внимание на то, что по логике условия, детали считаются различными - даже если они на самом деле однотипны и визуально одинаковы (в этом случае их можно, например, пронумеровать).

В задаче речь идёт о выборке из 4 деталей, считаем их количество:

Ответ: 1365 способами.

Задача 4. Сколькими способами из колоды в 36 карт можно выбрать 3 карты?

Решение:

Ответ: 7140 способами.

Задача 5. Для проведения лабораторных работ группа студентов, в которой 10 парней и 6 девушек, произвольно делится на две равные подгруппы. Найти вероятность того, что в каждой группе окажется по одинаковому числу девушек.

Решение: Число возможных элементарных исходов - количество способов разделить 16 студентов на 2 равные группы (то есть выбрать из 16 человек 8).

Число благоприятствующих исходов - число исходов, при котором в каждой группе будет по 3 студентки

(Из 6 студенток нужно выбрать 3 -  и из 10 студентов 5 - - по правилу умножения вероятностей независимых событий )

Тогда, по классическому определению вероятности

Ответ: .

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

Решение: Элементарными исходами здесь являются наборы, включающие 4 журнала. Поскольку порядок безразличен, будем считать их выбор неупорядоченным (и бесповторным). Общее число элементарных исходов равно числу способов выбрать 4 журнала из 8, т. е. числу сочетаний  . Число благоприятствующих исходов равно числу способов выбора 3 или 4 журнала в переплёте из имеющихся 4, т. е. 

Тогда искомая вероятность:

Ответ: .

Задача №7. В коробке пять золотых и семь серебряных шаров. Из коробки наугад вынимают три шара. Найти вероятность того, что среди взятых наудачу трех шаров будет: а) ровно два золотых; б) хотя бы два золотых.