Комбинаторика — один из разделов математики, нужный представителям самых разных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, лингвистам, инженерам и многим другим научно-техническим работникам. Комбинаторные рассмотрения лежат в основе решения многих задач теории вероятностей и её приложений.

В этой книге в популярной форме рассказывается о комбинаторике, методах решения комбинаторных задач, о рекуррентных соотношениях и производящих функциях. Материал частично захватывает области, выходящие из рамок элементарной математики, однако изложение доступно хорошему ученику средней школы.

Книга будет полезна школьникам старших классов, интересующимся математикой, студентам первых курсов математических факультетов университетов и пединститутов, а также всем, сталкивающимся в своей практической работе с комбинаторными задачами.

Виленкин Наум Яковлевич (род. в 1920 году), доктор физико-математических наук, профессор, автор около 100 научных работ в области топологической алгебры, теории функций действительного переменного и теории представлений групп. Кроме того, им написано более 50 научно-популярных и педагогических статей, его популярные книги «Рассказы о множествах» и «Метод последовательных приближений» переведены на многие иностранные языки.

Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Начальнику цеха надо распределить несколько видов работ между имеющимися станками, агроному — разместить посевы сельскохозяйственных культур на нескольких полях, заведующему учебной частью школы — составить расписание уроков, учёному-химику — рассмотреть возможные связи между атомами и молекулами, лингвисту — учесть различные варианты значений букв незнакомого языка и т. д. Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой.

Комбинаторика возникла в XVI веке. В жизни привилегированных слоёв тогдашнего общества большое место занимали азартные игры. В карты и кости выигрывались и проигрывались золото и бриллианты, дворцы и имения, породистые кони и дорогие украшения. Широко были распространены всевозможные лотереи. Понятно, что первоначально комбинаторные задачи касались в основном азартных игр — вопросов, сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей в данной карточной игре. Эти и другие проблемы азартных игр явились движущей силой в развитии комбинаторики и развивавшейся одновременно с ней теории вероятностей.

Одним из первых занялся подсчётом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицу, показывавшую, сколькими способами могут выпасть r костей. Однако при этом не учитывалось, что одна и та же сумма очков может быть получена разными способами (например, 1+3+4=4+2+2).

Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские учёные Паскаль и Ферма. Исходным пунктом их исследований тоже были проблемы азартных игр. Особенно большую роль сыграла здесь задача о разделе ставки, которую предложил Паскалю его друг шевалье де Мере, страстный игрок. Проблема состояла в следующем: «матч» в орлянку ведётся до шести выигранных партий; он был прерван, когда один игрок выиграл 5 партий, а другой — 4; как разделить ставку? Было ясно, что раздел в отношении 5:4 несправедлив. Применив методы комбинаторики, Паскаль решил задачу в общем случае, когда одному игроку остаётся до выигрыша r партий, а второму s партий. Другое решение задачи дал Ферма.

Дальнейшее развитие комбинаторики связано с именами Якова Бернулли, Лейбница и Эйлера. Однако и у них основную роль играли приложения к различным играм (лото, солитер и др.). За последние годы комбинаторика переживает период бурного развития, связанного с общим повышением интереса к проблемам дискретной математики. Комбинаторные методы используются для решения транспортных задач, в частности задач ло составлению расписаний; для составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования, статистики и т. д. Комбинаторика используется для составления и декодирования шифров и для решения других проблем теории информации.

Значительную роль комбинаторные методы играют и в чисто математических вопросах — теории групп и их представлений, изучении оснований геометрии, неассоциативных алгебр и т. д.

На русском языке очень мало книг по комбинаторике. Помимо совсем элементарных книг типа школьных учебников, можно указать лишь на переводные книги М. Холла «Комбинаторный анализ», ИЛ, 1963; Дж. Риордана «Введение в комбинаторный анализ», ИЛ, 1963, и Г. Дж. Райзера «Комбинаторная математика», «Мир», 1965.

В предлагаемой вниманию читателя книге о комбинаторных проблемах рассказывается в занимательной, популярной форме. Тем не менее в ней разбираются и некоторые довольно сложные комбинаторные задачи, даётся понятие о методах рекуррентных соотношений и производящих функций.

Первая глава книги посвящена общим правилам комбинаторики — правилам суммы и произведения. Во второй главе изучаются размещения, перестановки и сочетания. Этот традиционный школьный материал сопровождается разбором некоторых занимательных примеров. В главе III мы изучаем комбинаторные задачи, в которых на рассматриваемые комбинации налагаются те или иные ограничения. В главе IV рассмотрены задачи на разбиения чисел и рассказано о геометрических методах в комбинаторике. Глава V посвящена задачам о случайных блужданиях и различным модификациям арифметического треугольника. В главе VI рассказано о рекуррентных соотношениях, а в главе VII — о производящих функциях, и в частности о биномиальной формуле.

К книге приложено несколько сотен задач по комбинаторике, взятых автором из различных источников. Много задач заимствовано из книги Уитворта «Выбор и случай» (Whitworth W. A., Choice and Chance, London, 1901), упомянутой книги Риордана, книги А. М. Яглома и И. М. Яглома «Неэлементарные задачи в элементарном изложении», Гостехиздат, 1954, различных сборников задач математических олимпиад и т. д.

ПРЕДИСЛОВИЕ

Книги на ту же тему

1. Живые числа. Пять экскурсий, Боро В., Цагир Д., Рольфс Ю., Крафт Х., Янцен Е., 1985
2. Прикладная комбинаторная математика, Беккенбах Э., ред., 1968
3. Комбинаторные методы дискретной математики, Сачков В. Н., 1977
4. Преобразования и перестановки, Калужнин Л. А., Сущанский В. И., 1979
5. Введение в прикладную комбинаторику, Кофман А., 1975
6. Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
7. Комбинаторные задачи и (0, 1)-матрицы, Тараканов В. Е., 1985
8. Теория вероятностей и математическая статистика. Учеб. пособие для втузов. — 5-е изд., перераб. и доп., Гмурман В. Е., 1977
9. Теория вероятностей. Математическая статистика, Бочаров П. П., Печинкин А. В., 1998
10. Теория вероятностей, Солодовников А. С., 1999
11. Вероятность, Ламперти Д., 1973
12. Вероятность, Мостеллер Ф., Рурке Р., Томас Д., 1969
13. Задачник по теории вероятностей, Палий И. А., 2004
14. Дискретная математика для программистов, Хаггарти Р., 2004
15. Информатика, Луенбергер Д. Д., 2008
16. Эффективное кодирование, Новик Д. А., 1965
17. Основы кодирования, Вернер М., 2006
18. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение, Морелос-Сарагоса Р., 2005
19. Кибернетическое моделирование. Некоторые приложения, Кемени Д. Д., Снелл Д. Л., 1972