Иоганн Вольфганг Гёте
„Часто говорят, что цифры управляют миром; по крайней мере нет сомнения в том, что цифры показывают, как он управляется.“
Введение
Что есть комбинаторика?
Комбинаторика является неотъемлемой частью любой сферы деятельности человека, от нее зависят производственные отрасли, решение повседневных проблем, отмечается востребованность в науке, её применение влияет на эффективность деятельности и дальнейшее развитие.
Долгое время историки математики пренебрегали комбинаторикой. Но всё же есть веские причины для изучения этой истории происхождения, которая отлична от развития арифметики, алгебры или геометрии, потребовалось много времени, чтобы данный раздел математики стал идентифицируем как отдельный, со своими определениями и теоремами.
Долгое время историки математики пренебрегали комбинаторикой. Но всё же есть веские причины для изучения этой истории происхождения, которая отлична от развития арифметики, алгебры или геометрии, потребовалось много времени, чтобы данный раздел математики стал идентифицируем как отдельный, со своими определениями и теоремами.
«
Всем известные задачки были придуманы давным-давно:
«Волк, козел и капуста», игра «Крестики-нолики», они решаются путём составления правильной последовательности.
Рассмотрим методы решения комбинаторных задач:
1
Дерево возможных вариантов
Основа решения комбинаторных задач - составление схем, внешне похожих на дерево, где ветви обозначают различные события, объединённые корнем - общими условиями.
2
Перестановки
Являются самыми простыми комбинациями из множества элементов.
3
Размещение
Это расположение объектов в определенном порядке при условии, что каждое место занято только одним и все они различны.
С чего же всё началось?
В арабских учебных заведениях получил образование Леонардо Пизанский - сын купца, торговавшего в Алжире, получивший прозвище Фибоначчи.
Несколько комбинаторных задач содержит «Книга абака», написанная им в 1202 году.
Несколько комбинаторных задач содержит «Книга абака», написанная им в 1202 году.
«
В своей книге Фибоначчи привёл в систему всю арабскую арифметику, некоторые сведения по геометрии Евклида, и добавил к ним результаты своих исследований. Рассматривал Леонардо и отыскание целых решений уравнений. В дальнейшем аналогичные задачи привели к отысканию количества натуральных решений систем уравнений и неравенств, которое может рассматриваться как одна из глав комбинаторики.
»
Но главной заслугой Леонардо перед комбинаторикой было то, что он впервые вывел формулу, в которой следующий член выражался через два предыдущих. Подобные формулы получили название рекуррентных (от латинского recurrere - возвращаться).
Со времён греческих математиков были известны две последовательности, каждый член которых получался по определённым правилам из предыдущих - арифметическая и геометрическая прогрессии.
В задаче Леонардо появилась новая последовательность, члены которой были связаны друг с другом соотношением: un= nn-1+un-2.
В задаче Леонардо появилась новая последовательность, члены которой были связаны друг с другом соотношением: un= nn-1+un-2.
«
Одна из старейших сохранившихся математических рукописей - папирус Ринда (около 1650 г. до н.э.), которая была обнаружена в 1858 году.
Переводчики древних произведений, как правило, используют неточные и случайные значения, а не математические. Таким образом, работа, которая, как кажется, имеет дело с перестановками и комбинациями, может не быть связанной ни с одной, либо с одной, либо с обеими из этих тем.
Одним из самых простых аспектов предмета является перечисление строк из r символов, каждый из которых может быть одним из данного набора n символов.
В математической терминологии это комбинации с повторением, или просто, функции (от набора r позиций до набора n доступных символов). Пример этого правила встречается в китайской “Книге перемен” или И-Цзин (написанной ок. 700 г. до. н. э. и предназначавшейся для гадания, состоит из 64 гексаграмм).
Одним из самых простых аспектов предмета является перечисление строк из r символов, каждый из которых может быть одним из данного набора n символов.
В математической терминологии это комбинации с повторением, или просто, функции (от набора r позиций до набора n доступных символов). Пример этого правила встречается в китайской “Книге перемен” или И-Цзин (написанной ок. 700 г. до. н. э. и предназначавшейся для гадания, состоит из 64 гексаграмм).
»
Древний Китай
«В государстве мудрого правителя нет книг и записей на бамбуке, но единой доктриной является закон; нет речений былых правителей, — единственным образцом для подражания являются государственные мужи»
Хань Фэй
Хань Фэй
Гексаграмма из "книги перемен"
Первое упоминание о вопросах, близких к комбинаторным, встречается в китайских рукописях, относящихся к XII-XIII вв. до н. э. (точно датировать эти рукописи невозможно, поскольку в 213 г. до н.э. император Цин Шихуан приказал сжечь все книги, так что до нас дошли лишь сделанные позднее копии).
В этих книгах писалось, что всё в мире является сочетанием двух начал -- мужского и женского, которое авторы обозначали символами — и — —.
В рукописи “Же-ким” (”Книга перестановок”) показаны различные соединения этих знаков по два и по три.
Восемь рисунков из трёх рядов символов изображали землю, горы, воду, ветер, грозу, огонь, облака и небо (некоторые рисунки имели и иные значения).
Поэтому сумма первых 8 натуральных чисел (т.е. число 36) воплощала в представлениях древних китайцев весь мир.
В рукописи “Же-ким” (”Книга перестановок”) показаны различные соединения этих знаков по два и по три.
Восемь рисунков из трёх рядов символов изображали землю, горы, воду, ветер, грозу, огонь, облака и небо (некоторые рисунки имели и иные значения).
Поэтому сумма первых 8 натуральных чисел (т.е. число 36) воплощала в представлениях древних китайцев весь мир.
По мере углублений знаний понадобилось выразить и другие элементы мироздания с помощью тех же знаков.
Были составлены 64 фигуры, содержавшие уже пять рядов чёрточек.
Были составлены 64 фигуры, содержавшие уже пять рядов чёрточек.
В рукописи “Же-ким” есть и более сложные рисунки.
Надо полагать, что автор рукописи “Же-ким” заметил удвоение числа рисунков при добавлении одного ряда символов. Это можно рассматривать как первый общий результат комбинаторики.
Как утверждает приводимое в ней придание, император Ию, живший примерно 4000 лет тому назад, увидел на берегу реки священную черепаху, на панцире которой был изображён рисунок из белых и чёрных кружков.
Если заменить каждую фигуру соответствующим числом, возникнет такая таблица:
4 9 2
3 5 7
8 1 6
При сложении чисел в каждой строке, столбце и диагонали, получается одна и та же сумма – 15. При том мистическом толковании, которое придавали числам древние китайцы, открытие таблицы со столь чудесными свойствами произвело неизгладимое впечатление.
Как утверждает приводимое в ней придание, император Ию, живший примерно 4000 лет тому назад, увидел на берегу реки священную черепаху, на панцире которой был изображён рисунок из белых и чёрных кружков.
Если заменить каждую фигуру соответствующим числом, возникнет такая таблица:
4 9 2
3 5 7
8 1 6
При сложении чисел в каждой строке, столбце и диагонали, получается одна и та же сумма – 15. При том мистическом толковании, которое придавали числам древние китайцы, открытие таблицы со столь чудесными свойствами произвело неизгладимое впечатление.
Квадрат назвали “ло-шу”, стали считать его магическим символом и использовать в заклинаниях. Поэтому сейчас любую квадратную таблицу чисел с одинаковыми суммами по каждой строке, столбцу и диагонали называют магическим квадратом.
»
История повторяется?
Древняя Греция
Вычисления древних греков.
До нас дошло далеко не всё из их научного наследия. В 391 г. н.э. толпа монахов разрушила центр языческой науки - александрийский Музеум - и сожгла большую часть хранившейся в нём библиотеки, насчитывавшей многие тысячи томов. Остатки библиотеки разрушались в течение ещё трёх веков, а в 638 г. н. э. она окончательно погибла при взятии Александрии войсками арабского халифа Омара.
Большинство научных книг безвозратно утеряны, и мы можем лишь догадываться об их содержании по кратким пересказам и намёкам в сохранившихся рукописях.
По этим намёкам можно всё же судить, что определённые представления о комбинаторике у греческих учёных были.
Большинство научных книг безвозратно утеряны, и мы можем лишь догадываться об их содержании по кратким пересказам и намёкам в сохранившихся рукописях.
По этим намёкам можно всё же судить, что определённые представления о комбинаторике у греческих учёных были.
Философ Ксенократ, живший в IV в. до н. э., подсчитывал число слогов.
В III в. до н. э. стоик Хрисппи полагал, что число утверждений, получаемых из 10 аксиом, превышает миллион.
По мнению же Гипнарха, из утверждающих аксиом можно составить 103 049 сочетаний, а добавив к ним отрицающие, 310952.
Конкретные комбинаторные задачи, касавшиеся перечисления небольших групп предметов, греки решали без ошибок.
Аристотель описал без пропусков все виды правильных трёхчленных силлогизмов, а его ученик Аристоксен из Тарента перечислил различные комбинации длинных и коротких слогов в стихотворных размерах.
Живший в IV в. н. э. математик Папп рассматривал число пар и троек, которые можно получить из трёх элементов, допуская их повторения.
Аристотель описал без пропусков все виды правильных трёхчленных силлогизмов, а его ученик Аристоксен из Тарента перечислил различные комбинации длинных и коротких слогов в стихотворных размерах.
Живший в IV в. н. э. математик Папп рассматривал число пар и троек, которые можно получить из трёх элементов, допуская их повторения.
Мы не знаем, какой именно смысл придавали эти философы своим утверждениям и как они получали свои результаты - приводимые Гиппархом числа слишком точны, чтобы считать их результатом грубой оценки, и в то же время не поддаются разумному истолкованию. По-видимому, у греческих учёных были какие-то не дошедшие до нас правила комбинаторных расчётов, скорее всего ложные.
Большое внимание греческие учёные уделяли вопросам, пограничным между комбинаторикой и теорией чисел . Ещё в VI в до н. э. в школе философа-идеалиста и математика Пифагора возникло убеждение, что миром правят числа, а вещи только отражение чисел (возможно, что эти идеи возникли у Пифагора под влиянием вавилонской культуры и восходят к ещё более древним вглядам шумеров).
~
Чтобы познать мир, пифагорейцы начали изучать свойства натуральных чисел. Их исследования о чётных и нечётных числах, делимости чисел, простых и составных числах положили основу теории чисел.
~
Чтобы познать мир, пифагорейцы начали изучать свойства натуральных чисел. Их исследования о чётных и нечётных числах, делимости чисел, простых и составных числах положили основу теории чисел.
~
Для пифагорейцев особое значение имело число 36 - оно было не только суммой перых трёх кубов:
36 = 1^3+2^3+3^3. Символом совершенства пифагорейцы считали числа, равные сумме своих делителей, например, 6=1+2+3,28=1+2+4+7+14, а символом дружбы - дружественные числа, каждое из которых равно сумме делителей другого числа (например, 220 и 284). Отыскание таких чисел требовало комбинаторного искусства.
В школе Пифагора была доказана известная теорема о сторонах прямоугольного треугольника.
36 = 1^3+2^3+3^3. Символом совершенства пифагорейцы считали числа, равные сумме своих делителей, например, 6=1+2+3,28=1+2+4+7+14, а символом дружбы - дружественные числа, каждое из которых равно сумме делителей другого числа (например, 220 и 284). Отыскание таких чисел требовало комбинаторного искусства.
В школе Пифагора была доказана известная теорема о сторонах прямоугольного треугольника.
Переход от плоскости к пространству дал возможность строить ещё более сложные числа. Например, из треугольников можно составить пирамиды. Подсчитывая число точек в таких пирамидах. пришли к пирамидальным числам 1, 4, 10, 20,..., которые были суммами ряда 1+3+6+10+..., составленного из треугольных чисел. Однако дальнейшие обобщения требовали уже введения многомерных пространств, что лежало за рамками возможностей древнегреческой математики.
Наряду с комбинаторикой чисел греческие учёные занимались и отдельными вопросами геометрической комбинаторики - правильными и полуправильными многогранниками, составлением фигур из 14 частей особым образом разрезанного квадрата и т.д.
Учение о фигурных числах привлекало к себе математиков на протяжении многих столетий. Ими много занимался живший в XVII в. французский учёный Пьер Ферма, который доказал, например, что любое натуральное чило есть или треугольное или сумма 2 или 3 треугольных чисел, квадратное или сумма 2, 3 или 4 квадратов, пятиугольное или сумма 2, 3, 4 или 5 пятиугольных и т.д. Как и многие другие полученные им результаты, он лишь сформулировал это утверждение в письме к Блэзу Паскалю. (юрист по основной профессии, Ферма занимался математикой лишь в часы досуга). Частные случаи этой теоремы доказали Эйлер и Лагранж, а общее доказательство было дано в 1815 г. французским математиком О. Коши.
Астролог бен Эзра в 1140 г. рассчитал количество сочетаний семи планет по две, по три и т.д. Он знал, что число сочетаний планет по две равно числу их сочетаний по пять , а число сочетаний по три равно числу сочетаний по четыре. Его работа, написанная на малодоступном большинству учёных древнееврейском языке, осталась почти незамеченной - вновь эту формулу вывел в начале XVII в. французский математик И. Эригон.
Астролог бен Эзра в 1140 г. рассчитал количество сочетаний семи планет по две, по три и т.д. Он знал, что число сочетаний планет по две равно числу их сочетаний по пять , а число сочетаний по три равно числу сочетаний по четыре. Его работа, написанная на малодоступном большинству учёных древнееврейском языке, осталась почти незамеченной - вновь эту формулу вывел в начале XVII в. французский математик И. Эригон.
Своеобразной комбинаторикой занимались и логики. Продолжая исследования Аристотеля, они классифицировали понятия и логические рассуждения. В III в. н. э. сириец Порфирий для классификации понятий составил особую схему, получившую название “древа Порфирия”. На вершине этого древа помещалось самое широкое по объёму понятие, узлы древа соответствовали различным расчленениям понятия, а линии между узлами отражали подчинённость понятий друг другу. Подобные деревья сейчас широко применяются в приложениях комбинаторики к самым разным вопросам.
Один из основателей медицины, Гален, во II в. н. э. занимался классификацией силлогизмов, состоящих из четырёх частей. Римский философ и математик Боэций (V-VI вв. н. э.) нашёл число пар, которые можно составить из пяти категорий модальности, отбирая их как в утвердительной, так и в отрицательной форме и ставя либо на место условия, либо на место следствия. Он классифицировал также условные силлогизмы.
Большое внимание классификации видов суждений уделяла схоластическая наука. Споря о взаимоотношениях членов пресвятой троицы, о соподчинённости ангелов, архангелов, херувимов и серафимов, схоласты были вынуждены рассматривать различные отношения порядка и иерархии - достаточно вспомнить сложнейшую архитектонику загробного мира, описанную Данте в “Божественной комедии” с её кругами ада и различными областями чистилища и рая.
Схоласт Раймонд Луллий создал в XIII в. машину, состоявшую из нескольких кругов, на которых были нанесены основные предикаты, субъекты, атрибуты и иные понятия схоластической логики. Вращая эти круги, он получал различные сочетания понятий и надеялся получить истинное.
»
Страны востока
Изучение древних индуистских текстов является общеизвестной трудностью. Во многих случаях невозможно обозначить точные даты или отделить оригинальный текст от последующих комментариев и приукрашивания. Некоторые современные индийские историки претендуют на приоритет индусов в разработке частей высшей математики и комбинаторики.
Подобные концепции были неотъемлемой частью их культуры, так что математическое развитие было постепенным и неизбежным. После завоевания частей Индии силами Ислама (в 7 веке н.э.), достижения индуистских математиков начали просачиваться на запад. Арабы сами стали интересоваться искусством и наукой, они смогли объединить восточную мудрость с наследием греков. В комбинаторной математике восточный вклад имел первостепенное значение.
Ученые Ислама были не просто собирателями древних знаний. В работе Аль-Халила Ибн-Ахмада, описанной Рашедом [1974], Халил рассмотрел возможные расположения букв при образовании слогов, и его расчеты показывают, что он понимал основные формулы для нахождения чисел перестановок и комбинаций.
В VIII в. н. э. начался расцвет арабской науки. Ими переведены многие творения греческих учёных. Изучив их, те продвинулись вперёд в областях, мало привлекавших внимание греков, - в решении уравнений, теории и практике вычислений и т.д.
В VIII в. н. э. начался расцвет арабской науки. Ими переведены многие творения греческих учёных. Изучив их, те продвинулись вперёд в областях, мало привлекавших внимание греков, - в решении уравнений, теории и практике вычислений и т.д.
Решая вопрос об извлечении корней любой степени, арабские алгебраисты пришли к формуле для степени суммы двух чисел, известной под исторически неверным названием “бином Ньютона”. Эту формулу знал живший в XI-XII вв. н. э. поэт и математик Омар Хайям. В XIII в. такую формулу приводит в своих трудах Насир-ад-Дип ат-Туси, а в XV в. она была исследована Гинсэддином ал-Каши.
Для отыскания коэффициентов этой формулы брали число 10001 и возводили его во 2-ю, 3-ю, ..., 9-ю степени. Если опустить в полученной таблице лишние нули, то останется треугольная таблица из биномиальных коэффициентов.
Для отыскания коэффициентов этой формулы брали число 10001 и возводили его во 2-ю, 3-ю, ..., 9-ю степени. Если опустить в полученной таблице лишние нули, то останется треугольная таблица из биномиальных коэффициентов.
Биномиальные коэффициенты
»
Средневековье и Новое время
Азартные игры
Игра в кости, которая была очень популярна в древности, навела наблюдательные умы на мысль, что некоторые суммы очков выпадают чаще других.
Были составлены таблицы со способами получения того или иного числа очков. Сначала подсчитывали лишь число различных сочетаний костей, дававших данную сумму, но при бросании двух костей сочетание (3, 3) может быть получено единственным образом, а сочетание (3, 4) - двумя способами. Этим объясняется большая частота выпадения суммы 7. Надо учитывать не только сочетания очков, но и их порядок. Следующая задача для трёх костей. Здесь при учёте порядка костей оказывается 216 различных комбинаций, а без учёта порядка - лишь 56.
Такие задачи разбирали итальянские математики XVI в., как Д. Кардано, Н. Тарталья и др. Наиболее полно исследовал их в XVII в. Галилео Галилей, но его рукопись оставалась неопубликованной до 1718 г.
В поиске беспроигрышной стратегии игрок-энтузиаст Шевалье де Мера обратился к двум крупнейшим математикам Франции XVII в. - Блэзу Паскалю и Пьеру Ферма. Они сформулировали и доказали первые теоремы комбинаторики и теории вероятностей.
Открытие двух новых ветвей
математической науки - комбинаторики и теории вероятностей.
Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века).
Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века).
Проекты Лейбница казались несбыточными математикам его времени, но с появлениемя ЭВМ многие планы учёного стали претворяться в жизнь.
В 1666 г. Готтфрид Вильгельм Лейбниц публикует “Диссертацию о комбинаторном искусстве”, где впервые упоминается термин “комбинаторный”. Труд содержал приложения ко всем областям науки и новый подход к логике изобретения, приложение теории к замкАм, оргАнам, силлогизмам, смешению цветов и стихосложению, к логике, геометрии, военному искусству, грамматике, юриспруденции, медицине и теологии.
Диссертация Лейбница должна была стать началом большой работы. Лейбниц размышлял над новыми приложениями этого раздела математики: к кодированию и декодированию, играм, статистике, теории наблюдений.
Лейбниц:" Комбинаторика должна заниматься одинаковым и различным, похожим и непохожим, абсолютным и относительным расположением, в то время как обычная математика занимается большим и малым, единицей и многим, целым и частью."
К области комбинаторики Лейбниц относил и “универсальтую характеристику» — математику суждений, т. е. прообраз нынешней математической логики.
Диссертация Лейбница должна была стать началом большой работы. Лейбниц размышлял над новыми приложениями этого раздела математики: к кодированию и декодированию, играм, статистике, теории наблюдений.
Лейбниц:" Комбинаторика должна заниматься одинаковым и различным, похожим и непохожим, абсолютным и относительным расположением, в то время как обычная математика занимается большим и малым, единицей и многим, целым и частью."
К области комбинаторики Лейбниц относил и “универсальтую характеристику» — математику суждений, т. е. прообраз нынешней математической логики.
В 1713 г. была опубликована книга «Искусство предположений» Якоба Бернулли, в которой указывались формулы для числа размещений из n элементов по k, выводились выражения для степенных сумм и т. д. Сочинение Я. Бернулли превзошло работы его предшественников и современников систематичностью, простотой. В XVIII веке пользовалось известностью трактата и учебно-справочного издания.
В математике XIX века появился сначала термин "геометрическая конфигурация", в лекциях по проективной геометрии профессора университета в Страсбурге К.Т. Рейе (1882).
В 1896 году американский математик Элиаким Гастингс Мур (1862-1932) ввёл термин тактическая конфигурация в статье “Tactical memoriada”, понимая под этим термином систему n множеств, содержащих, соответственно а1, а2, ..., аn элементов. К тактическим конфигурациям Мур относит сочетания, размещения, он обогатил список построением новых, обобщающих системы троек Штейнера, и системы троек Киркмана. В своей статье он ссылается на Артура Кэли, который подчёркивал высокую значимость тактических задач в алгебре.
В 1896 году американский математик Элиаким Гастингс Мур (1862-1932) ввёл термин тактическая конфигурация в статье “Tactical memoriada”, понимая под этим термином систему n множеств, содержащих, соответственно а1, а2, ..., аn элементов. К тактическим конфигурациям Мур относит сочетания, размещения, он обогатил список построением новых, обобщающих системы троек Штейнера, и системы троек Киркмана. В своей статье он ссылается на Артура Кэли, который подчёркивал высокую значимость тактических задач в алгебре.
Термин “тактика” ввёл в математику английский математик Джеймс Джозеф Сильвестр (1814-1897) в 1861 году, как раздел математики, изучающий расположение элементов друг относительно друг друга и относил к ней теорию групп, комбинаторный анализ и теорию чисел.
Примечательны достижения швейцарского математика ХVIII в., Леонардо Эйлера. Прожив почти всю жизнь в России, он был членом Петербургской академии наук.
Им детально рассмотрены следующие проблемы: задача о ходе коня; задача о семи мостах, с которой началась теория графов; построение греко-латинских квадратов; обобщённые перестановки, разбиения, а также сочетания и размещения с условиями. Его работа о мостах стала зерном, из которого выросли топология и теория графов, задача об офицерах оказалась связана с планированием экспериментов, а методы, использованные при решении задачи о разбиении чисел превратились в науку об интегральных преобразованиях.
После упомянутых работ стали говорить о комбинаторике как о самостоятельной ветви. В конце XVIII в. немецкий учёный Гинденбург и его ученики попытались построить общую теорию комбинаторного анализа. Однако она не увенчалась успехом - в то время ещё не было накоплено достаточного количества важных и интересных задач, которые могли бы дать необходимый фундамент для такой теории. В XIX в. в ходе исследований по комбинаторике стали прослеживаться связи этой теории с определителями, конечными геометриями, группами, математической логикой и т.д.
После упомянутых работ стали говорить о комбинаторике как о самостоятельной ветви. В конце XVIII в. немецкий учёный Гинденбург и его ученики попытались построить общую теорию комбинаторного анализа. Однако она не увенчалась успехом - в то время ещё не было накоплено достаточного количества важных и интересных задач, которые могли бы дать необходимый фундамент для такой теории. В XIX в. в ходе исследований по комбинаторике стали прослеживаться связи этой теории с определителями, конечными геометриями, группами, математической логикой и т.д.
Кодирование и расшифровка
Научные журналы до XVII в. почти не выпускались. Учёные узнавали о трудах своих коллег из книг или частных писем. Большие трудности при опубликовании новых результатов составляло долгое печатание книг, часто возникали споры о принадлежности открытия. Например, между Ньютоном и Лейбницем (о том, кто открыл дифференциальное и интегральное исчисления), Ньютоном и Гуком.
Для того чтобы не допустить преждевременной огласки полученных результатов, учёные в краткой форме формулировали суть открытия, а потом, переставив в ней буквы, отправляли письмо своим коллегам. Такие анаграммы не всегда позволяли сохранить тайну.
Гюйгенс, открыв первый спутник Сатурна и определив период его вращения вокруг планеты, изложил своё открытие в анаграмме. Уоллис, получив и разгадав её, составил свою анаграмму и послал Гюйгепсу. Когда учёные обменялись разгадками, то получилось, будто бы Уоллис ещё до Гюйгенса сделал то же самое открытие. Позднее Уоллис признался, что подшутил над Гюйгенсом, чтобы доказать бесполезность анаграмм в деле тайнописи.
Для того чтобы не допустить преждевременной огласки полученных результатов, учёные в краткой форме формулировали суть открытия, а потом, переставив в ней буквы, отправляли письмо своим коллегам. Такие анаграммы не всегда позволяли сохранить тайну.
Гюйгенс, открыв первый спутник Сатурна и определив период его вращения вокруг планеты, изложил своё открытие в анаграмме. Уоллис, получив и разгадав её, составил свою анаграмму и послал Гюйгепсу. Когда учёные обменялись разгадками, то получилось, будто бы Уоллис ещё до Гюйгенса сделал то же самое открытие. Позднее Уоллис признался, что подшутил над Гюйгенсом, чтобы доказать бесполезность анаграмм в деле тайнописи.
Когда археологи начали откапывать камни и черепки с таинственными знаками - письменностью, использовавшейся несколько тысячелетий назад, одним из самых замечательных успехов в деле их расшифровки было прочтение французским филологом Жаном Франсуа Шампольоном иероглифов, которыми писали египтяне.
В 1814 г. путём лишь комбинаторного исследования текста он получил интересные результаты, а затем Шампольон, сочетавший комбинаторный дар с глубочайшим знанием филологии, смог прочесть иероглифы. Он обнаружил, что некоторые знаки в именах фараонов Птолемея и Клеопатры совпадают. Так были найдены звучания иероглифов, обозначавших буквы “п” и “л” (до этого места дошёл и Юнг). Таким же способом прочтены имена римских императоров Тиберия и Траяна, древних фараонов Рамсеса и Тутмеса.
Комбинаторика позволила прочесть и крито-микенское линейное письмо. Основы дешифровки этой письменности заложила Алиса Д. Кобер, защитившая в 1932 г. докторскую диссертацию по математике в Колумбийском университете.
Изучив знаки критского письма, Кобер установила, что это письмо является слоговым. Далее она заметила, что в исследуемых текстах некоторые слова встречаются в трёх различных формах, отличающихся друг от друга несколькими последними знаками, по-видимому, падежными окончаниями. А дальше она начала составлять “лингвистические уравнения” для слогов, чтобы найти слоги с одинаковыми согласными, но разными гласными, и одинаковыми гласными и разными согласными. В результате Кобер получила координатную сетку, в которой вместо осей координат стояли номера гласных и согласных букв. У этой сетки был лишь один недостаток - никто не знал, какие именно гласные и согласные образуют эту систему координат.
Позже английский архитектор Майкл Вентрис, пробовал определить значения некоторых гласных, которых меньше, чем согласных, и перебор лучше начинать с них. Одна из попыток оказалась удачной - текст заговорил на языке, весьма напоминавшем греческий язык более ранней эпохи. Вентрису помог завершить расшифровку знаток раннего греческого языка Чедвик.
Позже английский архитектор Майкл Вентрис, пробовал определить значения некоторых гласных, которых меньше, чем согласных, и перебор лучше начинать с них. Одна из попыток оказалась удачной - текст заговорил на языке, весьма напоминавшем греческий язык более ранней эпохи. Вентрису помог завершить расшифровку знаток раннего греческого языка Чедвик.
«
Комбинаторика в биологии
Сложность строения биологических систем, иерархичность делают биологию отличным полем для приложения комбинаторных методов.
Биолог А. А. Любищев полагал, что сходство растений и морозных узоров на окнах не случайно - в обоих случаях проявляются определённые законы комбинирования частей в единое целое.
Биолог А. А. Любищев полагал, что сходство растений и морозных узоров на окнах не случайно - в обоих случаях проявляются определённые законы комбинирования частей в единое целое.
Ген и строение ДНК
Биологи обнаружили, что в процессе передачи хромосомы переходят от одной бактерии к другой не целиком. Изучая перешедшие части, пытались выяснить порядок расположения генов в хромосоме. Французские учёные Жакоб и Вальмон обнаружили, что хромосомы бактерий оказались свёрнутыми в кольца, которые перед переходом разрываются, после чего к одному концу прикрепляется фактор, перетаскивающий часть хромосомы в другую бактерию. Так как кольцо может разорваться в любом месте, а фактор - прикрепиться к любому концу, то возникает многообразие исходов.
Одной из сложнейших загадок в биологии XX в. было строение “нитей жизни” - молекул белка и нуклеиновых кислот. Исследования показали, что молекулы белка - это объединения нескольких длинных цепей, составленных из 20 аминокислот. Чтобы разгадать структуру одной цепи, её отделяют от остальных и подвергают ферментам, разрывающим цепь на части, которые уже можно анализировать, чтобы выяснить порядок аминокислот. Затем происходит сборка цепи из изученных частей. Для этого снова берут те же молекулы белка и подвергают их действию иных ферментов. Путём изучения перекрытий отдельных частей удаётся выяснить порядок аминокислот во всей цепи.
Сочетая комбинаторику с изучением рентгеновских снимков, учёным удалось разгадать строение многих белков, в частности гемоглобина, инсулина и др.
Торжеством комбинаторного подхода можно считать расшифровку строения ДНК, проведённую в Кембридже Ф. Криком и Дж. Уотсоном в 1953 г. Было известно, что ДНК играет важную роль в наследовании свойств организмов. Химический анализ показал, что в состав ДНК входят фосфатосахарные группы, соединённые с четырьмя азотистыми основаниями цитозин и тимин, аденин и гуанин. Такие соединения называют нуклеотидами. Американский химик Чаргафф измерил количество различных нуклеотидов в ДНК растений и животных и открыл зависимость: количество молекул аденина всегда равнялось количеству молекул тимина, а количество молекул гуанина - молекулам цитозина.
Вопрос состоял в том, как соединены между собой нуклеотиды и как это соединение объясняет генетические свойства ДНК. По аналогии с раннее изученным строением белков возникла идея о спиральной структуре ДНК.
Крик и Уотсон решили начать комбинировать нуклеотиды друг с другом так, чтобы они дали спираль нужных размеров (размеры были установлены ранее с помощью рентгеноструктурного анализа). Наилучшей конструкцией послужила винтовая лестница, в которой фосфатосахарные группы образуют перила, а ступеньки состоят из пар азотистых оснований. Так как каждую ступеньку можно ещё повернуть на 180°, то получается четыре вида ступенек.
Как с помощью 4 видов нуклеотидов можно зашифровать 20 видов аминокислот?
Генетический код
Над этим вопросом задумался американский физик Г. Гамов. На первых порах он подверг эту проблему чисто комбинаторному анализу, выделив вопросы строения кода.
На вопрос о кодовом числе ответ дали простые комбинаторные соображения: число видов нуклеотидов равнялось 4 (аденин, гуанин, тимин, цитозин), а из 4 видов можно составить всего 16 различных пар. Этого было недостаточно для кодирования 20 аминокислот. Значит, в кодон должны были входить по крайней мере 3 нуклеотида.
Т. к. число аминокислот равнялось 20, то надо было придумать 20 различных комбинаций, определяемых тройками ступенек. Комбинаторные рассмотрения показали, что число 20 можно получить так: брать любые тройки, но не учитывать в них порядок нуклеотидов, а только состав. Эта идея была реализована Гамовым в виде ромбовидного кода, здесь каждый ромб задаётся тройкой нуклеотидов, причём верхний и нижний нуклеотиды принадлежат разным половинам молекулы ДНК, а средние составляют одну ступеньку лестницы. Несущественность порядка нуклеотидов в кодоне проявлялась, по мнению Гамова, в том, что два ромба, получающиеся друг из друга перестановками верхнего и нижнего или левого и правого нуклеотидов, кодировали одну и ту же аминокислоту.
Однако код Гамова не выдержал проверки экспериментом. Ф. Крик выдвинул идею невырожденного (т.е. большинство аминокислот кодируется не более чем одним кодоном) кода, составленного из неперекрывающихся кодонов. Он решил, что код должен обладать следующим свойством: смысл имеют лишь некоторые перестановки из 3 нуклеотидов. Получался код с требуемыми свойствами, состоявший из 20 кодонов - по одному на каждую аминокислоту.
Но и здесь эксперимент не подтвердил предсказаний теории. Кроме того, критики отметили, что если, по мнению Крика, неизвестно, откуда начинать чтение кода, то столь же неизвестно, читать ли его слева направо или справа налево. Поэтому надо было объединять друг с другом не только кодоны, получающиеся друг из друга перестановками, но и кодоны, отличающиеся порядком чтения (например, АТЦ и ЦТА).
Чисто комбинаторные попытки разгадать тайну генетического кода оказались безуспешными, зато они поставили вопросы, которые надо было решить экспериментально. В 1961 г. на биохимическом конгрессе в Москве американский учёный Ниренберг сообщил об эксперименте, позволившем поставить в соответствие одному из кодонов определённую аминокислоту. Через несколько лет генетический код оказался полностью разгаданным.
На самом деле код неперекрывающийся и вырожденный (т.е. большинство аминокислот кодируется более чем одним кодоном) - некоторые аминокислоты соответствуют четырём нуклеотидам. Были найдены и три бессмысленных кодона, которым не соответствует ни одна аминокислота, они, вероятно, играют роль знаков препинания в коде, показывая начало и конец синтезирования данного белка.
Теперь уже ясна и роль вырожденности кода. Из-за различных внешних воздействий в цепочке нуклеотидов возможны сбои. Благодаря вырожденности кода далеко не все сбои приводят к изменению синтезируемых аминокислот, к мутациям, которые могут оказаться гибельными для организма.
На вопрос о кодовом числе ответ дали простые комбинаторные соображения: число видов нуклеотидов равнялось 4 (аденин, гуанин, тимин, цитозин), а из 4 видов можно составить всего 16 различных пар. Этого было недостаточно для кодирования 20 аминокислот. Значит, в кодон должны были входить по крайней мере 3 нуклеотида.
Т. к. число аминокислот равнялось 20, то надо было придумать 20 различных комбинаций, определяемых тройками ступенек. Комбинаторные рассмотрения показали, что число 20 можно получить так: брать любые тройки, но не учитывать в них порядок нуклеотидов, а только состав. Эта идея была реализована Гамовым в виде ромбовидного кода, здесь каждый ромб задаётся тройкой нуклеотидов, причём верхний и нижний нуклеотиды принадлежат разным половинам молекулы ДНК, а средние составляют одну ступеньку лестницы. Несущественность порядка нуклеотидов в кодоне проявлялась, по мнению Гамова, в том, что два ромба, получающиеся друг из друга перестановками верхнего и нижнего или левого и правого нуклеотидов, кодировали одну и ту же аминокислоту.
Однако код Гамова не выдержал проверки экспериментом. Ф. Крик выдвинул идею невырожденного (т.е. большинство аминокислот кодируется не более чем одним кодоном) кода, составленного из неперекрывающихся кодонов. Он решил, что код должен обладать следующим свойством: смысл имеют лишь некоторые перестановки из 3 нуклеотидов. Получался код с требуемыми свойствами, состоявший из 20 кодонов - по одному на каждую аминокислоту.
Но и здесь эксперимент не подтвердил предсказаний теории. Кроме того, критики отметили, что если, по мнению Крика, неизвестно, откуда начинать чтение кода, то столь же неизвестно, читать ли его слева направо или справа налево. Поэтому надо было объединять друг с другом не только кодоны, получающиеся друг из друга перестановками, но и кодоны, отличающиеся порядком чтения (например, АТЦ и ЦТА).
Чисто комбинаторные попытки разгадать тайну генетического кода оказались безуспешными, зато они поставили вопросы, которые надо было решить экспериментально. В 1961 г. на биохимическом конгрессе в Москве американский учёный Ниренберг сообщил об эксперименте, позволившем поставить в соответствие одному из кодонов определённую аминокислоту. Через несколько лет генетический код оказался полностью разгаданным.
На самом деле код неперекрывающийся и вырожденный (т.е. большинство аминокислот кодируется более чем одним кодоном) - некоторые аминокислоты соответствуют четырём нуклеотидам. Были найдены и три бессмысленных кодона, которым не соответствует ни одна аминокислота, они, вероятно, играют роль знаков препинания в коде, показывая начало и конец синтезирования данного белка.
Теперь уже ясна и роль вырожденности кода. Из-за различных внешних воздействий в цепочке нуклеотидов возможны сбои. Благодаря вырожденности кода далеко не все сбои приводят к изменению синтезируемых аминокислот, к мутациям, которые могут оказаться гибельными для организма.
»
17 февраля 1869 открыт периодический закон Менделеева, ранее учёные отмечали лишь сходство химических свойств. Английский химик Ньюлендс в 1804 г. даже объединял элементы в тройки, но тогда было известно слишком мало элементов, и Ньюлендс не рискнул сделать предположение о существовании неоткрытых.
Менделеев, группируя друг с другом похожие элементы, попробовал расположить в правильном порядке и сами группы.
Менделеев, группируя друг с другом похожие элементы, попробовал расположить в правильном порядке и сами группы.
Учёный стал подбирать, написав на отдельных карточках элементы с их атомными весами и коренными свойствами, сходные элементы и близкие атомные веса. Как известно, среди органических соединений встречаются изомеры. т.е. соединения, имеющие один и тот же состав, но разное строение. Комбинаторика дала возможность перечислить изомеры данного состава. В физике она оказывается необходимой при изучении свойств кристаллов, описании модели феромагнетизма и т.д.
“Искать же чего-нибудь, хотя бы грибов, или какую-нибудь зависимость, нельзя иначе, как смотря и пробуя.”
Дмитрий Иванович Менделеев
»
КОМБИНАТОРИКА ЭПОХИ КОМПЬЮТЕРОВ
Математический анализ долгое время играл ведущую роль в изучении мира - дифференциальное и интегральное исчисления, дифференциальные уравнения математической физики, вариационное исчисление и т.д. Применялся развитый аппарат математики непрерывного.
С приходом быстродействующих ЭВМ ситуация изменилась: абстрактные области математики, как математическая логика, общая алгебра, формальные грамматики, стали прикладными.
Появилась нужда в специалистах по составлению алгоритмических языков, на которых пишут программы по решению данных задач. Всевозможные разностные схемы, исследования решёток и их свойств вышли на главный план, а также новые типы проблем, относящиеся к математическому программированию и, в частности, к целочисленному программированию.
В комбинаторной геометрии были доказаны теоремы Минковского — Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема (нач. ХХ в.)
Комбинаторика подверглась мощному процессу алгебраизации благодаря работам Дж.-К. Рота (1964), а также Р. Стенли. Изучение ими частично упорядоченных множеств, свойств функции Мёбиуса, абстрактных свойств линейной зависимости, выявление их роли при решении комбинаторных задач обогатило комбинаторные методы исследования и способствовало дальнейшей интеграции комбинаторики в современную математику: в рамках топологии, анализа и комбинаторики доказаны теоремы Борсука—Улама и Люстерника—Шнирельмана. Во второй четверти XX поставлены задачи Борсука и Нелсона—Эрдёша—Хадвигера. В 1940-х годах оформилась теория Рамсея. Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ, считается основателем современной комбинаторики.
В эту эпоху расцвета дискретной математики изменилась роль данной области, ведь ранее комбинаторика интересовала по большей части составителей занимательных задач и находила основные применения в кодировании и расшифровке древних письменностей. Стали выходить журналы и книги по комбинаторике, ЭВМ дали возможность осуществлять переборы, ранее занимавшие целые годы, поэтому комбинаторные методы исследования получают распространение в науке и технике.
Появилась нужда в специалистах по составлению алгоритмических языков, на которых пишут программы по решению данных задач. Всевозможные разностные схемы, исследования решёток и их свойств вышли на главный план, а также новые типы проблем, относящиеся к математическому программированию и, в частности, к целочисленному программированию.
В комбинаторной геометрии были доказаны теоремы Минковского — Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема (нач. ХХ в.)
Комбинаторика подверглась мощному процессу алгебраизации благодаря работам Дж.-К. Рота (1964), а также Р. Стенли. Изучение ими частично упорядоченных множеств, свойств функции Мёбиуса, абстрактных свойств линейной зависимости, выявление их роли при решении комбинаторных задач обогатило комбинаторные методы исследования и способствовало дальнейшей интеграции комбинаторики в современную математику: в рамках топологии, анализа и комбинаторики доказаны теоремы Борсука—Улама и Люстерника—Шнирельмана. Во второй четверти XX поставлены задачи Борсука и Нелсона—Эрдёша—Хадвигера. В 1940-х годах оформилась теория Рамсея. Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ, считается основателем современной комбинаторики.
В эту эпоху расцвета дискретной математики изменилась роль данной области, ведь ранее комбинаторика интересовала по большей части составителей занимательных задач и находила основные применения в кодировании и расшифровке древних письменностей. Стали выходить журналы и книги по комбинаторике, ЭВМ дали возможность осуществлять переборы, ранее занимавшие целые годы, поэтому комбинаторные методы исследования получают распространение в науке и технике.
Подведём итоги и сделаем выводы
Комбинаторика часто ассоциируется с необычными или нетрадиционными аспектами науки: пёстрые комбинации, мистические квадраты. Поначалу исследования были стимулированы проблемами без глубины, но со временем комбинаторное искусство нашло весомое применение в науке, в XX веке возросло прикладное значение.
Это большой и важный раздел математики, изучающий множества целых чисел и перестановки внутри этих множеств. Комбинаторика имеет огромное значение для многих сфер человеческой деятельности. Учёные-современники стремятся популяризировать её. Многие специалисты считают, что она может стать толчком в развитии всех технических наук, поскольку позволяет нестандартно подойти к решению тех или иных проблем, ответить на вопросы, которые несколько веков не дают покоя ученым.
Утверждают, что комбинаторика является подспорьем для всех современных наук, особенно космонавтики: возможность высчитывать траектории полета кораблей с помощью комбинаторных задач, определять точное нахождение тех или иных небесных светил.
Реализация данного потенциала уже началась в азиатских странах: ученики решают задачи по умножению, вычитанию, сложению и делению, используя комбинаторные методы. Европейские школы пока только начали перенимать восточный опыт.
Комбинаторные задачи сопровождают человечество на протяжении всей истории, переплетаясь с искусством, бытом и наукой.
Математике присущ элемент игры, которая тренирует воображение, интеллект, прокладывает путь к иным решениям любой проблемы и развивает умственные и творческие способности учащегося.
Важный вывод из всего сказанного — дальнейшее развитие комбинаторики необходимо для человечества.
"С помощью цифр доказать можно всё что угодно."
Томас Карлейль
Британский писатель
Written by Anna Pavlova
All rights for images and videos belong to their authors.
All rights for images and videos belong to their authors.
