Комбинаторика
Комбинаторика - раздел математики, в котором изучаются простейшие «соединения». Перестановки - соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число их Размещения - соединения, содержащие по m предметов из числа n данных, различающиеся либо порядком предметов, либо самими предметами; число их Сочетания - соединения, содержащие по m предметов из n, различающиеся друг от друга, по крайней мере, одним предметом
С задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов – во время работы.
Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника
ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.
В этот же период формируется терминология новой науки. Термин «сочетание» впервые встречается у Паскаля. Термин «перестановка» употребил в указанной книге Якоб Бернулли. Бернулли использовал и термин «размещение».
После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала.
В начале XX века начала развиваться комбинаторная геометрия: были доказаны теоремы Минковского — Радона, Радона, Хелли,Юнга, Бляшке, а также строго доказана изопериметрическая теорема. На стыке топологии, анализа и комбинаторики были доказаны теоремы Борсука — Улама и Люстерника — Шнирельмана. Во второй четверти XX века были поставлены проблема Борсука ипроблема Нелсона — Эрдёша — Хадвигера. В 1940-х годах оформилась теория Рамсея. Отцом современной комбинаторики считается Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ. Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились компьютеры. Сейчас это чрезвычайно содержательная и быстроразвивающаяся область математики.
Замечательно, что наука, которая начала с рассмотрения азартных игр, обещает стать наиболее важным объектом человеческого знания. Ведь большей частью жизненные вопросы являются на самом деле задачами из теории вероятностей.
П. Лаплас
Области применения комбинаторики:
- учебные заведения (составление расписаний)
- сфера общественного питания (составление меню)
- лингвистика (рассмотрение вариантов комбинаций букв)
- география (раскраска карт)
- спортивные соревнования (расчёт количества игр между участниками)
- производство (распределение нескольких видов работ между рабочими)
- агротехника (размещение посевов на нескольких полях)
- азартные игры (подсчёт частоты выигрышей)
- химия (анализ возможных связей между химическими элементами)
- экономика (анализ вариантов купли-продажи акций)
- криптография (разработка методов шифрования)
- доставка почты (рассмотрение вариантов пересылки)
- Задачи, в которых идет речь о тех или иных комбинациях объектов, называются комбинаторными.
Правило сложения: если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m + n способами.
Например:
- На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?
По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу сложения, можно осуществить 5+4=9 способами.
- Давайте рассмотрим такую задачу: сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?
- Решение: для того, чтобы не пропустить и не повторить ни одно из чисел, будем записывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4, и, наконец, с цифры 7:
14, 17, 41, 47, 71, 74.
Ответ: 6.
Этот метод называется перебором вариантов. Таким образом, их трех данных цифр можно составить всего 6 различных двузначных чисел.
Эту задачу можно решить и другим способом. Его название – дерево возможных вариантов. Для этой задачи построена специальная схема.
Ставим звездочку. Она будет обозначать количество возможных вариантов.
Далее отводим от звездочки 3 отрезка. В условии задачи даны 3 цифры – 1, 4, 7.
Ставим эти цифры на концах отрезков. Они будут обозначать число десятков в данном числе.
Далее от каждой цифры проводим по 2 отрезка.
На концах этих отрезков записываем также цифры 1, 4, 7. Они будут обозначать число единиц.
Рассмотрим, какие числа получились: 14, 17, 41, 47, 71, 74. То есть всего получилось 6 чисел.
Ответ: 6.
Эта схема действительно похожа на дерево, правда «вверх ногами» и без ствола.
Правило умножения: если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить 
способами.
- Сколько двузначных чисел можно составить из цифр 1,4,7, используя в записи числа каждую из них не более одного раза?
Эту задачу можно решить по-другому и намного быстрее, не строя дерева возможных вариантов. Рассуждать будем так. Первую цифру двузначного числа можно выбрать тремя способами. Так как после выбора первой цифры останутся две, то вторую цифру можно выбрать из оставшихся цифр уже двумя способами. Следовательно, общее число искомых трехзначных чисел равно произведению 
, т.е. 6.
- Сколько пятизначных чисел можно составить из цифр 5, 9, 0, 6?
По правилу умножения получаем: 
чисел.
Перестановки – соединения, каждое из которых содержит n различных элементов, взятых в определенном порядке.
Задача.
Сколькими способами можно расставить на полке семь различных книг?
Решение:
Число таких способов равно числу перестановок из семи элементов,
Ответ: 5040.
Задача.
Имеются 10 различных книг, три из которых – справочники. Сколькими способами
Можно расставить эти книги на полке так, чтобы все справочники стояли рядом?
Решение:
Т.к. в справочники должны стоять рядом, то будем рассматривать их как одну книгу. Тогда на полке надо расставить 10 – 3+1=8 книг. Это можно сделать P8 способами. Для каждой из полученных комбинаций можно сделать P3 перестановок справочников.
Поэтому число способов расположения книг на полке равно произведению:
Ответ: 241920.
Размещения – соединения, отличающиеся друг от друга составом элементов или их порядком, каждая из которых содержит k элементов, взятых из n различных элементов.
Порядок следования элементов важен.
Число размещений из n элементов по k обозначают символом 
(читается: А из n по k).
Сочетания – соединения, отличающиеся друг от друга по крайней мере одним элементом, каждое из которых содержит k элементов, выбранных из n различных элементов.
Порядок следования элементов неважен.
Число сочетаний из n элементов по k обозначают символом 
(читается: С из n по k).
сочетания
перестановки размещения
Вопросы.
Сколькими способами можно выбрать 5 учеников из 30 для дежурства в столовой; актив класса (староста, культорг, редактор стенгазеты, организатор спортивных мероприятий) – 4 человека из 30; 7 монет из 10 данных монет; 10 карт из колоды в 32 карты?
Ответ:
- 5 учеников из 30 для дежурства в столовой можно выбрать
способами; 7 монет из 10 данных монет можно выбрать 
способами; 10 карт из колоды в 32 карты 
способами (в этих случаях порядок не важен, и поэтому мы используем сочетания). - Для состава актива класса важно, кто именно будет старостой, кто – культоргом, кто – редактором стенгазеты и кто будет отвечать за спорт. Поэтому следует использовать размещения: нужный выбор (4 человека из 30) можно произвести
способами.
Для любых натуральных чисел n и k, таких, что k<n, справедливы соотношения:
Задача.
Сколько трехзначных чисел с различными цифрами можно составить из цифр 0, 1, 2, 3, 4, 5?
Решение:
Из шести данных цифр можно составить 
чисел, но среди них будут и трехзначные числа, начинающиеся с нуля (чего, естественно, быть не может). Посчитаем количество таких чисел 
. В них на первом месте стоит нуль. Значит, на оставшиеся две позиции размещают оставшиеся пять цифр. Поэтому таких чисел будет:
Следовательно, искомых чисел можно получить:
Ответ: 100
Вероятность
Что такое событие?
Например:
В теории вероятностей возможный исход эксперимента, называется элементарным событием, а множество таких исходов называется просто событием.
Событие – это результат испытания.
Пример.
Стрелок стреляет по мишени, разделенной на четыре области. Выстрел – это испытание. Попадание в определенную область мишени – событие. В урне имеются цветные шары. Из урны наудачу берут один шар. Извлечение шара из урны есть испытание. Появление шара определенного цвета – событие.
В теории вероятностей под событием понимают то, относительно чего после некоторого момента времени можно сказать одно и только одно из двух. Да, оно произошло. Нет, оно не произошло.
В жизни мы постоянно сталкиваемся с тем, что некоторое событие может произойти, а может и не произойти.
Например:
В следующем году первый снег выпадет в субботу. Бутерброд упадет маслом вниз. При бросании кубика выпадет шестерка. При бросании кубика выпадет четное число.
У меня есть лотерейный билет. После опубликования результатов розыгрыша лотереи интересующее меня событие – выигрыш тысячи рублей, либо происходит, либо не происходит. В следующем году первый снег выпадет в субботу.
Такие непредсказуемые события называются случайными.
Теория вероятностей изучает различные модели случайных событий, их свойства и характеристики. Разумеется, эта теория не может однозначно предсказать, какое событие в реальности произойдет, но может оценить, какое событие наиболее вероятно. При этом будем считать, что случайные события равновероятны (или равновозможны), - идеализированная модель.
Два события, которые в данных условиях могут происходить одновременно, называются совместными, а те, которые не могут происходить одновременно, - несовместными.
Примеры.
- Из ящика с деталями наудачу извлечена деталь. Появление стандартной детали исключает появление нестандартной детали. События «появилась стандартная деталь» и «появилась нестандартная деталь» - несовместные.
- Брошена монета. Появление «герба» исключает появление надписи. События «появился герб» и «появилась надпись» - несовместные.
- Примеры ребят.
Равновозможными называются события, когда в их наступлении нет преимуществ
Неравновозможные события те, у которых в наступлении одного из событий есть какое то преимущество.
Примеры.
- Появление герба или надписи при бросании монеты представляют собой равновероятные события.
- Пусть бросают игральную кость. В силу симметрии кубика можно считать, что появление любой из цифр 1, 2, 3, 4, 5 или 6 одинаково возможно (равновероятно).
- Примеры ребят.
Событие, которое происходит всегда, называют достоверным событием.
Вероятность достоверного события равна 1.
Событие, которое не может произойти, называется невозможным.
Вероятность невозможного события равна 0.
Примеры.
- В следующем году снег не выпадет. При бросании кубика выпадет семерка. Это невозможные события.
- В следующем году снег выпадет. При бросании кубика выпадет число, меньше семи. Ежедневный восход солнца. Это достоверные события.
- Пусть, например, из урны, содержащей только черные шары, вынимают шар. Тогда появление черного шара – достоверное событие; появление белого шара – невозможное событие.
- Приведите примеры достоверных и невозможных событий.
3.3. Что такое «теория вероятностей»?
Например:
Теория вероятностей – раздел математики, изучающий закономерности случайных явлений: случайные события, случайные величины, их свойства и операции над ними. (Советский энциклопедический словарь, 1982 год)
Теория вероятностей – это математическая наука, позволяющая по вероятностям одних случайных событий находить вероятности других случайных событий, связанных каким – либо образом с первыми. (А.А.Боровков «Теория вероятностей», М.: Наука, 1986 год.)
Вероятность – это численная характеристика реальности появления того или иного события.
Классическое определение вероятности.
Вероятностью события А при проведении некоторого испытания называют отношение числа тех исходов, в результате которых наступает событие А, к общему числу всех (равновозможных между собой) исходов этого испытания.
Для решения задач используют алгоритм нахождения вероятности случайного события.
Для нахождения вероятности случайного события А при проведении некоторого испытания следует найти:
число N всех возможных исходов данного испытания;
количество N(A) тех исходов, в которых наступает событие А;
частное 
оно и будет равно вероятности события А.
Принято вероятность события А обозначать так: Р(А). Значит Р(А) =
Примеры.
1. На завод привезли партию из 1000 подшипников. Случайно в эту партию попало 30 подшипников, не удовлетворяющих стандарту. Определить вероятность Р(А) того, что взятый наудачу подшипник окажется стандартным.
Решение. Число стандартных подшипников равно 1000 – 30 = 970. Будем считать, что каждый подшипник имеет одинаковую вероятность быть выбранным. Тогда полная группа событий состоит из N = 1000 равновероятных исходов, из которых событию А благоприятствуют N(A) = 970 исходов.
Поэтому Р(А) = 
Ответ: 0,97.
2. Найдем вероятность того, что при одном бросании игральной кости (кубика) выпадает: а) три очка; б) число очков, кратное трем; в) число очков больше трех; г) число очков, не кратное трем.
Решение. Всего имеется N=6 возможных исходов: выпадение 1,2,3,4,5,6 очков. Считаем, что эти исходы равновозможны.
Для вычисления вероятности часто используют правило умножения.
Для того, чтобы найти число всех возможных исходов независимого проведения двух испытаний А и В, следует перемножить число всех исходов испытания А и число всех исходов испытания В.
3. Найдем вероятность того, что при подбрасывании двух костей суммарное число очков окажется равным 5.
Решение.
Вероятность Р(А) некоторого события 
.
При решении некоторых задач удобно использовать свойство вероятностей противоположных событий.
События А и В называются противоположными, если всякое наступление события А означает ненаступление события В, а ненаступление события А – наступление события В.
Событие, противоположное событию А, обозначают символом 
. Сумма вероятностей противоположных событий равна 1.
.
Примеры.
1. Бросаем один раз игральную кость. Событие А – выпадение четного числа очков, тогда событие - выпадение нечетного числа очков.
2. В среднем из 1000 аккумуляторов, поступивших в продажу, 6 неисправны. Найдите вероятность того, что один купленный аккумулятор окажется исправным.
Решение. Элементарный исход – случайно выбранный аккумулятор. Поэтому
N = 1000.
Событию А = (аккумулятор исправен) благоприятствуют 1000 – 6 = 994 исхода.
Поэтому N(A) = 994.
