ИЗ ИСТОРИИ КОМБИНАТОРИКИ

Комбинаторика в быту
С задачами, в которых приходится выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшие расположения охотников во время охоты, воинов во время битвы, инструментов во время работы. Определенным образом располагались украшения на одежде, узоры на керамике, перья в оперении стрелы. По мере усложнения производилось пользоваться общими понятиями о порядке, иерархии, группировании. В том же направлении действовало развитие ремесел и торговли.
Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие в первую очередь умения рассчитывать, составлять планы и опровергать планы противника. О таких играх Ульями Вордсворт писал:
Не нужно нам владеть клинком.
Не ищем славы громкой.
Тот побеждает, кто знаком.
С искусством мыслить тонким.
Среди предметов, положенных в пирамиду, где 35 веков тому назад был похоронен египетский фараон Тутанхамон, нашли разграфленную доску с тремя горизонталями и 10 вертикалями и фигурки для древней игры «сенет», правила которой мы, вероятно, никогда не узнаем. Позже появились нарды, шашки и шахматы, а также их различные варианты (китайские и японские шахматы, японские облавные шашки и т. д.). В каждой из этих игр приходилось рассматривать различные сочетания передвигаемых фигур и выигрывал и умел избегать проигрывающих.
Первое упоминание
Первое упоминание о вопросах, близких к комбинаторным, встречается в китайских рукописях, относящихся к XII-XIII векам до н. э. В этих книгах писалось, что все в мире является сочетанием двух начал – мужского и женского, которое авторы обозначали символами « ‑ » и « ‑ ‑ ». В рукописи, сейчас известной как «Книга перемен», показаны на рисунке 1.1 различные соединения этих знаков по два и по три. Восемь рисунков из трех рядов символов изображали землю, гору, воду, ветер, гром, огонь, пар и небо. По мере углубления знаний понадобилось выразить и другие элементы мироздания с помощью тех же знаков « ‑ » и « ‑ ‑ ». Были составлены 64 фигуры, содержавшие уже пять рядов черточек. Надо полагать, что удвоение числа рисунков при добавлении одного ряда символов было замечено. Это можно рассматривать как первый общий результат комбинаторики


Рисунок 1. 1 – Фрагмент из рукописи "Книга перемен"
Комбинаторика в Древней Греции
Говорить с полной уверенностью об уровне знаний древних греков в области комбинаторики затруднительно, поскольку до нас дошло далеко не все из их научного наследия. В 391 г. н. э. толпа монахов разрушила центр языческой науки – александрийский мусейон (храм муз) – и сожгла большую часть хранившейся в нем библиотеки разрушались в течение еще трех веков, а в 638 г. Н. Э. она окончательно погибла при взятии Александрии войсками арабского халифа Омара. Большинство научных книг безвозвратно погибло, и мы можем лишь догадываться об их содержании по кратким пересказам и намекам в сохранившихся рукописях.
По этим намекам можно все же судить, что определенные представления о комбинаторике у греческих ученых были. Философ Ксенократ, живший в IV веке до н. э., подсчитывал число слогов. В III веке до н. э. стоик Хрисипп полагал, что число утрверждений, получаемых из 10 аксиом, превышает миллион. По мнению же Гиппарха, из утверждающих аксиом можно составить 103 049 сочетаний, а добавив к ним отрицающие, 310 952.
Какой именно смысл придавали эти философы своим утверждениям и как они получали свои результаты – приводимые Гиппархом числа слишком многозначны, поэтому их нельзя считать результатом грубой оценки, и в то же время они не поддаются разумному истолкованию. По-видимому, у греческих ученых были какие-то не дошедшие до нас правила комбинаторных расчетов, скорее всего ложные.
Конкретные комбинаторные задачи, касавшиеся перечисления небольших групп предметов, греки решали без ошибок. Аристотель описал без пропусков все виды правильных трехчленных силлогизмов, а его ученик Аристоксен из Тарента перечислил различные комбинации длинных и коротких слогов в стихотворных размерах. Живший в IV веке н. э. математик Папп рассматривал число пар и троек, которые можно получить из трех элементов, допуская их повторения.
Большое внимание греческие ученые уделяли вопросами, пограничным между комбинаторикой и теорией чисел. Еще в VI веке до н. э. в школе философа и математика Пифагора возникло убеждение, что миром правят числа, а вещи только отражение чисел. Поэтому чтобы познать мир, пифагорейцы начали изучить свойства натуральных чисел. Их исследования о четных и нечетных числах, делимости чисел, простых и составных числах заложили основу теории чисел (в науке бывает, что неверные исходные дают толчок к полезным исследованиям).
В школе Пифагора была доказана известная теорема о сторонах прямоугольного треугольника. Это вызвало интерес к представлению чисел в виде суммы двух квадратов, к квадратным числам 1, 4, 9, 16 и т. д. Квадраты натуральных чисел изображались при этом геометрически.
Древняя Индия
Классические задачи комбинаторики упоминается в сутрах древней Индии, начиная примерно с IV века до н. э. Индийские математики были первыми, которые открыли биноминальные коэффициенты и их связь с биномом Ньютона. Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематического изложения ими этих вопросов, если оно и существовало, до наших дней не дошло. Аристоксен рассматривал различные чередования длинных и коротких слогов в стихотворных размерах. Некоторые комбинаторные правила использовали пифагорейцы при построении своей теории чисел и нумерологии.
В XII веке индийский математик Бхаскара в своем основном труде «Лилавити» исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторением. В Западной Европе ряд важных открытий в области комбинаторики сделали два европейских исследователя: Авраам бен Меир ибн Эзра и Леви бен Гершом. Средневековому философу и математику Авраму бен Меир ибн Эзра принадлежат вычисления и установление свойств биноминальных коэффициентов. А Леви бен Гершом в своей работе «Дело вычислителя» он первым в Европе вывел основные комбинаторные формулы подсчета числа сочетаний, перестановок и размещений. Работа ученного была написана на труднодоступном большинству ученых древнеевропейском языке, поэтому в начале XVII веке данные формулы были окончательно оформлены П. Эригоном. Также комбинаторные задачи упоминаются в XIII веке в труде Фибонначчи «Книга абака», например, задача о наименьшем количестве гирь для взвешивания товара.
Мистики, астрологи, каббалисты
Со II века до н. э. начинается сначала медленный, а потом все более быстрый упадок науки в эллинистических странах, отражавший быстрый упадок науки в эллинистических странах, отражавший общий кризис античного общества. Многие работы того времени были посвящены мистическим толкованиям чисел в духе пифагорейцев. Большое развитие получили различные числовые суеверия и толкования, связанные с заменой букв соответствующими числами. Были «ученые», называвшиеся каббалистами, которые подвергали такому «анализу» слова Библии и других священных книг и делали на основе своих изысканий пророчества о будущем мира.
Во время богословских споров, начавшихся после победы христианства, старались получить из имен еретиков число 666 – ведь по Апокалипсису это было «звериное число», символ антихриста. Такие попытки предпринимались и позднее – лютеране пытались вывести число 666 из имени римского папы, а католики – из имени Мартина Лютера. В романе «Война и мир» Л. Н. Толстой описывает, как Пьер Безухов пытался вывести это число из имени Наполеона Бонапарта. Такого рода исследования при всей своей бесплодности давали точок к дальнейшему развитию комбинаторики.
Наряду с каббалистами и мистиками комбинаторикой в эти темные века упадка науки занимались астрологии. Их интересовал вопрос о движении планет и их «влиянии» на судьбы людей. Особое значение придавали они сочетаниями планет – встречам различных планет в одном знаке Зодиака. Астролог бен Эзра в 1140 г. рассчитал количество сочетаний семи планет по две, по три и т. д. 
Однако его работа, написанная на малодоступном большинству ученых древнееврейском языке, осталась почти незамеченной – вновь эту формулу вывел в начале XVII века французский математик П. Эригон.
Комбинаторика и схоластика
Своеобразной комбинаторикой занимались и логики. Продолжая исследования Аристотеля, они классифицировали понятия и логические рассуждения. В III веке н. э. сириец Порфирий для классификации понятий составил особую схему, получившую название «древа Порфирия». На вершине этого древа помещалось самое широкое по объему понятие, узлы древа помещалось самое широкое по объему понятие, узлы древа соответствовали различным расчленениям понятия, а линии между узлами отражали подчиненность понятий друг другу. Подобные деревья сейчас широко применяются в приложениях комбинаторики к самым разным вопросам.
Один из основателей медицины, Гален, во II веке н. э. занимался классификацией силлогизмов, состоящих из четырех частей. Римский философ и математик Боэций нашел число пар, которые можно составить из пяти категорий модальности, беря их как в утвердительной, так и в отрицательной форме и ставя либо на место условия, либо на место следствия. Он классифицировал также условные силлогизмы.
Значительное внимание классификации видов суждений уделяла схоластическая наука. В схоластике причудливо переплетались философские изыскания с исследованием проблем, примыкающих к комбинаторике, математической логике, теории множеств и другим современным областям математики. Большими знатоками схоластических исследований были основатели теории множеств Бернард Больцано и Георг Кантор.
Споря о взаимоотношениях членов пресвятой троицы, о соподчиненности ангелов, архангелов, херувимов и серафимов, схоласты были вынуждены рассматривать различные отношения порядка и иерархии – достаточно вспомнить сложнейшую архитектонику загробного мира с ее кругами ада и различными областями чистилища и рая, описанную Данте в «Божественной комедии».
Схоласт Раймонд Люллий создал в XIII веке устройство, состоявшее из нескольких кругов, на которых были нанесены основные предикаты, субъекты, атрибуты и иные понятия схоластической логики. Вращая эти круги, он получал различные сочетания понятий и надеялся получить с их помощью истину.
Комбинаторика в странах Востока
В VIII веке н. э. начался расцвет арабской науки. Арабы перевели многие творения греческих ученых, изучили их, а затем продвинулись вперед в областях, мало привлекавших внимание греков, - в науке о решении уравнений, теории и практике вычислений и т. д. Решая вопрос об извлечении корней любой степени, арабские алгебраисты пришли к формуле для степени суммы двух чисел, известной под исторически неверным названием «бином Ньютона». По-видимому, эту формулу знал живший в XI XII веках н. э. поэт и математик Омар Хайям. Во всяком случае, уже в XIII веке такую формулу приводит в своих трудах Насир ад-Дин ат-Туси, а в XV веке она была исследована Гиясэддином ал-Каши.
Судя по некоторым европейским источникам, восходящим к арабским оригиналам, для отыскания коэффициентов этой формулы брали число 10001 и возводили его во 2-ю, 3-ю, …, 9-ю степени. В итоги получаем:
100011=10001
100012=100020001
100013=1000300030001
100014=10004000600040001
100015=100050010001000050001
100016=1000600150020001500060001
100017=1000700210035003500210070001
100018=100080028005600700056002800080001
100019=1000900360084012601260084003600090001
в которой подчеркнуты коэффициенты бинома Ньютона. Если опустить в этих записях все излишние нули и добавить сверху 100010=1, то получиться треугольная таблица из биномиальных коэффициентов.
Liber Abaci
В начале XII века Западная Европа начала пробуждаться после многовековой духовной спячки. Развитие торговли с Востоком привело к проникновению в Европу арабской науки. Наиболее смелые и любознательные европейцы пробирались в находившуюся под владычеством арабов Испанию и знакомились там не только с творением греческих ученных, но и с достижениями арабской и индийской научной мысли – алгеброй и десятичной системой счисления.
В арабских учебных заведениях получил образование и Леонардо – сын пизанского купца, торговавшего в Алжире. В своей книге «Liber Abaci», вышедшей в 1202 г., Леонардо, получивший прозвище Фибоначчи, привел в систему всю арифметику арабов, некоторые сведения по геометрии Евклида и добавил к ним результаты своих изысканий. Труд Фибонначи содержал и новые комбинаторные задачи, например, об отыскании наименьшего количества гирь, с помощью которых можно получить любой целый вес от 1 до 40 фунтов. Рассматривал Леонардо и отыскание целочисленных решений уравнений. В дальнейшем аналогичные задачи привели к отысканию количества натуральных решений систем уравнений и неравенств, которое может рассматриваться как одна из глав комбинаторики.
Но главной заслугой Леонардо перед комбинаторикой было то, что он сформулировал и решил задачу о кроликах. Со времен греческих математиков были известны две последовательности, каждый член  которых получался по определенным правилам из предыдущих – арифметическая и геометрическая прогрессии. 
Это была первая в истории науки формула, в которой следующий член выражался через два предыдущих. Подобные формулы получили название рекуррентных. Метод рекуррентных формул оказался впоследствии одним из самых мощных для решения комбинаторных задач.
Игра в кости
Значительный толчок в XVI веке к развитию комбинаторики дали азартные игры. Наибольшее распространение получила игра в кости – два или три кубика с нанесенными на них очками выбрасывали на стол, и выигрывал тот, кто выбросит большую сумму очков. Игроки заметили, что некоторые суммы очков выпадают часто, а другие - редко. Пытаясь понять, в чем дело, составили таблицы, показывавшие, сколькими способами можно получить то или иное число очков.
Постановления церковных соборов, поучения святых отшельников полны грозных запретов этой игры. Мусульманские ученые писали проигру в нарды, в которой передвижения шашек определяются броском костей: «Как же отвратительно для мудрого стать рабом двух камней до такой степени, что он вручает свое достояние и свою землю в их руки, и они приказывают ему и запрещают, а он подчиняется их руководству больше, чем подчиняется верблюд, когда его маленькая девочка».
Но ничто не помогло, и в любом городе можно было наблюдать картину, описанную в «Божественной комедии» Данте:
Когда кончается игра в три кости,
То проигравший снова их берет,
И мечет их один в унылой злости;
Другого провожает весь народ …
Несмотря на древность игр, в которых применялись кости, они долго не подвергались математическому исследованию. Но игроки, неустанно упражнявшиеся в бросании костей, заметили, что некоторые суммы очков выпадают часто, а другие – редко. Само слово «азартный» происходит от арабского «азар» - трудный, так называли редко выпадавшие комбинации костей.
Пытаясь понять, в чем тут дело, составляли таблицы, показывавшие, сколькими способами можно получить то или иное число очков. На первых порах иногда допускалась ошибка – показывавшие, сколькими способами можно получить то или иное число очков. На первых порах иногда допускалась ошибка – подсчитывали лишь число различных сочетаний костей, дававших данную сумму.
Игрок и ученый
Одним из самых азартных игроков в кости в XVII веке был шевалье де Мере, непрерывно изобретавший новые виды состязаний. Например, он предложил, что будет бросать четыре кости и брать выигрыш лишь в случае, когда хотя бы одна из них откроется на шести. Однако вскоре его партнеры отказались от участия в такой игре – шевалье чаще выигрывал, чем проигрывал. Тогда де Мере придумал новый вариант – он бросал несколько раз пару костей и брал выигрыш, если хотя бы раз выпадали две шестерки. Надо было лишь определить, сколько следует сделать бросков, чтобы игра была ему столь же выгодна, как и первая. Шевалье решил, что надо бросать кости 24 раза. Ведь при четырех бросках одной кости шестерка выпадала более чем в половине случаев, а так как вторая кость дает шесть вариантов выпадения, то и надо умножить 4 на 6. Рассуждение казалось безукоризненным, но опыт не подтвердил надежд де Мере – теперь он стал чаще проигрывать, чем выигрывать.
Другой проблемой для де Мере была задача о разделе ставки. Проблема состояла в следующем: «матч» ведется до шести выигранных партий; он был прерван, когда один игрок выиграл 5 партий, а другой – 4; как разделить ставку? Было ясно, что раздел в отношении 5:4 несправедлив.
Де Мере обратился за разъяснениями к двум крупнейшим математикам Франции XVII века – Блезу Паскалю и Пьеру Ферма. Разбираясь в этих и других задачах, поставленных перед ними де Мере, они сформулировали и доказали первые теоремы комбинаторики и теории вероятностей. А задачу о разделе ставки Паскаль решил в общем случае, когда одному игроку остается до выигрыша r партий, в второму s партий. Другое решение задачи дал Ферма.
Новая ветвь математики
Первые научные исследования по комбинаторике принадлежат итальянским математикам XVI века Дж. Кардано, Н. Тарталье. Наиболее полное исследование было сделано в XVII в. Галилео Галилеем. Затем работу продолжили французские ученые П. Ферма и Б. Паскаль, которые стали основателями двух новых ветвей математической науки - комбинаторики и теории вероятности. Паскаль, в отличии от своих предшественников, занимаясь биноминальными коэффициентами, смог открыть простой их способ вычисления, который называется как «треугольник Паскаля». Благодаря данному открытию, его наравне с Лейбницем стали считать основоположником современной комбинаторики.
Если до Б. Паскаля и П. Ферма комбинаторные проблемы лишь затрагивались в общих трудах по астрологии, логике и математике, а большей частью относились к области математических развлечений, то уже в 1666 г. Г. В. Лейбниц публикует работу «Размышления о комбинаторном искусстве», в которой впервые появляется сам термин «комбинаторный». Данный термин он понимал чрезмерно широко, включая в него всю конечную математику и даже логику. Его ученик Я. Бернулли изложил в своей книге «Искусство предположений» множество сведений о комбинаторике, например, он использовал такие термины как «перестановка» и «размещение». Сама же комбинаторика стала называться наукой в XVII веке, когда возникла теория вероятности.
Дальнейшее возникновение основных понятий и развитие комбинаторики шло параллельно с развитием других разделов математики, таких как теория чисел, теория вероятности, математический анализ и т. д.
Значительный вклад в развитие комбинаторики внес Л. Эйлер. Его задачи о том, можно ли обойти мосты так, чтобы не побывать дважды на одном и том же мосту, или можно ли поставить 36 офицеров из 6 разных полков так, чтобы в каждой шеренге и каждой колонне было по одному офицеру каждого воинского звания из каждого полка. Задачи стали началом развития топологии и теории графов.
Комбинаторика и шифр
Комбинаторику использовали для кодировки и расшифровки секретных шифров. Например, итальянский ученный XVI века Джовани Баттиста делла Порта разработал метод основанный на циклической перестановке букв. А русские дипломаты в XV XVI веках применяли «тарабарскую грамоту», в которой все гласные буквы оставались неизменными, а согласные заменялись друг на друга по такой схеме: (см. рис. 1) все согласные делили поровну на два ряда, в первой строке согласные идут в обычном порядке, а во второй строке – в обратном. Однако такие шифры легко разгадывались по характерным сочетаниям букв. Поэтому стали применять шифры, основанные на комбинаторных принципах, например, замена букв с использованием ключевых слов.
б
в
г
д
ж
з
к
л
м
н
щ
ш
ч
ц
х
ф
т
с
р
п
Рисунок 1. – Схема «тарабарской грамоты»
Для кодирования и расшифровки привлекались математики. Еще в конце XVI века расшифровкой переписки между противниками французского короля Генриха III и испанцами занимался один из создателей современной алгебры Франсуа Виета. А в Англии XVII века монархистские заговорщики поражались быстроте, с которой Кромвель проникал в их замыслы. Монархисты считали шифры, которыми они пользовались при переписке, неразгадываемыми, и считали, что ключи к ним были выданы кем-то из участников заговора. И лишь после падения республики и воцарения Карла II они узнали, что все их шифры разгадывал один из лучших английских математиков того времени, профессор Оксфордского университета Уоллис, обладавший исключительными комбинаторными способностями. Он назвал себя основателем новой науки «криптографии» (тайнописи).
Анаграммы
До XVII столетия почти не было научных журналов. Ученые узнавали о трудах своих коллег из книг или из частных писем. Это создавало большие трудности при опубликовании новых результатов – ведь печатание книг занимало целые годы, а написать о своем открытии в частном письме было рискованно – не ровен час, кто-нибудь присвоит достижение, и поди доказывай, что он узнал это из получатель письма долго думал над тем же вопросом, нашел его решение, и письмо действительно ничего нового ему не открыло – он сам собирался написать коллеге аналогичное сообщение.
Из-за этого часто возникали споры о приоритете. Еще в конце XVII столетия шли долгие споры о приоритете между Ньютоном и Лейбницем (о том, кто первый создал дифференциальное и интегральное исчисления), между Ньютоном и Гуком (кто первый сформулировал закон всемирного тяготения) и т. д.
А в древности Архимеду пришлось даже пуститься на хитрость. Когда некоторые александрийские ученые присвоили себе его результаты, о которых узнали из полученных от него писем, он написал им еще одно письмо. В нем содержались совершенно замечательные формулы для площадей и объемов некоторых фигур. Александрийцы снова сказали, что эти формулы они давным-давно знают, и ничего нового им Архимед не сообщил. Но тут выяснилось, что Архимед поймал их в ловушку – сообщенные в письме формулы были неверными!
Для того чтобы и приоритет обеспечить, и не допустить преждевременной огласки достигнутых результатов, ученые в краткой фразе формулировали суть открытия, а потом переставляли в ней буквы и посылали письмо с переставленными буквами называются анаграммами. Например, слова «Москва» и «смоква» - анаграммы. Когда же печаталась книга с подробным изложением результата, в ней давалась расшифровка анаграммы.
Однако не всегда анаграммы позволяли сохранять тайну. Когда тот же Гюйгенс открыл первый спутник Сатурна (Титан) и нашел, что время его обращения вокруг планеты равно 15 дням, он составил по этому поводу анаграмму и послал свои коллегам. Однако один из них, уже упоминавшийся Уоллис, большой мастер в расшифровке тайнописи, разгадал эту анаграмму и составил по этому поводу свою анаграмму, которую послал Гюйгенсу. Когда ученые обменялись разгадками анаграмм, то получилось так, что будто бы Уоллис еще до Гюйгенса сделал то же самое открытие. Потом Уоллис еще до Гюйгенса  сделал то же самое открытие. Потом Уоллис признался, что он пошутил, чтобы доказать бесполезность анаграмм в деле тайнописи. Гюйгенс, однако, хотя и сам был большим любителем и знатоком комбинаторики, не оценил этой шутки и рассердился…

Комментариев нет:

Отправить комментарий