Электронная библиотека
Программисту веб-дизайнеру
Другие материалы
Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
М. Холл, Комбинаторика
• Бесплатно скачать книгу, объем 7.57 Мб, формат .djvu (полный курс, Москва, 1970)
Глава 1. Перестановки и сочетания
§ 1.1. Определения
§ 1.2. Приложения к теории вероятностей
Глава 2. Формулы обращения
§ 2.1. Принцип включения и исключения. Обращение Мебиуса
§ 2.2. Частично упорядоченные множества и их функции Мебиуса
Глава 3. Производящие функции и рекуррентные соотношения
§ 3.1. Правила и свойства
§ 3.2. Комбинаторные задачи
Глава 4. Разбиения
§ 4.1. Разбиения. Тождества и арифметические свойства
§ 4.2. Асимптотические свойства
Глава 5. Системы различных представителей
§ 5.1. Теоремы Ф. Холла и Д. Кенига
Глава 6. Теорема Рамсея
§ 6.1. Формулировка и доказательство теоремы
§ 6.2. Одно приложение теоремы Рамсея
Глава 7. Некоторые экстремальные задачи
§ 7.1. Задача о назначениях
§ 7.2. Теорема Дилуорса
Глава 8. Выпуклые пространства и линейное программирование
§ 8.1. Выпуклые пространства. Выпуклые конусы и двой
§ ственные им пространства
§ 8.2. Линейные неравенства
§ 8.3. Линейное программирование. Симплексный метод
Глава 9. Графические методы. Последовательности де Бревна
§ 9.1. Полные циклы
§ 9.2. Теоремы о графах
§ 9.3. Доказательство теоремы де Брейна
Глава 10. Блок-схемы
§ 10.1. Предварительное обсуждение
§ 10.2. Элементарные теоремы о блок-схемах
§ 10.3. Теорема Брука - Райзера - Човла
§ 10.4. Формулировка теоремы Хассе - Минковского. Приложения
Глава 11. Разностные множества
§ 11.1. Примеры и определения
§ 11.2. Конечные поля
§ 11.3. Теорема Зингера
§ 11.4. Теорема о множителе
§ 11.5. Разностные множества в группах общего вида
§ 11.6. Некоторые семейства разностных множеств
Глава 12. Конечные геометрии
§ 12.1. Основания
§ 12.2. Конечные геометрии как блок-схемы
§ 12.3. Конечные плоскости
§ 12.4. Некоторые типы конечных плоскостей
Глава 13. Ортогональные латинские квадраты
§ 13.1. Ортогональность и ортогональные таблицы
§ 13.2. Основные теоремы
§ 13.3. Построение ортогональных квадратов
§ 13.4. Опровержение предположения Эйлера
Глава 14. Матрицы Адамара
§ 14.1. Конструкции Пэли
§ 14.2. Метод Уильямсона
§ 14.3. Три новых метода
Глава 15. Общие методы построения блок-схем
§ 15.1. Методы построения
§ 15.2. Основные определения. Теоремы Ханани
§ 15.3. Прямые методы построения
§ 15.4. Системы троек
§ 15.5. Блок-схемы
Глава 16. Теоремы о пополнении и вложении
§ 16.1. Метод Коннора
§ 16.2. Неположительные и вполне положительные квадратичные формы
§ 16.3. Рациональные пополнения матриц инцидентности
§ 16.4. Целые решения уравнений инцидентности
Приложение I. Уравновешенные неполные блок-схемы с числом повторений каждого элемента от 3 до 15
Приложение II. Матрицы Адамара типа Уильямсона
Краткая аннотация книги
Известный американский математик М. Холл уже знаком советскому читателю по изданным в русском переводе книгам - "Теория групп" (ИЛ, 1962) и "Комбинаторный анализ" (ИЛ, 1963). Настоящая книга является наиболее полным изданием в области комбинаторного анализа. Она состоит из трех основных частей: проблемы перечисления, теоремы выбора и связанные с ними вопросы и проблемы существования и построения блок-схем. Книга написана на высоком научном уровне и освещает самые новейшие достижения в области комбинаторики. Она доступна весьма широкому кругу читателей и, несомненно, заинтересует математиков различных специальностей.
"Комбинаторика" М. Холла занимает особое место среди вышедших за последние годы на русском языке монографий зарубежных авторов, посвященных комбинаторике. Если "Введение в комбинаторный анализ" Дж. Риордана содержит довольно полное изложение методов решения перечислительных задач, а в "Комбинаторной математике" Г. Дж. Райзера в очень хорошем изложении представлены разнообразные, но лишь самые основные, принципиальные стороны комбинаторной теории, то книга М. Холла характерна, прежде всего, тем, что в ней весьма подробно и на высоком математическом уровне рассматриваются сложные и красивые вопросы существования и построения блок-схем, матриц Адамара и латинских квадратов.
Комбинаторные задачи построения привлекают к себе внимание уже давно (можно вспомнить, например, знаменитую задачу Эйлера о 36 офицерах), но их большое прикладное значение выяснилось сравнительно недавно и явилось, очевидно, дополнительным мощным стимулом, вызвавшим все возрастающее количество комбинаторных исследований, посвященных существованию и построению блок-схем. В книге М. Холла, одного из ярких представителей именно этого направления комбинаторики, представлены многие из полученных (в том числе и самим автором) в недавнее время интересны* результатов, таких, как опровержение предположения Эйлера, построение матриц Адамара, построение целого ряда систем разностных множеств и др.
Этим вопросам посвящены гл. 10-16, занимающие две трети книги. Другим сторонам комбинаторной теории уделено сравнительно меньшее внимание, что, однако, не мешает рассматривать книгу М. Холла как книгу по "комбинаторике в целом". Следует отметить, что и в гл. 1-9, наряду с более традиционным материалом, читатель найдет немало нового и интересного, как, например, теорию различных представителей для системы конечных подмножеств бесконечного множества в гл. 5, лаконичное изложение основ линейного программирования в гл. 8, решение с помощью теории графов задачи перечисления полных циклов в гл. 9.
Инициатором перевода книги М. Холла явился член-корреспондент АН СССР (Академия Наук РФ) А. О. Гельфонд, уделявший комбинаторике много внимания, особенно в последнее время. Безвременная кончина прервала работу Александра Осиповича над редактированием книги. Продолжили эту работу его сотрудники из Математического института АН СССР (Академия Наук РФ). Следует отметить, что в процессе перевода и редактирования замечено довольно много неточностей и опечаток, которые были исправлены. Всем принявшим участие в работе над русским изданием книги я выражаю свою искреннюю признательность.
Комбинаторная теория - название предмета, прежде именовавшегося "комбинаторным анализом" или "комбинаторикой"; впрочем, этими терминами многие пользуются и до сих пор. Как и во многих разделах математики, границы комбинаторной теории четко не определены, но центральной ее задачей можно считать задачу размещения объектов в соответствии со специальными правилами и нахождения числа способов, которыми это может быть сделано. Если правила очень просты, то основным в этой задаче является подсчет числа возможностей для осуществления искомого размещения. Если же эти правила тонкие или запутанные, главной проблемой становится вопрос существования таких размещений и нахождения методов их построения. Промежуточную область образуют вопросы о возможностях, возникающих при связанных между собой альтернативах, и типичная в этой области теорема утверждает, что максимум при альтернативе одного рода равен минимуму при альтернативе другого рода.
Примечание. Сохраняйте книги на мобильный телефон и скачивайте их с Вашего телефона на компьютер. Удобное скачивание книг через мобильный телефон (в память телефона) и на Ваш компьютер через мобильный интерфейс. Быстрый Интернет без излишних тэгов. Материал носит неофициальный характер и приведен для ознакомления. Прямые ссылки на файлы книг запрещены.