Комбинаторика как наука

                           Введение:

В повседневной жизни нередко перед нами возникают проблемы, которые имеют не одно, а несколько различных вариантов решения. Чтобы сделать правильный выбор, очень важно не уступить ни одной из них. Для этого нужно осуществлять перебор всех возможных вариантов или хотя бы подсчитать их число. Задачи, в которых идет речь о тех или иных комбинациях объектов, называются комбинаторными .Данная работа посвящена математическому элементу комбинаторики и её применение в лотереи. В процессе исследования был проведен опрос УЧЕНИКОВ  об их мнении на эту тему .В последнее время идёт очень много споров на тему может ли математика помочь выиграть лотерею именно на эту гипотезу я попытаюсь ответить в своём проекте «Элементы комбинаторики  и лотерея».Комбинаторика возникла в XVI веке. В жизни привилегированных слоев общества большое место занимали азартные игры. В карты и кости выигрывались и проигрывались золото, бриллианты, дворцы и имения. Широко были распространены всевозможные лотереи. Поэтому первые комбинаторные задачи касались в основном азартных игр:   сколькими способами можно выбросить нужное число очков, бросая кости; сколькими способами можно получить двух королей в карточной игре и т.д Актуальность моего проекта в том что применение комбинаторики в некоторых сферах деятельности может быть очень полезным. Азартным людям посвящающим играм значимую часть своей жизни весьма необходимо разбираться в комбинаторике . Объект моего исследования: комбинаторика. Метод исследования : Анализ математической, и дополнительной литературы. Возможны ли расчеты в азартных играх? Можно ли с помощью комбинаторики выиграть лотерею???-именно на эти вопросы я отвечу в своём проекте

1)Что такое комбинаторика?

Комбинаторика – ветвь математики, изучающая комбинации и перестановки предметов. Еще комбинаторику можно понимать как перебор возможных вариантов. Комбинаторика возникла в XII веке. Долгое время она лежала вне основного русла развития математики.

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

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

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

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

Задачи, в которых идет речь о тех или иных комбинациях объектов, называются комбинаторными. Область математики, в которой изучаются комбинаторные задачи, называется комбинаторикой. Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях

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

Комбинаторика как наука стала развиваться в XIII веке параллельно с возникновением теории вероятностей, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов. Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н. Тарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б. Паскалю (1623-1662) и П. Ферма. Комбинаторику как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 году. Он также впервые ввел термин «комбинаторика». Значительный вклад в развитие комбинаторики внес Л.Эйлер.

Основными и типичными операциями и связанными с ними задачами комбинаторики

являются следующие:

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

порядка следования элементов множества друг за другом, - составление

перестановок;

2) образование  подмножеств, состоящее в выделении  из данного множества

некоторой части его элементов, - составление сочетаний;

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

ТИПЫ КОМБИНАТОРНЫХ ЗАДАЧ.

1. Магический квадрат - квадратная таблица (n * n) целых чисел от

1 до n¤ такая, что суммы чисел вдоль любого столбца, любой строки и двух

диагоналей таблицы равны одному и тому же числу s=n(n¤+1)/2. Число n называют

порядом магического квадрата.

Доказано, что магический квадрат можно построить для любого n Є 3. Уже в

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

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

условий, например магический квадрат с n=8 , который можно разделить на

четыре меньших магических квадрата 4x4. В Индии и некоторых других странах

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

магических квадратов не существует. Неизвестно даже общее число магических

квадратов порядка n.

2. Латинский квадрат - квадратная матрица порядка n, каждая

строка и каждый столбец которой являются перестановками элементов конечного

множества S, состоящего из n элементов.

3. Задача размещения - одна из классических комбинаторных задач,

в которой требуется определить число способов размещения m различных предметов

в n различных ячейках с заданным числом r пустых ячеек. Это число равно

r n-r m

C (r)=C дельта O , r=0,1,2,...,n,

nm n

где

k m k j j m

дельта O =сигма (-1) C (k-j)

j=0 k

4. Задача коммивояжера, задача о бродячем торговце –

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

образом: даны n городов и известно расстояние между каждыми двумя городами;

коммивояжер, выходящий из какого-нибудь города, должен посетить n-1 других

городов и вернуться в исходный. В каком порядке должен он посещать города (по

одному разу каждый) чтобы общее пройденное расстояние было минимальным?

Методы решения задачи коммивояжера, по существу, сводятся к организации

полного перебора вариантов.

МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ

 1. Метод рекуррентных соотношений.

Метод рекуррентных соотношений состоит в том, что решение комбинаторной

задачи с n предметами выражается через решение аналогичной задачи с меньшим

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

рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить,

исходя из того, что для небольшого количества предметов решение задачи легко

находится.

 2. Метод включения и исключения.

Пусть N(A) - число элементов множества A. Тогда методом математической

индукции можно доказать, что

N(A1 U A2 U ... An) = N(A1) + ... + N(An) -

- {N(A1 П A2) + ... + N(An-1 П An)} +

+ {N(A1 П A2 П A3) + ... + N(An-2 П An-1 П An)} - ...

... +(-1)^n-1*N(A1 П A2 П ... П An-1 П An).

Метод подсчета числа элементов объединения множеств по этой формуле,

состоящий в поочередном сложении и вычитании, называется методом включения и

исключения.

 3. Метод траекторий.

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

интерпретацию, которая сводит задачу к подсчету числа путей (траекторий),

обладающих определенным свойством.

Основные формулы комбинаторики

Комбинаторика изучает количества комбинаций, подчиненных определенным

условиям, которые можно составить из элементов, безразлично какой природы,

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

часто используют формулы комбинаторики. Приведем наиболее употребительные из

них.

Перестановками называют комбинации, состоящие из одних и тех же n

различных элементов и отличающиеся только порядком их расположения. Число всех

возможных перестановок

Pn = n!,

где n! = 1 * 2 * 3 ... n.

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.

 Размещениями называют комбинации, составленные из n различных элементов

по m элементов, которые отличаются либо составом элементов, либо их порядком.

Число всех возможных размещений

Amn = n (n - 1)(n - 2) ... (n - m + 1).

 Сочетаниями называют комбинации, составленные из n различных элементов по

m элементов, которые отличаются хотя бы одним элементом. Число сочетаний

С mn = n! / (m! (n - m)!).

примеры перестановок, размещений, сочетаний

Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством

Amn = PmC mn.

З а м е ч а н и е. Выше предполагалось, что все n элементов различны. Если же

некоторые элементы повторяются, то в этом случае комбинации с повторениями

вычисляют по другим формулам. Например, если среди n элементов есть n1

элементов одного вида, n2 элементов другого вида и т.д., то число

перестановок с повторениями

Pn (n1, n2, ...) = n! / (n1! n2! ... ),

где n1 + n2 + ... = n.

При решении задач комбинаторики используют следующие правила:

    

Правило суммы.

 

Если некоторый объект А может быть выбран из совокупности объектов m

способами, а другой объект В может быть выбран n способами, то выбрать либо

А, либо В можно m + n способами.

Суммой А + В двух событий А и В называют событие, состоящее в

появлении события А, или события В, или обоих этих событий. Например, если из

орудия произведены два выстрела и А — попадание при первом выстреле, В —

попадание при втором выстреле, то А + В — попадание при первом выстреле, или

при втором, или в обоих выстрелах.

В частности, если два события А и B — несовместные, то А + В — событие,

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

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

хотя бы одного из этих событий. Например, событие А + В + С состоит в появлении

одного из следующих событий: А, В, С, А и В, А и С, В и С, А и В и С.

Пусть события A и В — несовместные, причем вероятности этих событий известны.

Как найти вероятность того, что наступит либо событие A, либо событие В?

Ответ на этот вопрос дает теорема сложения.

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

безразлично какого, равна сумме вероятностей этих событий:

Р (А + В) = Р (А) + Р (В)

 

Правило произведения.

 

Если объект А можно выбрать из совокупности объектов m способами и после

каждого такого выбора объект В можно выбрать n способами, то пара объектов

(А, В) в указанном порядке  может быть выбрана mn способами.

     Произведение событий. Произведением двух событий А и В называют

событие АВ, состоящее в совместном появлении (совмещении) этих событий.

Например, если А — деталь годная, В — деталь окрашенная, то АВ — деталь годна и

окрашена.

     Произведением нескольких событий называют событие, состоящее в совместном

появлении всех этих событий. Например, если А, В, С — появление «герба»

соответственно в первом, втором и третьем бросаниях монеты, то АВС — выпадение

«герба» во всех трех испытаниях.

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

событие, которое при осуществлении совокупности условий S может произойти или

не произойти. Если при вычислении вероятности события никаких других

ограничений, кроме условий S, не налагается, то такую вероятность называют

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

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

вероятность события В при дополнительном условии, что произошло событие А.

Заметим, что и безусловная вероятность, строго говоря, является условной,

поскольку предполагается осуществление условий S.

     Условной вероятностью РA (В) называют вероятность события В,

вычисленную в предположении, что событие А уже наступило.

Исходя из классического определения вероятности, формулу РA (В) = Р

(АВ) / Р (А) (Р (А) > 0 можно доказать. Это обстоятельство и служит

основанием для следующего общего (применимого не только для классической

вероятности) определения.

     Условная вероятность события В при условии, что событие А уже наступило,

по определению, равна

РA (В) = Р (АВ) / Р (А)    (Р(A)>0).

Рассмотрим два события: А и В; пусть вероятности Р (А) и РA (В)

известны. Как найти вероятность совмещения этих событий, т. е. вероятность

того, что появится и событие А и событие В? Ответ на этот вопрос дает теорема

умножения.

     Теорема. Вероятность совместного появления двух событий равна

произведению вероятности одного из них на условную вероятность другого,

вычисленную в предположении, что первое событие уже наступило:

Р (АВ) = Р (А) РA (В).

2 Из истории комбинаторики

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в.