Применение комбинаторики к подсчёту вероятностей
Содержание
Введение
История
возникновения
Формулы
комбинаторики
Практика
Литература
Введение
Комбинаторика (комбинаторный анализ) - раздел
математики, который исследует в основном различные способы выборки заданного
числа m элементов из заданного конечного множества: размещения, сочетания,
перестановки, а также перечисление и смежные проблемы. Начав с анализа
головоломок и азартных игр, комбинаторика оказалась исключительно полезной для
решения практических задач почти во всех разделах математики. Кроме того,
комбинаторные методы оказались полезными в статистике, генетике, лингвистике и
многих других науках.
Термин «комбинаторика» был введён Лейбницем,
который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном
искусстве».
История возникновения
Комбинаторные мотивы можно заметить в символике
китайской «Книги Перемен» (V век до н. э.). Большой интерес математиков многих
стран с древних времён неизменно вызывали магические квадраты. Классическая
задача комбинаторики: «сколько есть способов извлечь m элементов из N
возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века
до н.э.). Индийские математики, видимо, первыми открыли биномиальные
коэффициенты и их связь с биномом Ньютона. Во II веке до н. э. индийцы знали,
что сумма всех биномиальных коэффициентов степени n равна 
.
Античные греки также рассматривали отдельные комбинаторные задачи, хотя
систематическое изложение ими этих вопросов, если оно и существовало, до нас не
дошло.
В XII веке индийский математик Бхаскара в своём
основном труде «Лилавати» подробно исследовал задачи, связанные с
перестановками и сочетаниями, включая перестановки с повторениями. В Западной
Европе ряд глубоких открытий в области комбинаторики сделали два еврейских
исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV
век). Ибн Эзра обнаружил симметричность биномиальных коэффициентов, а Герсонид
дал явные формулы для их подсчёта и применения в задачах вычисления числа
размещений и сочетаний. Несколько комбинаторных задач содержит «Книга абака»
(Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число
гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.
Джероламо Кардано написал математическое
исследование игры в кости, опубликованное посмертно. Теорией этой игры
занимались также Тарталья и Галилей. В историю зарождавшейся теории
вероятностей вошла переписка заядлого игрока шевалье де Мерэ с Пьером Ферма и
Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов.
Помимо азартных игр, комбинаторные методы использовались (и продолжают
использоваться) в криптографии - как для разработки шифров, так и для их
взлома.
Блез Паскаль много занимался биномиальными
коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля».
Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в
отличие от предшественников, строго изложил и доказал свойства этого
треугольника. Наряду с Лейбницем, он считается основоположником современной
комбинаторики. Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году
(ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном
искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко,
включая в него всю конечную математику и даже логику. Ученик Лейбница Якоб
Бернулли, один из основателей теории вероятностей, изложил в своей книге
«Искусство предположений» (1713) множество сведений по комбинаторике.
В этот же период формируется терминология новой
науки. Термин «сочетание» впервые встречается у Паскаля (1653). Термин
«перестановка» употребил в указанной книге Якоб Бернулли (хотя эпизодически он
встречался и раньше). Бернулли использовал и термин «размещение».
Окончательно комбинаторика как самостоятельный
раздел математики оформилась в трудах Эйлера. Он детально рассмотрел, например,
следующие проблемы:
задача о ходе коня;
задача о семи мостах, с которой началась теория
графов;
построение греко-латинских квадратов;
обобщённые перестановки.
В начале XX века начала развиваться
комбинаторная геометрия. В 1940-х годах оформилась теория Рамсея. Отцом
современной комбинаторики считается Пал Эрдёш, который ввёл в комбинаторику
вероятностный анализ. Внимание к конечной математике и, в частности, к
комбинаторике значительно повысилось со второй половины XX века, когда
появились компьютеры.
Сейчас это чрезвычайно содержательная и
быстроразвивающаяся область математики.
Формулы комбинаторики
Комбинаторика изучает количества комбинаций,
подчиненных определенным условиям, которые можно составить из элементов
заданного конечного множества.
При решении задач комбинаторики используют
следующие правила:
Правило суммы. Если некоторый объект А может
быть выбран из совокупности объектов m способами, а другой объект В может быть
выбран n способами, то выбрать либо А, либо В можно m + n способами.
Правило произведения. Если объект А можно
выбрать из совокупности объектов m способами и после каждого такого выбора
объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке
может быть выбрана m * n способами.