Читать онлайн «Комбинаторика»

MARSHALL HALL, JR. California Institute of Technology COMBINATORIAL THEORY BLAISDELL PUBLISHING COMPANY Waltham (Massachusetts) • Toronto• London 1967 M. ХОЛЛ КОМБИНАТОРИКА Перевод с английского с. а. Широковой Под редакцией | А. О. ГЕЛЬФОНДА | и В. Е. ТАРАКАНОВА ИЗДАТЕЛЬСТВО «МИР> Москва 1 970 УДК 519. 1 Известный американский математик М. Холл уже знаком советскому читателю по изданным в русском пе- переводе книгам — «Теория групп» {ИЛ, 1962) и «Комби- «Комбинаторный анализ» (ИЛ, 1963). Настоящая книга являет- является наиболее полным изданием в области комбинатор- комбинаторного анализа. Она состоит из трех основных частей: проблемы перечисления, теоремы выбора и связанные с ними вопросы и проблемы существования и построе- построения блок-схем. Книга написана на высоком научном уровне и освещает самые новейшие достижения в об- области комбинаторики. Она доступна весьма широкому кругу читателей и, несомненно, заинтересует математиков различных спе- специальностей. Редакция литературы по математическим наукам Инд. 2-2-3 19-70 Предисловие редактора перевода „Комбинаторика" М. Холла занимает особое место среди вышедших за последние годы на русском языке монографий зарубежных авторов, посвященных комби- комбинаторике. Если „Введение в комбинаторный анализ" Дж. Риордана содержит довольно полное изложение методов решения перечислительных задач, а в „Комби- „Комбинаторной математике" Г. Дж. Райзера в очень хорошем изложении представлены разнообразные, но лишь самые основные, принципиальные стороны комбинаторной тео- теории, то книга М. Холла характерна, прежде всего, тем, что в ней весьма подробно и на высоком математиче- математическом уровне рассматриваются сложные и красивые во- вопросы существования и построения блок-схем, матриц Адамара и латинских квадратов !)< Комбинаторные задачи построения привлекают к себе внимание уже давно (можно вспомнить, например, зна- знаменитую задачу Эйлера о 36 офицерах), но их большое прикладное значение выяснилось сравнительно недавно и явилось, очевидно, дополнительным мощным стиму- стимулом, вызвавшим все возрастающее количество комбина- комбинаторных исследований, посвященных существованию и построению блок-схем. В книге М. Холла, одного из ярких представителей именно этого направления комби* наторики, представлены многие из полученных (в то\с числе и самим автором) в недавнее время интересны* результатов, таких, как опровержение предположения Эйлера, построение матриц Адамара, построение целого ряда систем разностных множеств и др. Этим вопро- •) Вышедший на русском языке в 1963 г. обзор М. Холла „Ком- „Комбинаторный анализ" можно рассматривать как предварительный эскиз настоящей книги. Предисловие редактора перевода сам посвящены гл. 10—16, занимающие две трети книги. Другим сторонам комбинаторной теории уделено срав- сравнительно меньшее внимание, что, однако, не мешает рассматривать книгу М. Холла как книгу по „комби- „комбинаторике в целом". Следует отметить, что и в гл. 1—9, наряду с более традиционным материалом, читатель найдет немало нового и интересного, как, например, теорию различных представителей для системы конеч- конечных подмножеств бесконечного множества в гл. 5, ла- лаконичное изложение основ линейного программирования в гл. 8, решение с помощью теории графов задачи пере- перечисления полных циклов в гл. 9.