История комбинаторики - History of combinatorics

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

Самые ранние записи

Фрагмент папируса Райнда.

Самое раннее зарегистрированное использование комбинаторных методов связано с проблемой 79 Папирус Ринда, который датируется 16 веком до нашей эры. Проблема касается определенного геометрического ряда и имеет сходство с проблемой Фибоначчи о подсчете количества композиции единиц и двоек, которые в сумме составляют заданную сумму.[1]

В Греции, Плутарх написал это Ксенократ из Халкидона (396–314 г. до н.э.) обнаружил, что в греческом языке возможно множество различных слогов. Это была бы первая попытка решить сложную проблему в перестановки и комбинации.[2] Это утверждение, однако, неправдоподобно: это одно из немногих упоминаний комбинаторики в Греции, и найденное ими число 1,002 × 10. 12, кажется слишком круглым, чтобы быть более чем предположением.[3][4]

В Бхагавати Сутра первое упоминание о проблеме комбинаторики; Задача заключалась в следующем: сколько возможных комбинаций вкусов возможно при выборе вкусов по одному, по два, по три и т. д. из шести различных вкусов (сладкий, острый, терпкий, кислый, соленый и горький). Бхагавати также является первым текстом, в котором упоминается выбрать функцию.[5] Во втором веке до нашей эры Пингала включил проблему перечисления в Чанда Сутра (также Chandahsutra), который спрашивал, сколько способов можно составить шестисложный метр из коротких и длинных нот.[6][7] Пингала нашла количество метров, в которых длинные заметки и короткие заметки; это эквивалентно нахождению биномиальные коэффициенты.

Идеи Бхагавати были обобщены индийским математиком. Махавира в 850 г. н.э., а работа Пингалы по просодия был расширен Бхаскара II[5][8] и Хемачандра в 1100 году нашей эры. Бхаскара был первым известным человеком, который нашел функцию обобщенного выбора, хотя Брахмагупта возможно, знал раньше.[1] Хемачандра спросил, сколько метров существует определенной длины, если длинная нота считается вдвое длиннее короткой, что равносильно нахождению Числа Фибоначчи.[6]

А гексаграмма

Древняя китайская книга гаданий И Цзин описывает гексаграмму как перестановку с повторением шести линий, где каждая линия может быть в одном из двух состояний: сплошной или пунктирной. Описывая гексаграммы таким образом, они определяют, что существуют возможные гексаграммы. Китайский монах также мог подсчитать количество конфигураций в игре, похожей на Идти около 700 г. н.э.[3] Хотя в Китае было относительно мало достижений в области перечислительной комбинаторики, около 100 г. н.э. они решили Площадь Ло Шу какой комбинаторный дизайн проблема нормального магический квадрат третьего порядка.[1][9] Магические квадраты по-прежнему интересовали Китай, и они начали обобщать свои оригинальные площадь между 900 и 1300 годами нашей эры. Китай переписывался с Ближним Востоком по этой проблеме в 13 веке.[1] Ближний Восток также узнал о биномиальных коэффициентах из индийских работ и обнаружил связь с полиномиальным расширением.[10] Работа индусов повлияла на арабов, как видно из работы аль-Халил ибн Ахмад который рассмотрел возможные варианты расположения букв для образования слогов. Его расчеты показывают понимание перестановок и комбинаций. В отрывке из работы арабского математика Умара аль-Хайями, датируемом примерно 1100 годом, подтверждается, что индусы знали биномиальные коэффициенты, но также и то, что их методы достигли Ближнего Востока.

В Греции, Плутарх писал, что Ксенократ открыл количество различных слогов, возможных в греческом языке. Маловероятно, но это одно из немногих упоминаний комбинаторики в Греции. Число, которое они нашли, 1,002 × 10 12, также кажется слишком круглым, чтобы быть более чем предположением.[3][4]

Абу Бакр ибн Мухаммад ибн аль-Хусейн аль-Караджи (c.953-1029) писал о биномиальной теореме и треугольнике Паскаля. В уже утерянной работе, известной только из последующего цитирования аль-Самав'аль, Аль-Караджи ввел идею аргументации с помощью математической индукции.

В философ и астроном Раввин Авраам ибн Эзра (ок. 1140) подсчитал перестановки с повторениями в вокализации Божественного Имени.[11] Он также установил симметрию биномиальные коэффициенты, а замкнутая формула была получена позже талмудист и математик Леви бен Герсон (более известный как Герсонид), в 1321 г.[12]Арифметический треугольник - графическая диаграмма, показывающая отношения между биномиальные коэффициенты - был представлен математиками в трактатах, датируемых еще 10 веком, и в конечном итоге стал известен как Треугольник Паскаля. Позже Средневековая Англия, кампанология предоставил примеры того, что сейчас известно как Гамильтоновы циклы в определенных Графики Кэли по перестановкам.[13]

Комбинаторика на Западе

Комбинаторика пришла в Европу в 13 веке благодаря математикам. Леонардо Фибоначчи и Иорданус де Немор. Фибоначчи Liber Abaci познакомил Европу со многими арабскими и индийскими идеями, в том числе с числами Фибоначчи.[14][15] Иордан был первым, кто расположил биномиальные коэффициенты в треугольнике, как он это сделал в предложении 70 из De Arithmetica. Это также было сделано на Ближнем Востоке в 1265 году и в Китае около 1300 года.[1] Сегодня этот треугольник известен как Треугольник Паскаля.

Паскаль Вклад в треугольник, носящий его имя, основан на его работе над его формальными доказательствами и связями, которые он установил между треугольником Паскаля и вероятностью.[1] Из письма Лейбниц отправлен в Даниэль Бернулли мы узнаем, что Лейбниц формально изучал математическую теорию перегородки в 17 веке, хотя никаких официальных работ опубликовано не было. Вместе с Лейбницем Паскаль опубликовал De Arte Combinatoria в 1666 году, позже переизданный.[16] Паскаль и Лейбниц считаются основоположниками современной комбинаторики.[17]

И Паскаль, и Лейбниц понимали, что биномиальное разложение был эквивалентен функция выбора. Представление о соответствии алгебры и комбинаторики было расширено Де Муавром, который нашел расширение полинома.[18] Де Муавр также нашел формулу психических расстройств, используя принцип принцип включения-исключения, метод, отличный от Николауса Бернулли, который нашел его ранее.[1] Де Муавру также удалось приблизиться к биномиальные коэффициенты и факториал, и нашел замкнутую форму чисел Фибоначчи, изобретая производящие функции.[19][20]

В 18 веке Эйлер работал над проблемами комбинаторики и несколькими проблемами вероятности, которые связаны с комбинаторикой. Проблемы, над которыми работал Эйлер, включают Рыцарский тур, Греко-латинский квадрат, Числа Эйлера, и другие. Чтобы решить Семь мостов Кенигсберга проблема, которую он изобрел теорию графов, которая также привела к формированию топология. Наконец, он начал с перегородки с использованием производящие функции.[21]

Современная комбинаторика

В 19 веке предметом частично упорядоченные наборы и теория решетки возникла в результате работы Дедекинд, Пирс, и Шредер. Однако это было Гаррет Биркофф плодотворная работа в его книге Теория решеток опубликовано в 1967 г.,[22] и работа Джон фон Нейман это действительно установило предметы.[23] В 1930-е гг. зал (1936) и Вайснер (1935) независимо сформулировал общую формулу обращения Мёбиуса.[24] В 1964 г. Джан-Карло Рота Об основах комбинаторной теории I. Теория функций Мёбиуса. представил теорию посетов и решеток как теории комбинаторики.[23] Ричард П. Стэнли оказал большое влияние на современную комбинаторику благодаря своей работе в теория матроидов,[25] для введения полиномов Дзета,[26] для явного определения эйлеровых множеств,[27] развивая теорию биномиальных поз вместе с Ротой и Питером Дубиле,[28] и больше.

Примечания

  1. ^ а б c d е ж грамм Биггс, Норман; Кейт Ллойд; Робин Уилсон (1995). «44». В Рональде Грэме; Мартин Грётшель; Ласло Ловас (ред.). Справочник по комбинаторике (Гугл книга). MIT Press. С. 2163–2188. ISBN  0-262-57172-2. Получено 2008-03-08.
  2. ^ Хит, сэр Томас (1981). История греческой математики (Репродукция. На факс. Ред.). Нью-Йорк: Дувр. ISBN  0486240738.
  3. ^ а б c Дьедонне, Ж. "Папирус Райнда / Ахмеса - математика и гуманитарные науки". Historia Math. Государственный университет Трумэна. Архивировано из оригинал на 2012-12-12. Получено 2008-03-06.
  4. ^ а б Гоу, Джеймс (1968). Краткая история греческой математики. Книжный магазин AMS. п. 71. ISBN  0-8284-0218-3.
  5. ^ а б "Индия". Архивировано из оригинал на 2007-11-14. Получено 2008-03-05.
  6. ^ а б Холл, Рэйчел (16 февраля 2005 г.). «Математика для поэтов и барабанщиков - Математика метра» (PDF). Получено 2008-03-05. Цитировать журнал требует | журнал = (помощь)
  7. ^ Кулкарни, Амба (2007). «Рекурсивная и комбинаторная математика в Чандашастре». arXiv:математика / 0703658. Bibcode:2007математика ...... 3658K. Цитировать журнал требует | журнал = (помощь)
  8. ^ Бхаскара. "Лилавати Бхаскары". Брауновский университет. Архивировано из оригинал на 2008-03-25. Получено 2008-03-06.
  9. ^ Свани, Марк. «Марк Свани об истории магических квадратов». Архивировано из оригинал на 2004-08-07.
  10. ^ "Средний Восток". Архивировано из оригинал на 2007-11-14. Получено 2008-03-08.
  11. ^ Краткий комментарий к Исход 3:13
  12. ^ История комбинаторики, глава в учебнике.
  13. ^ Артур Т. Уайт, "Звонок козетам", Амер. Математика. Ежемесячно 94 (1987), нет. 8, 721-746; Артур Т. Уайт, "Фабиан Стедман: первый теоретик групп?" Амер. Математика. Ежемесячно 103 (1996), нет. 9, 771-778.
  14. ^ Девлин, Кейт (октябрь 2002 г.). «800-летие книги, принесшей цифры на запад». Угол Девлина. Получено 2008-03-08.
  15. ^ «Последовательность Фибоначчи - История». Чистые отрасли. 2008 г.. Получено 2008-03-08.
  16. ^ Тезис о абилитации Лейбница De Arte Combinatoria была опубликована в виде книги в 1666 году и переиздана позже
  17. ^ Диксон, Леонард (2005) [1919]. «Глава III». Диофантов анализ. История теории чисел. Минеола, Нью-Йорк: Dover Publications, Inc., стр. 101. ISBN  0-486-44233-0.
  18. ^ Ходжсон, Джеймс; Уильям Дерхам; Ричард Мид (1708). Miscellanea Curiosa (Книга Google). Том II. стр. 183–191. Получено 2008-03-08.
  19. ^ О'Коннор, Джон; Эдмунд Робертсон (июнь 2004 г.). "Авраам де Муавр". Архив истории математики MacTutor. Получено 2008-03-09.
  20. ^ Пан, Чон-Ши; Ольви Мангасарян (1999). «10.6 Генерирующая функция». В Чжон-Ши Панг (ред.). Вычислительная оптимизация (Книга Google). Том 1. Нидерланды: Kluwer Academic Publishers. С. 182–183. ISBN  0-7923-8480-6. Получено 2008-03-09.
  21. ^ «Комбинаторика и вероятность». Получено 2008-03-08.
  22. ^ Биркгоф, Гарретт (1984). Теория решетки (3-е изд., Перепечатано с исправлениями. Ред.). Провиденс, Р.И .: Американское математическое общество. ISBN  978-0821810255.
  23. ^ а б Стэнли, Ричард П. (2012). Перечислительная комбинаторика (2-е изд.). Кембридж: Издательство Кембриджского университета. стр.391 –393. ISBN  978-1107602625.
  24. ^ Бендер, Эдвард А .; Гольдман, Дж. Р. (1975). «О приложениях обращения Мёбиуса в комбинаторном анализе». Амер. Математика. Ежемесячно. 82 (8): 789–803. Дои:10.2307/2319793. JSTOR  2319793.
  25. ^ Стэнли, Ричард (2007). «Введение в устройства гиперплоскостей». Геометрическая комбинаторика. IAS / Серия математики Парк-Сити. 13 (IAS / Park City Mathematics Series): 389–496. Дои:10,1090 / шт / 013/08. ISBN  9780821837368.
  26. ^ Стэнли, Ричард (1974). «Комбинаторные теоремы взаимности». Успехи в математике. 14 (2): 194–253. Дои:10.1016/0001-8708(74)90030-9.
  27. ^ Стэнли, Ричард (1982). «Некоторые аспекты групп, действующих на конечных множествах». Журнал комбинаторной теории. Сер. А 32 (2): 132–161. Дои:10.1016/0097-3165(82)90017-6.
  28. ^ Стэнли, Ричард (1976). «Биномиальные позы, обращение Мёбиуса и перестановочное перечисление». Журнал комбинаторной теории. Сер. А 20 (3): 336–356. Дои:10.1016/0097-3165(76)90028-5.

Рекомендации

  • Н.Л. Биггс, Корни комбинаторики, Historia Mathematica 6 (1979), 109–136.
  • Кац, Виктор Дж. (1998). История математики: введение, 2-е издание. Издательство Эддисон-Уэсли по образованию. ISBN  0-321-01618-1.
  • О'Коннор, Джон Дж. И Робертсон, Эдмунд Ф. (1999–2004). Архив истории математики MacTutor. Сент-Эндрюсский университет.
  • Рашед Р. (1994). Развитие арабской математики: между арифметикой и алгеброй. Лондон.
  • Уилсон, Р. и Уоткинс, Дж. (2013). Комбинаторика: древнее и современное. Оксфорд.
  • Стэнли, Ричард (2012). Перечислительная комбинаторика (2-е изд.), 2-е издание. Издательство Кембриджского университета. ISBN  1107602629.