Читать онлайн «Комбинаторный анализ. Очерки истории.»

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет К. А. Рыбников Комб нато ыи анализ Очерки истории Москва 1996 год ББК 22. 1г Рецензенты: доктор фиэ. -мат. наук И. Г. Башмакова доктор физ. -мат. наук С. С. Демидов Рыбников К. А. Комбинаторный анализ. Очерки истории. Учебн. пособие. М. : Изд- во Механико-математического факультета МГУ —125 с. Тираж 500 экз. В учебном пособии представлена серия очерков о причинах, обстоятельствах, способах и путях формировния теоретических основ комбинаторного анализа во второй половине ХХ-го века. Для студентов, преподавателей, научных работников, а также читателей, интересующихся историей и методологией науки. ISBN 5-87597-023-5 © механико-математический факультет МГУ © Рыбников К. А. , 1996г. К. А. Рыбников К. А. Рыбников. Комбинаторный анализ; очерки истории. Аннотация Серия очерков о причинах, обстоятельствах, способах и путях формирования теоретических основ комбинаторного анализа во второй половине 20-го века. ПЕРЕЧЕНЬ ОЧЕРКОВ 1. ПОСТАНОВКА ЗАДАЧИ И ВВОДНЫЕ ЗАМЕЧАНИЯ 4 2. КОМБИНАТОРНЫЙ "ВЗРЫВ"; ПРИЧИНЫ И ОБСТОЯТЕЛЬСТВА 6 3. ОБРАЩЕНИЕ МЁБИУСА И ТЕОРИЯ ДЖ. -К. РОТА 18 4. ГРУППЫ ПОДСТАНОВОК И ТЕОРИЯ Д. ПОЙА 32 5. КОМБИНАТОРНЫЕ ГЕОМЕТРИИ И МАТРОИДЫ 39 6. ТЕОРЕМЫ СУЩЕСТВОВАНИЯ И АЛГОРИТМИЧЕСКИЕ ТРУДНОСТИ 58 7. КОНЕЧНЫЕ ГЕОМЕТРИИ В ОБЩЕЙ КОМБИНАТОРНОЙ ТЕОРИИ. 65 8. КОМБИНАТОРНЫЙ АНАЛИЗ И ТЕОРИЯ ВЕРОЯТНОСТЕЙ 72 9. ОБ АЛГЕБРАИЧЕСКОЙ КОМБИНАТОРИКЕ 80 10. О ГРАФАХ 92 11. ВОПРОСЫ ПОСТРОЕНИЯ ОБЩЕЙ КОМБИНАТОРНОЙ ТЕОРИИ 115 12. ПРЕДВАРИТЕЛЬНЫЕ ИТОГИ И НОВЫЕ ЗАДАЧИ 122 4 К. А. Рыбииков 1. Постановка задачи и вводные замечания У автора настоящих очерков накопился значительный запас информации, позволяющий обсуждать достаточно конкретно и обоснованно причины и обстоятельства, под воздействием которых во второй половине 20-го века складывался современный (по состоянию на конец века) облик комбинаторного анализа, а также то, как этот процесс протекал. Привести эту информацию в порядок и сохранить ее тем самым для будущих исследований - такова цель, ради достижения которой пишутся эти очерки. Формирование сколько-нибудь значительной части математики - процесс сложный. Сложность изучения подобных процессов резко возрастает, когда выбирают для исследования состояние науки во времена, не столь от нас отдаленные. В таких ситуациях трудности проистекают не от недостатка материала для изучения, а скорее от его избытка. На первый план выступают своеобразные проблемы выбора: выделения и анализа подлинно фундаментальных результатов, имеющих принципиальное значение. Неизбежная разнородность фактов, подлежащих изучению, заставляет расширять поле исследований и не торопиться с уточнениями определений и с жесткой формализацией суждений. И в нашем случае, в применении к комбинаторному анализу, мы будем вынуждены применять, для начала, широкий подход к математическому исследованию дискретных систем в их разнообразных интерпретациях, исходящий из общих комбинаторных представлений о наборе операций.