История комбинаторики
Математическая область комбинаторики в той или иной степени изучалась во многих древних обществах. Его изучение в Европе восходит к работам Леонардо Фибоначчи в 13 веке нашей эры, который познакомил континент с арабскими и индийскими идеями. Его продолжают изучать и в современную эпоху.
Самые ранние записи [ править ]
Самое раннее зарегистрированное использование комбинаторных методов происходит из задачи 79 папируса Ринда , датируемого 16 веком до нашей эры. Проблема касается определенной геометрической серии и имеет сходство с проблемой Фибоначчи о подсчете количества композиций единиц и двоек, сумма которых дает заданную сумму. [1]
В Греции Плутарх писал, что Ксенократ Халкидонский (396–314 до н. э.) обнаружил возможное количество различных слогов в греческом языке. Это была бы первая попытка решить сложную задачу перестановок и комбинаций . [2] Утверждение, однако, неправдоподобно: это одно из немногих упоминаний о комбинаторике в Греции, а найденное ими число — 1,002 × 10. 12 , кажется слишком круглым, чтобы быть чем-то большим, чем предположением. [3] [4]
Позже упоминается спор между Хрисиппом (3 век до н.э.) и Гиппархом (2 век до н.э.) о довольно деликатной перечислительной задаче, которая, как позже было показано, связана с числами Шредера-Гиппарха . [5] [6] Есть также свидетельства того, что в «Остомахионе » Архимед (3 век до н. э.) рассматривал конфигурации мозаичной головоломки , [7] в то время как некоторые комбинаторные интересы, возможно, присутствовали в утраченных работах Аполлония . [8] [9]
В Индии в « Бхагавати-сутре» впервые упоминается проблема комбинаторики; Задача заключалась в том, сколько возможных комбинаций вкусов возможно при выборе единиц, двойок, троек и т. д. из шести разных вкусов (сладкого, острого, вяжущего, кислого, соленого и горького). Бхагавати также является первым текстом, в котором упоминается функция выбора . [10] Во втором веке до нашей эры Пингала (также Чанда-сутру) задачу перечисления включил в Чанда-сутру , в которой спрашивалось, сколькими способами можно составить шестисложный размер из коротких и длинных нот. [11] [12] Пингала нашел количество метров, которые имели длинные ноты и короткие заметки; это эквивалентно нахождению биномиальных коэффициентов .
Идеи Бхагавати были обобщены индийским математиком Махавирой в 850 году нашей эры, а работа Пингалы по просодии была расширена Бхаскарой II. [10] [13] и Гемакандра в 1100 году нашей эры. Бхаскара был первым известным человеком, обнаружившим обобщенную функцию выбора, хотя Брахмагупта, возможно, знал это раньше. [1] Гемакандра спросил, сколько существует метров определенной длины, если считается, что длинная нота вдвое длиннее короткой, что эквивалентно нахождению чисел Фибоначчи . [11]
Древняя китайская книга гаданий «И Цзин» описывает гексаграмму как перестановку с повторениями шести линий, где каждая линия может находиться в одном из двух состояний: сплошном или пунктирном. Описывая таким образом гексаграммы, они определяют, что существуют возможные гексаграммы. Китайский монах также мог посчитать количество конфигураций в игре, похожей на Goaround 700 AD. [3] Хотя в Китае было относительно мало достижений в перечислительной комбинаторике, около 100 г. н. э. они решили квадрат Ло Шу , который представляет собой задачу комбинаторного построения обычного магического квадрата третьего порядка. [1] [14] Магические квадраты по-прежнему интересовали Китай, и они начали обобщать свои первоначальные площадь между 900 и 1300 годами нашей эры. Китай переписывался с Ближним Востоком по поводу этой проблемы еще в 13 веке. [1] Ближний Восток также узнал о биномиальных коэффициентах из индийских работ и обнаружил связь с полиномиальным разложением. [15] Работы индуистов оказали влияние на арабов, как это видно из работ аль-Халиля ибн Ахмада, который рассматривал возможные варианты расположения букв для образования слогов. Его расчеты показывают понимание перестановок и комбинаций. В отрывке из работы арабского математика Умара аль-Хайями, датируемом примерно 1100 годом, подтверждается, что индусы знали биномиальные коэффициенты, но также и то, что их методы достигли Ближнего Востока.
Абу Бакр ибн Мухаммад ибн аль-Хусейн Аль-Караджи (ок. 953–1029) писал о биномиальной теореме и треугольнике Паскаля. В ныне утерянной работе, известной только по последующей цитате ас-Самауала , аль-Караджи представил идею аргументации посредством математической индукции.
Философ астроном и (ок . раввин Авраам ибн Эзра 1140 г.) подсчитал перестановки с повторениями при произнесении Божественного Имени. [16] Он также установил симметрию биномиальных коэффициентов , а замкнутая формула была получена позднее талмудистом и математиком Леви бен Герсоном (более известным как Герсонид), в 1321 году. [17] Арифметический треугольник — графическая диаграмма, показывающая отношения между биномиальными коэффициентами — был представлен математиками в трактатах, датируемых еще 10 веком, и в конечном итоге стал известен как треугольник Паскаля . Позже, в средневековой Англии , кампанология предоставила примеры того, что сейчас известно как гамильтоновы циклы в некоторых графах Кэли при перестановках. [18]
Комбинаторика на Западе [ править ]
Комбинаторика пришла в Европу в 13 веке благодаря математикам Леонардо Фибоначчи и Иордану де Немору . » Фибоначчи «Liber Abaci познакомила Европу со многими арабскими и индийскими идеями, включая идеи чисел Фибоначчи. [19] Йордан был первым, кто расположил биномиальные коэффициенты в треугольнике, как он это сделал в предложении 70 «Арифметики» . То же самое было сделано на Ближнем Востоке в 1265 году и в Китае около 1300 года. [1] Сегодня этот треугольник известен как треугольник Паскаля .
Вклад Паскаля в создание треугольника, носящего его имя, связан с его работой над формальными доказательствами этого треугольника и связями, которые он установил между треугольником Паскаля и вероятностью. [1] Из письма Лейбница, отправленного Даниэлю Бернулли, мы узнаем, что Лейбниц формально изучал математическую теорию разбиений в 17 веке, хотя никаких официальных работ опубликовано не было. Вместе с Лейбницем Паскаль в 1666 году опубликовал книгу «De Arte Combinatoria» , которая позже была переиздана. [20] Паскаль и Лейбниц считаются основоположниками современной комбинаторики. [21]
И Паскаль, и Лейбниц понимали, что биномиальное разложение эквивалентно функции выбора . Представление о соответствии алгебры и комбинаторики было расширено Де Муавром, который нашел разложение многочлена. [22] Де Муавр также нашел формулу расстройств, используя принцип включения-исключения , метод, отличный от метода Николауса Бернулли, который нашел его ранее. [1] Де Муавр также сумел аппроксимировать биномиальные коэффициенты и факториал и нашел замкнутую форму чисел Фибоначчи, изобретя производящие функции . [23] [24]
В 18 веке Эйлер работал над проблемами комбинаторики и рядом проблем вероятности, связанных с комбинаторикой. Проблемы, над которыми работал Эйлер, включают тур рыцарей , греко-латинский квадрат , числа Эйлера и другие. Для решения проблемы семи мостов Кенигсберга он изобрел теорию графов, которая также привела к формированию топологии . Наконец, он начал работу с разделами , используя производящие функции . [25]
Современная комбинаторика [ править ]
В 19 веке тема частично упорядоченных множеств и теории решеток зародилась в работах Дедекинда , Пирса и Шредера . Тем не менее, это была Гаррета Биркгоффа плодотворная работа в его книге «Теория решетки», опубликованной в 1967 году. [26] и работа Джона фон Неймана, которая действительно определила эти предметы. [27] В 1930-е годы Холл (1936) и Вейснер (1935) независимо друг от друга сформулировали общую формулу обращения Мёбиуса. [28] В 1964 году книга Джан-Карло Роты « Об основах комбинаторной теории I. Теория функций Мёбиуса» представила теорию ЧУМ и решетчатую теорию как теории комбинаторики. [27] Ричард П. Стэнли оказал большое влияние на современную комбинаторику своей работой по теории матроидов . [29] для введения дзета-полиномов, [30] для явного определения эйлеровых ЧПУ, [31] развивая теорию биномиальных ЧУМ вместе с Ротой и Питером Дубиле, [32] и многое другое. Пауль Эрдеш на протяжении столетия внес основополагающий вклад в комбинаторику, частично за этот вклад получив премию Вольфа. [33]
Примечания [ править ]
- ↑ Перейти обратно: Перейти обратно: а б с д и ж г Биггс, Норман; Кейт Ллойд; Робин Уилсон (1995). «44». В Рональде Грэме; Мартин Гретшель ; Ласло Ловаш (ред.). Справочник по комбинаторике (Google книга) . МТИ Пресс. стр. 2163–2188. ISBN 0-262-57172-2 . Проверено 8 марта 2008 г.
- ^ Хит, сэр Томас (1981). История греческой математики (Reprod. en fac-sim. Ed.). Нью-Йорк: Дувр. ISBN 0486240738 .
- ↑ Перейти обратно: Перейти обратно: а б Дьедонне, Ж. «Папирус Ринда/Ахмеса - математика и гуманитарные науки» . История математики . Государственный университет Трумэна. Архивировано из оригинала 12 декабря 2012 г. Проверено 6 марта 2008 г.
- ^ Гоу, Джеймс (1968). Краткая история греческой математики . Книжный магазин АМС. п. 71. ИСБН 0-8284-0218-3 .
- ^ Ачерби, Ф. (2003). «На плечах Гиппарха» . Архив истории точных наук . 57 (6): 465–502. дои : 10.1007/s00407-003-0067-0 . S2CID 122758966 .
- ^ Стэнли, Ричард П. (10 апреля 2018 г.). «Гиппарх, Плутарх, Шредер и Хаф» . Американский математический ежемесячник . 104 (4): 344–350. дои : 10.2307/2974582 . ISSN 0002-9890 . JSTOR 2974582 .
- ^ Нетц, Р.; Ачерби, Ф.; Уилсон, Н. «На пути к реконструкции желудка Архимеда» . Скиамвс . 5 : 67–99.
- ^ Хогендейк, Ян П. (1986). «Арабские следы утраченных произведений Аполлония» . Архив истории точных наук . 35 (3): 187–253. дои : 10.1007/BF00357307 . ISSN 0003-9519 . JSTOR 41133783 . S2CID 121613986 .
- ^ Хаксли, Г. (1967). «Окитокион» . Греческие, римские и византийские исследования . 8 (3): 203–204.
- ↑ Перейти обратно: Перейти обратно: а б «Индия» . Архивировано из оригинала 14 ноября 2007 г. Проверено 5 марта 2008 г.
- ↑ Перейти обратно: Перейти обратно: а б Холл, Рэйчел Уэллс (февраль 2008 г.). «Математика для поэтов и барабанщиков» . Математические горизонты . 15 (3): 10–24. дои : 10.1080/10724117.2008.11974752 . JSTOR 25678735 .
- ^ Кулкарни, Амба (2007). «Рекурсия и комбинаторная математика в Чандашастре». arXiv : math/0703658 .
- ^ Бхаскара . «Лилавати Бхаскары» . Брауновский университет. Архивировано из оригинала 25 марта 2008 г. Проверено 6 марта 2008 г.
- ^ Суэйни, Марк. «Марк Суони об истории магических квадратов» . Архивировано из оригинала 7 августа 2004 г.
- ^ "Средний Восток" . Архивировано из оригинала 14 ноября 2007 г. Проверено 8 марта 2008 г.
- ^ Краткий комментарий к Исходу 3:13.
- ^ История комбинаторики , глава в учебнике.
- ^ Артур Т. Уайт, «Звонок косетов», Amer. Математика. Ежемесячник 94 (1987), вып. 8, 721-746; Артур Т. Уайт, «Фабиан Стедман: первый теоретик групп?», Amer. Математика. Ежемесячник 103 (1996), вып. 9, 771–778.
- ^ Девлин, Кейт (октябрь 2002 г.). «800-летие со дня рождения книги, принесшей цифры на Запад» . Угол Девлина . Проверено 8 марта 2008 г.
- ↑ Кандидатская диссертация Лейбница De Arte Combinatoria была опубликована в виде книги в 1666 году и позже переиздана.
- ^ Диксон, Леонард (2005) [1919]. «Глава III». Диофантовый анализ . История теории чисел . Минеола, Нью-Йорк: Dover Publications, Inc., с. 101. ИСБН 0-486-44233-0 .
- ^ Ходжсон, Джеймс; Уильям Дерхэм; Ричард Мид (1708 г.). Miscellanea Curiosa (книга Google) . Том II. стр. 183–191 . Проверено 8 марта 2008 г.
- ^ О'Коннор, Джон; Эдмунд Робертсон (июнь 2004 г.). «Авраам де Муавр» . Архив истории математики MacTutor . Проверено 9 марта 2008 г.
- ^ Панг, Чон-Ши; Олви Мангасарян (1999). «10.6 Генерирующая функция». В Чон-Ши Панге (ред.). Вычислительная оптимизация (книга Google) . Том 1. Нидерланды: Kluwer Academic Publishers. стр. 182–183. ISBN 0-7923-8480-6 . Проверено 9 марта 2008 г.
- ^ «Комбинаторика и вероятность» . Проверено 8 марта 2008 г.
- ^ Биркгоф, Гаррет (1984). Теория решеток (3-е изд., переиздается с исправлениями. Изд.). Провиденс, Род-Айленд: Американское математическое общество. ISBN 978-0821810255 .
- ↑ Перейти обратно: Перейти обратно: а б Стэнли, Ричард П. (2012). Перечислительная комбинаторика (2-е изд.). Кембридж: Издательство Кембриджского университета. стр. 391–393 . ISBN 978-1107602625 .
- ^ Бендер, Эдвард А.; Гольдман, младший (1975). «О применении обращения Мёбиуса в комбинаторном анализе» . амер. Математика. Ежемесячно . 82 (8): 789–803. дои : 10.2307/2319793 . JSTOR 2319793 .
- ^ Стэнли, Ричард (2007). «Введение в устройства гиперплоскости». Геометрическая комбинаторика . Серия IAS / Парк-Сити по математике. Том. 13. С. 389–496. дои : 10.1090/pcms/013/08 . ISBN 9780821837368 .
- ^ Стэнли, Ричард (1974). «Комбинаторные теоремы взаимности» . Достижения в математике . 14 (2): 194–253. дои : 10.1016/0001-8708(74)90030-9 .
- ^ Стэнли, Ричард (1982). «Некоторые аспекты групп, действующих на конечных частично упорядоченных множествах» . Журнал комбинаторной теории . Сер. А 32 (2): 132–161. дои : 10.1016/0097-3165(82)90017-6 .
- ^ Стэнли, Ричард (1976). «Биномиальные упорядоченные множества, инверсия Мёбиуса и перечисление перестановок» . Журнал комбинаторной теории . Сер. А 20 (3): 336–356. дои : 10.1016/0097-3165(76)90028-5 .
- ^ «Страница премии Фонда Вольфа по математике» . Wolffund.org.il. Архивировано из оригинала 10 апреля 2008 г. Проверено 29 мая 2010 г.
Ссылки [ править ]
- Н. Л. Биггс, Корни комбинаторики, Historia Mathematica 6 (1979), 109–136.
- Кац, Виктор Дж. (1998). История математики: Введение , 2-е издание. Издательство Addison-Wesley Education. ISBN 0-321-01618-1 .
- О'Коннор, Джон Дж. и Робертсон, Эдмунд Ф. (1999–2004 гг.). MacTutor Архив истории математики . Университет Сент-Эндрюс .
- Рашид, Р. (1994). Развитие арабской математики: между арифметикой и алгеброй . Лондон.
- Уилсон Р. и Уоткинс Дж. (2013). Комбинаторика: древняя и современная . Оксфорд.
- Стэнли, Ричард (2012). Перечислительная комбинаторика (2-е изд.) , 2-е изд. Издательство Кембриджского университета. ISBN 1107602629 .
