Читать онлайн «Популярная комбинаторика»

АКАДЕМИЯ И А УК СССР Научно-иипулириан серия Н. Я. ВИЛЕНКПП ПОПУЛЯРНАЯ КОМБИНАТОРИКА ИЗ ДАТЕ Л ЬСТВО «ПА УК А» Москва 1975 Комбинаторика — важный раздел математики, знание которого необходимо представителям самых рваных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, биологам, лингвистам, специалистам по кодам и др. Комбинаторные методы лежат в основе решения многих вадач теории вероятностей и ее приложений. В книге в популярней форме рассказывается об интересных комбинаторных вадачах и методах их решении. 20202—011 ° 054(02)—74 274НП © Издательство «Наука», 1975 ПРЕДИСЛОВИЕ Комбинаторика — ветвь математики, изучающая комбинации и перестановки предметов,— возникла в XVII в. Долгое время казалось, что комбинаторика лежит вне основного русла развития математики и ее приложений. Положение дел резко изменилось после появления быстродействующих вычислительных машин и связанного с этим расцвета конечной математики. Сейчас комбинаторные методы применяются в теории случайных процессов, статистике, математическом программировании, вычислительной математике, планировании экспериментов и т. д. В математике комбинаторика используется при изучении конечных геометрий, комбинаторной геометрии, теории представлений групп, неассоциативных алгебр и т. д. На русском языке есть несколько книг, посвященных комбинаторике: «Комбинаторика» М. Холла (М. , 1970), «Введение в комбинаторный анализ» Дж. Риордаиа (М. , 19G3), «Прикладная комбинаторная математика» (М. , 1968). Отдельным вопросам комбинаторики посвящены книги А. А. Зыкова «Теория конечных графов» (Новосибирск, 1909), Ф. Харарв «Теория графов» (М. , 1973), Т. Саати «Целочисленные методы оптимизации и связанные с ними экстремальные проблемы» (М. , 1973) и др. Однако все эти книги предъявляют высокие требования к математической подготовке читателя. Популярные же книги обычно охватывают лишь немногие начальные сведения. В 1969 г. автор сделал попытку популярно изложить некоторые вопросы комбинаторики («Комбинаторика». М. , 1969). В основпом книга была посвящена вопросам перечислений. Такие важные разделы, как теоремы о различных и общих представителях, теорема Рамсея, метод Пойя перечисления орбит и т. д. , остались вне рамок книги. Поэтому возникла необходидюсть написать новую книгу, в которой наряду с вопросами перечислительной 3 комбинаторики освещались бы и нпые сторопы этой науки. Такая кнпга и предлагается вниманию читателя. Она состоит из шести глав. В главе 1 рассказывается крзтко об историп комбинаторики и некоторых наиболее важных приложений комбинаторных методов (к расшифровке древних письменностей, разгадке генетического кода, составлению периодической таблицы элементов и т. д. ). Глава II посвящена кругу вопросов, связапных с возможными невозможным в комбинаторике! теореме Рамсея, выбору представителей и т. д. Здесь же рассказапо о некоторых понятиях теорпп графов. Классическая комбинаторика, т. е. размещения, сочетвния и перестановки, изложена в главе III Здесь применяется язык теории множеств, который, однако, используется лпшь в объеме, изучаемом сейчас в средней школе (вообще вся книга написана с таким расчетом, чтобы ее могли понимать школьники старших классов).