Изучение основ комбинаторики и теории вероятностей (стр. 2 из 17)
1. свойствам фигурных чисел,
2. построению магических (и иных числовых) квадратов,
3. свойствам биномиальных коэффициентов.
Термин "комбинаторика" был введён в математический обиход знаменитым Лейбницем.Готфрид Вильгельм Лейбниц(1.07.1646 - 14.11.1716) - всемирно известный немецкий учёный, занимался философией, математикой, физикой, организовал Берлинскую академию наук и стал её первым президентом. В математике он вместе с И. Ньютоном разделяет честь создателя дифференциального и интегрального исчислений. В 1666 году Лейбниц опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов, выводит свойства сочетаний:
, 
, 
,- строит таблицы сочетаний до n = k = 12, после чего рассуждает о приложениях комбинаторики к логике, арифметике, к проблемам стихосложения и др.
В течение всей своей жизни Лейбниц многократно возвращался к идеям комбинаторного искусства. Комбинаторику он понимал весьма широко, именно, как составляющую любого исследования, любого творческого акта, предполагающего сначала анализ (расчленение целого на части), а затем синтез (соединение частей в целое). Мечтой Лейбница, оставшейся, увы, неосуществлённой, оставалось построение общей комбинаторной теории. Комбинаторике Лейбниц предрекал блестящее будущее, широкое применение.
В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.
В 1713 году было опубликовано сочинение Я. Бернулли "Искусство предположений", в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. "Искусство предположений" появилось после смерти автора и не было автором завершено. Сочинение состояло из 4 частей, комбинаторике была посвящена вторая часть, в которой содержатся формулы:
· для числа перестановок из n элементов,
· для числа сочетаний (называемого Я. Бернулли классовым числом) без повторений и с повторениями,
· для числа размещений с повторениями и без повторений.
Для вывода формул автор использовал наиболее простые и наглядные методы, сопровождая их многочисленными таблицами и примерами. Сочинение Я. Бернулли превзошло работы его предшественников и современников систематичностью, простотой методов, строгостью изложения и в течение XVIII века пользовалось известностью не только как серьёзного научного трактата, но и как учебно-справочного издания. В работах Я. Бернулли и Лейбница тщательно изучены свойства сочетаний, размещений, перестановок. Перечисленные комбинаторные объекты относятся к основным комбинаторным конфигурациям.
В математике в XIX веке появился сначала термин "геометрическая конфигурация" в лекциях по проективной геометрии профессора университета в Страсбурге К.Т. Рейе (1882).Термин "тактика" ввёл в математику английский математик Джеймс Джозеф Сильвестр(1814-1897) в 1861 году. Сильвестр определял тактику как раздел математики, изучающий расположение элементов друг относительно друга. В сфере этого раздела находится, по мнению Сильвестра, теория групп, комбинаторный анализ и теория чисел. Мысли Сильвестра о тактике разделял его друг Артур Кэли.
j) равен числу элементов i-ого множества, инцидентных j -ому множеству. К тактическим конфигурациям Мур относит сочетания, размещения, системы решений задачи Киркмана о 15 школьницах, подгруппы некоторых групп. Он демонстрирует широкий спектр задач из геометрии, теории групп, которые приводят к тактическим разложениям или используют тактические разложения. Мур обогатил список известных комбинаторных конфигураций построением новых, обобщающих системы троек Штейнера, и системы троек Киркмана. Мур построил системы S[k, l, m], m 
k 
l ( m, k, l - натуральные числа), содержащие такие k -сочетания (блоки) из m элементов, что каждое l -сочетание входит точно в одно k -сочетание. Число k -сочетаний в системеS[k, l, m]равно 
. Мур в своей статье ссылается на Артура Кэли, который подчёркивал высокую значимость тактических задач в алгебре. Комбинаторика, пройдя многовековой путь развития, обретя собственные методы исследования, с одной стороны, широко используется при решении задач алгебры, геометрии, анализа, с другой стороны, сама использует геометрические, аналитические и алгебраические методы исследования. В конце XVIII века учёные, принадлежащие комбинаторной школе Гинденбурга, попытались построить общую комбинаторную теорию, используя бесконечные ряды. Исследователи этой школы изучили большое количество преобразований рядов: умножение, деление, возведение в степень, извлечение корней, обращение рядов, разложение трансцендентных функций. Использование производящих функций в комбинаторике можно отнести к (уже) классическим традициям.
1.2. Предмет комбинаторики
Комбинаторный анализ, комбинаторная математика, комбинаторика, - раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбинаторных конфигураций, в частности, вопросы их существования, алгоритмы построения, решение задач на перечисление. Примерами комбинаторных конфигураций являются перестановки, размещения и сочетания; блок-схемы и латинские квадраты.
В Математическом Энциклопедическом Словаре говорится, что комбинаторика- один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике.
В Большой Советской Энциклопедии говорится, что комбинаторика - это раздел математики в котором изучаются некоторые операции над конечными множествами.
1.3. Основные понятия и теоремы комбинаторики
Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. При непосредственном вычислении вероятностей часто используют формулы комбинаторики. Приведем наиболее употребительные из них.
1.3.1. Основные правила комбинаторики
При вычислении количества различных комбинаций используются правила сложения и умножения. Сложение используется, когда множества не совместны. Умножение - когда для каждой комбинации первого множества имеются все комбинации (или одинаковое число комбинаций) второго множества.
Пример. Из 28 костей домино берутся 2 кости. В каком числе комбинаций вторая кость будет приложима к первой?
На первом шаге имеется два варианта: выбрать дубль (7 комбинаций) или недубль (21 комбинация). В первом случае имеется 6 вариантов продолжения, во втором - 12.
Общее число благоприятных комбинаций равно:
.А всего вариантов выбора 2 костей из 28 равно 378; т. е. при большом числе экспериментов в 7 случаях из 9 (294/378 = 7/9) при выборе 2 костей одна кость окажется приложимой к другой.
1.3.2. Размещения с повторениями
Размещение с повторением также в комбинаторике называется кортежем.
Рассмотрим задачу: сколько разных числовых последовательностей, длины 5, можно составить из 10 цифр?
Перенумеруем разряды:
| 1 | 2 | 3 | 4 | 5 |
В первый разряд можно поставить одну из 10 цифр.
Независимо от того, какая цифра поставлена, во второй разряд можно также поставить одну из 10 цифр и т. д. Всего получается 105 различных чисел.