Комбинаторика. История создания теории

Размещено на http://www.allbest.ru/

1. Комбинаторика. История создания теории

Термин «комбинаторика» был введён в математический обиход знаменитым Лейбницем. Готфрид Вильгельм Лейбниц (1646-1716) - всемирно известный немецкий учёный, занимался философией, математикой, физикой, организовал Берлинскую академию наук и стал её первым президентом.

В 1666 году Лейбниц опубликовал «Рассуждения о комбинаторном искусстве». В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k-сочетания из n элементов выводит свойства сочетаний:

, ,

комбинаторика математика умножение лейбниц

- строит таблицы сочетаний до n = k = 12, после чего рассуждает о приложениях комбинаторики к логике, арифметике, к проблемам стихосложения и др.

В течение всей своей жизни Лейбниц многократно возвращался к идеям комбинаторного искусства. Комбинаторику он понимал весьма широко, именно, как составляющую любого исследования, любого творческого акта, предполагающего сначала анализ (расчленение целого на части), а затем синтез (соединение частей в целое). Мечтой Лейбница, оставшейся неосуществлённой, оставалось построение общей комбинаторной теории. Комбинаторике Лейбниц предрекал блестящее будущее, широкое применение^.

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, математик и механик международного уровня Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

В 1713 году было опубликовано сочинение швейцарского математика Якоба Бернулли «Искусство предположений», в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. «Искусство предположений» появилось после смерти автора и не было им завершено. Сочинение состояло из 4 частей, комбинаторике была посвящена вторая часть, в которой содержатся формулы:

для числа перестановок из n элементов;

для числа сочетаний (называемого Я. Бернулли классовым числом) без повторений и с повторениями;

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

Для вывода формул автор использовал наиболее простые и наглядные методы, сопровождая их многочисленными таблицами и примерами. Сочинение Бернулли превзошло работы его предшественников и современников систематичностью, простотой методов, строгостью изложения и в течение XVIII века пользовалось известностью не только как серьёзного научного трактата, но и как учебно-справочного издания. В работах Бернулли и Лейбница тщательно изучены свойства сочетаний, размещений, перестановок. Перечисленные комбинаторные объекты относятся к основным комбинаторным конфигурациям.

В 1896 году американский математик Элиаким Гастингс Мур (1862-1932) ввёл термин «тактическая конфигурация» в статье «Tactical memoranda», понимая под этим термином систему n множеств, содержащих, соответственно, a₁, a₂, …, a_n элементов. Тактическую конфигурацию Мур задаёт квадратной матрицей порядка n, в которой элемент a_kk, стоящий на главной диагонали, равен числу a_k (числу элементов в k-ом множестве); элемент a_ij (i j) равен числу элементов i-ого множества, инцидентных j-ому множеству.

Термин «тактика» ввёл в математику английский математик Джеймс Джозеф Сильвестр (1814-1897) в 1861 году. Сильвестр определял тактику как раздел математики, изучающий расположение элементов друг относительно друга. В сфере этого раздела находится, по мнению Сильвестра, теория групп, комбинаторный анализ и теория чисел. Мысли Сильвестра о тактике разделял его друг Артур Кэли.

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

В XX веке комбинаторика подверглась мощному процессу алгебраизации благодаря работам американо-канадских учёных Дж.-К. Рота (1964), а затем Р. Стенли. Изучение ими частично упорядоченных множеств, абстрактных свойств линейной зависимости, выявление их роли при решении комбинаторных задач способствовали обогащению комбинаторных методов исследования и дальнейшей интеграции комбинаторики в современную математику.

2. Правила суммы и умножения

Правило суммы. Если элемент a может быть выбран m способами, а элемент b другими k способами, то выбор одного из этих элементов ? a или b может быть сделан m + k способами.

Пример. На конюшне четыре лошади и два пони. Сколько возможностей выбрать себе скакуна? Здесь используем правило суммы: выбираем один элемент из двух множеств (лошадь или пони) 4 + 2 = 6 способами.

Правило произведения. Если элемент a может быть выбран m способами, а после этого элемент b выбирается k способами, то выбор пары элементов (a,b) в заданном порядке может быть произведен m х k способами.

Пример. Пару лыж можно выбрать шестью способами, пару ботинок - тремя. Сколькими способами можно выбрать лыжи с ботинками? Здесь выбираем пару элементов (лыжи, ботинки) - всего 6 х 3 =18 способов.

3. Урновые схемы

Урновая схема - одна из простейших моделей теории вероятностей. Её описание таково: рассматривается некий сосуд - урна - с шарами белого и черного цвета. Из урны наугад извлекается один шар, а затем он возвращается в урну вместе с шарами того же цвета, что и вынутый шар, и шарами другого цвета. После перемешивания шаров в урне процедура повторяется любое нужное число раз. Предполагается, что первоначально урна содержала а > 0 и b > 0 белых и черных шаров соответственно. Числа с и d - параметры.

Урновая схема дает удобную возможность вычисления некоторых основных вероятностей через условные вероятности. При различных значениях параметров с и d получаются многие известные схемы теории вероятностей:

при с = 0, d = 0 - схема случайного выбора с возвращением,

при с = -1, d = 0 - схема случайного выбора без возвращения,

при с = -1, d = -1 - модель диффузии Эренфестов,

при с > 0, d = 0 - урновая схема Пойа

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

4. Задачи

Все задания взяты с пособия И.В. Яковлева «Комбинаторика - олимпиаднику».

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

Задача 1. На подносе лежат 5 яблок и 3 груши. Сколькими способами можно выбрать фрукт с подноса?

Решение: Яблоко можно выбрать пятью способами. Грушу - тремя. Стало быть, один из этих фруктов можно выбрать 5 + 3 = 8 способами.

Задача 2. На полке стоит 10 томов Пушкина, 4 тома Лермонтова и 6 томов Гоголя. Сколькими способами можно выбрать с полки 1 книгу?

Решение: 10 + 4 + 6 = 20 способами.

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

Задача 3. В магазине есть 7 видов пиджаков, 5 видов брюк и 4 вида галстука. Сколькими способами можно купить комплект из пиджака, брюк и галстука?

Решение: Предположим, что пиджак уже выбран (это можно сделать 7 способами). К пиджаку выбираем брюки 5 способами. Итого пару (пиджак, брюки) можно выбрать 7 х 5 способами. К этой паре можно купить галстук 4 способами. Следовательно, для покупки пиджака, брюк и галстука имеется

7 х 5 х 4 = 140 способов.

Задача 4. Сколько подмножеств у 5-элементного множества? У n-элементного?

Решение: Пусть имеется множество из 5 элементов A = {a₁,a_2,a₃,a₄,a₅}. Каждому его подмножеству B можно дать уникальное имя в виде в виде упорядоченной пятёрки нулей и единиц по следующему правилу: если на i-й позиции стоит единица, то a_i ? B; если же на i-й позиции пятёрки стоит нуль, то a_i ? B.

Например, пятёрка 10010 обозначает подмножество {a₁,a₄,}. Пятёрки 00000 и 11111 обозначают соответственно пустое множество и само множество A.

Таким образом, у множества A имеется ровно столько подмножеств, сколько существует упорядоченных пятёрок из нулей и единиц. Каждую позицию пятёрки можно заполнить двумя способами (0 или 1), поэтому таких пятёрок 2 х 2 х 2 х 2 х 2 = 2⁵ = 32. Это и есть число подмножеств 5-элементного множества.

Для n-элементного множества рассуждение аналогично. Каждое его подмножество получает уникальное имя (по тому же правилу) в виде цепочки длины n, состоящей из нулей и единиц. Всего таких цепочек 2ⁿ. Следовательно, число всех подмножеств n-элементного множества равно 2ⁿ.

Размещения с повторениями

Задача 5. Сколькими способами можно m различных шаров в n различных ящиков? На число шаров в ящике ограничений нет.

Решение: Представим себе m клеток (это шары). В каждую клетку можно вписать любое число от 1 до n (номер ящика, в который кладётся шар). Всего получится n^m всевозможных способов заполнить клетки, то есть разложить шары по ящикам.

Число разложений m различных шаров по n различным ящикам (без ограничений шаров в ящике) называется иногда числом размещений с повторениями из n по m и обозначается , и это обозначение равно n^m.

Размещено на Allbest.ru